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