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

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(Экзамен)
Строка 146: Строка 146:
 
# и оценка за работу на семинарах в четвертом модуле не ниже восьми (так как именно эта форма контроля ближе других по жанру к устному экзамену).
 
# и оценка за работу на семинарах в четвертом модуле не ниже восьми (так как именно эта форма контроля ближе других по жанру к устному экзамену).
 
Автоматом выставляется следующая оценка, округленная по обычным правилам: (второй модуль * 0,33 + д/з * 0,2 + к/р * 0,07 + семинары * 0,07) / 0,67. Все оценки в формуле — целые.
 
Автоматом выставляется следующая оценка, округленная по обычным правилам: (второй модуль * 0,33 + д/з * 0,2 + к/р * 0,07 + семинары * 0,07) / 0,67. Все оценки в формуле — целые.
 +
 +
==Примерный список тем==
 +
# Алгоритмы и их сложность, асимптотический анализ (''О'' большое и малое).
 +
# Простейшие структуры данных: стек, очередь, дэк, их реализация на списках и массивах.
 +
# Рекурсивные алгоритмы и рекуррентные соотношения.
 +
# Динамическое программирование.
 +
# Сортировки (вставкой, слиянием и др.).
 +
# Графы. Способы представления графов. Обход в глубину и в ширину, поиск компонент связности, топологическая сортировка.
 +
# Алгоритмы Флойда – Уоршелла и Беллмана – Форда.
 +
# Разделяй и властвуй.
 +
# Структуры данных. Амортизационный анализ.
 +
# Хеш-функции и хеш-таблицы. Разрешение коллизий при помощи цепочек. Открытая адресация. Универсальное хеширование.
 +
# Деревья поиска. Сбалансированные деревья поиска. Красно-черные деревья.
 +
# Жадные алгоритмы. Матроиды.
 +
# Алгоритм Дейкстры.
 +
# Приоритетная очередь на основе двоичной кучи.
 +
# Минимальные остовные деревья, алгоритмы Прима и Крускала.
 +
# Система непересекающихся множеств.
 +
# Конечные автоматы, регулярные выражения, регулярные и нерегулярные языки.
  
 
=Оценки=
 
=Оценки=

Версия 01:59, 8 июня 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. Домашнее задание 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 декабря.
  7. Домашнее задание 7 (контест). Дедлайн - 22 декабря.

Семинары

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

Четвертый модуль

Лекции

Понедельник 9:00 – 10:20

Четверг 15:10 – 16:30

  1. 6 апреля. Структуры данных. Амортизационный анализ. Слайды
  2. 9 апреля. Хеш-функции и хеш-таблицы. Разрешение коллизий при помощи цепочек. Открытая адресация. Слайды
  3. 13 апреля. Методы задания хеш-функций. Универсальное хеширование. Слайды
  4. 16 апреля. Двоичные деревья поиска. Слайды
  5. 20 апреля. Краcно-черные деревья. Слайды. Заметки: 1, 2, 3, 4
  6. 23 апреля. Жадные алгоритмы. Слайды. Иллюстрация к последнему доказательству.
  7. 27 апреля. Алгоритм Дейкстры. Слайды
  8. 30 апреля. Двоичная куча. Слайды
  9. 7 мая. Биномиальная куча. Слайды
  10. 14 мая. Контрольная работа (контест) по темам 1 – 6. Оценка: одна решенная задача — 3 балла, две — 7 баллов, три — 10 баллов. Пробный вариант.
  11. 18 мая. Минимальные остовные деревья. Слайды
  12. 21 мая. Система непересекающихся множеств. Слайды
  13. 24 мая. Жадный алгоритм на матроиде. Слайды
  14. 28 мая. Конечные автоматы. Слайды
  15. 1 июня. Недетерминированные конечные автоматы. Слайды
  16. 4 июня. Регулярные выражения и нерегулярные языки. Слайды
  17. 8 июня. Повторение перед экзаменом, разбор нескольких задач.

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

  1. Домашнее задание 1. Дедлайн — 16 апреля.
  2. Домашнее задание 2 (контест). Дедлайн — 26 апреля, 18:05. Штрафы, которые назначаются в системе за количество попыток, не учитываются при выставлении оценки. Дедлайн со штрафом 50% — 2 мая. Внутренние тесты для первых двух задач.
  3. Домашнее задание 3. Дедлайн — 3 мая, 18:00. Дедлайн со штрафом 50% — 10 мая.
  4. Домашнее задание 4 (контест). Дедлайн — 14 мая. Для алгоритмов в задачах задач B и C нужно дополнительно доказать корректность и оценить сложность (и прислать доказательства преподавателю своей группы).
  5. Домашнее задание 5 (контест). Дедлайн — 21 мая.
  6. Домашнее задание 6 (контест). Дедлайн — 28 мая. Дедлайн со штрафом 50% — 2 июня.
  7. Домашнее задание 7 (контест). Дедлайн — 7 июня. Последние две задачи подразумевают знание материала лекции 4 июня.

