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

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

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

Первые шесть недель лекции шли в формате онлайн-курса, а семинары читались вживую. Видео и слайды с онлайн курса опубликованы в занятиях-лекциях в курсе. Все видео онлайн-курса можно найти на канале CS центра на YouTube. Остальные лекции курса (с седьмой недели живые лекции) не записывались, по ссылке можно найти лекции 2011 года и смотреть их.

Литература

  • S. Dasgupta, C. Papadimitriou, U. Vazirani. Algorithms. McGraw-Hill. 2006.
  • А. Х. Шень. Программирование: теоремы и задачи. Издательство МЦНМО. 2007.
  • М. А. Бабенко, М. В. Левин. Введение в теорию алгоритмов и структур данных. Издательство МЦНМО. 2012.
  • Т. Кормен, Ч. Лейзерсон, И. Ривест, К. Штайн. Алгоритмы: построение и анализ.

Для получения оценки по курсу нужно

Прошлогодние правила осень, весна.

Правила этого года. Если коротко: сдать онлайн курс, сдать задачи в Я.Контест, пройти CodeReview по одной из задач в Я.Контест

Распределение задач для CodeReview

Дата и время Название Место Материалы
18 сентября
17:00–18:20
Введение в алгоритмы и структуры данных, лекция ФМЛ 239, Актовый зал видеофайлы
18 сентября
18:30–20:00
Время работы программы и циклы for , семинар ФМЛ 239, Актовый зал другие
23 сентября
17:00–18:20
Пути в графах, лекция ФМЛ 239, Актовый зал видеофайлы
25 сентября
17:00–18:20
Метод «разделяй и властвуй», лекция ФМЛ 239, Актовый зал видеофайлы
25 сентября
18:30–19:50
Сортировки. Жадность., семинар ФМЛ 239, Актовый зал другие
02 октября
17:00–18:20
Структуры данных, лекция ФМЛ 239, Актовый зал видеофайлы
02 октября
18:30–19:30
Жадности. Время ввода/вывода. Разделяй и властвуй., семинар ФМЛ 239, Актовый зал другие
09 октября
17:00–18:20
Сортировка, лекция ФМЛ 239, Актовый зал видеофайлы
09 октября
18:30–20:00
Структуры данных и разделяй и властвуй, семинар ФМЛ 239, Актовый зал другие
16 октября
17:00–18:20
Декомпозиция графов, лекция ФМЛ 239, Актовый зал видеофайлы
16 октября
18:30–20:00
Структуры данных: СНМ, дерево отрезков, семинар ФМЛ 239, Актовый зал Нет
23 октября
18:30–20:00
Задачи про точки и прямую + практика, семинар ФМЛ 239, Актовый зал другие
30 октября
18:30–19:50
dfs, лекция ФМЛ 239, Актовый зал другие
30 октября
20:00–21:20
Жадные алгоритмы, лекция ФМЛ 239, Актовый зал Нет
06 ноября
18:30–19:50
Крачтайшие пути, семинар ФМЛ 239, Актовый зал Нет
06 ноября
20:00–21:20
Жадные алгоритмы (продолжение), лекция ФМЛ 239, Актовый зал Нет
13 ноября
18:30–19:50
Динамическое программирование, лекция ФМЛ 239, Актовый зал Нет
13 ноября
20:00–21:20
Динамическое программирование (продолжение), лекция ФМЛ 239, Актовый зал Нет
20 ноября
18:30–21:00
Динамика. Обычная и по подмножествам., семинар ФМЛ 239, Актовый зал другие
27 ноября
18:30–19:50
Динамическое программирование по подмножествам, лекция ФМЛ 239, Актовый зал Нет
27 ноября
20:00–21:20
Деревья поиска, АВЛ-деревья, лекция ФМЛ 239, Актовый зал Нет
04 декабря
18:30–20:00
Деревья поиска, неявный ключ, персистентность, семинар ФМЛ 239, Актовый зал другие
04 декабря
20:00–21:20
Splay-дерево, лекция ФМЛ 239, Актовый зал Нет
11 декабря
18:30–20:00
Корневая оптимизация, семинар ФМЛ 239, Актовый зал другие
11 декабря
20:00–21:20
Декартово дерево, задача RMQ, лекция ФМЛ 239, Актовый зал Нет