Алгоритмы и структуры данных 1

Лектор: Глеб Олегович Евстропов

Предполагаемая программа на 4 модуля

Текущая успеваемость

Формула выставления итоговой оценки

В первый отчетный период, состоящий из 2 и 3 модулей 2017-18 учебного года будет использоваться следующая формула определения оценки:

0.3 * Контесты + 0.25 * Листочки + 0.15 * Контрольные + 0.3 * Экзамен + Бонус, округлённое до ближайшего целого.

• Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).

• Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные.

• Итоговая оценка за раздел "Контесты" определяется как 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка). Поправка по умолчанию равна нулю, но если отлична от нуля, то равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.

• Листочки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно как во время семинара, когда листочек был выдан, так и во время присутственных часов. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке. Формула оценки за данный раздел аналогична предыдущей: 10 * (баллы за короткие контесты + баллы поделить за длинные контесты) / (общее число задач - поправка).

• В течение первого отчётного периода предполагается две контрольные работы (по одной в каждом модуле). За каждую контрольную студент получает оценку от 0 до 10, итоговая оценка за данный раздел ставится как среднее арифметическое этих двух, или определяется по одной оценке, если вторую контрольную студент пропустил по уважительной причине. Если студент пропускает по уважительной причине обе контрольные работы, то для него изменяется итоговая формула оценки.

• За экзамен студент получает оценку от 0 до 10.

• Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.

Сроки выполнения заданий

Тип задания	Тема	Дата выдачи	Сроки выполнения до (включительно)	материалы
Листочек	Введение в теорвер и анализ алгоритмов	8 ноября	21 ноября	клац
Листочек	Упорядоченные данные	22 ноября	5 декабря	клац
Листочек	Кучи, амортизационный анализ	30 ноября	13 декабря	клац
Листочек	Хеши	14 декабря	28 декабря	клац
Листочек	Деревья поиска	11 января	25 января	клац
Листочек	Запросы на отрезках	24 января	7 января	клац
Листочек	Различные структуры	31 января	14 января	клац
Контест	Короткий контест 1	9 ноября	день до экзамена (дорешка)
Контест	Короткий контест 2	23 ноября	день до экзамена (дорешка)
Контест	Необычный контест 1	20 декабря	только на паре
Контест	Длинный контест 1	30 ноября	25 декабря
Контест	Короткий контест 3	18 января	день до экзамена (дорешка)
Контест	Короткий контест 4	1 февраля	день до экзамена (дорешка)
Контест	Длинный контест 2	1 февраля	26 февраля

Лекции

Номер	Дата лекции	Темы
1	1 ноября	Знакомство со структурой курса и системой выставления оценок. Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность.
2	2 ноября	Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства.
3	8 ноября	Краткое введение в понятие RAM модели. Методы доказательства корректности алгоритма по индукции, по инварианту и от противного на примере квадратичных сортировок. Оценка времени работы методом прямого учёта.
4	15 ноября	Эффективные алгоритмы сортировки сравнениями: сортировка слиянием, быстрая сортировка. Оценка снизу на сложность сортировки сравнениями. Линейный алгоритм поиска порядковой статистики.
5	16 ноября	Метод бинарного поиска. Алгоритмы сортировки, обращающиеся к непосредственным значениям элементов: сортировка подсчётом, цифровая сортировка, корзинная сортировка. Сортировка случайных данных за линейное время с помощью алгоритма корзинной сортировки.
6	22 ноября	Линейные структуры данных: односвязный и двусвязный списки, стек, очередь, дек. Двоичные пирамиды.
7	29 ноября	k-ичные пирамиды, амортизационный анализ методом кредитов и методом потенциалов. Пример амортизационного анализа при реализации очереди через два стека и дека через три стека.
8	30 ноября	Биномиальный и фибоначчиевы пирамиды.
9	6 декабря	Завершаем доказательство оценки времени работы фибоначчиевой пирамиды. Задача хеширования, свойства идеальной хеш-функции.
10	13 декабря	Хеш-таблицы с закрытой и открытой адресацией. Методы сканирования хеш-таблиц с открытой адресацией. Удаление из хеш-таблицы с открытой адресацией. Стратегии масштабирования хеш-таблиц. Совершенное хеширование.
11	10 января	Бинарные деревья поиска, декартово дерево
12	11 января	Декартово дерево по неявному ключу. Задачи на отрезках, префиксные суммы и разреженные таблицы. Дерево отрезков, групповые модификации.
13	17 января	Многомерные деревья отрезков. Задачи LCA и LA, двоичные подъёмы, преобразование LCA к RMQ и наоборот, алгоритм Фарака-Колтона и Бендера
14	24 января	Задача LCA за O(n log n) \ O(1), понятие персистентной структуры данных, виды персистентности. Персистентные стек, массив и дерево отрезков.
15	25 января	Персистентные деревья поиска и персистентные деревья с неявным ключом. Примеры решаемых с помощью этих структур данных задач. Простые алгоритмы сборки мусора.

