Теория алгоритмов

Аннотация курса: В данном курсе мы изучим алгоритмы поиска и сортировки, рекурсивные алгоритмы, алгоритмы на графах, рассмотрим алгоритмы хеширования и криптографические алгоритмы, методы криптоанализа, изучим динамическое и линейное программирование, изучим целый ряд других тем.

1. Обзор курса. Список литературы. Примеры алгоритмов: (классический) алгоритм Евклида, рекурсивный и расширенный алгоритм Евклида, вычисление чисел Фибоначчи (рекурсивный алгоритм и подход динамического программирования), решето Эратосфена, фракталы и алгоритмы построения фракталов.
2. Границы рационального познания: теоремы Гёделя, гипотеза Кантора, результаты Пола Дж. Коэна. Сотрудничество человека и машины: теорема о четырех красках, исследования по гипотезе Римана.
3. Анализ алгоритмов: вычислимые функции, рекурсивные функции. Временная и пространственная сложность алгоритма. Классы P, PSPACE, NP. Классические вычислительные схемы. Дизъюнктивная нормальная форма. Обратимые вентили.
4. Задачи сортировки: сортировка вставками, сортировка выбором, рекурсивная сортировка слиянием, рандомизированная сортировка, быстрые сортировки. Двоичный поиск. Алгоритмы сложения, вычитания, умножения столбиком, рекурсивного умножения, деления.
5. Рекурсивные алгоритмы: теорема об оценке сложности рекурсивного алгоритма. Рекурсивное умножение матриц методом Штрассена. Быстрое преобразование Фурье. Рекурсивное умножение многочленов. Решение задачи интерполяции с помощью интерполяционного многочлена Лагранжа и методом быстрого преобразования Фурье.
6. Алгоритмы на графах. Практические задачи на теорию графов: задача о кенигсбергских мостах, задача Эйлера о колодцах, гамильтонов цикл на додекаэдре, задача о коммивояжере, задача о четырех красках, поиск пути из лабиринта замка Хемптон Корт. Алгоритмы выхода из лабиринта.
7. Алгоритмы на графах. Представление графа матрицей смежности и списками смежности.Обход графа в глубину и его применения.Обход графа в ширину.
8. Алгоритмы на графах, жадные алгоритмы. Поиск кратчайшего пути в графе (алгоритм Дейкстры). Поиск критического (максимального) пути в графе. Остовные деревья. Алгоритм Прима. Покрывающие деревья: пример жадного алгоритма. Реализация алгоритма Крускала. Дерево Штейнера. Покрытие множествами.
9. Хеш-функции. Хеширование. Коллизии первого и второго рода. Устойчивость хеш-функций. Атаки на хеш-функции. Сигнатурный антивирусный сканнер.
10. Хеш-функции. Алгоритм MD5. Алгоритм SHA-3.
11. Криптографические алгоритмы. Введение в криптологию. Симметричное шифрование: стандарты DES и TripleDES. Конечные поля. Стандарт AES.
12. Криптографические алгоритмы с открытым ключом. Мультипликативные функции. Теория сравнений. Арифметика сравнений: алгоритмы сложения, умножения и возведения в степень по модулю. Деление по модулю с помощью расширенного алгоритма Евклида. Протокол шифрования с открытым ключом RSA.
13. Распределение простых чисел: теоремы Чебышёва. Проверка чисел на простоту. Генерация простых чисел.
14. Методы криптоанализа. Атака методом грубой силы. Атака дней рождения. Дифференциальный криптоанализ. Линейный криптоанализ. Метод бумеранга.
15. Динамическое программирование. Вычисление биномиальных коэффициентов. Кратчайшие пути в ориентированных ациклических графах. Поиск наибольшей строго возрастающей подпоследовательности. Оптимальная расстановка скобок при вычислении произведения не менее трех матриц. Оптимальная триангуляция многоугольника. Задача линейного разбиения.
16. Линейное программирование. Постановка задачи линейного программирования. Пример задач линейного программирования: максимизация прибыли, планирование производства. Симплекс-метод. Транспортная задача.
17. Сдача практикума: реализация криптографического алгоритма.

