Научно-исследовательский семинар "Алгоритмы и модели вычислений"

2019/2020

Статус: Дисциплина общефакультетского пула

Кто читает: Факультет математики

Где читается: Факультет математики

Когда читается: 1, 2 модуль

Преподаватели: Голубенко Дмитрий Александрович

Язык: русский

Кредиты: 3

Контактные часы: 30

Полная версия программы учебной дисциплины

Аннотация

Теория алгоритмов возникла естественным образом из вычислитель-ных задач в разных областях математики и по сей день остается живой областью, в которой некоторые тривиальные на первый взгляд вопросы до сих пор открыты — не доказано, например, существование полиномиального алгоритма разложения натурального числа на простые множители.ПРЕДВАРИТЕЛЬНАЯ ПОДГОТОВКА: обязательные — дискретная математика, алгебра (1 курс), логика; желательные — теория сложности (определения классов P, NP, PSPACE, сводимости), теория вероятности.

Цель освоения дисциплины

Разобрать основные алгоритмы на числах, графах, в вычислительной алгебре и геометрии, исследовать некоторые их свойства и ознакомимся с их применениями.

Планируемые результаты обучения

Построение алгоритма, решающего некоторую задачу, доказательство его корректности и оценка его сложности по времени и ресурсоемкости.

Содержание учебной дисциплины

Модели вычисления, веротяностные алгоритмы (определение), оценки асимптотик, Quicksort
Арифметические операции, быстрое умножение (Карацуба, Штрассен), полиномиальные реализации алгоритмов Евклида и Гаусса
Быстрое преобразование Фурье и его применения в арифметике: алгоритм Шенхаге-Штрассена, модулярное деление многочленов
Тесты на простоту (Ферма, Рабин-Миллер, АКС, Соловей-Штрассен), простейшие криптографические протоколы, дискретное логарифмирование
Разложение числа на простые множители (Поллард, эллиптическая кривая)
Модулярная арифметика многочленов, разложение многочленов на множителей (Цассенхаус, Фробениус, трюк с поднятием Гензеля).
Базисы Гребнера, алгоритм Бухбергера, многомерное деление с остатком.
Вычисления в группах, алгоритм Шрайера-Симса и его применения, изоморфизм кубических графов.
DFS, топологическая сортировка, поиск мостов, точек сочленения, компонент сильной связности, прочие применения (автоматные группы --- если успеем).
BFS, кратчайшие пути (Дейстра, Беллман-Форд, Флойд-Уоршелл).
Минимальные остовные деревья.
Потоки в графе, алгоритм Форда-Фалкерсона, поиск паросочетаний.
Алгоритм Тарьяна-Голдберга, комбинаторные приложения.

Элементы контроля

Решение домашних задач
Итоговый экзамен

Промежуточная аттестация

Промежуточная аттестация (2 модуль)
0.5 * Итоговый экзамен + 0.5 * Решение домашних задач

Программа дисциплины