Алгоритмы и структуры данных 1 основной поток 2019/202 — различия между версиями
.obj (обсуждение | вклад) (→Лекции) |
.obj (обсуждение | вклад) (→Домашние задания) |
||
Строка 89: | Строка 89: | ||
# [https://official.contest.yandex.ru/contest/18237/enter/ Домашнее задание 4 (контест)]. Дедлайн — 14 мая. Для алгоритмов в задачах задач B и C нужно дополнительно доказать корректность и оценить сложность (и прислать доказательства преподавателю своей группы). | # [https://official.contest.yandex.ru/contest/18237/enter/ Домашнее задание 4 (контест)]. Дедлайн — 14 мая. Для алгоритмов в задачах задач B и C нужно дополнительно доказать корректность и оценить сложность (и прислать доказательства преподавателю своей группы). | ||
# [https://official.contest.yandex.ru/contest/18267/enter/ Домашнее задание 5 (контест)]. Дедлайн — 21 мая. | # [https://official.contest.yandex.ru/contest/18267/enter/ Домашнее задание 5 (контест)]. Дедлайн — 21 мая. | ||
− | # | + | # [https://official.contest.yandex.ru/contest/18474/enter/ Домашнее задание 6 (контест)]. Дедлайн — 28 мая. Дедлайн со штрафом 50% — 4 июня. |
# | # | ||
Версия 00:22, 21 мая 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 мая. Минимальные остовные деревья. Слайды.
Домашние задания
- Домашнее задание 1. Дедлайн — 16 апреля.
- Домашнее задание 2 (контест). Дедлайн — 26 апреля, 18:05. Штрафы, которые назначаются в системе за количество попыток, не учитываются при выставлении оценки. Дедлайн со штрафом 50% — 2 мая. Внутренние тесты для первых двух задач.
- Домашнее задание 3. Дедлайн — 3 мая, 18:00. Дедлайн со штрафом 50% — 10 мая.
- Домашнее задание 4 (контест). Дедлайн — 14 мая. Для алгоритмов в задачах задач B и C нужно дополнительно доказать корректность и оценить сложность (и прислать доказательства преподавателю своей группы).
- Домашнее задание 5 (контест). Дедлайн — 21 мая.
- Домашнее задание 6 (контест). Дедлайн — 28 мая. Дедлайн со штрафом 50% — 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.
Экзамен
Экзамен пройдет в устном формате и будет включать в себя темы всего курса (второй и четвертый модули).
Оценки
Итоговая оценка рассчитывается следующим образом:
- Оценка за второй модуль — 33%
- Домашние задания в четвертом модуле — 20%
- Контрольная работа в четвертом модуле — 7%
- Работа на семинарах в четвертом модуле — 7%
- Экзамен — 33%