Алгоритмы и структуры данных 1 основной поток 2019/202 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(week 7)
(10 дек)
Строка 30: Строка 30:
 
12. '''5 декабря.''' Графы, поиск в глубину, проверка ацикличности. [https://www.dropbox.com/s/ofujay1s7huz0h7/lecture12.ipynb?dl=0 Jupyter] [https://www.dropbox.com/s/1zfpqu3tczzbhym/lecture12.html?dl=0 Jupyter html]  
 
12. '''5 декабря.''' Графы, поиск в глубину, проверка ацикличности. [https://www.dropbox.com/s/ofujay1s7huz0h7/lecture12.ipynb?dl=0 Jupyter] [https://www.dropbox.com/s/1zfpqu3tczzbhym/lecture12.html?dl=0 Jupyter html]  
 
Почитать: [http://jeffe.cs.illinois.edu/teaching/algorithms/book/05-graphs.pdf часть 1] [http://jeffe.cs.illinois.edu/teaching/algorithms/book/06-dfs.pdf часть 2]
 
Почитать: [http://jeffe.cs.illinois.edu/teaching/algorithms/book/05-graphs.pdf часть 1] [http://jeffe.cs.illinois.edu/teaching/algorithms/book/06-dfs.pdf часть 2]
 +
 +
13. '''10 декабря.''' Поиск в глубину (продолжение), поиск в ширину. [https://www.dropbox.com/s/0fv66ta878vdjpg/Lecture13.ipynb?dl=0 Jupyter (до лекции)]
  
 
==Домашние задания==
 
==Домашние задания==

Версия 00:46, 10 декабря 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 ноября. Контрольная работа. Задачи

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 (до лекции)

Домашние задания

  1. Домашнее задание 1. Дедлайн - 8 ноября.
  2. Домашнее задание 2 (контест). Дополнительно к контесту нужно написать оценку сложности своего алгоритма в задачах A и C. Дедлайн - 15 ноября.
  3. Домашнее задание 3. Дедлайн - 22 ноября.
  4. Домашнее задание 4 (контест). Дополнительно к контесту нужно написать оценку сложности своего алгоритма в задачах A и B. Дедлайн - 29 ноября. Дедлайн со штрафом 50% - 6 декабря.
  5. Домашнее задание 5 (контест). Дедлайн - 8 декабря. Дедлайн со штрафом 50% - 13 декабря.
  6. Домашнее задание 6 (контест). Дедлайн - 15 декабря. Дедлайн со штрафом 50% - 20 декабря.

Семинары

  1. Неделя 1
  2. Неделя 2
  3. Неделя 3
  4. Неделя 4
  5. Неделя 5
  6. Неделя 6
  7. Неделя 7

Литература

Наш курс не следует какому-то конкретному учебнику. Я бы рекомендовал для дополнительного (и душеполезного!) чтения следующие книги

  1. Algorithms, Jeff Erickson
  2. Algorithms, Dasgupta, Papadimitriou, Vazirani, english, russian (недавно издана МЦНМО, можно купить бумажную)