• Реализовать рекурсивный алгоритм Штрассена умножения матриц.
• Реализовать алгоритм поиска циклов в графах.
• Реализовать один из многораундовых алгоритмов блочного шифрования на основе сети Фейстеля (можно придумать свой) и оценить его параметры: быстродействие, криптостойкость.
• (Классический) алгоритм Евклида, рекурсивный и расширенный алгоритм Евклида.
• Вычисление чисел Фибоначчи (рекурсивный алгоритм и подход динамического программирования), фракталы и алгоритмы построения фракталов.
• Границы рационального познания: теоремы Гёделя, гипотеза Кантора, результаты Пола Дж. Коэна. Сотрудничество человека и машины: теорема о четырех красках, исследования по гипотезе Римана.
• Машина Тьюринга. Программа вычисления суммы натуральных чисел на машине Тьюринга. Вычислимые функции. Тезис Тьюринга.
• Примитивно рекурсивные, частично рекурсивные и общерекурсивные функции. Примеры примитивно рекурсивных функций.
• Анализ алгоритмов: временная и пространственная сложность алгоритма. Классы P, PSPACE, NP. Примеры задач класса NP.
• Классические вычислительные схемы. Дизъюнктивная нормальная форма. Обратимые вентили.
• Задачи сортировки: сортировка вставками, сортировка выбором, рекурсивная сортировка слиянием, рандомизированная сортировка. Двоичный поиск.
• Рекурсивные алгоритмы: теорема об оценке сложности рекурсивного алгоритма. Рекурсивное умножение матриц методом Штрассена.
• Алгоритмы для вычисления элементарных операций: сложение, вычитание, умножение (столбиком и рекурсивный алгоритм), деление.
• Быстрое преобразование Фурье. Рекурсивное умножение многочленов. Решение задачи интерполяции с помощью интерполяционного многочлена Лагранжа и методом быстрого преобразования Фурье.
• Практические задачи на теорию графов: задача о кенигсбергских мостах, задача Эйлера о колодцах, гамильтонов цикл на додекаэдре, задача о коммивояжере, задача о четырех красках (построение графа по карте).
• Поиск пути из лабиринта (построение графа по заданному лабиринту). Алгоритмы выхода из лабиринта.
• Представление графа матрицей смежности и списками смежности. Обход графа в глубину и его применения. Обход графа в ширину.
• Поиск кратчайшего пути в графе (алгоритм Дейкстры). Поиск критического (максимального) пути в графе.
• Жадные алгоритмы. Остовные деревья. Алгоритм Прима. Алгоритм Крускала.
• Дерево Штейнера. Задача о вершинном покрытии. Оптимальное покрытие множествами.
• Хеш-функции. Хеширование. Коллизии первого и второго рода. Устойчивость хеш-функций. Атаки на хеш-функции.
• Алгоритм MD5.
• Алгоритм SHA-3.
• Введение в криптологию. Примеры шифров. Моноалфавитные и полиалфавитные шифры. Симметричное шифрование. Сеть Фейстеля. Алгоритм шифрования с открытым ключом.
• Стандарты DES и Triple DES.
• Конечные поля. Стандарт AES.
• Мультипликативные функции. Формула обращения. Функции Мёбиуса и Эйлера.
• Простейшие свойства сравнений. Обратимые элементы в кольце вычетов. Малая теорема Ферма. Теорема Эйлера.
• Протокол шифрования с открытым ключом RSA.
• Арифметика сравнений: алгоритмы сложения, умножения и возведения в степень по модулю. Деление по модулю с помощью расширенного алгоритма Евклида.
• Распределение простых чисел: теоремы Чебышёва. Проверка чисел на простоту – с помощью решета Эратосфена и тестом Ферма. Генерация простых чисел.
• Методы криптоанализа. Атака методом грубой силы. Атака дней рождения.
• Дифференциальный криптоанализ. Линейный криптоанализ. Метод бумеранга.
• Динамическое программирование. Вычисление биномиальных коэффициентов.
• Кратчайшие пути в ориентированных ациклических графах.
• Поиск наибольшей строго возрастающей подпоследовательности. Оптимальная расстановка скобок при вычислении произведения не менее трех матриц.
• Оптимальная триангуляция многоугольника. Задача линейного разбиения.
• Линейное программирование. Постановка задачи линейного программирования.
• Пример задач линейного программирования: максимизация прибыли, планирование производства.
• Симплекс-метод.
• Транспортная задача.

• Стивен Скиена «Алгоритмы. Руководство по разработке». 2014.
• С. Дасгупта, Х. Пападимитриу, У. Вазирани «Алгоритмы». 2014.
• Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн «Алгоритмы. Построение и анализ». 2013.
• С. Панасенко «Алгоритмы шифрования», 2008.
• Ю.В.Нестеренко «Теория чисел», 2008.
• В.И.Игошин «Теория алгоритмов». 2013.
• Дж. Прескилл «Квантовая информация и квантовые вычисления. Том 1». 2008.
• Под ред. В.В.Ященко «Ведение в криптографию», 2000.
• Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков «Численные методы». 1987.
• О.Н.Василенко «Теоретико-числовые алгоритмы в криптографии», 2006.
• М.П.Минеев, В.Н.Чубариков, «Лекции по арифметическим вопросам криптографии», 2014.
• В.И.Крупский, В.Е.Плиско «Математическая логика и теория алгоритмов». 2013.
• Н.П.Редькин «Дискретная математика», 2009.
• Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, “Handbook of Applied Cryptography”, 2014.
• Myasnikov A., Shpilrain V., Ushakov A., “Group-based Cryptography”, 2008.