Алгоритмы и структуры данных 1 основной поток 2019/202 — различия между версиями
Gpogudin (обсуждение | вклад) (extra reading) |
Gpogudin (обсуждение | вклад) (lecture 5) |
||
| Строка 8: | Строка 8: | ||
1. '''29 октября.''' Понятие сложности алгоритма, О-большое и о-малое, анализ простейших алгоритмов.[https://www.dropbox.com/s/dk98dd219pq2qdg/lecture01.ipynb?dl=0 Jupyter], [https://www.dropbox.com/s/hl3g0nvn0qb2lkc/BA_intro.pdf?dl=0 Слайды] | 1. '''29 октября.''' Понятие сложности алгоритма, О-большое и о-малое, анализ простейших алгоритмов.[https://www.dropbox.com/s/dk98dd219pq2qdg/lecture01.ipynb?dl=0 Jupyter], [https://www.dropbox.com/s/hl3g0nvn0qb2lkc/BA_intro.pdf?dl=0 Слайды] | ||
| − | + | 2. '''31 октября.''' Про О-большие и пределы. Примеры: скользящее среднее, два указателя (merge). In-place алгоритмы: отражение и циклический сдвиг. [https://www.dropbox.com/s/0w8q3eh71i6ydjf/lecture02.ipynb?dl=0 Jupyter], [https://www.dropbox.com/s/3newozpu606hdar/lecture02_jup.pdf?dl=0 Jupyter PDF], [https://www.dropbox.com/s/lrugaht29fx8ah1/lecture02.pdf?dl=0 Слайды] | |
| − | + | 3. '''5 ноября.''' Стэк, очередь, дэк. Про реализации на списках и массивах. [https://www.dropbox.com/s/681ouqwnbvkx6xl/lecture03.ipynb?dl=0 Jupyter], [https://www.dropbox.com/s/lmp70um5vwsytil/lecture03_jup.pdf?dl=0 Jupyter PDF], [https://www.dropbox.com/s/vtk3vsmk6jn9fyt/lecture03.pdf?dl=0 Slides]. Дополнительное чтение: [https://www.cs.cmu.edu/~fp/courses/15122-f15/lectures/09-stackqueue.pdf Стэки и очереди] | |
| − | + | 4. '''7 ноября.''' Рекурсия: быстрое возведение в степень, перечисление подмножеств. [https://www.dropbox.com/s/fp5hdiggx5qfzq3/lecture04.ipynb?dl=0 Jupyter], [https://www.dropbox.com/s/kin45ermepowtcu/lecture04_jup.pdf?dl=0 Jupyter PDF], [https://www.dropbox.com/s/rpwn4s01v73pb56/lecture04.pdf?dl=0 Slides]. Дополнительное чтение: [http://jeffe.cs.illinois.edu/teaching/algorithms/book/01-recursion.pdf Раздел 1.10 про быстрое возведение в степень] | |
| + | |||
| + | 5. '''12 ноября.''' Рекурсия: перечисление перестановок и подмножеств, subset sum как пример простейшего branch&bound. [https://www.dropbox.com/s/eo071319drhssdi/lecture05_jup.html?dl=0 Jupyter html] [https://www.dropbox.com/s/0r3ik1h9jmpq07x/lecture05.ipynb?dl=0 Jupyter] | ||
==Домашние задания== | ==Домашние задания== | ||
Версия 17:56, 13 ноября 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
Домашние задания
- Домашнее задание 1. Дедлайн - 8 ноября.
- Домашнее задание 2 (контест). Дополнительно к контесту нужно написать оценку сложности своего алгоритма в задачах A и C. Дедлайн - 15 ноября.
Семинары
Литература
Наш курс не следует какому-то конкретному учебнику. Я бы рекомендовал для дополнительного (и душеполезного!) чтения следующие книги
- Algorithms, Jeff Erickson
- Algorithms, Dasgupta, Papadimitriou, Vazirani, english, russian (недавно издана МЦНМО, можно купить бумажную)
