Материалы

Книги

Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест. «Алгоритмы: построение и анализ»

Седжвик Р., Уэйн К. «Алгоритмы на Java»

Гасфилд Д. «Строки, деревья и последовательности в алгоритмах»

Ссылки

NP и сложность

NP класс и NP-полные задачи

Амортизированная сложность

Метод Монте-Карло

Применение в машинном обучении (4 лекция)

Хабрахабр

Графы

Раскраска графов

[В работе] Конспект лекции по раскраскам

Лекция CS club (сложность 1,45 можно не смотреть)

Применение раскраски

Раскраска в компиляторах

Кратчайшие пути. A*

Лекция ШАД

Алгоритмы Дейкстра и Флойда-Уоршелла

Алгоритм А*

Кратчайшие пути. Расширения A*

Подходы к применению A* в ГИС

ALT + REACH

Компоненты связности

5 лекция Stepik

Паросочетания

Определения

Максимальное паросочетание

Потоки в графах

Основы тетории потоков в CS club с алгоритмом Форда-фолкерсона (Гольдберга (проталкивания предпотока), лекции 1, 4, 5)

Интерактивный пример работы алгоритма Гольдберга (проталкивания предпотока)

Минимальный разрез

Лекция в CS club по вероятностным алгоритмам (Каргер-Штейн)

Конспект ИТМО (Каргер-Штейн, оценка сложности для обеспечения вероятности 1/n)

Методичка ИТМО

Задача о коммивояжёре

CS club лекции

Визуализация имитации отжига

Изоморфизм графов

Краткое изложение алгоритма Ульмана

Строки

Редакционное расстояние

Редакционное расстояние из курса биоинформатики

Гасфилд Д. «Строки, деревья и последовательности в алгоритмах» Раздел 11 «Ядро методов редактирования строк и выстраивания» (п.11.1, п.11.2, п.11.3)

Пошаговая визуализация работы алгоритма (входные строки задаются в константах: const str1 = 'stack'; const str2 = 'racket';)

Задача поиска точного поиска подстроки в строке, Кнут-Моррис-Пратт

Лекция Н. Вяххи в CS Club

Лекция А.Куликова в CS-центре

Кормен «Алгоритмы. Построение и анализ» 3 изд. Глава 32 (Введение, п.32.1, 32.4)

Алгоритм Рабина-Карпа

Лекция Н. Вяххи в CS Club

Презентации Михаила Левина ( Хеширование строк, п.4, алгоритм Рабина-Карпа)

Точный поиск набора образцов. Алгоритм Ахо-Корасик

Лекция Павла Маврина

Лекция М.Дворкина в CS-центре

Оригинальная статья "Alfred V. Aho, Margaret J. Corasick. Efficient string matching: Anaid to bibliographic search"

Статьи на хабре:

Алгоритм Ахо-Корасик

Неверная интерпретация алгоритма Ахо-Корасик

Алгоритм на e-maxx.ru

Суффиксные массивы и деревья

Суть и построение суффиксного дерева

CSCenter: Суффиксные массивы, Михаил Дворкин

Презентация построение суффиксного массива, Михаил Левин