Сайт в процессе наполнения. Архив всех прошедших курсов доступен на старой версии сайта по адресу old.compsciclub.ru
Город: Санкт-Петербург Казань Язык: Русский English

Дополнительные главы алгоритмов
Осень 2014, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

В рамках курса будут рассмотрены продвинутые алгоритмы и структуры данных, как правило, не покрываемые курсом базовых алгоритмов. Отчетность: задача по программированию, теоропрос в конце курса. Правила получения зачёта.

Список планируемых тем, порядок может поменяться:

  • Персистентные структуры данных
  • Ортогональные запросы в K-мерных пространствах (дерево отрезков, fractional cascading)
  • MST и запросы на пути дерева (min, sum на пути дерева за \( O(1) \), рандомизированный алгоритм для поиска MST за \( O(E) \))
  • Алгоритмы без использования дополнительной памяти (rotate, \( d \)-куча, minmax-куча, merge, стабильная сортировка BlockSort)
  • Кучи (куча Фибоначчи, Leftist, Skew, Pairing, Weak, Radix, алгоритм Дейкстры за \( O(m + n\sqrt{\log C}) \))

  • Поиск на плоскости (локализация точки в планарном графе в offline и online)

  • Неортогональные запросы на плоскости (число точек в полуплоскости, в треугольнике в online за \( O(n^{0.44}) \), где n − число исходных точек)

  • Вычисления и структуры данных во внешней памяти, cache-oblivious вычисления

  • LCA, RMQ, LA

  • Euler-Tour trees, Heavy-Light декомпозиция, Link-Cut trees, Динамическая связность графов в online

  • Динамическая связность и 2-связность в offline; задача о поиске MST: \( \max w - \min w = \min \)

  • Потоки и разрезы (глобальный разрез за \( O(V^3) \) и \( O(V^2\log V) \), preflow push & global relabeling, поток за \( O(VE + V^2\log U) \))

  • Графы (stable marriage problem, поток минимальной стоимости за полином, цикл минимального среднего веса, кратчайший путь за \( E\sqrt V \))

  • Метод четырех русских (число единичных бит, умножение булевых матриц за \( O(n^3/log^2n) \), НОП за \( O(n^2/log^2n) \), построение схемы по булевой функции)

Последние три темы (потоки, графы, метод четырех русских) мы скорее всего не успеем рассмотреть за 12 пар.

Дата и время Название Место Материалы
14 сентября
13:00–14:35
Алгоритмы без использования дополнительной памяти, лекция ПОМИ РАН Нет
05 октября
13:00–14:35
Персистентные структуры данных, лекция ПОМИ РАН видео
12 октября
13:00–14:35
Heaps, лекция ПОМИ РАН видео
19 октября
13:00–14:35
Поиск на плоскости, лекция ПОМИ РАН видео
09 ноября
13:00–14:35
Fractional Cascading, лекция ПОМИ РАН видео
23 ноября
13:00–14:35
Вычисления и структуры данных во внешней памяти, лекция ПОМИ РАН видео
30 ноября
13:00–14:35
Heaps (окончание), лекция ПОМИ РАН видео
07 декабря
13:00–14:30
Динамическая связность offline, лекция ПОМИ РАН Нет
14 декабря
11:15–12:50
Cache-oblivious вычисления, лекция ПОМИ РАН видео
14 декабря
13:00–14:35
Динамическая связность online , лекция ПОМИ РАН видео
20 декабря
11:00–15:00
Теорзачет (мы в ПОМИ, в 402!), лекция ПОМИ РАН Нет
09 декабря 2014

Теоретический зачёт

Добрый день, ребята!

Если хотите поучаствовать в мероприятии «Теоретический зачёт по дополнительным главам алгоритмов», у вас есть такая возможность в субботу, 20 декабря, с 11:00 до 15:00 в ПОМИ. О своём желании лучше заранее сообщить на curators@compscicenter.ru

Катя Лебедева

17 ноября 2014

Правила получения оценки по курсу

Добрый день.

Появились правила получения оценки по курсу. Полный текст можно найти в файле по ссылке.

Коротко, что нужно сделать.

Выбрать оценку, на которую вы претендуете и сделать любое одно из заданий на эту оценку. Во всех заданиях нужно реализовать предложенный алгоритм или структуру данных и сделать для него тесты. В качестве результата нужно предоставить исходный код и краткий отчет с результатами тестов. Список заданий в файле выше.