Видеолекции курса Алгоритмы и структуры данных. Часть 2

Видеолекции курса Алгоритмы и структуры данных. Часть 2.

Лекторы: Александр Куликов, Михаил Дворкин.

Лекция 1. Пути в графах.
Кратчайшие пути при наличии рёбер отрицательного веса: алгоритм Беллмана-Форда; определение наличия цикла отрицательного веса в графе. Кратчайшие пути в ациклических ориентированных графах. Кратчайшие пути между всеми парами вершин: алгоритм Флойда-Уоршолла, алгоритм Джонсона.

Посмотреть видео на сайте Лекториума


Лекция 2. Жадные алгоритмы.
Общие принципы жадного метода. Непрерывная и дискретная задачи о рюкзаке. Задача о выборе заявок. Минимальное покрывающее дерево: свойство разреза, жадная стратегия.

Посмотреть видео на сайте Лекториума


Лекция 3. Алгоритм Крускала, система непересекающихся множеств.
Алгоритм Крускала, система непересекающихся множеств.

Посмотреть видео на сайте Лекториума


Семинар 1. Алгоритм Прима.

Посмотреть видео на сайте Лекториума


Семинар 2.

Посмотреть видео на сайте Лекториума


Семинар 3.

Посмотреть видео на сайте Лекториума


Лекция 4. Числовые алгоритмы.
Система непересекающихся множеств: доказательство оценки на время работы алгоритма с эвристикой сжатия путей. Числовые алгоритмы. Основные арифметические операции: сложение, умножение, деление, нахождение наибольшего общего делителя.

Посмотреть видео на сайте Лекториума


Семинар 4.

Посмотреть видео на сайте Лекториума


Лекция 5. Проверка простоты числа.
Арифметика сравнений: сложение, умножение, возведение в степень, нахождение обратного по модулю. Вероятностный тест на простоту.

Посмотреть видео на сайте Лекториума


Семинар 5.

Посмотреть видео на сайте Лекториума


Лекция 6. RSA.
Генерация случайных простых чисел. Криптография: схемы с закрытым ключом, RSA.

Посмотреть видео на сайте Лекториума


Семинар 6.

Посмотреть видео на сайте Лекториума


Лекция 7. Быстрое преобразование Фурье.
Быстрое вычисление значений многочлена в точках: два способа задания многочленов — коэффициентами и значениями в точках; вычисление значений многочлена в точках методом "разделяй и властвуй"; дискретное преобразование Фурье; быстрое преобразование Фурье. Интерполяция: интерполяция в терминах матриц; матрица Вандермонда; интерполяция как домножение на обратную матрицу.

Посмотреть видео на сайте Лекториума


Семинар 7.

Посмотреть видео на сайте Лекториума


Лекция 8. Линейное программирование.
Линейное программирование: общий вид задачи, двойственность. Задача о максимальном потоке. Задача о паросочетании в двудольном графе.

Посмотреть видео на сайте Лекториума


Семинар 8.

Посмотреть видео на сайте Лекториума


Лекция 9. Симплекс-метод.
Подробнее о двойственности, симплекс-метод.

Посмотреть видео на сайте Лекториума


Семинар 9.

Посмотреть видео на сайте Лекториума


Лекция 10. Алгоритм Кнута-Морриса-Пратта.
Задача поиска подстроки в строке. Наивный алгоритм, алгоритм Карпа-Рабина, алгоритм Кнута-Морриса-Пратта.

Посмотреть видео на сайте Лекториума


Семинар 10.

Посмотреть видео на сайте Лекториума


Лекция 11. Суффиксные деревья.
Построение суффиксного дерева за линейное время.

Посмотреть видео на сайте Лекториума


Семинар 11.

Посмотреть видео на сайте Лекториума


Лекция 12. NP-полные задачи.
Задачи поиска, классы P и NP. Сведения. Доказательство NP-полноты задач выполнимости, 3-выполнимости, выполнимости схемы, задачи о независимом множестве.

Посмотреть видео на сайте Лекториума


Семинар 12.

Посмотреть видео на сайте Лекториума