Мы живем в золотой век абстракций. Docker-контейнеры, облачные функции, многослойные фреймворки и бесконечные библиотеки — все это создает впечатление, что программирование свелось к сборке конструктора лего. Достаточно знать, какой блок куда поставить, и сложная система готова. Но эта мощь абстракций имеет и обратную сторону: мы становимся архитекторами, не знающими физики материалов, из которых строим. Мы используем алгоритмы, не понимая, из чего они сделаны и зачем они нужны. Мы делаем нечто, что как-то работает, и не имеем никакого понятия о том, почему оно работает, и не знаем, что делать в случае каких-то изменений условий.

Мы знаем, что быстрая сортировка «быстрая», что хеш-таблица обеспечивает «время $O(1)$», а красно-черное дерево «сбалансировано». Но это — знание ритуала, а не принципа. Но что скрывается за этими оптимистичными фактами? Где та грань, где элегантный алгоритм вдруг ломается под весом реальных данных? Как быть, когда память исчерпана, а набор инструкций процессора скуден? И, главное, как мыслят те, кто создаёт эти алгоритмы с нуля? И, что самое главное, как создатели этих алгоритмов пришли к своим неочевидным, а подчас и гениальным решениям?

Мы не будем скользить по поверхности. Мы погрузимся в самые глубины. Наша цель — не просто показать, как работает алгоритм, а понять, почему он работает именно так, и как его можно сломать, улучшить или адаптировать под безумные требования современного железа и экстремальных нагрузок.

Жёсткий подход. Играть в режиме хардкор сложно и неприятно. Но это необходимая мера.

С первой страницы мы отбросим упрощения. Нас не устроит знание, что сортировка работает за $O(n \log n)$. Мы будем строго вычислять точное количество сравнений, дисперсию времени выполнения, влияние распределения данных на производительность. Мы вскроем каждый алгоритм и измерим каждую его переменную. И делаем мы это не забавы ради. Нам нужно понять, что влияет на эффективность, что можно развивать и как придумывать хорошие алгоритмы.

Для этого нам потребуется мощный математический аппарат: от линейной алгебры и математического анализа до комбинаторики и статистики. Этот математический аппарат — не академическая роскошь, а рабочий инструмент. Он позволяет нам формально доказывать свойства алгоритмов, сравнивать их между собой не на уровне интуиции, а на уровне строгих количественных характеристик и, в конечном счёте, конструировать новые, более эффективные решения.

Это — единственное будущее для серьёзного разработчика

Эра черных ящиков заканчивается. Когда ваше приложение было игрушкой у вас на компьютере и запускалось всего раз, вы могли позволить себе не знать, как работает std::sort. Но когда вы запускаете ваш код в распределенной системе, обрабатывающей петабайты данных, цена одной неоптимальной строки кода умножается на миллион. Вызов $O(n^2)$-алгоритма может обернуться счетом от облачного провайдера, который похож на номер телефона. Вы обязаны знать, что скрывается за вызовом библиотечной функции, потому что вы отвечаете за каждую миллисекунду и каждую копейку. Более того, вы должны уметь в любой момент отказаться от библиотечных функций, написав свой алгоритм, который именно в вашей ситуации гораздо эффективнее общих решений.

Лекарство от интеллектуального банкротства. Современные инструменты позволяют поднять проект за день. Но они же порождают разработчиков, беспомощных перед проблемой, для которой нет готового npm-пакета. Здесь вы получите прививку от этой беспомощности. Вы научитесь не искать готовое решение, а конструировать его из первопринципов.

Аппаратная революция диктует новые правила. Закон Мура мертв в его классическом понимании. Рост производительности теперь достигается не за счет бешеных тактовых частот, а за счет сложной иерархии кешей, суперскалярных конвейеров, SIMD-инструкций и GPU. Абстрактная «Big-O notation» ничего не говорит о том, как ваш алгоритм поведет себя в условиях промахов в кеше или ошибочного предсказания ветвления. Производительность сегодня — это не только математика, это ещё и психология процессора. Вы должны думать так, как думает он: предвосхищать его потребности, избегать неожиданностей, упаковывать данные так, как ему удобно. Вам нужно научиться разговаривать с железом на его языке.

Эта работа — не для развлечения. Это — интенсивная, выматывающая, жёсткая тренировка. Она сжигает поверхностные знания, оставляя кристальный, прочный каркас понимания. Вы научитесь не просто использовать готовые алгоритмы, а создавать свои, которые в разы эффективнее для конкретно вашего случая. Вы получите способность не решать задачи, а видеть их внутреннюю структуру и порождать подходящие методы на лету. Вы сможете не только исправлять узкие места, но и предвидеть их.

Эти материалы потребуют усидчивости, терпения и готовности ломать голову над сложными задачами. Они не для тех, кто ищет быстрых ответов или хочет просто научиться кодить. Они для тех, кого не устраивает роль пассивного пользователя, для тех, кто хочет строить громадные слаженные производительные системы, для тех, кто готов создавать современную науку и по-настоящему программировать.

Мы играем в хардкор, потому что только так можно стать творцом.

Всё, что сейчас находится перед вами, я буду называть материалами. Не потому что мне не хватает смелости назвать это книгой или курсом. А потому, что здесь изложены знания. И не важно, в какой форме эти знания излагаются: бумажная книга на тысячи страниц, markdown текст, видеокурс или просто обычный сайт на самом краю интернета.

Изложение здесь ведётся от первого лица. Такое изложение позволяет мне напрямую делиться с вами ходом своих рассуждений. Вы видите не просто готовые истины, а логику их формирования.

Алгоритмы и математика — это не набор догм, высеченных в камне. Это живые идеи, рождённые в головах конкретных людей, через борьбу с конкретными проблемами. Вы учитесь не у безликого учебника, а у живого процесса, наблюдая за рождением идей из реальных проблем и сомнений.

Этот курс не предназначен для полных новичков. Он строится на предположении, что вы уже сталкивались с основами дискретной математики, линейной алгебры, математического анализа, теории вероятностей и базовых структур данных и алгоритмов.

Возможно, вы изучали эти темы в вузе или на других курсах, но со временем детали материала забылись, но сохранилось общее понимание. Если это так, то ничего страшного нет. Я всё равно буду приводить все определения и теоремы, буду учить пользоваться инструментами, показывать много примеров и давать кучу упражнений. Вы без труда сможете вспомнить весь материал, если вы его когда-то знали. Но с полного нуля изучать это будет очень трудно.

Вам потребуется

Курс формально самодостаточен: все понятия вводятся строго и последовательно, объясняется применение каждого алгоритма, явно показывается потребность в изучаемых методах. Но объем и плотность материала огромны, а также темп и глубина повествования предполагают уже сформированное математическое и программистическое мышление.

Материал, в первую очередь, структурирован по темам. То есть, например, в статье «Группы» изложена вся базовая теория групп. Я не стал разбивать эту самодостаточную тему на много-много маленьких статей, несмотря на то, что так делают многие авторы.

Предположим, вы изучаете статью «Линейные пространства», материалы из которой необходимы для понимания последовательностей, рядов, и всего того, на чём строится математический анализ, так необходимый нам для анализа алгоритмов. В этой статье используется понятие «поле», которое изложено в одноимённой статье «поля».

У нас постоянно будут возникать очень важные факты, леммы, теоремы и утверждения. Все такие важные объекты будут рисоваться в таких жёлтых блоках.

Математические обозначения — список всех используемых в этих материалах математических и программистических обозначений.