Алгоритмы и структуры данных пилотный поток 2019/2020 — различия между версиями
Debnatkh (обсуждение | вклад) |
Debnatkh (обсуждение | вклад) |
||
Строка 428: | Строка 428: | ||
| [https://drive.google.com/file/d/1COCB2MZHNmZvrkG_VEXAmkmzKb6e9F1m/view?usp=sharing бан] | | [https://drive.google.com/file/d/1COCB2MZHNmZvrkG_VEXAmkmzKb6e9F1m/view?usp=sharing бан] | ||
| | | | ||
+ | |- | ||
+ | | colspan="5" style="text-align: center; background-color:#dae8fc;" | 5 модуль | ||
|- | |- | ||
|} | |} |
Версия 14:03, 11 июня 2020
Лектор: Глеб Олегович Евстропов
План учебной дисциплины, только лучше
Важные ссылки | ||
---|---|---|
Текущая успеваемость html-версия |
Google.Classroom инвайт: hhp3okt
|
Запись на консультации |
Содержание
Формула выставления итоговой оценки
0.3 · Оконтесты + 0.25 · Oлистки + 0.15 · OКР + 0.3 · Oэкз + Oбонус
-
Оконтесты вычисляется по формуле:
Оконтесты = 10 · ( КК + ДК + БЗ ), где: ОЗ - поправка ОЗ - КК — баллы за короткие контесты
- ДК — баллы за длинные контесты (исключая бонусные задачи)
- БЗ — баллы за бонусные задачи в длинных контестах
- ОЗ — общее число задач во всех контестах (исключая бонусные задачи)
- Поправка по умолчанию равна нулю, но если отлична от нуля, то равна примерно 1/10 от общего числа задач (то есть предполагается, что сдать все задачи вовремя крайне трудно) и может быть увеличена индивидуально для каждого студента при наличии пропусков по уважительным причинам.
Виды контестов:
- Короткие контесты будут проводиться в разнообразных форматах во время сдвоенных семинаров. Если не оговорено иное, то короткий контест является личным соревнованием, состоящим из 5 задач разной сложности, требующим владеть общей сообразительностью, некоторой математической подготовкой, и, возможно, различными уже изученными алгоритмами. На коротких контестах отсутствует проверка кода, если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).
- Длинные контесты имеют продолжительность до двух недель, и состоят в основном из задач, требующих реализации алгоритмов, изученных на лекциях. Некоторые задачи являются обязательными и проходят дополнительную ручную проверку кода. Все задачи стоят 1 балл, но чтобы получить баллы за необязательные задачи, необходимо сначала сдать все обязательные.
- Олистки вычисляется по формуле:
Олистки = 10 · количество решённых задач количество обязательных задач - поправка Листки являются теоретическими домашними заданиями. Все задачи стоят одинаково, сдавать их можно во время присутственных часов, на консультациях ассистентам. Дополнительно предусматривается возможность сдать задания в электронном виде в хорошей вёрстке.
- В течение каждого модуля предполагается по одной контрольной работе. За каждую контрольную студент получает оценку от 0 до 10, которая и будет являться ОКР. Если студент пропускает по уважительной причине контрольную работу, то для него изменяется итоговая формула оценки.
- За экзамен студент получает оценку от 0 до 10, эта оценка будет являться Оэкз.
- Бонус. Эта графа определяет произвольные баллы, которые могут быть прибавлены к оценке студента за различные виды деятельности и соревнований. Например, в этой графе будут использованы некоторые короткие контесты с необычным форматом.
Итоговая оценка округляется арифметически (то есть при дробной части меньше 0.5 округление производится вниз, иначе вверх).
Лекции и семинары
2 модуль
Дата | Семинар | Листочек | Лекция |
---|---|---|---|
29 октября | Понятие асимптотического времени работы алгоритма. Сильно-, слабо- и псевдополиномиальное время работы. Обозначения O, o, Ω, ω | 64726976 | Знакомство со структурой курса и системой выставления оценок.Введение в теорию вероятностей, конечные вероятностные пространства, события, независимость событий, условная вероятность |
31 октября | Совместное решение задач по теории вероятностей | 652e676f | Продолжение введения в теорию вероятностей, понятие математического ожидания и его базовые свойства |
5 ноября | Совместное решение задач на мат. ожидание | 6f676c65 | Модель вычислений, описание RAM-модели. Три основных способа доказательства корректности на примере квадратичных сортировок. |
7 ноября | Короткий контест №1 | ||
12 ноября | Разговор про тестирование | не было | Сортировки сравнения, схема доказательства времени работы по индукции, невозможность сортировки быстрее n log n. |
14 ноября | Сортировки и порядковые статистики | 2e636f6d | Сортировки, использующие значения элементов. Сортировка подсчётом, поразрядная сортировка, корзинная сортировка.Сортировка случайных чисел за линейное время. Модель вычислений во внешней памяти. Сортировка сравнениями во внешней памяти |
19 ноября | Сортировки и порядковые статистики (2) | 2f6f7065 | Элементарные структуры данных, двоичная куча. |
21 ноября | Короткий контест №2 | ||
26 ноября | Разбор домашнего задания №1 | k-ичная куча, амортизационный анализ методом кредитов и методом потенциалов. Словарь с доступом по значению через сливаемые массивы,очередь с минимумом, дек с минимумом, динамический массив | |
28 ноября | Непростые задачи на простые структуры | 6e3f6964 | Биномиальные кучи и фибоначчиевы кучи |
3 декабря | Задачи на кучи | 3d315935 | Хеширование, вводная лекция. Полиномиальный хеш. |
5 декабря | Контрольная работа №1 | ||
10 декабря | Разбор домашнего задания №2 | Хеш-таблицы, стратегии масштабирования, фильтры Блума. | |
12 декабря | Хеши и хеш-таблицы | 42756a31 | Бинарные деревья поиска. Сбалансированные деревья. Декартово дерево. |
17 декабря | Деревья поиска | 53643279 | 2-3 дерево, B-дерево |
19 декабря | Бонусный контест №1 |
3 модуль
Дата | Семинар | Листочек | Лекция |
---|---|---|---|
14 января | Самобалансирующиеся деревья Тарьяна-Слейтора | 374d6b47 | Запросы на отрезках, префиксные суммы, разреженные таблицы, дерево отрезков, групповые модификации |
16 января | Запросы на отрезках | 4f503751 | Задачи LCA и LA, метод четырёх русских |
21 января | Короткий контест №3 | ||
23 января | Двумерные запросы на отрезках и подобное | 34597662 | Понятие персистентной структуры данных, персистентное декартово дерево |
28 января | Персистентные структуры данных. | 55493345 | Перебор и динамическое программирование с примерами. Подотрезки, подмножества, поддеревья, ацкиличные графы, meet-in-the-middle |
30 января | Динамическое программирование. | 57426b4b | Классические приёмы задач динамического программирования. Замена параметра, битовые операции, эффективное использование памяти |
4 февраля | Занятий не будет | ||
6 февраля | Продвинутое динамическое программирование и перебор | 56522020 | Эффективный перебор, асимптотические и неасимптотические оптимизации. |
11 февраля | Ещё немного переборов и динамического программирования | тык | Эффективный перебор в играх с нулевой суммой. Альфа-бета отсечение |
13 февраля | Разбор домашнего задания №4 | Теория графов, основные задачи на обход в глубину. | |
18 февраля | Контрольная работа №2 | ||
20 февраля | Задачи на графы | тыц | Мосты и точки сочленения, компоненты рёберной и вершинной двусвязности. |
25 февраля | Задачи на графы №2 | тук | Кратчайшие пути в графах |
27 февраля | Разбор домашнего задания №5 | Минимальный остов. Прим, Краскал, Борувка, критерии оптимальности | |
3 марта | Короткий контест №4 | ||
5 марта | Задачи на кратчайшие пути и остовы | тыщ | Система непересекающихся множеств. Оценки log* и обратная функция Аккермана |
10 марта | Разговор про оптимизации кода | не было | Графы во внешней памяти. Задача о ранжировании списка |
12 марта | Разбор домашнего задания №6 | Задача о максимальном паросочетании в двудольных графах. | |
17 марта | Короткий контест №5 | ||
19 марта | Бонсуный контест №2 |
4 модуль
Дата | Семинар | Листочек | Лекция |
---|---|---|---|
7 апреля | Разбор домашнего задания №7 | Введение в потоки, две постановки задачи и декомпозиция | |
9 апреля | Короткий контест с подвохом №6 | ||
14 апреля | Задачи на паросочетания. | тыщ | Теорема Форда-Фалкерсона, приёма масштабирования, Эдмондс-Карп и Диниц. |
16 апреля | Задачи на потоки. | тыщ | Диниц+масштабирование, первая теорема Карзанова, паросочетание за O(m sqrt n), стоимостные потоки. записи доски |
21 апреля | Сложные задачи на потоки. | тыщ | Корректность жадного алгоритма стоимостного потока + задача о назначениях. Постановка основных строковых задач. |
23 марта | Короткий контест №7 | ||
28 апреля | Ещё немного задач на потоки и стоимостные потоки. | тыщ | Задача поиска шаблона в тексте, префикс-функция и z-функция. Автомат префикс-функции. |
30 апреля | Задачи на строковые алгоритмы. | тыщ | Алгоритм Бойера-Мура. Бор, Ахо-Корасик. |
7 мая | Короткий контест №8 | ||
12 мая | Задачи на Ахо-Корасик | тыщ | Сжатый бор, алгоритм Укконена построения суффиксного дерева. |
14 мая | Задачи на Укконена + определения и примеры из автоматов и языков | тыщ | Выразительная эквивалетность РВ, ДКА, НКА, eps-НКА, лемма о накачке, иерархия языков |
19 мая | Разбор домашнего задания №8 | Минимизация ДКА | |
21 мая | Короткий контест №9 | ||
26 мая | Задачи на автоматы, языки и машину Тьюринга | тыщ | Проблема P ? NP, теорема Кука-Левина, NP-полнота некоторых задач. |
28 мая | Задачи на строковые алгоритмы и автоматы | тыщ | Простое ТЧ, расширенный Евклид, факторизация, линейное решето, дискретное логарифмирование |
2 июня | Задачи на сводимости и NP-полноту | тыщ | Ро-метод Полларда, тест на простоту Миллера-Рабина |
4 июня | Бонусный контест №3 | ||
9 июня | Задачи на ТЧ | тыц | Шифрование с открытым ключом, схема RSA, цифровая подпись. |
5 модуль
Дата | Семинар | Листочек | Лекция |
---|---|---|---|
1 сентября |
Листки
Устно листки сдаются преподавателям и ассистентам в присутственные часы. Таблица для записи на консультации sheets.google.com
Листки в электронном виде отправляются в систему Google Classroom (инвайт: hhp3okt
). Принимается только TeX — нельзя отправлять фотографии записей от руки (за исключением случая, когда к теху вы прикрепляете пояснительную картинку от руки); решения, написанные в MS Word и подобных программах и т.д. Решения отправляются ровно один раз — нельзя отправить что-то, а потом через неделю прислать исправленную версию (небольшие исправления и уточнения разрешаются, если сделаны в течение нескольких часов после отправки листка и строго до дедлайна).
Общие предположения, которыми можно пользоваться в задачах
- Если в задаче говорится про запросы, то по умолчанию online
- Если не оговорено иное, можно использовать столько же памяти, сколько времени
- Если не оговорено иное, то можно ожидаемое амортизированное время с хешами
Список листков
№ | Дедлайн | Темы | Листок | Пояснения |
---|---|---|---|---|
2 модуль | ||||
1 | Полночь с 25 на 26 ноября | Вероятности и математическое ожидание | тык | |
2 | Полночь с 9 на 10 декабря | Сортировки, простые структуры данных и кучи | тук |
|
3 | Полночь с 21 на 22 декабря | Хеши и деревья поиска | тыц |
|
3 модуль | ||||
4 | Полночь с 12 на 13 февраля | Структуры данных | бац | |
5 | Полночь с 26 на 27 февраля | Динамическое программирование, перебор и метод meet-in-the-middle | бах |
|
6 | Полночь с 11 на 12 марта | Обходы графов и кратчайшие расстояния | бам |
|
7 | Полночь с 30 на 31 марта | Остовы, графы и СНМ | бум | |
4 модуль | ||||
8 | Полночь с 18 на 19 мая | Потоки и паросочетания | бац |
|
9 | Полночь с 27 на 28 мая | Строки и регулярные языки | бах |
|
10 | Полночь с 10 на 11 июня | Классы сложности и теоретико-числовые алгоритмы | бан | |
5 модуль |
Короткие контесты
Если не оговорено иное, то задачи можно дорешивать вплоть до окончания текущего отчётного периода (то есть почти до экзамена), получая за каждую сданную задачу 0.5 балла вместо 1 балла (за сдачу во время контеста).
№ | Дата | Ссылка | Дорешивать |
---|---|---|---|
2 модуль | |||
1 | 7 ноября 2019 | 15290 | полночь с 27 на 28 декабря |
2 | 21 ноября 2019 | 15816 | полночь с 27 на 28 декабря |
3 модуль | |||
3 | 21 января 2020 | 16928 | полночь с 21 на 22 июня |
4 | 3 марта 2020 | 17435 | полночь с 21 на 22 июня |
5 | 17 марта 2020 | 17611 | полночь с 21 на 22 июня |
4 модуль | |||
6 | 9 апреля 2020 | 17927 | полночь с 21 на 22 июня |
7 | 23 апреля 2020 | 18158 | полночь с 21 на 22 июня |
8 | 7 мая 2020 | 18262 | полночь с 21 на 22 июня |
9 | 21 мая 2020 | 18478 | полночь с 21 на 22 июня |
Длинные контесты
Дедлайн | Темы | Ссылка |
---|---|---|
2 модуль | ||
полночь с 9 на 10 декабря | Cортировки, порядковые статистики, простые структуры данных | 15815 |
полночь с 22 на 23 декабря | Хеши и деревья поиска | 16271 |
3 модуль | ||
Полночь с 17 на 18 февраля | Структуры данных, запросы на отрезках | 17022 |
Полночь с 31 марта на 1 апреля | Динамика, перебор, графы | 17506 |
4 модуль | ||
Полночь с 24 на 25 мая | Графы, паросочетания, потоки | 18261 |
Полночь с 14 на 15 июня | Строки, языки, ТЧ | 18261 |
Экзамены
Правила экзамена
- Состоит из письменного теста и устной части.
- За тест ставится оценка от 1 до 8.
- На устную часть приглашаются те, кто написал тест на 4 и выше.
- У тех, кто идёт на устную часть, оценка понижается на 1.
- На устной части вы последовательно увеличиваете свою оценку на 1, отвечая на теоретические вопросы и задачи.
- За экзамен можно два раза перетянуть билет.
- Три неправильных подхода к снаряду приводят к форсированному перетягиванию билета в счёт одной попытки.
- Если попытки кончились, то экзамен для студента завершается.
Дата и время
Модуль | Дата | Время, аудитория | Программа | |
---|---|---|---|---|
2 модуль | 28 декабря (суббота) | Письменная часть | 11:00-12:30, ауд. R401 | тык |
Устная часть | 14:00-17:00, ауд. R401 | |||
3-4 модуль | 23 июня | Письменная часть | TBA | TBA |
Ссылки на материалы
Основные источники:
- Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы: Построение и анализ, [2013, 3 издание]
- neerc.ifmo.ru
Изученные темы:
2 модуль
- Виды задач, сильно-, слабо-, и псевдополиномиальность: https://www.epfl.ch/labs/disopt/wp-content/uploads/2018/09/algorithms.pdf
- Ликбез по теории вероятностей
- Кормен, приложение В "Комбинаторика и теория вероятности", c 1235
- Памятка по основным определениям
- Индикаторная случайная величина: Кормен, раздел 5.2, с 144.
- Методы решения рекуррентных соотношений: Кормен, гл. 4, разделы 4.3-4.5 (со стр. 108)
- Модель вычислений во внешней памяти, сортировка слиянием во внешней памяти: https://neerc.ifmo.ru/wiki/index.php?title=Алгоритмы_во_внешней_памяти._Базовые_конструкции
- Двоичная куча, сортировки, порядковые статистики
- Кормен, часть 2 "Сортировка и порядковая статистика" с. 173
- https://neerc.ifmo.ru/wiki/index.php?title=Двоичная_куча
- Невозможность сортировки быстрее n log n: Кормен, начало главы "Сортировка за линейное время", стр. 220
- Фибоначчиевы кучи
- Кормен, гл. 19, с 542
- https://neerc.ifmo.ru/wiki/index.php?title=Фибоначчиева_куча
- Биномиальные кучи: https://neerc.ifmo.ru/wiki/index.php?title=Биномиальная_куча
- Хеширование и хеш-таблицы
- Кормен, гл. 11, с. 285
- http://neerc.ifmo.ru/wiki/index.php?title=Разрешение_коллизий
- Фильтр Блума: http://neerc.ifmo.ru/wiki/index.php?title=Фильтр_Блума
- Амортизационный анализ: Кормен, гл. 17, с 487
- Бинарные деревья поиска: Кормен, гл. 12, c 319
- Декартово дерево
- B-деревья
- Кормен, гл.18, стр. 521
- http://neerc.ifmo.ru/wiki/index.php?title=B-дерево
- 2-3-деревья: http://neerc.ifmo.ru/wiki/index.php?title=2-3_дерево
- Стек и очередь с минимумом: https://e-maxx.ru/algo/stacks_for_minima
- Дек на 3 стеках: https://neerc.ifmo.ru/wiki/index.php?title=Дек
FAQ
Q: А когда будет FAQ?
A: Уже готово, см. вики-страницу курса
Преподаватели и ассистенты
Преподаватель | Подгруппа | Присутственные часы | Контакты |
---|---|---|---|
Преподаватели | |||
Глеб Евстропов | 191-1 | ||
Станислав Артюхин | 191-2 | ||
Григорий Резников | 193-1 | ||
Иван Смирнов | 193-2 | ||
Святослав Фельдшеров | 195-1 | ||
Никита Сендерович | 195-2 | ||
Ассистенты | |||
Филипп Грибов | вторник, 4 пара (13:30 - 15:10) | @grphil | |
Иван Сафонов | понедельник, 2 пара (10:30 - 11:50) | @isaf27 | |
Максим Деб Натх | среда, 5.5 пара (15:40 - 17:00) | @debnatkh | |
Александр Курилкин | среда, (18:00 - ?) | @wrg0ababd | |
Никита Морозов | пятница, 5 пара (15:10 - 16:30) | @madn_boi |