Алгоритмы и структуры данных 1 основной поток 2019/202 — различия между версиями
.obj (обсуждение | вклад) |
.obj (обсуждение | вклад) |
||
Строка 62: | Строка 62: | ||
# [https://www.dropbox.com/s/z75eljucodlka80/week8.pdf?dl=0 Неделя 8] | # [https://www.dropbox.com/s/z75eljucodlka80/week8.pdf?dl=0 Неделя 8] | ||
− | = | + | =Четвертый модуль= |
− | Наш курс не следует какому-то конкретному учебнику. | + | =Литература= |
+ | |||
+ | Наш курс не следует какому-то конкретному учебнику. Мы бы рекомендовали для дополнительного чтения следующие книги: | ||
# [http://jeffe.cs.illinois.edu/teaching/algorithms/ Algorithms, Jeff Erickson] | # [http://jeffe.cs.illinois.edu/teaching/algorithms/ Algorithms, Jeff Erickson] | ||
# Algorithms, Dasgupta, Papadimitriou, Vazirani, [http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf english], [http://www.math.nsc.ru/LBRT/k5/OR-MMF/dasgupta_2014.pdf russian] (недавно издана МЦНМО, можно купить бумажную) | # Algorithms, Dasgupta, Papadimitriou, Vazirani, [http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf english], [http://www.math.nsc.ru/LBRT/k5/OR-MMF/dasgupta_2014.pdf russian] (недавно издана МЦНМО, можно купить бумажную) | ||
− | |||
− |
Версия 11:44, 31 марта 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 декабря.
Семинары
Четвертый модуль
Литература
Наш курс не следует какому-то конкретному учебнику. Мы бы рекомендовали для дополнительного чтения следующие книги:
- Algorithms, Jeff Erickson
- Algorithms, Dasgupta, Papadimitriou, Vazirani, english, russian (недавно издана МЦНМО, можно купить бумажную)