Алгоритмы и структуры данных 1 основной поток 2019/202 — различия между версиями
.obj (обсуждение | вклад) (→Домашние задания) |
.obj (обсуждение | вклад) (→Лекции) |
||
Строка 77: | Строка 77: | ||
# '''23 апреля.''' Жадные алгоритмы. [https://www.dropbox.com/s/4l0h1zgbao5p0pu/algo-6-greedy.pdf?dl=0 Слайды.] [https://www.dropbox.com/s/yj9sk047zlg8eie/algo-6-greedy.mp4?dl=0 Иллюстрация к последнему доказательству.] | # '''23 апреля.''' Жадные алгоритмы. [https://www.dropbox.com/s/4l0h1zgbao5p0pu/algo-6-greedy.pdf?dl=0 Слайды.] [https://www.dropbox.com/s/yj9sk047zlg8eie/algo-6-greedy.mp4?dl=0 Иллюстрация к последнему доказательству.] | ||
# '''27 апреля.''' Алгоритм Дейкстры. [https://www.dropbox.com/s/eadtl5tb2fta2hm/algo-7-dijkstra.pdf?dl=0 Слайды.] | # '''27 апреля.''' Алгоритм Дейкстры. [https://www.dropbox.com/s/eadtl5tb2fta2hm/algo-7-dijkstra.pdf?dl=0 Слайды.] | ||
+ | # '''30 апреля.''' Двоичная куча. [https://www.dropbox.com/s/nepng6m4rhzpsig/algo-8-heap.pdf?dl=0 Слайды.] | ||
==Домашние задания== | ==Домашние задания== |
Версия 15:05, 30 апреля 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 апреля. Двоичная куча. Слайды.
Домашние задания
- Домашнее задание 1. Дедлайн — 16 апреля.
- Домашнее задание 2 (контест). Дедлайн — 26 апреля, 18:05. Штрафы, которые назначаются в системе за количество попыток, не учитываются при выставлении оценки. Дедлайн со штрафом 50% — 2 мая. Внутренние тесты для первых двух задач.
- Домашнее задание 3. Дедлайн — 3 мая, 18:00.
Семинары
Учебные ассистенты
- 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%