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

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

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

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

Содержание

Программа

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

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

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

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

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

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

Графы

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

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

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

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

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

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

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

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

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

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

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

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

Симбиоз ИИ и А*

  1. Выбор лучших нейросетевых моделей поиска пути с применением генетических алгоритмов
  2. Применение рекуррентных сетей с динамическими вероятностными эвристиками при многоагентном планировании
  3. Анализ изображения препятствий для коректировки эвристических фукнций с примением свёрточных сетей и трансформеров

Динамические графы

  1. Постановка задачи, отличие от статических графов
  2. Практические примеры
  3. Поддержка динамического МОД после обновлений графа

Строки

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

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

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

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

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

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

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

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

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

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

Исключено из программы после переноса в другие курсы

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

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

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

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

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

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

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

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

Клики

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

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

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

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

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

Кандидаты на включение в программу

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

  1. Локальный поиск
  2. Метод расщепления
  3. Сведения
courses/algorithms_building_and_analysis/lectures.txt · Последнее изменение: — nskurasov