Алгоритмы и структуры данных, часть 1
Санкт-Петербург / осень 2012, посмотреть все семестры

Курс знакомит слушателей с базовыми алгоритмическими приёмами и структурами данных. В частности, мы узнаем следующее:

  • Почему не стоит вычислять числа Фибоначчи рекурсивно.
  • Как отсортировать массив размера n за время \(O(n\log n)\) и почему в общем случае быстрее сделать не получится.
  • Как послать закодированное сообщение другу так, чтобы только он мог его раскодировать, при условии, что канал прослушивается.
  • Как умножать числа быстрее, чем школьным методом в столбик.
  • Как предобработать Войну и мир так, чтобы потом иметь возможность почти мгновенно ответить на вопрос, сколько раз в тексте встречается заданное слово.
  • Как динамическое программирование используется в геномике.
  • Как двоичное дерево поиска может самобалансироваться в процессе добавления, удаления и даже поиска элемента.
  • Когда имеет смысл действовать жадно.
  • Как быстро найти кратчайший путь в графе.
  • Как подкидывание монетки может помочь алгоритму работать быстрее.
  • Как найти пару ближайших точек на плоскости, не проверяя при этом все пары точек.
  • Почему за решение некоторых алгоритмических задач обещан миллион долларов.

Дедлайны:

  • теоретическое доказательство: 21 ноября
  • домашние задания: 28 ноября
  • code review: 9 декабря
  • упражнения: 16 декабря

В данном курсе нет записи лекций, видео можно смотреть в курсе 2011 года.

Дата и время Название Место Материалы
13 сентября
18:30–19:50
Элементарные структуры данных, лекция ФМЛ 239, Актовый зал Нет
13 сентября
20:00–21:20
Введение, лекция ФМЛ 239, Актовый зал Нет
20 сентября
18:30–19:50
Метод "разделяй и властвуй", лекция ФМЛ 239, Актовый зал Нет
20 сентября
20:00–21:20
Семинар 1, семинар ФМЛ 239, Актовый зал Нет
27 сентября
18:30–19:50
Сортировка, лекция ФМЛ 239, Актовый зал Нет
27 сентября
20:00–21:20
Семинар 2, семинар ФМЛ 239, Актовый зал Нет
04 октября
18:30–19:50
Сортировка (продолжение), лекция ФМЛ 239, Актовый зал Нет
04 октября
20:00–21:20
Семинар 3, семинар ФМЛ 239, Актовый зал Нет
11 октября
18:30–19:50
Порядковые статистики, лекция ФМЛ 239, Актовый зал Нет
11 октября
20:00–21:20
Семинар 4, семинар ФМЛ 239, Актовый зал Нет
18 октября
18:30–19:50
Декомпозиция графов, лекция ФМЛ 239, Актовый зал Нет
18 октября
20:00–21:20
Семинар 5, семинар ФМЛ 239, Актовый зал Нет
25 октября
18:30–19:50
Пути в графах, лекция ФМЛ 239, Актовый зал Нет
25 октября
20:00–21:20
Семинар 6, семинар ФМЛ 239, Актовый зал Нет
01 ноября
18:30–19:50
Жадные алгоритмы, лекция ФМЛ 239, Актовый зал Нет
01 ноября
20:00–21:20
Семинар 7, семинар ФМЛ 239, Актовый зал Нет
08 ноября
18:30–19:50
Система непересекающихся множеств, лекция ФМЛ 239, Актовый зал Нет
08 ноября
20:00–21:20
Семинар 8, семинар ФМЛ 239, Актовый зал Нет
15 ноября
18:30–19:50
Жадные алгоритмы (продолжение), лекция ФМЛ 239, Актовый зал Нет
15 ноября
20:00–21:20
Семинар 9, семинар ФМЛ 239, Актовый зал Нет
22 ноября
18:30–19:50
Семинар 10, семинар ФМЛ 239, Актовый зал Нет
22 ноября
20:00–21:20
Семинар 11, семинар ФМЛ 239, Актовый зал Нет
29 ноября
18:30–19:50
Динамическое программирование, лекция ФМЛ 239, Актовый зал Нет
29 ноября
20:00–21:20
Динамическое программирование (продолжение), лекция ФМЛ 239, Актовый зал Нет
06 декабря
18:30–19:50
Деревья поиска, лекция ФМЛ 239, Актовый зал Нет
06 декабря
20:00–21:20
Семинар 12, семинар ФМЛ 239, Актовый зал Нет