Учебные материалы

Книги

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

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

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

Ссылки

Курс на виртуальном образовательном кластере "ЛЭТИ" (moodle)

NP и сложность

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

Графы

Кратчайшие пути

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

Алгоритм А*

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

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

Хабрахабр

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

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

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

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

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

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

5 лекция Stepik

Эвристические алгоритмы на графах

Краткий констпект А*

Псевдокод А*

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

Определения

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

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

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

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

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

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

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

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

Строки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Суффиксные массивы

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

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