Алгоритмы и структуры данных 2MIT осень 2020

Содержание

1 Преподаватели
2 Оценка за курс
3 Информация
4 Лекции
5 Домашние задания
6 ACM

Преподаватели

Лектор: Пётр Смирнов

(1) Ютман Михаил (myutman+hsealgo2@gmail.com, telegram:@hey_boris)
(2) Степанов Всеволод (tehnar5@gmail.com, telegram:@Tehnar5)
(3) Олемская Александра (alexandra.olemskaya@gmail.com, telegram:@SiERic)
(4) Сурков Максим (surkovmax007@mail.ru, maximsurkov980@gmail.com, telegram:@maximumSHOOT)

Оценка за курс

Оценка за экзамены $s_{e,1}$ и $s_{e,2}$

Оценки за экзамен после первого модуля («коллоквиум») $s_{e,1}$ и за экзамен после второго модуля $s_{e,2}$ — числа от 3 до 10.

Оценки за коллоквиум

Оценка за практику $s_{p}$

В этой части учитываются баллы за контесты и теоретические домашние задания. $r$ обозначает долю баллов от суммы баллов обязательных задач.

$s_{p}$	$r\geqslant \ldots$
10	1.2
9	1.0
8	0.95
7	0.88
6	0.8
5	0.72
4	0.65

Общая оценка за курс

В этом семестре ставится одна формальная оценка — в конце семестра.

Блокирующие элементы оценки:

Оба экзамена должны быть сданы: $s_{e,1}\geqslant 4$ , $s_{e,2}\geqslant 4$ .
По практике должен быть получен зачёт: $s_{p}\geqslant 4$ .
В контестах должны быть сданы все задачи, помеченные как «must have».

Если блок пройден, оценка за курс вычисляется так: $s=\lfloor 0.6\cdot s_{p}+0.2\cdot s_{e,1}+0.2\cdot s_{e,2}\rceil$ , где $\lfloor \cdot \rceil$ --- округление к ближайшему целому.

Словами то же самое: при прохождении блока оценка за курс получается округлением к ближайшему целому средневзвешенного трёх оценок:

оценки за практику с коэффициентом 0.6;
оценки за экзамен после первого модуля («коллоквиум») с коэффициентом 0.2.
оценки за экзамен после второго модуля с коэффициентом 0.2.

Информация

Деление на группы, осень 2020

Результаты практик

svn-репозиторий для сдачи дз (логин тот же, что и в прошлом году)

Тестирующая система

Дедлайны

Практика, контест: дедлайн в субботу в 23:59

Теория в tex, дедлайн в субботу в 23:59

Исправления и только исправления (не новые задачи!) можно отправлять до 11:10 вторника.

Отношения к дедлайнам: их нельзя продалбывать. Еcли заболели/внезапная контрольная/опаздываете -- всегда предупредите. Если у вас проблемы, и вам жизненно необходим именно на этой неделе разовый сдвиг дедлайна, не постесняйтесь попросить об этом (заранее, не за полчаса до).

Все домашние задания отправляем в svn

Лекции

Вопросы к экзамену за первый модуль

Конспект

«Доски» с лекций:

1 сентября: теория чисел
3 сентября: линейная алгебра
10 сентября: FFT и длинная арифметика
17 сентября: Деление, метод четырёх русских и строки (префикс-функция)
22 сентября: Z-функция, полиномиальный хеш [оффлайн]
24 сентября: Полиномиальный хеш, алгоритм Бойера-Мура, суффиксный массив
1 октября: Бинпоиск в суффиксном массиве, бор, алгоритм Ахо-Корасик
10 октября: Алгоритм Укконена, его реализация и доказательство; потоки
17 октября: Потоки: алгоритмы Форда-Фалкерсона и Эдмондса-Карпа
5 ноября: Потоки: алгоритм Диница, теоремы Карзанова
12 ноября: Глобальный разрез: алгоритм Каргера-Штейна, поток минимальной стоимости
19 ноября: Циркуляция минимальной стоимости, паросочетания
[доп] 25 ноября: проталкивание предпотока, код с лекции

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

Результаты контестов

В pdf с домашним заданием также лежат задачи практики и их разбор. Как вы догадываетесь, ими полезно пользоваться при решении дз. Конспект прочесть тоже полезно.
Домашнее задание разбирается в начале практики. В этот момент удобно спросить о всём, что не получилось. И про контест тоже. После разбора в pdf с дз появляется его разбор.