МОЭВМ Вики [se.moevm.info]

Инструменты пользователя

Инструменты сайта

Вы находитесь здесь: МОЭВМ Вики » Курсы » Построение и анализ алгоритмов » Программа
courses:algorithms_building_and_analysis:lectures

Содержание

Программа

Сложность алгоритмов

  1. Виды сложности:
    • Операции
    • Время
    • Память
  2. Понятие вычислительной сложности в зависимости от размера входа
  3. Константная сложность на примере vector и unordered_set:
    • Амортизированная
    • В среднем
    • В худшем

Поиск с возвращением

  1. Идея поиска с возвращением (backtracking)
    • Пример на задаче о ферзях
    • Подходы метода ветвей и границ по отсеканию вариантов
  2. Метод Монте-Карло
    • Пример на размере дерева
    • Пример на площади фигуры
    • Ограничения и условия применимости

Жадные алгоритмы

  1. Задача об оптимальном расписании
  2. Задача о префиксном кодировании
  3. Принцип доказательства оптимальности работы жадного алгоритма

Графы

Раскраска в 3 цвета

  1. Алгоритм полного перебора
  2. Перебор с учётом выбора только из 2 цветов
  3. Перебор подмножеств размера ⇐ n/3
  4. Вероятностный алгоритм. Сведение к задаче выполнимости
  5. Применение раскраски на практике

Минимальный разрез

  1. Примеры практических задач
  2. Алгоритм Каргера
  3. Оптимизация Штейна алгоритма Каргера

Кратчайшие пути. A*

  1. Напоминание об алгоритмах поиска пути:
    1. Поиск в ширину
    2. Дейкстра
  2. A*:
    1. Выбор направления пути Дейкстрой при 0-взвешивании рёбер оптимального пути
    2. Доказательство неизменности пути при перевзвешивании рёбер
    3. Ограничения А*
  3. Эвристические функции

Кратчайшие пути. Расширения A*

  1. Алгоритм ALT
  2. Алгоритм REACH
  3. Оптимизация слияния рёбер

Задача о коммивояжёре

  1. Сложность полного перебора
  2. Метод ветвей и границ:
    • Отсечка по текущему найденному пути
    • Отсечка по весу МОД
  3. Локальный поиск
    • 2-окружение
    • Имитация отжига
  4. Приближённое решение (2-приближённый алгоритм)

Потоки в графах

  1. Напоминание Форда-Фалкерсона
    • Идея поиска пути в остаточной сети
    • Обратные рёбра
    • Сложность
  2. Алгоритм Гольдберга (проталкивания предпотока):
    • Идея push-relabel алгоритмов
    • Формализмы и инварианты
    • Доказательство корректности
    • Сравнение сложности с Фордом-Фалкерсоном

Изоморфизм графов

  1. Задача изоморфизма:
    • Точный изоморфизм
    • Поиск подграфа в графе
  2. Алгоритм Ульмана (переборный с матрицей)
  3. Применение изоморфизма

Строки

Редакционное расстояние

  1. Расстояние Левенштейна (редакционное расстояние)
  2. Вычисление редакционного расстояния методом ДП
  3. Восстановление РП по таблице (обратный ход в методе ДП)
  4. Сведение задачи к путям в графе

Алгоритм Кнута-Морриса-Пратта

  1. Основные определения
  2. Задача точного поиска образца в строке
  3. Наивный алгоритм и его сложность
  4. Алгоритм КМП
  5. Наивное построение префикс-функции и его сложность
  6. Построение префикс-функции за линейное время
  7. Оптимизация сложности по памяти

Алгоритм Ахо-Корасик

  1. Задача точного поиска набора образцов
  2. Trie
  3. Задача о словаре
  4. Алгоритм Ахо-Корасик

Суффиксные деревья и массивы

  1. Суффиксное дерево - мотивация, сложность, поиск
  2. Суффиксный массив - мотивация, сложность, поиск
  3. Алгоритм Укконена

Динамическое программирование

  1. Примеры вычисления чисел Фибоначчи
  2. Масимальная возрастающая подпоследовательность:
    • Сведение к графу
    • Выделение подзадачи
  3. Задача о порядке перемножения матриц

Не рассматривается (пересечение с курсами и т.п.)

Графы и структуры данных

  1. Графы: определения и примеры. Упорядоченный граф
  2. Представления графов: матрица инциденций, матрица смежности, список пар, структура смежности (списки инцидентности)

Остовные деревья

  1. Задача о связности графа и остовный лес
  2. Минимальное остовное дерево. Теорема «о минимальном ребре»:
    • Жадный алгоритм (Краскал)
    • Алгоритм «ближайшего соседа» (Ярник, Прим, Дейкстра)
    • Алгоритм Борувки (О(m*log n))

Задачи связности

  1. Связные компоненты
  2. Алгоритм нахождения сильно связных компонент (Косарайю)

Потоки в графах

  1. Алгоритм Форда-Фалкерсона

Кратчайшие пути. Дейкстра

  1. Кратчайшие пути от фиксированной вершины
  2. Случай неотрицательных весов: алгоритм Дейкстры
  3. Алгоритм Флойда-Уоршелла вычисления расстояний между всеми парами вершин, одновременное построение путей

Паросочетания

  1. Понятия вершинных и рёберных покрытий
  2. Теорема Галлаи
  3. Алгоритм Куна поиска паросочетания в двудольном графе

Клики

  1. Полные подграфы, клики
  2. Применения и сложность задачи построения клик графа
  3. Алгоритм нахождения клик на основе поиска с возвращением.

Топологическая сортировка

  1. Ограничения на циклы
  2. Алгоритм нумерацией шагов обхода
  3. Алгоритм исключения вершины с минимальным количеством входящих рёбер

Алгоритм Рабина-Карпа

  1. Идея использования хешей для решения задачи точного поиска образца в строке
  2. Полиномиальные хеши для строк
  3. Алгоритм быстрого вычисления всех хешей текста длины образца
  4. Алгоритм Рабина-Карпа

Задачи выполнимости

  1. Локальный поиск
  2. Метод расщепления
  3. Сведения

Динамическое программирование

  1. Задача о рюкзаке:
    • Без повторений (одномерный случай)
    • С повторениями (двумерный случай)