Семинары

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

Ближайшая консультация

16 мая 12:10 – 13:30

Учебные ассистенты

Литература

Наш курс не следует какому-то конкретному учебнику. Мы бы рекомендовали для дополнительного чтения следующие книги:

  1. Dasgupta S., Papadimitriou K., Vazirani U. Algorithms english, russian (недавно издана МЦНМО, можно купить бумажную)
  2. Erickson J. Algorithms
  3. Клейнберг Дж., Тардос Е. Алгоритмы: разработка и применение. — СПб.: Питер, 2016.
  4. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. — 3-е издание — М.: Вильямс, 2013.

Экзамен

Экзамен пройдет 18 июня в устном формате и будет включать в себя темы всего курса (второй и четвертый модули). Студенту будет предложено несколько простых задач, решить которые нужно без подготовки: “как работает алгоритм Дейкстры на данном входе?”, “какова сложность приведённого алгоритма?”, “можно ли раскрасить данное дерево так, чтобы оно стало красно-черным?”.

Оценка за экзамен может быть выставлена автоматом, если

  1. оценка за второй модуль не ниже восьми (так как экзамен проводится по материалам всего курса);
  2. и оценка за работу на семинарах в четвертом модуле не ниже восьми (так как именно эта форма контроля ближе других по жанру к устному экзамену).

Автоматом выставляется следующая оценка, округленная по обычным правилам: (второй модуль * 0,33 + д/з * 0,2 + к/р * 0,07 + семинары * 0,07) / 0,67. Все оценки в формуле — целые.

Примерный список тем

  1. Алгоритмы и их сложность, асимптотический анализ (О большое и малое).
  2. Простейшие структуры данных: стек, очередь, дэк, их реализация на списках и массивах.
  3. Рекурсивные алгоритмы и рекуррентные соотношения.
  4. Динамическое программирование.
  5. Сортировки (вставкой, слиянием и др.).
  6. Графы. Способы представления графов. Обход в глубину и в ширину, поиск компонент связности, топологическая сортировка.
  7. Алгоритмы Флойда – Уоршелла и Беллмана – Форда.
  8. Разделяй и властвуй.
  9. Структуры данных. Амортизационный анализ.
  10. Хеш-функции и хеш-таблицы. Разрешение коллизий при помощи цепочек. Открытая адресация. Универсальное хеширование.
  11. Деревья поиска. Сбалансированные деревья поиска. Красно-черные деревья.
  12. Жадные алгоритмы. Матроиды.
  13. Алгоритм Дейкстры.
  14. Приоритетная очередь на основе двоичной кучи.
  15. Минимальные остовные деревья, алгоритмы Прима и Крускала.
  16. Система непересекающихся множеств.
  17. Конечные автоматы, регулярные выражения, регулярные и нерегулярные языки.

Оценки

Итоговая оценка рассчитывается следующим образом:

  • Оценка за второй модуль — 33%
  • Домашние задания в четвертом модуле — 20%
  • Контрольная работа в четвертом модуле — 7%
  • Работа на семинарах в четвертом модуле — 7%
  • Экзамен — 33%

Таблицы с оценками