• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

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

2019/2020
Учебный год
RUS
Обучение ведется на русском языке
2
Кредиты

Преподаватель

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

Аннотация

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

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

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

Результаты освоения дисциплины

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

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

  • Модели вычислений и сложность. Стандартные способы представления графов относительно вычислительной модели 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 алгоритм для взвешенного варианта этих задач.
Элементы контроля

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

  • неблокирующий Домашнее задание
  • неблокирующий Домашнее задание
  • неблокирующий Устный экзамен
Промежуточная аттестация

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

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

Список литературы

Рекомендуемая основная литература

  • Графы и алгоритмы. Структуры данных. Модели вычислений, учебник, 319 с., Алексеев, В. Е., Таланов, В. А., 2012

Рекомендуемая дополнительная литература

  • Алгоритмы : построение и анализ, пер. с англ., 3-е изд., 1323 с., Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К., 2018
  • Бинарные отношения, графы и коллективные решения, учебное пособие, 298 с., Алескеров, Ф. Т., Хабина, Э. Л., Шварц, Д. А., 2006