2017:2018 Spring - Algocourse/info GitHub Wiki

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

• Необходимо на занятии иметь с собой ноутбук.

Занятие 23. 12 мая 2018.

• Корневая декомпозиция.
• Примеры задач. Сумма на отрезке.
• Задача про модули

Занятие 22. 5 мая 2018.

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

Задание:

• Персистентный массив.
• Задача на спуск в персистентном ДО.

Занятие 21. 21 апреля 2018.

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

Задание:

• Оставшиеся задачи прошлого занятия

Занятие 20. 14 апреля 2018.

• Задача нахождения суммы на отрезке. Частичные суммы.
• Дерево отрезков.
• Прибавление в точке, запрос суммы на отрезке.

Задание:

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

Занятие 19. 7 апреля 2018.

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

Задание:

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

Занятие 18. 31 марта 2018.

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

Задание:

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

Занятие 17. 24 марта 2018.

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

Задание:

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

Занятие 16. 17 марта 2018.

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

Задание:

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

Занятие 15. 3 марта 2018.

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

Задание:

• Задачи A из тренировки.
• Задача C из тренировки.
• Задача на топологическую сортировку.
• Задача на поиск мостов

Занятие 14. 24 февраля 2018.

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

Задание:

• Задачи на Дейкстру - задача F и G из тренировки.
• Задача Транспортировка.
• Задача Короткий путь.
• Задача Пути и деревья.
• Задачи С и D из тренировки.
• Задача A и B из тренировки.
• Задача на Дейкстру.

Занятие 13. 17 февраля 2018.

• Графы. Основные понятия.
• Поиск в ширину. Конспект.
• Поиск в глубину. Конспект.
• Дерево обхода в глубину.
• Топологическая сортировка графа.

Задание:

• Поиск в глубину. Задачи.
• Поиск в ширину. Задачи.

Будущие темы:

• Поиск компонент сильной связности. Конденсация графа.
• Задача на построение конденсации графа.
• Ретроспективный анализ. Его применение для решения задач на примере Задачи A.