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

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

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

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

Литература:

  • S. Dasgupta, C. Papadimitriou, U. Vazirani. Algorithms. McGraw-Hill. 2006.
  • А. Х. Шень. Программирование: теоремы и задачи. Издательство МЦНМО. 2007.
  • М. А. Бабенко, М. В. Левин. Введение в теорию алгоритмов и структур данных. Издательство МЦНМО. 2012.
  • Т. Кормен, Ч. Лейзерсон, И. Ривест, К. Штайн. Алгоритмы: построение и анализ.
Дата и время Название Место Материалы
11 сентября
18:30–19:50
Введение, лекция ФМЛ 239, Актовый зал Нет
11 сентября
20:00–21:20
Простые задачки, семинар ФМЛ 239, Актовый зал Нет
18 сентября
18:30–19:50
Числовые алгоритмы, лекция ФМЛ 239, Актовый зал Нет
18 сентября
20:00–21:20
Теория чисел, семинар ФМЛ 239, Актовый зал Нет
02 октября
18:30–19:50
Криптосистема RSA, лекция ФМЛ 239, Актовый зал Нет
02 октября
20:00–21:20
Элементарные структуры данных, семинар ФМЛ 239, Актовый зал другие
09 октября
18:30–19:50
Элементарные структуры данных, лекция ФМЛ 239, Актовый зал Нет
09 октября
20:00–21:20
Задачи на массивах и окружностях, семинар ФМЛ 239, Актовый зал другие
16 октября
18:30–19:50
Метод «разделяй и властвуй», лекция ФМЛ 239, Актовый зал Нет
16 октября
20:00–21:20
Алгоритмы сортировки, лекция ФМЛ 239, Актовый зал Нет
23 октября
18:30–19:50
Элементарные структуры данных (конец), семинар ФМЛ 239, Актовый зал другие
23 октября
20:00–21:20
Разделяй и властвуй, семинар ФМЛ 239, Актовый зал другие
30 октября
18:30–19:50
Алгоритмы сортировки (продолжение), лекция ФМЛ 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–19:50
Пути в графах (продолжение), лекция ФМЛ 239, Актовый зал Нет
20 ноября
20:00–21:20
Еще про графы, семинар ФМЛ 239, Актовый зал Нет
27 ноября
18:30–19:50
Система непересекающихся множеств, лекция ФМЛ 239, Актовый зал Нет
27 ноября
20:00–21:20
Задачи на Жадность, семинар ФМЛ 239, Актовый зал Нет
11 декабря
18:30–19:50
Жадные алгоритмы, лекция ФМЛ 239, Актовый зал Нет
11 декабря
20:00–21:20
Жадность и графы. Окончание, семинар ФМЛ 239, Актовый зал Нет