2018:2019 Spring - Algocourse/info GitHub Wiki

Занятия проходят по субботам в аудитории В-119. Время: 12:00.

Занятие 10. 20 апреля 2019.

• Двумерное дерево отрезков.
• Хеширование. Полиномиальный хеш.
• Хеш-таблица.

Задание:

• Задача на поиск подстроки в строке.
• Задача на хеширование.
• Задача на csacademy.
• Задача на ДО.

Занятие 9. 13 апреля 2019.

• Персистентные структуры данных.
• Персистентное дерево отрезков.
• Конспект от ИТМО.
• Heavy-light декомпозиция

Задание

• Задача на применение ДО.
• Простое задание.
• Тренировки СПБГУ на ДО: #1, #2, #3.
• Количество различных чисел на отрезке.
• Персистентный массив.
• Задача на спуск в персистентном ДО.
• Задачи на Heavy-ligth.

Занятие 8. 6 апреля 2019.

• Дерево отрезков.
• Прибавление в точке, запрос суммы на отрезке.
• Операции на отрезке.
• Прибавление на отрезке, запрос суммы на отрезке.
• Присвоение на отрезке, запрос суммы на отрезке.

Занятие 7. 30 марта 2019.

• Sparse table.
• Дерево Фенвика.

Задание:

• Задача на Sparse table
• Задача на дерево Фенвика

Занятие 6. 23 марта 2019.

• Система непересекающихся множеств (СНМ, DSU). Эвристики, используемые при реализации. Конспект от ИТМО.
• Минимальное остовное дерево. Алгоритмы построения.
• Алгоритм Прима.
• Алгоритм Крускала.

Задание:

• Комплект задач #1 и #2.
• Задача на слияние множеств.

Занятие 5. 16 марта 2019.

• Поиск компонент сильной связности. Конденсация графа.
• Наименьший общий предок.
• Метод двоичного подъёма. Конспект от ИТМО.

Задание:

• Задача на построение конденсации графа.
• Задача на реализацию.
• Задача с переподвешиванием.

Занятие 4. 9 марта 2019.

• Поиск мостов и точек сочленения. Алгоритм с использованием DFS.
• Топологическая сортировка графа.
• Идея Meet-in-the-middle.

Задание:

• Задача на топологическую сортировку.
• Задача на поиск мостов.
• Задача на Meet-in-the-middle.

Занятие 3. 2 марта 2019.

• Нахождение кратчайших путей между всеми парами вершин. Алгоритм Флойда-Уоршелла.
• Поиск кратчайшего пути во взвешенном графе. Алгоритм Форда-Беллмана. Конспект.
• Поиск цикла отрицательного веса алгоритмом Форда-Беллмана.

Задание:

• Задачи A, С и D из тренировки.
• Задача A, B и C из тренировки.
• Контест.

Занятие 2. 23 февраля 2019.

• Графы. Основные понятия.
• Поиск в ширину.
• Поиск в глубину.
• Дерево обхода в глубину.
• Поиск кратчайшего пути во взвешенном графе с неотрицательными ребрами. Алгоритм Дейкстры.

Задание:

• Поиск в глубину. Задачи.
• Поиск в ширину. Задачи.
• Задачи на Дейкстру - задача F и G из тренировки.
• Задача Транспортировка.
• Задача Короткий путь.
• Задача Пути и деревья.

Занятие 1 (Дополнительное). 17 февраля 2019.

• Контест.