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

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

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

• (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 октября: Алгоритм Укконена, его реализация и доказательство; потоки
• 15 октября: Потоки: алгоритмы Форда-Фалкерсона и Эдмондса-Карпа
• 5 ноября: Потоки: алгоритм Диница, теоремы Карзанова
• 12 ноября: Глобальный разрез: алгоритм Каргера-Штейна, поток минимальной стоимости
• 19 ноября: Циркуляция минимальной стоимости, паросочетания
• [доп] 25 ноября: проталкивание предпотока: конспект, код с лекции
• 26 ноября: паросочетания-2
• [доп] 2 декабря: хеширование кукушки, совершенное хеширование (двухуровневая и графовая схемы), суффиксный массив за O(n) (алгоритм Карккайнена-Сандерса) материалы лекции
• 3 декабря: игры на графах
• [доп] 9 декабря: количество простых до n, материалы лекции
• 10 декабря: универсальное хеширование, фильтр Блума, паросочетания в недвудольных графах

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

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

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

Тема	Условия	Результаты	Теордз
Теория чисел	№1	№1	№1
Линейная алгебра	№2	№2	№2
FFT и длинная арифметика	№3	№3	№3
Базовые алгоритмы на строках	№4	№4	№4
Суффиксный массив и хеши	№5	№5	№5
Бор, Ахо-Корасик и суфдерево	№6	№6	№6
Укконен и потоки	—	—	№7
Потоки и разрезы	№7	№7	№8
Быстрые потоки	№8	№8	№9
Потоки и разрезы	№9	№9	№10
Паросочетания	№10	№10	№11
Паросочетания-2	№11	№11	№12
Игры на графах	№12	№12	№13

ACM

• https://vk.com/au_acm
• https://codeforces.com/group/QG4ATt59SL