Семинары

Дата	Материалы	Тема
1 ноября	клац	Понятие асимптотического времени работы алгоритма. Сильно, слабо и псевдополиномиальное время работы. Обозначения O, o, Ω, ω
2 ноябр	клац	Совместное решение задач по теории вероятностей.
8 ноября	клац	Теоретическое домашнее задание по теме "Вероятности и математическое ожидание", приём задач.
9 ноября	сурс	Первый короткий контест.
15 ноября	None	Обсуждение методов тестирования программ.
16 ноября	клац	Совместное решение задач на алгоритмы сортировки и поиска порядковой статистики.
22 ноября	клац	Теоретическое домашнее задание по теме "Упорядоченные данные, элементарные стурктуры данных", приём задач.
23 ноября	сурс	Второй короткий контест.
29 ноября	клац	Разбор задач первого теоретического домашнего задания. Совместное решение задач на элементарные структуры данных и двоичные кучи.
30 ноября	клац	Теоретическое домашнее задание по теме "Кучи, амортизационный анализ", приём задач.
6 декабря	клац	Подготовка к контрольной, совместное решение задач на различные темы.
7 декабря	None	Контрольная работа за текущий модуль на две пары.
13 декабря	None	Разбор второго теоретического домашнего задания и контрольной работы. Приём апелляций по контрольной работе.
14 декабря	клац	Хеши
20 декабря	сурс	Бонусный контест на две пары
10 января	None	Разбор третьего домашнего задания и задач первого длинного контеста.
11 января	клац	Разбор четвёртого домашнего задания. Приём задач листочка по теме "Деревья поиска"
17 января	клац	Совместное решение задач на тему "Деревья отрезков"
18 января	сурс	Третий короткий контест
24 января	клац	Приём домашнего задания по теме "запросы на отрезках и связанные задачи"
25 января	клац	Разбор домашнего задания по теме "Деревья поиска", совместное решение задач на персистентные деревья отрезков
31 января	клац	Приём домашнего задания по теме "Последнее ДЗ по структурам данных, задачи на разные темы."
1 февраля	сурс	Короткий контест 4

Рекомендуемая литература

1. Кормен, Лейзерсон, Ривест, Штайн. Алгоритмы: построение и анализ
2. Дасгупта, Пападимитриу, Вазирани. Алгоритмы
3. Корте, Фиген. Комбинаторная оптимизация. Теория и алгоритмы

Преподаватели и ассистенты

Преподаватель	Подгруппа	Присутственные часы
Глеб Евстропов	171-1
Станислав Артюхин	171-2
Иван Смирнов	173-1
Артем Жук	173-2
Данила Кутенин		Вторник, 12.10-13.30 + офис Яндекса по договоренности
Валентин Бирюков		Вторник, 12.10-13.30 + офис Яндекса по договоренности
Глеб Третьяков		Вторник, с 13:40 до 15:00 в аудитории 503

Листики

Все листки на Яндекс.Диске