Алгоритмы и структуры данных, часть 2
Новосибирск, весна 2022
Описание
Продолжение курса Алгоритмы и структуры данных, часть 1
, посвящено углублённому изучению алгоритмов по темам:
- Строки.
- Конечные автоматы, регулярные выражения, формальные грамматики.
- Графы.
Критерии оценки
- Отлично: F≥2 и S≥800,
- Хорошо: F≥2 и S≥600 или F≥1 и S≥800,
- Зачет: F≥2 и S≥400 или F≥1 и S≥600,
где F — количество задач, сданных по полной схеме, S — сумма баллов за задачи в контестах. Всего будет 2 задачи по полной схеме.
Инструкция по сдаче заданий
Подробная инструкция к нашему курсу содержится в этом документе: https://disk.yandex.ru/i/Z0eIiaPVrY9pIg.
Преподаватели
Список лекций
Алгоритм Кнута-Морриса-Пратта: идея, время работы. Префикс-суффиксы (borders), максимальный из них, множество всех префикс-суффиксов строки. Префикс-функция строки. Алгоритм вычисления префикс-функции, время работы. Префикс-функция строки P#T, предподсчёт и поиск КМП. Много образцов: время работы. Бор (trie), вставка слов в бор. Порождённый образцами бор, пометки вершин бора. Определение функции отката FF(a). Проход по тексту с отслеживанием вершины в боре, время работы. Определение найденных вхождений образцов, время работы. Построение функции FF, порядок обхода вершин (в ширину), время работы. Зависимость затрат времени и памяти от размера алфавита: использование массива, списка, дерева поиска для хранения переходов.
Лекция прошлого года: https://youtu.be/KpNRyqmHm38
Определения: сеть, поток, задача о макс. потоке; разрез, остаточная сеть, дополняющий путь.
Теорема Форда-Фалкерсона. Метод Форда-Фалкерсона.
Алгоритм Эдмонса-Карпа.
Метод Диница.