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