Научный семинар

Бакалавриат 2019/2020

Статус: Курс обязательный (Прикладная математика и информатика)

Направление: 01.03.02. Прикладная математика и информатика

Кто читает: Кафедра прикладной математики и информатики (Нижний Новгород)

Где читается: Факультет информатики, математики и компьютерных наук (Нижний Новгород)

Когда читается: 3-й курс, 1-3 модуль

Формат изучения: без онлайн-курса

Преподаватели: Грибанов Дмитрий Владимирович

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

Кредиты: 2

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

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

Аннотация

Целями освоения дисциплины «научный семинар» является подготовка в области основ математических и естественно-научных знаний, получение высшего профессионально профилированного (на уровне бакалавра) образования, позволяющего выпускнику успешно работать в избранной сфере деятельности, обладать универсальными и предметно-специализированными компетенциями, способствующими его социальной мобильности и устойчивости на рынке труда.

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

Владеет навыками решения математических задач, возникающих в некоторых прикладных областях
Знает основные понятия и теоремы. Умеет решать задачи
Умеет применять на практике алгоритмы для работы с графами
Умеет формулировать современные теоретические и прикладные задачи на языке теории графов
Знает основные алгоритмы для решения задач на графах

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

Знает основные понятия и теоремы. Умеет решать задачи
Знает основные алгоритмы для решения задач на графах
Умеет формулировать современные теоретические и прикладные задачи на языке теории графов
Владеет навыками решения математических задач, возникающих в некоторых прикладных областях
Умеет применять на практике алгоритмы для работы с графами

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

Модели вычислений и сложность. Стандартные способы представления графов относительно вычислительной модели RAM.
Введение понятия вычислительной модели и сложности алгоритма. Введение в базовые модели вычислений: машина Тьюринга, модель RAM. Полиномиальная эквивалентность этих моделей. Различные виды оценок сложности алгоритмов: худший случай, лучший случай, оценка в среднем (по входу), рандомизированная оценка в среднем (относительно генератора случайных чисел), аммортизационная сложность. O-нотация. Примеры. Способы представления графов в RAM: матрица смежности, матрица инцидентности, список смежности, сжатый список смежности. Плюсы и минусы этих представлений.
Стеки, очереди, деки. Обходы графов.
Стек и очередь. Реализация стека и очереди с поддержкой максимума (сложность операций O(1)). Дек. Обход в ширину (BFS). Задачи решаемые через BFS: построение компонент связности, кратчайшие реберные пути. Обход в глубину (DFS). Задачи решаемые через DFS: эйлеров обход, эйлеров цикл, топологическая сортировка, тест ацикличности, построение сильных компонент связности, поиск мостов и точек сочленения.
Применение методов алгебры для решения задач на графах
Кольцо и поле вычетов. Обращение в поле вычетов. Малая теорема Ферма. Примеры. Напоминание: линейные пространства над полем. Пространство циклов и разрезов графа. Построение базы циклов. Рандомизированный алгоритм построения мостов и 2-мостов. Линейные сортировки: counting sort, radix sort, buckrt sort.
Задача о минимальном глобальном разрезе.
Понятие разреза в ориентированном и неориентированном графах. Задача о минимальном глобальном разрезе. Алгоритм Каргера-Штайна. Алгоритм Штера-Вагнера.
Задача о кратчайшем пути и приоритетные очереди.
Постановка задачи о кратчайшем пути. Отрицательные циклы. Операция релаксации ребра. Алгоритм Белмана-Форда. Алгоритм Дейкстры. Ускорение алгоритма Дейксты с помощью приоритетных очередей. Изучение по порядку следующих приоритетных очередей: d-кучи, левастые кучи, косые кучи, биномиальные кучи, тонкие кучи, толстые кучи, F-кучи. Задача о кратчайших путях между всеми парами вершин. Алгоритмы Джонсона и Флойда. Задача о кратчайших путях с маленькими весами ребер, vEB - деревья. Алгоритм A*. Прикладные аспекты задачи отыскания кратчайших путей на графах дорог: landmarks, ridges, shortcuts and etc.
Задача об остове максимального веса. Система разделенных множеств. Матроиды.
Понятия матроида и жадного алгоритма. Теорема Радо-Эдмондса. Примеры матроидов: реализуемый над полем, циклический, равномерный и др. Задача об остове максимального веса, формулировка на языке матроидов. Система разделенных множеств и алгоритм краскала. Различные варианты реализации разделенного множества: массивы, древовидные структуры с рангами вершин, эвристика сжатия путей. Теорема Хопкрофта, теорема Тарьяна. Алгоритм Прима для задачи об остове максимального веса, ускорение с использованием приоритетных очередей. Алгоритм Борувки. Гибрид алгоритма Борувки и алгоритма Прима.
Максимальный поток и минимальный разрез
Постановка задач о максимальном потоке и минимальном s-t разрезе. Теорема и алгоритм Форда-Фалкерсона. Полиномиальные и псевдополиномиальные алгоритмы. Метод шкалирования весов. Алгоритм Эдмондса-Карпа. Алгоритм Динница. Задача о максимальном двудольном паросочетании, сведение этой задачи к задаче о максимальном потоке с единичными весами ребер. Push-relabel алгоритмы. Приложение задачи о максимальном потоке к задаче об отыскании плотного подграфа.
Связь теории выпуклой оптимизации с экстремальными задачами на графах
Задача линейного программирования. Полиэдры, целочисленные полиэдры и тотально унимодулярные матрицы. Симплекс метод, метод эллипсоидов, метод внутренней точки. Теория двойственности. Полиномиальность задачи линейного программирования. Primal-Dual алгоритмы на примере задачи о кратчайшем пути. Линейная программа для задачи о максимальном потоке. Primal-Dual алгоритм и Push-Relabel алгоритм. Primal-Dual алгоритм для задачи о минимальном совершенном паросочетании в двудольном графе. Задача о максимальном паросочетании в графах общего вида, полиномиальный алгоритм, формула Татта-Бержа. Primal-Dual алгоритм для взвешенного варианта этих задач.

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

Домашнее задание
Домашнее задание
Устный экзамен
Экзамен проводится в устной форме (опрос по материалам курса). Экзамен проводится на платформе Discord (https://https://discord.com/). К экзамену необходимо подключиться согласно расписанию ответов, высланному преподавателем на корпоративные почты студентов накануне экзамена. Компьютер студента должен удовлетворять требованиям: наличие рабочей камеры и микрофона, поддержка Discord. Для участия в экзамене студент обязан: поставить на аватар свою фотографию, явиться на экзамен согласно точному расписанию, при ответе включить камеру и микрофон. Во время экзамена студентам запрещено: выключать камеру, пользоваться конспектами и подсказками. Кратковременным нарушением связи во время экзамена считается нарушение связи до 5 минут. Долговременным нарушением связи во время экзамена считается нарушение 5 минут и более. При долговременном нарушении связи студент не может продолжить участие в экзамене. Процедура пересдачи аналогична процедуре сдачи.

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

Промежуточная аттестация (3 модуль)
0.3 * Домашнее задание + 0.3 * Домашнее задание + 0.4 * Устный экзамен

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