Домашнее задание для 2 семестра алгоритмов и структур данных

Для удобства можно пользоваться папкой lib, все файлы из этой папки будут подключаться к любой задаче

Можно получить дополнительные баллы, если добавить интересные текстовые задачи. Необходимы текст задачи, решение и тесты.

Теория по алгоритмам:

1. Обходы гррафа

1.1. Ориентированный граф, псевдограф. Неориентированный граф, псевдограф. Связность в неор. графе, компоненты связности. Слабая и сильная связность в ор. графе. Компоненты слабой, сильной связности.

1.2. Обход в глубину. Цвета вершин. Времена входа и выхода. Лемма о белых путях(с доказательством).

1.3. Проверка связности неориентированного графа. Поиск цикла в неориентированном и ориентированном графе. Топологическая сортировка.

1.4. Нахождение компонент сильной связности. Алгоритм Косарайю с доказательством корректности(концепция). Алгоритм Тарьяна без доказательства корректности.

1.5. Компоненты реберной двусвязности. Мосты. Поиск мостов.

1.6. Компоненты вершинной двусвязности. Точки сочленения. Поиск точек сочленения.

1.7. Волновой алгоритм. Обход в ширину (применение очереди в волновом алгоритме).

1.8. Критерий существования Эйлерова пути и цикла в ориентированном и неориентированном графе. Поиск эйлерова пути и цикла.

2. Планарность графа

2.1. Формула Эйлера. Теорема Портнягина-Куратовского. Теорема Вагнера

2.2. Гамма алгоритм. Контактная вершина.

2.3. Теорема о корректности Гамма алгоритма. Асимптотика алгоритма.

3. Кратчайшие пути во взвешенном графе.

3.1. Алгоритм Дейкстры. Доказательство корректности(с доказательством) Оценка времени работы. Дерево кратчайших путей.

3.2. Потенциалы. Условие применимости алгоритма Дейкстры для измененных длин ребер. Потенциал π(v) = ρ(v, t).) = ρ(v) = ρ(v, t)., t).

3.3. Алгоритм A*. Условие монотонности на эвристику. Примеры эвристик.

3.4. Алгоритм Форда-Беллмана. Хранение в матрице: Dv) = ρ(v, t).k равно длине кратчайшего пути до вершины v) = ρ(v, t). за ровно k ребер (не более k ребер). Доказательство корректности(полное). Оценка времени работы.

3.5. Восстановление пути. Детектирование цикла отрицательного веса. Поиск самого цикла.

3.6. Нахождение кратчайших путей с учетом циклов отрицательного веса.

3.7. Алгоритм Флойда. Доказательство (концепция). Восстановление пути.

3.8. Нахождение цикла отрицательного веса.

3.9. Алгоритм Джонсона. Добавление фиктивного корня и фиктивных ребер для запуска алгоритма Форда-Беллмана.

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

4.1. Остовное дерево. Построение с помощью обхода в глубину и в ширину.

4.2. Определение минимального остовного дерева.

4.3. Теорема о разрезе. Доказательство.

4.4. Алгоритм Прима. Аналогия с алгоритмом Дейкстры. Оценка времени работы для различных реализаций очереди с приоритетом: бинарная куча, Фибоначчиева куча (последнее без доказательства).

4.5. Алгоритм Прима. Доказательство корректности с помощью теоремы о разрезе.

4.6. Алгоритм Крускала. Доказательство корректности. Оценка времени работы.

4.7. Система непересекающихся множеств. Эвристика потенциалов без доказательства. Эвристика сжатия пути без доказательства. Почти константное время работы(без доказательства).

4.8. Алгоритм Борувки. Доказательство(полное). Оценка времени работы.

4.9. Приближение решения задачи коммивояжера с помощью минимального остовного дерева.

5. Потоки в сетях.

5.1. Определение сети. Определение потока. Физический смысл. Аналогия с законами Кирхгофа. Определение разреза. Понятия потока через разрез.

5.2. Определение разреза. Понятия потока через разрез. Доказательство факта, что поток через любой разрез одинаковый.

5.3. Понятие остаточной сети. Понятие дополняющего пути. Необходимость отсутствия дополняющего пути для максимальности потока.

5.4. Теорема Форда-Фалкерсона.

5.5. Алгоритм Форда-Фалкерсона. Поиск минимального разреза. Пример целочисленной сети, в котором алгоритм работает долго.

5.6. Алгоритм Эдмондса-Карпа. Доказательство, что кратчайшее расстояние в остаточной сети не уменьшается.

5.7. Общая оценка времени работы алгоритма Эдмондса-Карпа. (не строго)

5.8. Слоистая сеть. Алгоритм Диница. Оценка времени работы без доказательства.

RMQ. Sparse-table, дерево отрезков. LCA. Декартово дерево по неявному ключу.

6.1. RSQ и RMQ. Sparse-table.

6.2. Дерево отрезков. Обработка запросов от листьев. Обработка запросов от корня.

6.3. Дерево отрезков. Изменение значения в массиве, обновление дерева отрезков. Множественные операции.

6.4. LCA. Метод двоичного подъёма.

6.5. Декартово дерево по неявному ключу. Интерфейс быстрого массива: Доступ к элементу в позиции i, Вставка элемента в позицию i, Удаление элемента из позиции i, Конкатенация двух массивов, разделение массива на два.