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

Первый семестр курса будет посвящён базовым идеям построения и анализа алгоритмов. Мы начнём с того, что обсудим, как оценивать сложность алгоритмов, и применим это к алгоритмам, известным нам из курса математики. Далее мы рассмотрим три основополагающих подхода к построению алгоритмов: жадные алгоритмы, разделяй и властвуй и динамическое программирование. Оставшееся время мы потратим на изучение структур данных.

Формат занятий

Занятия проводятся каждый вторник и состоят из лекции (18:30-19:50) и практики (20:00-21:20).

Формат лекций

Основной лекционный материал курса будет предложен для самостоятельного изучения в виде онлайн-курса. На лекциях мы будем обсуждать вопросы, которые возникли в связи с материалом онлайн-курса, и изучать дополнительный материал, который в онлайн-курсе отсутствует.

Онлайн-курс в этом семестре состоит из двух частей: https://stepik.org/course/217/syllabus и https://stepik.org/course/1547/syllabus.

Формат практик

Практика будет проводится в группах. На практиках будут решаться задачи и обсуждаться домашние задания. Разбиение на группы произойдет по результатам контеста на первой неделе.

Домашние задания

Будут состоять из двух типов задач:

  • Задачи на программирование будут приниматься в автоматическом режиме на системе для контестов.

  • Задачи на доказательство будет приниматься через сайт центра.

Критерии выставления оценки

Оценка будет выставляться по результатам решения домашних заданий и летучек. Летучки составляют 10% от общей оценки, теоретические домашние задания - 30%, задачи на программирование - 60%.

  • За 85% решённых задач выставляется оценка отлично,

  • за 75% - хорошо,

  • за 60% - зачёт.

Список литературы

Дата и время Название Место Материалы
11 сентября
18:30–19:50
Введение, лекция Таймс, ауд. с чёрными досками Нет
11 сентября
20:00–21:20
Семинар 1, семинар Таймс, ауд. с чёрными досками файлы
18 сентября
18:30–19:50
Жадные алгоритмы, лекция Таймс, ауд. с чёрными досками Нет
18 сентября
20:00–21:20
Семинар 2, семинар Таймс, ауд. с чёрными досками Нет
25 сентября
18:30–19:50
Разделяй и властвуй, лекция Таймс, ауд. с чёрными досками Нет
25 сентября
20:00–21:20
Семинар 3, семинар Таймс, ауд. с чёрными досками Нет
02 октября
18:30–19:50
Сортировки, лекция Таймс, ауд. с чёрными досками Нет
02 октября
20:00–21:20
Семинар 4, семинар Таймс, ауд. с чёрными досками Нет
09 октября
18:30–19:50
Динамическое программирование, часть 1, лекция Таймс, ауд. с чёрными досками Нет
09 октября
20:00–21:20
Семинар 5, семинар Таймс, ауд. с чёрными досками Нет
16 октября
18:30–19:50
Динамическое программирование, часть 2, лекция Таймс, ауд. с чёрными досками Нет
16 октября
20:00–21:20
Семинар 6, семинар Таймс, ауд. с чёрными досками Нет
23 октября
18:30–19:50
Базовые структуры данных, лекция Таймс, ауд. с чёрными досками файлы
23 октября
20:00–21:20
Семинар 7, семинар Таймс, ауд. с чёрными досками Нет
30 октября
18:30–19:50
Очереди с приоритетом и системы непересекающихся множеств, лекция Таймс, ауд. с чёрными досками Нет
30 октября
20:00–21:20
Семинар 8, семинар Таймс, ауд. с чёрными досками файлы
06 ноября
18:30–19:50
Хеш-таблицы, лекция Таймс, ауд. с чёрными досками Нет
06 ноября
20:00–21:20
Семинар 9, лекция Таймс, ауд. с чёрными досками Нет
13 ноября
18:30–19:50
Деревья поиска, лекция Таймс, ауд. с чёрными досками Нет
13 ноября
20:00–21:20
Семинар 10, лекция Таймс, ауд. с чёрными досками Нет
20 ноября
18:30–19:50
Сплей-деревья, лекция Таймс, ауд. с чёрными досками Нет
20 ноября
20:00–21:20
Семинар 11, лекция Таймс, ауд. с чёрными досками файлы
27 ноября
18:30–19:50
Задачи RMQ и LCA, лекция Таймс, ауд. с чёрными досками Нет
27 ноября
20:00–21:20
Семинар 12, лекция Таймс, ауд. с чёрными досками Нет
04 декабря
18:30–19:50
Числовые алгоритмы, лекция Таймс, ауд. с чёрными досками Нет
04 декабря
20:00–21:30
Семинар 13, семинар Таймс, ауд. с чёрными досками Нет
11 декабря
18:30–19:50
Другие модели вычисления, лекция Таймс, ауд. с чёрными досками Нет
11 декабря
20:00–21:20
Семинар 14, семинар Таймс, ауд. с чёрными досками файлы