Computer Science
Алгоритмы и теория «на пальцах»
Фундамент, который отличает кодера от инженера: алгоритмы, структуры данных, оценка сложности и то, как машина исполняет программы. Объясняем интуитивно, а строгость — там, где она помогает.
Что такое NP-полные задачи и почему за них дадут миллион
Существует задача, за решение которой Институт Клэя обещал миллион долларов. Самое странное: она не про физику и не про космос, а про то, можно ли решать примеры так же быстро, как их проверять.
Как Spotify понимает, какая песня вам понравится
Ты включаешь Spotify, а он будто читает мысли: подсовывает трек, который идеально ложится под настроение. Никакой магии тут нет — есть математика, миллионы чужих плейлистов и пара хитрых алгоритмов. Разбираемся, как это устроено.
Как компьютер играет в шахматы лучше человека
В 1997 году машина впервые обыграла чемпиона мира по шахматам. Сегодня даже программа на твоём телефоне разгромит любого гроссмейстера. Разбираемся, как у компьютера это получается и в чём он реально сильнее человека.
Как работает автодополнение и исправление опечаток
Ты пишешь «превед», а телефон вежливо предлагает «привет». Откуда он знает, что ты хотел сказать? Разбираем, как машина читает твои мысли по буквам и почему иногда промахивается.
Как сжимаются фотографии: JPEG простыми словами
Одна фотография с телефона — это миллионы цветных точек, и честно весит она десятки мегабайт. Но в галерее лежит файл в десять раз легче, а глазом разницы не видно. Разбираемся, как JPEG творит эту магию.
Как навигатор объезжает пробки: алгоритмы на графах
Навигатор за долю секунды перебирает миллионы вариантов проезда и выдаёт лучший — да ещё и с учётом пробок прямо сейчас. Разбираем, как обычная карта города превращается в граф и почему алгоритм Дейкстры лежит в основе этой магии.
Почему поиск в отсортированном списке — это деление пополам
Угадать число от 1 до миллиона можно всего за 20 вопросов — если задавать их с умом. Тот же фокус прячется внутри телефонной книги, словаря и любого быстрого поиска. Разбираемся, почему деление пополам бьёт перебор наповал.
Алгоритмы и блок-схемы для начинающих: как научиться мыслить как программист
Прежде чем писать код, полезно научиться раскладывать задачу на шаги. Этому учат блок-схемы.
Как сайт хранит твой пароль, даже не зная его
Когда ты вводишь пароль на любимом сайте, он почти наверняка не сохраняет его буквами. Разбираемся, как сервер проверяет твой пароль, по факту его не зная, — и почему «12345» взломают за доли секунды.
Префиксное дерево (trie): как телефон угадывает слово по трём буквам
Вы набираете «прог» — и телефон уже предлагает «программирование». Как он так быстро находит все слова с этим началом среди сотен тысяч? Секрет в дереве, где общие приставки слов хранятся один раз.
Алгоритм Евклида: код, которому две тысячи лет
Самый старый нетривиальный алгоритм, дошедший до нас, придумали задолго до компьютеров и даже до нуля как цифры. Он до сих пор крутится внутри криптографии вашего браузера.
Машина Тьюринга простыми словами: бумажная лента, изменившая мир
Самый влиятельный компьютер в истории не имеет ни процессора, ни экрана — это воображаемая лента бумаги и головка, которая ползает по ней. Разберёмся, как эта игрушка определила, что вообще такое «вычисление».
Большое-О простыми словами: почему один код быстрее другого
O(n), O(n²), O(log n) — за этими значками прячется одна простая идея: как растёт время работы, когда данных становится больше. Объясняем без формул.
Решето Эратосфена: как вычеркнуть всё лишнее и оставить простые
Библиотекарь Александрийской библиотеки придумал способ находить простые числа, не деля вообще ничего. Достаточно вычёркивать — и через две тысячи лет этот метод всё ещё один из самых быстрых.
Парадокс лжеца и теоремы Гёделя глазами программиста
«Это утверждение ложно» — фраза, которая ломает логику, как деление на ноль. Курт Гёдель превратил эту шутку в строгую теорему, доказавшую: в любой достаточно мощной системе есть истины, которые она не может доказать. И это напрямую касается кода.
Сбалансированное дерево: почему дерево иногда вырождается в список
Деревья поиска быстры, пока остаются «пушистыми». Но при неудачном порядке вставки дерево может вытянуться в цепочку и потерять всю скорость. Балансировка не даёт этому случиться.
Как появился Unix и почему он внутри почти всего
Операционную систему, которая теперь живёт в вашем телефоне, серверах и даже в Mac, два инженера написали в свободное время на списанной мини-ЭВМ. История Unix — это история идей, оказавшихся сильнее своих создателей.
Почему случайные числа в компьютере на самом деле не случайны
Компьютер — машина абсолютной предсказуемости: одни и те же входные данные всегда дают один и тот же результат. Откуда же тогда берётся random()? Спойлер: это умная подделка, и иногда подделка опасная.
Бэббидж и Лавлейс: программа, написанная за сто лет до компьютера
В 1843 году женщина написала алгоритм для машины, которой ещё не существовало в металле. Историю первого программиста придумали не маркетологи — она настоящая и куда страннее легенды.
Язык Си: как маленький язык стал фундаментом всего
На Си написаны операционные системы, базы данных и почти все языки, которыми вы пользуетесь сегодня. Разбираем, как простой инструмент 1972 года стал универсальным языком, на котором держится вся индустрия.
Кнут — Моррис — Пратт: поиск подстроки, который не возвращается назад
Искать слово в тексте «в лоб» — значит постоянно откатываться и перепроверять уже прочитанное. Трое учёных придумали, как не возвращаться ни на шаг, запоминая то, что уже совпало.
Проблема остановки: почему нельзя написать идеальный антивирус
Существует задача, которую не решит ни один компьютер — ни сегодня, ни через тысячу лет, какой бы мощный он ни был. И из неё напрямую следует, что идеального антивируса быть не может в принципе.
Первый баг был настоящим: мотылёк, Грейс Хоппер и рождение слова
Почему ошибку в программе называют «багом» — жучком? За словом стоит реальный мотылёк, приклеенный скотчем в журнал в 1947 году, и женщина, научившая компьютеры понимать слова.
Куча и очередь с приоритетом: кто в приёмном покое раньше
В обычной очереди обслуживают по порядку прихода. А в приёмном покое — по тяжести состояния. Структура, которая всегда мгновенно выдаёт «самого важного», называется кучей.
Быстрое возведение в степень: как посчитать 2 в миллионной без миллиона умножений
Чтобы возвести число в степень n, кажется, нужно n умножений. На самом деле хватает примерно логарифма от n — и именно этот трюк позволяет шифровать сообщения числами в сотни знаков.
Черепаха и заяц: как поймать цикл, имея память всего на два указателя
Как понять, что вы ходите по кругу, если нельзя ничего записывать и запоминать пройденное? Роберт Флойд предложил пустить вдогонку двух бегунов с разной скоростью — и быстрый неизбежно нагонит медленного.
Хеш-таблица: как словарь находит нужное за один миг
Почему поиск телефона по имени в словаре Python мгновенный, даже если записей миллион? Разбираемся, что такое хеш-функция и почему она превращает перебор в прямое попадание.
Сложность алгоритма на пальцах: что скрывается за «О-большим»
Почему один поиск находит товар среди миллиона мгновенно, а другой думает минутами? Дело не в мощности компьютера, а в том, как растёт время работы с объёмом данных. Разбираем О-большое без формул и занудства.
Динамическое программирование: рюкзак, который научил машины не считать дважды
Название «динамическое программирование» придумали, чтобы спрятать математику от недовольного начальства. А суть проста: не решай одну и ту же подзадачу дважды — запиши ответ и переиспользуй.
Вычислимость: функции, которые не сможет посчитать ни один компьютер
Существуют точно определённые математические функции, значение которых не способна вычислить ни одна программа во Вселенной. Их не просто «трудно» посчитать — это невозможно в принципе. Знакомимся с миром невычислимого.
Фильтр Блума: как сказать «возможно есть» или «точно нет», почти не тратя память
Существует структура, которая на вопрос «видела ли ты этот элемент?» честно отвечает «точно нет» или осторожно «возможно, да» — и при этом занимает в разы меньше места, чем настоящее множество. Цена — допущение редких ошибок.
Кольцевой буфер: лента, у которой нет конца
Как хранить «последние 100 событий» в потоке, который не кончается, не съедая всю память? Ответ — буфер, замкнутый в кольцо, где новые данные затирают самые старые.
Сортировка слиянием: алгоритм, придуманный фон Нейманом ещё до настоящих компьютеров
В 1945 году, когда компьютеры ещё толком не существовали, Джон фон Нейман описал способ сортировки, который гарантированно быстр на любых данных. Его до сих пор используют там, где важна предсказуемость.
Теорема о сжатии: почему нельзя сжать вообще всё
Архиваторы творят чудеса: текст ужимается в разы. Но существует железный математический запрет — универсального сжатия, которое уменьшает любой файл, быть не может. Любая программа, которая что-то сжимает, что-то другое обязана раздувать.
Машина фон Неймана: почему все компьютеры устроены одинаково
От смартфона до суперкомпьютера — внутри одна и та же схема, придуманная в 1945 году. Разбираем, что такое архитектура фон Неймана и почему мир так и не придумал ничего радикально иного.
Закон Мура: предсказание, которое полвека двигало прогресс — и закончилось
Полвека чипы исправно удваивали число транзисторов, как по расписанию, придуманному в 1965 году. Теперь физика говорит «стоп». Что такое закон Мура, почему он работал так долго и что происходит сейчас.
Хеш-множество: как за миг понять, что элемент уже встречался
Удалить дубликаты из миллиона записей, проверить, голосовал ли уже пользователь, найти общих друзей — всё это про одну операцию: «видели мы это раньше или нет». Множество отвечает на неё мгновенно.
Хеш-таблица: почему поиск занимает одно и то же время хоть в десятке, хоть в миллиарде
Найти телефон в записной книжке из миллиона контактов так же быстро, как из десяти. Это не магия, а хеширование — и за кулисами там идёт постоянная борьба с коллизиями.
Связный список против массива: вагоны поезда или ряд в кинотеатре
Массив — это пронумерованные кресла в зале, к любому можно подойти сразу. Связный список — цепочка вагонов, где каждый знает только следующий. Разбираемся, почему у каждого свои сильные стороны.
ENIAC: тридцать тонн, восемнадцать тысяч ламп и заря компьютеров
Первый большой электронный компьютер весил как стадо слонов, грелся как печь и программировался перетыканием проводов вручную. История ENIAC — это история о том, как считать стали электронами.
Мышь, окна и Xerox PARC: где придумали привычный экран
Окна, иконки, курсор, который вы двигаете мышью, — всё это родилось в одной исследовательской лаборатории, чья компания так и не сумела это продать. История величайшего упущенного шанса в IT.
Бинарный поиск: почему его 9 из 10 пишут с багом
Идея бинарного поиска объясняется за минуту, а правильно его написать не могут даже мэйнтейнеры стандартных библиотек. Двадцать лет в JDK жила одна и та же ошибка переполнения.
Чёрный ящик P против BPP: когда монетка помогает считать
Иногда подбросить монетку — это не безрассудство, а гениальная стратегия. Рандомизированные алгоритмы решают задачи быстрее детерминированных, соглашаясь на крошечный шанс ошибки. Разбираемся, что такое класс BPP и почему случайность — это вычислительная сила.
Стек и очередь: стопка тарелок против турникета в метро
Две простейшие структуры данных отличаются одним правилом — кого обслуживать первым. Это правило определяет, как работает кнопка «Назад» в браузере и почему принтер печатает документы по порядку.
Граф и обходы BFS и DFS: как пройти лабиринт двумя способами
Граф — это просто точки и связи между ними: перекрёстки и дороги, страницы и ссылки. А обойти его можно двумя характерами: осторожно расходясь кругами или смело ныряя вглубь.
Открытый код и Linux: как студент из Хельсинки изменил мир бесплатно
Студент написал учебную операционную систему «просто для развлечения» и выложил в сеть. Сегодня его код крутит большую часть интернета. История о том, как раздать исходники оказалось сильнее, чем продавать их.
Почему две одинаковые программы могут работать с разной скоростью
Берёшь два кода, которые делают одно и то же, запускаешь — и один летит, а другой ползёт. Разбираемся, почему «одинаковое» на самом деле очень разное и где прячется скорость.
Что такое состояние гонки и почему параллельность сложна
Два потока хотят добавить деньги на один счёт — и в итоге одна из операций просто исчезает. Это не магия и не баг компилятора, а состояние гонки: коварная ошибка, из-за которой параллельные программы ведут себя непредсказуемо.
Что такое кэш и почему он ускоряет всё
Почему сайт, на который ты заходишь второй раз, грузится мгновенно? Почему процессор не ждёт память целую вечность? Ответ один и тот же на всех уровнях — кэш. Разбираемся, как маленькая хитрость ускоряет вообще всё.
Код Хаффмана: как студент случайно изобрёл идеальное сжатие
В 1951 году профессор предложил студентам выбор: сдать экзамен или решить открытую задачу. Один студент выбрал задачу — и придумал способ сжатия, который оказался математически оптимальным.
Как находят кратчайший маршрут для курьера
Курьер развозит десять заказов по городу — и кто-то должен решить, в каком порядке. Этим занимается не диспетчер, а алгоритм, который умеет находить кратчайший путь среди миллионов вариантов за доли секунды.
Квантовые вычисления: что реально меняется, а что — хайп
Про квантовые компьютеры говорят, что они «перебирают все варианты сразу» и скоро взломают всё на свете. Это красивое, но неверное упрощение. Разберёмся без мистики, в чём настоящая сила кубита и где её предел.
Как родился интернет: от ARPANET до сети, в которой мы живём
Интернет не включили в один день — он рос из военного эксперимента, в котором четыре компьютера впервые заговорили друг с другом. История о том, как идея резать сообщения на кусочки победила телефонную логику.
Как сжать текст без потери ни одной буквы: коды Хаффмана
Архиватор ужимает файл вдвое, но при распаковке возвращает всё до последней буквы. Никакой магии — внутри хитрая идея 25-летнего студента, придуманная в 1952 году. Разбираемся, как коротким буквам достаются короткие коды.
Что такое бит на самом деле: теория информации Шеннона
Мы привыкли, что бит — это ноль или единица. Но Клод Шеннон дал биту куда более глубокий смысл: это мера удивления, единица устранённой неопределённости. И именно поэтому существует сжатие данных.
Как работает проверка на плагиат
Учитель загружает твоё сочинение в систему, и через пару секунд она выдаёт: «совпадение 14%». Но как машина за это время сравнила твой текст с миллионами чужих? Разбираем магию без магии.
Хеш-таблицы: как найти нужное мгновенно
Представь библиотеку, где не нужно искать книгу по полкам — ты просто называешь имя, и она сама падает тебе в руки. Хеш-таблицы делают ровно это с данными: находят нужное почти мгновенно, не перебирая остальное.
Динамическое программирование на примере размена монет
Кассир хочет дать сдачу как можно меньшим числом монет — а компьютер хочет того же, но не угадывая. Разменяй монеты грамотно, и ты на самом деле освоишь динамическое программирование — приём, на котором держатся маршруты в навигаторе и проверка орфографии.
Что такое жадный алгоритм и когда он подводит
Жадный алгоритм всегда хватает то, что прямо сейчас выглядит выгоднее всего. Иногда это гениально просто, а иногда заводит прямо в тупик. Разбираемся, когда жадности можно доверять, а когда она тебя подведёт.
Алгоритм, который помог расшифровать «Энигму»
Немецкая шифровальная машина «Энигма» казалась неприступной: число вариантов настроек было астрономическим. Но математик Алан Тьюринг придумал алгоритм, который не перебирал их все, а отбрасывал ложные. Разбираемся, как это работало.
Рекурсия: функция, которая вызывает саму себя
Что будет, если функция позовёт сама себя? Не бесконечная катастрофа, а один из самых элегантных приёмов в программировании. Разбираемся, как рекурсия решает большие задачи, разбивая их на копии самих себя поменьше.
Что такое сложность алгоритма и зачем нужно O-большое
Один алгоритм находит ответ мгновенно, а другой завис бы до конца Вселенной — хотя оба решают одну задачу. Разбираемся, что такое сложность алгоритма и почему загадочное O-большое — главный язык программистов о скорости.
Как отсортировать миллион чисел и не сойти с ума
Разложить колоду из 52 карт по порядку легко. А миллион чисел? Если действовать в лоб, компьютер будет молотить часами. Разбираемся, как пара хитрых идей превращает вечность в доли секунды.