Алгоритмы и структуры данных, часть 2
Санкт-Петербург, весна 2012
Описание
Продолжение изучения базовых алгоритмов, продолжение курса Алгоритмы и структуры данных 1.
Преподаватели
Список лекций
Кратчайшие пути при наличии рёбер отрицательного веса: алгоритм Беллмана-Форда; определение наличия цикла отрицательного веса в графе. Кратчайшие пути в ациклических ориентированных графах. Кратчайшие пути между всеми парами вершин: алгоритм Флойда-Уоршолла, алгоритм Джонсона.
Общие принципы жадного метода. Непрерывная и дискретная задачи о рюкзаке. Задача о выборе заявок. Минимальное покрывающее дерево: свойство разреза, жадная стратегия.
Алгоритм Крускала, система непересекающихся множеств.
Система непересекающихся множеств: доказательство оценки на время работы алгоритма с эвристикой сжатия путей. Числовые алгоритмы. Основные арифметические операции: сложение, умножение, деление, нахождение наибольшего общего делителя.
Арифметика сравнений: сложение, умножение, возведение в степень, нахождение обратного по модулю. Вероятностный тест на простоту.
Генерация случайных простых чисел. Криптография: схемы с закрытым ключом, RSA.
Быстрое вычисление значений многочлена в точках: два способа задания многочленов — коэффициентами и значениями в точках; вычисление значений многочлена в точках методом разделяй и властвуй
; дискретное преобразование Фурье; быстрое преобразование Фурье. Интерполяция: интерполяция в терминах матриц; матрица Вандермонда; интерполяция как домножение на обратную матрицу.
Линейное программирование: общий вид задачи, двойственность. Задача о максимальном потоке. Задача о паросочетании в двудольном графе.
Подробнее о двойственности, симплекс-метод.
Задача поиска подстроки в строке. Наивный алгоритм, алгоритм Карпа-Рабина, алгоритм Кнута-Морриса-Пратта.
Построение суффиксного дерева за линейное время.
Задачи поиска, классы P и NP. Сведения. Доказательство NP-полноты задач выполнимости, 3-выполнимости, выполнимости схемы, задачи о независимом множестве.