Алгоритмы и структуры данных 1 основной поток 2019/202 — различия между версиями
Gpogudin (обсуждение | вклад) (KR problems) |
Gpogudin (обсуждение | вклад) (video added) |
||
| Строка 18: | Строка 18: | ||
6. '''14 ноября.''' Динамическое программирование: введение и text justification. [https://www.dropbox.com/s/el723xpp30wg0ut/lecture06.pdf?dl=0 Slides] [https://www.dropbox.com/s/pn837p2kb5a82aq/lecture06.ipynb?dl=0 Jupyter] [https://www.dropbox.com/s/848uwc5k5bktaz8/lecture06.html?dl=0 Jupyter html]. Дополнительное чтение: [https://www.geeksforgeeks.org/word-wrap-problem-dp-19/ TJ], [https://xxyxyz.org/line-breaking/ TJ (как за n log n)] | 6. '''14 ноября.''' Динамическое программирование: введение и text justification. [https://www.dropbox.com/s/el723xpp30wg0ut/lecture06.pdf?dl=0 Slides] [https://www.dropbox.com/s/pn837p2kb5a82aq/lecture06.ipynb?dl=0 Jupyter] [https://www.dropbox.com/s/848uwc5k5bktaz8/lecture06.html?dl=0 Jupyter html]. Дополнительное чтение: [https://www.geeksforgeeks.org/word-wrap-problem-dp-19/ TJ], [https://xxyxyz.org/line-breaking/ TJ (как за n log n)] | ||
| − | 7. '''19 ноября.''' Динамическое программирование: наибольшая общая подпоследовательность, top-down vs bottom-up. [https://www.dropbox.com/s/ics1399zjfdgzl6/lecture07.ipynb?dl=0 Jupyter] [https://www.dropbox.com/s/old6cwjdjndqoku/lecture07.html?dl=0 Jupyter html] | + | 7. '''19 ноября.''' Динамическое программирование: наибольшая общая подпоследовательность, top-down vs bottom-up. [https://www.dropbox.com/s/ics1399zjfdgzl6/lecture07.ipynb?dl=0 Jupyter] [https://www.dropbox.com/s/old6cwjdjndqoku/lecture07.html?dl=0 Jupyter html]. Дополнительное чтение: [https://www.youtube.com/watch?v=sSno9rV8Rhg видеолекция про LCS] |
8. '''21 ноября.''' Контрольная работа. [https://www.dropbox.com/s/dtoaxc3nclbn4wz/AiSD_KR.pdf?dl=0 Задачи] | 8. '''21 ноября.''' Контрольная работа. [https://www.dropbox.com/s/dtoaxc3nclbn4wz/AiSD_KR.pdf?dl=0 Задачи] | ||
Версия 21:06, 24 ноября 2019
Лекторы: Г.А. Погудин (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 ноября. Контрольная работа. Задачи
Домашние задания
- Домашнее задание 1. Дедлайн - 8 ноября.
- Домашнее задание 2 (контест). Дополнительно к контесту нужно написать оценку сложности своего алгоритма в задачах A и C. Дедлайн - 15 ноября.
- Домашнее задание 3. Дедлайн - 22 ноября.
- Домашнее задание 4 (контест). Дополнительно к контесту нужно написать оценку сложности своего алгоритма в задачах A и B. Дедлайн - 29 ноября. Дедлайн со штрафом 50% - 6 декабря.
Семинары
Литература
Наш курс не следует какому-то конкретному учебнику. Я бы рекомендовал для дополнительного (и душеполезного!) чтения следующие книги
- Algorithms, Jeff Erickson
- Algorithms, Dasgupta, Papadimitriou, Vazirani, english, russian (недавно издана МЦНМО, можно купить бумажную)
