Алгоритмы и структуры данных 1 основной поток 2019/202

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

Лекторы: Г.А. Погудин (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
  9. Неделя 9


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

Литература

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

  1. [DPV] Dasgupta S., Papadimitriou K., Vazirani U. Algorithms english, russian (недавно издана МЦНМО, можно купить бумажную)
  2. [E] Erickson J. Algorithms
  3. [S] Sipser M. Introduction to the Theory of Computation. — Boston, Mass.: Cengage Learning, 2013.
  4. [KT] Клейнберг Дж., Тардос Е. Алгоритмы: разработка и применение. — СПб.: Питер, 2016.
  5. [CLRS] Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. — 3-е издание — М.: Вильямс, 2013.

Экзамен

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

В последних столбцах таблицы каждой группы для каждого студента, сдающего экзамен, указан экзаменатор, временной слот, когда нужно сдавать экзамен, и ссылка, по которой нужно подключиться. Если вы планируете сдавать экзамен, но не находите себя в таблице или не находите фамилии экзаменатора напротив своей фамилии, напишите об этом лектору сегодня (17 июня). Если экзаменатор указан, но не указан временной слот или ссылка, немного подождите или свяжитесь с экзаменатором.

Время экзамена для одного студента — 30 мин. Студенту предлагаются четыре задачи, которые можно решать в любом порядке. Если студент отказывается отвечать, то получает 0 и уходит. Если студент отвечает, он получает 1 балл и еще 0, 1 или 2 балла за каждую задачу (в зависимости от полноты решения). Если студент набрал 9 баллов и остается время, студенту предлагается пятая задача, за которую можно получить 0 или 1 балл.

Студенту разрешается пользоваться бумагой, ручкой, а также рисовать на экране компьютера / планшета в специализированном приложении. Студент отвечает устно при включенной веб-камере, используя при необходимости записи на бумаге или экране компьютера / планшета.

Запрещается открывать какие-либо сайты в браузере (кроме таблицы со ссылками на экзамен или сайты виртуальной доски для рисования), пользоваться литературой, иными материалами и мобильным телефоном.

В случае разрыва соединения студенту следует по возможности сообщить в чат свои имя и фамилию, группу и описание проблемы, а также попытаться восстановить соединение. При отсутствии возможности вновь подключиться к экзамену необходимо зафиксировать скриншотом или фотографией с телефона факт возникновения неустранимой проблемы.

Процедура сдачи экзамена записывается.

Чат для экстренных объявлений во время экзамена

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

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

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

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

В квадратных скобках приведены указания на главы из книг, перечисленных в разделе Литература. В разных книгах некоторых понятия определяются по-разному. В отношении тем четвертого модуля нужно ориентироваться на терминологию, используемую в слайдах.

  1. Алгоритмы и их сложность, асимптотический анализ (О большое и малое). [DPV 0, KT 2, CLRS 2–3]
  2. Простейшие структуры данных: стек, очередь, дэк, их реализация на списках и массивах. [CLRS 10]
  3. Рекурсивные алгоритмы и рекуррентные соотношения. [DPV 2, E 1–2, KT 5, CLRS 4]
  4. Динамическое программирование. [DPV 6, E 3, KT 6, CLRS 15]
  5. Сортировки (вставкой, слиянием и др.). [DPV 2, KT 5, CLRS 4–8]
  6. Графы. Способы представления графов. Обход в глубину и в ширину, поиск компонент связности, топологическая сортировка. [DPV 3–4, E 5–6, KT 3, CLRS 22]
  7. Алгоритмы Флойда – Уоршелла и Беллмана – Форда. [DPV 4, E 8–9, KT 6, CLRS 24–25]
  8. Разделяй и властвуй. [DPV 2, KT 5, CLRS 4]
  9. Структуры данных. Амортизационный анализ. [CLRS 17]
  10. Хеш-функции и хеш-таблицы. Разрешение коллизий при помощи цепочек. Открытая адресация. Универсальное хеширование. [KT 13.6, CLRS 11]
  11. Деревья поиска. Сбалансированные деревья поиска. Красно-черные деревья. [CLRS 12–13]
  12. Жадные алгоритмы. Матроиды. [DPV 5, E 4, KT 4, CLRS 16]
  13. Алгоритм Дейкстры. [DPV 4.4, E 8, KT 4.4, CLRS 24]
  14. Приоритетная очередь на основе двоичной кучи. [DPV 4.5, KT 2.5, CLRS 6]
  15. Минимальные остовные деревья, алгоритмы Прима и Крускала. [DPV 5.1, E 7, KT 4.5, CLRS 23]
  16. Система непересекающихся множеств. [DPV 5.1, KT 4.6, CLRS 21]
  17. Конечные автоматы, регулярные выражения, регулярные и нерегулярные языки. [S 1]

Оценки

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

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

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

Источник — «http://wiki.cs.hse.ru/index.php?title=Алгоритмы_и_структуры_данных_1_основной_поток_2019/202&oldid=41917»