Алгоритмы и структуры данных на ПМИ (пилотный поток)

Лектор: Глеб Евстропов

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

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

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

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

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

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

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

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

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

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

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

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

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

Тип задания	Тема	Дата выдачи	Сроки выполнения до (включительно)
Теоретические задачи	Введение в теорвер и анализ алгоритмов	11 ноября 2016	25 ноября 2016
Короткий контест	Разное	16 ноября 2016	25 марта 2017 (дорешивание)

Лекции

• 2 ноября. Структура курса, его концепция и задачи. Введение в теорию вероятностей, понятие вероятностного пространства для случая конечного множества элементарных исходов. Условная вероятность, полная группа события. Понятие геометрической вероятности. Заметки.

• 9 ноября. Продолжение введения в теорию вероятностей. Понятие случайной величины и математического ожидания в случае конечно множества элементарных исходов. Индикаторные случайные величины. Математическое ожидание случайной величины и его линейность. Неравенства Маркова и Чебышёва. Примеры вероятностного анализа простых случайных структур.

• 11 Ноября. Методы доказательства корректности алгоритмов на примере квадратичных сортировок. Тривиальные методы оценки времени работы. Индуктивный метод доказательства рекуррентных оценок сложности. Сортировка слиянием и быстрая сортировка.

Семинары

• 2 ноября 2016. Некоторые необходимые обозначения и термины для описания времени работы (и других используемых ресурсов) алгоритма. Совместное решение задач.

• 9 ноября 2016. Совместное решение комбинаторных и геометрических задач по теории вероятностей.

• 11 ноября 2016. Приём задач первого теоретического домашнего задания, тема: введение в теорию вероятностей, анализ алгоритмов.

• 16 ноября 2016. Короткий личный контест.

Длинные контесты

Сортировки, порядковые статистики, элементарные структуры

Ссылка на контест: https://contest.yandex.ru/contest/3478/problems/. Старт: 22 ноября в 21:00.

Контест идет 2 недели + 3 часа, после чего можно будет сдавать задачи еще 2 недели, но с коэффициентом 0.5. Это будет отражено в баллах за задачу в контесте.

По первым двум задачам нужно пройти ревью. Это необходимое условие для получения баллов за остальные задачи. Ревью проводится в системе Anytask. Перед отправкой задачи на ревью обязательно укажите в настройках свой логин в контесте (тот, который вы зарегистрировали сами, а не тот, который был выдан в 1-ом модуле), если вы еще этого не сделали.

В задачах с ревью используется другая схема тестирования. Компилируется 2 варианта вашего решения --- с включенными санитайзерами и без. На маленьких тестах будет запускаться решение с санитайзерами.

Полная строка компиляции (с санитайзерами): clang++ -fsanitize=address,undefined -x c++ -std=c++14 -O2 -Wall -Werror

Обратите внимание на -Werror --- компилятор не должен выдавать никаких предупреждений при компиляции. Стандарт С++14.

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

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

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

Преподаватель	Подгруппа	Присутственные часы
Глеб Евстропов	161-1	Среда, 15:10 - 16:30, ауд. 322
Павел Мельничук	161-2
Станислав Артюхин	163-1
Алексей Панов	163-2
Александр Тиунов		Среда, 15:00 - 16:30
Александр Зойкин		Среда, 14:20-15:40

Листики

https://yadi.sk/d/uN86f35WyeryR