se.moevm.info

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== Программа ======
===== Сложность алгоритмов =====
  - Виды сложности:
    * Операции
    * Время
    * Память
  - Понятие вычислительной сложности в зависимости от размера входа
  - Константная сложность на примере vector и unordered_set:
    * Амортизированная
    * В среднем
    * В худшем

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

===== Жадные алгоритмы =====
  - Задача об оптимальном расписании
  - Задача о префиксном кодировании
  - Принцип доказательства оптимальности работы жадного алгоритма

===== Графы =====
==== Раскраска в 3 цвета ====
  - Алгоритм полного перебора
  - Перебор с учётом выбора только из 2 цветов
  - Перебор подмножеств размера <= n/3
  - Вероятностный алгоритм. Сведение к задаче выполнимости
  - Применение раскраски на практике

==== Минимальный разрез ====
  - Примеры практических задач
  - Алгоритм Каргера
  - Оптимизация Штейна алгоритма Каргера

==== Кратчайшие пути. A* и его расширения ====
  - Напоминание о A*
  - Эвристические функции
  - Алгоритм ALT
  - Алгоритм REACH
  - Алгоритм Arc flags

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

==== Потоки в графах ====
  - Алгоритм Гольдберга (проталкивания предпотока):
    * Идея push-relabel алгоритмов
    * Формализмы и инварианты
    * Доказательство корректности
    * Сравнение сложности с Фордом-Фалкерсоном 

==== Изоморфизм графов ====
  - Задача изоморфизма:
    * Точный изоморфизм
    * Поиск подграфа в графе
  - Алгоритм Ульмана (переборный с матрицей)
  - Применение изоморфизма

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

==== Алгоритм Кнута-Морриса-Пратта ====
  - Основные определения
  - Задача точного поиска образца в строке
  - Наивный алгоритм и его сложность
  - Алгоритм КМП
  - Наивное построение префикс-функции и его сложность
  - Построение префикс-функции за линейное время
  - Оптимизация сложности по памяти

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

===== Динамическое программирование =====
  - Примеры вычисления чисел Фибоначчи
  - Масимальная возрастающая подпоследовательность:
    * Сведение к графу
    * Выделение подзадачи
  - Задача о порядке перемножения матриц  

-----
<WRAP>
===== Не рассматривается (пересечение с курсами и т.п.) =====
==== Графы и структуры данных ====
  - Графы: определения и примеры.  Упорядоченный граф
  - Представления графов: матрица инциденций,  матрица смежности,  список пар, структура смежности (списки инцидентности)

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

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

==== Потоки в графах ====
  - Алгоритм Форда-Фалкерсона

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

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

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

==== Топологическая сортировка ====  
  - Ограничения на циклы
  - Алгоритм нумерацией шагов обхода
  - Алгоритм исключения вершины с минимальным количеством входящих рёбер

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

===== Задачи выполнимости =====
  - Локальный поиск
  - Метод расщепления
  - Сведения

===== Динамическое программирование =====
  - Задача о рюкзаке:
    * Без повторений (одномерный случай)
    * С повторениями (двумерный случай)
</WRAP>
se.moevm.info

User Tools

Site Tools

Page Tools
