Алгоритмы и структуры данных 1 основной поток 2019/202 — различия между версиями
.obj (обсуждение | вклад) (→Экзамен) |
.obj (обсуждение | вклад) (→Примерный список тем) |
||
Строка 147: | Строка 147: | ||
==Примерный список тем== | ==Примерный список тем== | ||
− | # Алгоритмы и их сложность, асимптотический анализ (''О'' большое и малое). | + | # Алгоритмы и их сложность, асимптотический анализ (''О'' большое и малое). [DPV 0, KT 2, CLRS 2–3] |
− | # Простейшие структуры данных: стек, очередь, дэк, их реализация на списках и массивах. | + | # Простейшие структуры данных: стек, очередь, дэк, их реализация на списках и массивах. [CLRS 10] |
− | # Рекурсивные алгоритмы и рекуррентные соотношения. | + | # Рекурсивные алгоритмы и рекуррентные соотношения. [DPV 2, E 1–2, KT 5, CLRS 4] |
− | # Динамическое программирование. | + | # Динамическое программирование. [DPV 6, E 3, KT 6, CLRS 15] |
− | # Сортировки (вставкой, слиянием и др.). | + | # Сортировки (вставкой, слиянием и др.). [DPV 2, KT 5, CLRS 4–8] |
− | # Графы. Способы представления графов. Обход в глубину и в ширину, поиск компонент связности, топологическая сортировка. | + | # Графы. Способы представления графов. Обход в глубину и в ширину, поиск компонент связности, топологическая сортировка. [DPV 3–4, E 5–6, KT 3, CLRS 22] |
− | # Алгоритмы Флойда – Уоршелла и Беллмана – Форда. | + | # Алгоритмы Флойда – Уоршелла и Беллмана – Форда. [DPV 4, E 8–9, KT 6, CLRS 24–25] |
− | # Разделяй и властвуй. | + | # Разделяй и властвуй. [DPV 2, KT 5, CLRS 4] |
− | # Структуры данных. Амортизационный анализ. | + | # Структуры данных. Амортизационный анализ. [CLRS 17] |
− | # Хеш-функции и хеш-таблицы. Разрешение коллизий при помощи цепочек. Открытая адресация. Универсальное хеширование. | + | # Хеш-функции и хеш-таблицы. Разрешение коллизий при помощи цепочек. Открытая адресация. Универсальное хеширование. [KT 13.6, CLRS 11] |
− | # Деревья поиска. Сбалансированные деревья поиска. Красно-черные деревья. | + | # Деревья поиска. Сбалансированные деревья поиска. Красно-черные деревья. [CLRS 12–13] |
− | # Жадные алгоритмы. Матроиды. | + | # Жадные алгоритмы. Матроиды. [DPV 5, E 4, KT 4, CLRS 16] |
− | # Алгоритм Дейкстры. | + | # Алгоритм Дейкстры. [DPV 4.4, E 8, KT 4.4, CLRS 24] |
− | # Приоритетная очередь на основе двоичной кучи. | + | # Приоритетная очередь на основе двоичной кучи. [DPV 4.5, KT 2.5, CLRS 6] |
− | # Минимальные остовные деревья, алгоритмы Прима и Крускала. | + | # Минимальные остовные деревья, алгоритмы Прима и Крускала. [DPV 5.1, E 7, KT 4.5, CLRS 23] |
− | # Система непересекающихся множеств. | + | # Система непересекающихся множеств. [DPV 5.1, KT 4.6, CLRS 21] |
# Конечные автоматы, регулярные выражения, регулярные и нерегулярные языки. | # Конечные автоматы, регулярные выражения, регулярные и нерегулярные языки. | ||
Версия 08:49, 15 июня 2020
Лекторы: Г.А. Погудин (2-ой модуль) С.А. Объедков (4-ый модуль)
Содержание
Второй модуль
Лекции
Вторник 10:30 – 11:50, ауд. R404
Четверг 15:10 – 16:30, ауд. R404
1. 29 октября. Понятие сложности алгоритма, О-большое и о-малое, анализ простейших алгоритмов.Jupyter, Слайды
2. 31 октября. Про О-большие и пределы. Примеры: скользящее среднее, два указателя (merge). In-place алгоритмы: отражение и циклический сдвиг. Jupyter, Jupyter PDF, Слайды
3. 5 ноября. Стэк, очередь, дэк. Про реализации на списках и массивах. Jupyter, Jupyter PDF, Slides. Дополнительное чтение: Стэки и очереди
4. 7 ноября. Рекурсия: быстрое возведение в степень, перечисление подмножеств. Jupyter, Jupyter PDF, Slides. Дополнительное чтение: Раздел 1.10 про быстрое возведение в степень
5. 12 ноября. Рекурсия: перечисление перестановок и подмножеств, subset sum как пример простейшего branch&bound. Jupyter html Jupyter
6. 14 ноября. Динамическое программирование: введение и text justification. Slides Jupyter Jupyter html. Дополнительное чтение: TJ, TJ (как за n log n)
7. 19 ноября. Динамическое программирование: наибольшая общая подпоследовательность, top-down vs bottom-up. Jupyter Jupyter html. Дополнительное чтение: видеолекция про LCS
8. 21 ноября. Контрольная работа. Задачи
9. 26 ноября. Динамическое программирование: задача о рюкзаке, приближенный алгоритм. Jupyter, Jupyter html. Чтение: как делать рюкзак динамикой (bottom-up), видео про то же, но top-down, полиномальная аппроксимация (очень рекомендую)
10. 28 ноября. Поиск и сортировка: бинарный поиск, сортировка вставкой, сортировка слиянием. Jupyter (до лекции)
11. 3 декабря. Сортировка: сложность слияния, нижняя оценка на comparison-based sorting, qsort без анализа сложности. Jupyter Jupyter html
12. 5 декабря. Графы, поиск в глубину, проверка ацикличности. Jupyter Jupyter html Почитать: часть 1 часть 2
13. 10 декабря. Поиск в глубину (продолжение), поиск в ширину. Jupyter Jupyter html
14. 12 декабря. Алгоритмы поиска кратчайших путей: Floyd-Warshall & Bellman-Ford. Jupyter Jupyter html
15. 16 декабря. Внимание: лекция будет именно 16 декабря, в понедельник в 16:40-18:00 в ауд. R401. Разделяй и властвую: умножение многочленов и быстрое преобразование Фурье Jupyter (до лекции)
16. 19 декабря. Повторение перед экзаменом, разбор нескольких задач Jupyter (до лекции)
Домашние задания
- Домашнее задание 1. Дедлайн - 8 ноября.
- Домашнее задание 2 (контест). Дополнительно к контесту нужно написать оценку сложности своего алгоритма в задачах A и C. Дедлайн - 15 ноября.
- Домашнее задание 3. Дедлайн - 22 ноября.
- Домашнее задание 4 (контест). Дополнительно к контесту нужно написать оценку сложности своего алгоритма в задачах A и B. Дедлайн - 29 ноября. Дедлайн со штрафом 50% - 6 декабря.
- Домашнее задание 5 (контест). Дедлайн - 8 декабря. Дедлайн со штрафом 50% - 13 декабря.
- Домашнее задание 6 (контест). Дедлайн - 15 декабря. Дедлайн со штрафом 50% - 20 декабря.
- Домашнее задание 7 (контест). Дедлайн - 22 декабря.
Семинары
Четвертый модуль
Лекции
Понедельник 9:00 – 10:20
Четверг 15:10 – 16:30
- 6 апреля. Структуры данных. Амортизационный анализ. Слайды
- 9 апреля. Хеш-функции и хеш-таблицы. Разрешение коллизий при помощи цепочек. Открытая адресация. Слайды
- 13 апреля. Методы задания хеш-функций. Универсальное хеширование. Слайды
- 16 апреля. Двоичные деревья поиска. Слайды
- 20 апреля. Краcно-черные деревья. Слайды. Заметки: 1, 2, 3, 4
- 23 апреля. Жадные алгоритмы. Слайды. Иллюстрация к последнему доказательству.
- 27 апреля. Алгоритм Дейкстры. Слайды
- 30 апреля. Двоичная куча. Слайды
- 7 мая. Биномиальная куча. Слайды
- 14 мая. Контрольная работа (контест) по темам 1 – 6. Оценка: одна решенная задача — 3 балла, две — 7 баллов, три — 10 баллов. Пробный вариант.
- 18 мая. Минимальные остовные деревья. Слайды
- 21 мая. Система непересекающихся множеств. Слайды
- 24 мая. Жадный алгоритм на матроиде. Слайды
- 28 мая. Конечные автоматы. Слайды
- 1 июня. Недетерминированные конечные автоматы. Слайды
- 4 июня. Регулярные выражения и нерегулярные языки. Слайды
- 8 июня. Повторение перед экзаменом, разбор нескольких задач. Слайды
Домашние задания
- Домашнее задание 1. Дедлайн — 16 апреля.
- Домашнее задание 2 (контест). Дедлайн — 26 апреля, 18:05. Штрафы, которые назначаются в системе за количество попыток, не учитываются при выставлении оценки. Дедлайн со штрафом 50% — 2 мая. Внутренние тесты для первых двух задач.
- Домашнее задание 3. Дедлайн — 3 мая, 18:00. Дедлайн со штрафом 50% — 10 мая.
- Домашнее задание 4 (контест). Дедлайн — 14 мая. Для алгоритмов в задачах задач B и C нужно дополнительно доказать корректность и оценить сложность (и прислать доказательства преподавателю своей группы).
- Домашнее задание 5 (контест). Дедлайн — 21 мая.
- Домашнее задание 6 (контест). Дедлайн — 28 мая. Дедлайн со штрафом 50% — 2 июня.
- Домашнее задание 7 (контест). Дедлайн — 7 июня. Последние две задачи подразумевают знание материала лекции 4 июня.
Семинары
Учебные ассистенты
- 192-2 Шамиль Аюпов
- 194-1 Першина Анна
- 194-2 Константин Матвеев
- 196-1 Денис Семенов
- 196-2 Георгий Новиков
- 197-1 Шамиль Аюпов
- 197-2 Георгий Новиков
- 198-1 Денис Семенов
- 198-2 Арсений Болотин
- 199-1 Константин Матвеев
- 199-2 Першина Анна
- 1910-1 Арсений Болотин
- 1910-2 Даниил Мячин
- 1911-1 Байков Ильнур
- 1911-2 Байков Ильнур
- 1912-1 Даниил Мячин
Литература
Наш курс не следует какому-то конкретному учебнику. Мы бы рекомендовали для дополнительного чтения следующие книги:
- Dasgupta S., Papadimitriou K., Vazirani U. Algorithms english, russian (недавно издана МЦНМО, можно купить бумажную)
- Erickson J. Algorithms
- Клейнберг Дж., Тардос Е. Алгоритмы: разработка и применение. — СПб.: Питер, 2016.
- Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. — 3-е издание — М.: Вильямс, 2013.
Экзамен
Экзамен пройдет 18 июня в устном формате и будет включать в себя темы всего курса (второй и четвертый модули). Студенту будет предложено несколько простых задач, решить которые нужно без подготовки: “как работает алгоритм Дейкстры на данном входе?”, “какова сложность приведённого алгоритма?”, “можно ли раскрасить данное дерево так, чтобы оно стало красно-черным?”. Для участия в экзамене понадобится компьютер или планшет с веб-камерой, которую нужно будет включить во время экзамена.
Оценка за экзамен может быть выставлена автоматом, если
- оценка за второй модуль не ниже восьми (так как экзамен проводится по материалам всего курса);
- и оценка за работу на семинарах в четвертом модуле не ниже восьми (так как именно эта форма контроля ближе других по жанру к устному экзамену).
Автоматом выставляется следующая оценка, округленная по обычным правилам: (второй модуль * 0,33 + д/з * 0,2 + к/р * 0,07 + семинары * 0,07) / 0,67. Все оценки в формуле — целые.
Примерный список тем
- Алгоритмы и их сложность, асимптотический анализ (О большое и малое). [DPV 0, KT 2, CLRS 2–3]
- Простейшие структуры данных: стек, очередь, дэк, их реализация на списках и массивах. [CLRS 10]
- Рекурсивные алгоритмы и рекуррентные соотношения. [DPV 2, E 1–2, KT 5, CLRS 4]
- Динамическое программирование. [DPV 6, E 3, KT 6, CLRS 15]
- Сортировки (вставкой, слиянием и др.). [DPV 2, KT 5, CLRS 4–8]
- Графы. Способы представления графов. Обход в глубину и в ширину, поиск компонент связности, топологическая сортировка. [DPV 3–4, E 5–6, KT 3, CLRS 22]
- Алгоритмы Флойда – Уоршелла и Беллмана – Форда. [DPV 4, E 8–9, KT 6, CLRS 24–25]
- Разделяй и властвуй. [DPV 2, KT 5, CLRS 4]
- Структуры данных. Амортизационный анализ. [CLRS 17]
- Хеш-функции и хеш-таблицы. Разрешение коллизий при помощи цепочек. Открытая адресация. Универсальное хеширование. [KT 13.6, CLRS 11]
- Деревья поиска. Сбалансированные деревья поиска. Красно-черные деревья. [CLRS 12–13]
- Жадные алгоритмы. Матроиды. [DPV 5, E 4, KT 4, CLRS 16]
- Алгоритм Дейкстры. [DPV 4.4, E 8, KT 4.4, CLRS 24]
- Приоритетная очередь на основе двоичной кучи. [DPV 4.5, KT 2.5, CLRS 6]
- Минимальные остовные деревья, алгоритмы Прима и Крускала. [DPV 5.1, E 7, KT 4.5, CLRS 23]
- Система непересекающихся множеств. [DPV 5.1, KT 4.6, CLRS 21]
- Конечные автоматы, регулярные выражения, регулярные и нерегулярные языки.
Оценки
Итоговая оценка рассчитывается следующим образом:
- Оценка за второй модуль — 33%
- Домашние задания в четвертом модуле — 20%
- Контрольная работа в четвертом модуле — 7%
- Работа на семинарах в четвертом модуле — 7%
- Экзамен — 33%