Алгоритмы и структуры данных 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)
Оценка за курс
Оценка за экзамены и
Оценки за экзамен после первого модуля («коллоквиум») и за экзамен после второго модуля — числа от 3 до 10.
Оценка за практику
В этой части учитываются баллы за контесты и теоретические домашние задания. обозначает долю баллов от суммы баллов обязательных задач.
| 10 | 1.2 |
|---|---|
| 9 | 1.0 |
| 8 | 0.95 |
| 7 | 0.88 |
| 6 | 0.8 |
| 5 | 0.72 |
| 4 | 0.65 |
Общая оценка за курс
В этом семестре ставится одна формальная оценка — в конце семестра.
Блокирующие элементы оценки:
- Оба экзамена должны быть сданы: , .
- По практике должен быть получен зачёт: .
- В контестах должны быть сданы все задачи, помеченные как «must have».
Если блок пройден, оценка за курс вычисляется так: , где — округление к ближайшему целому.
Словами то же самое: при прохождении блока оценка за курс получается округлением к ближайшему целому средневзвешенного трёх оценок:
- оценки за практику с коэффициентом 0.6;
- оценки за экзамен после первого модуля («коллоквиум») с коэффициентом 0.2.
- оценки за экзамен после второго модуля с коэффициентом 0.2.
Информация
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 ноября: проталкивание предпотока: конспект, код с лекции
- 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 |
