алгоритмы
Статьи EssayAI по теме «алгоритмы»: разборы, методы и примеры.
Задача о рюкзаке: динамическое программирование
Разбор задачи о рюкзаке (0/1 Knapsack) методом ДП: таблица dp[i][w], рекуррентный переход, traceback-восстановление набора. Пошаговые примеры и анализ сложности O(n*W).
Бинарный поиск по ответу: метод и примеры задач
Бинарный поиск по ответу: как применять метод к задачам на оптимизацию, как формулировать предикат, строить монотонную функцию и избегать ошибок в границах.
Высота и глубина дерева: формулы и примеры
Разбираем высоту и глубину дерева в информатике: точные определения, формулы для полного двоичного и вырожденного дерева, примеры задач и типичные ошибки.
Алгоритм Рабина-Карпа: поиск подстроки за O(n+m)
Разбираем алгоритм Рабина-Карпа: как полиномиальный хеш и скользящее окно ускоряют поиск подстроки до O(n+m) в среднем, почему бывают ложные совпадения и при чём тут плагиат.
Алгоритм Прима - как построить остовное дерево по шагам
Разбираем, как алгоритм Прима шаг за шагом строит минимальное остовное дерево графа: идея жадного выбора, лемма о разрезе и трассировка на конкретном примере.
Алгоритм Ахо-Корасик: поиск множества образцов в тексте
Разбираем алгоритм Ахо-Корасик: как из бора паттернов и суффиксных ссылок собрать автомат и найти все вхождения множества образцов в тексте за один линейный проход.
Алгоритм Эдмондса-Карпа: поиск максимального потока
Алгоритм Эдмондса-Карпа находит максимальный поток в сети: BFS ищет дополняющий путь, что даёт полиномиальную сложность. Разбираем идею, реализацию и оценку.
Алгоритм Куна: как найти максимальное паросочетание
Алгоритм Куна шаг за шагом: ищем увеличивающие цепи обычным DFS и находим максимальное паросочетание в двудольном графе за O(V·E), с разбором идеи и сложности.
Алгоритм Кадане: максимальная сумма подмассива
Алгоритм Кадане за линейное время находит подмассив с наибольшей суммой. Разбираем идею динамического программирования, ловушку отрицательных чисел и реализацию.
Алгоритм Манакера: поиск всех палиндромов за O(n)
Алгоритм Манакера находит все палиндромные подстроки за линейное время O(n). Разбираем разделители, массив радиусов и зеркальную симметрию на понятном примере.
Алгоритм Луна: как проверить номер карты по модулю 10
Разбираем алгоритм Луна: как пошагово проверить номер банковской карты, IMEI или SIN по модулю 10, какие опечатки он ловит, а какие пропускает, и чем отличается от Verhoeff.
Алгоритм Кнута-Морриса-Пратта: поиск подстроки за O(n+m)
Алгоритм Кнута-Морриса-Пратта ищет подстроку без возвратов по тексту. Разбираем префикс-функцию по шагам, оцениваем сложность и смотрим понятный пример работы.
Алгоритм Бойера-Мура: почему он ищет подстроку так быстро
Разбираем алгоритм Бойера-Мура: зачем сравнивать паттерн справа налево, как работают эвристики плохого символа и хорошего суффикса и почему поиск выходит сублинейным.
Алгоритм Дейкстры: как найти кратчайший путь в графе
Разбираем алгоритм Дейкстры на взвешенном графе по шагам: как он находит кратчайшие пути от стартовой вершины и почему ломается на ребрах с отрицательными весами.
Алгоритм Карацубы: умножение длинных чисел быстрее столбика
Разбираем алгоритм Карацубы: почему три умножения вместо четырёх ускоряют перемножение длинных чисел, как выглядит рекуррентность и зачем это нужно на практике.
Алгоритм Беллмана-Форда: пути с отрицательными весами
Разбираем алгоритм Беллмана-Форда: как искать кратчайшие пути в графе с отрицательными рёбрами, ловить отрицательные циклы и чем он отличается от Дейкстры.