Алгоритмы и структуры данных 2018/2019
Лектор: С.А. Объедков
Содержание
Второй модуль
Лекции
понедельник 10:30 – 11:50, ауд. 622
среда 15:10 – 16:30, ауд. 622
- 29 октября. Задача сортировки. Сортировка вставками: анализ корректности с использованием инварианта цикла и времени работы. Асимптотические обозначения. Циклическая сортировка.
- 31 октября. Стратегия "Разделяй и властвуй". Сортировка слиянием. Доказательство корректности рекурсивных алгоритмов по индукции. Оценка времени работы рекурсивных алгоритмов при помощи рекуррентных соотношений: дерево рекурсии, итерационный метод, основная теорема.
- 7 ноября. Решение рекуррентных соотношений методом подстановки. Линейный алгоритм поиска k-ой порядковой статистики.
- 12 ноября. Нижние оценки для сортировки сравнениями. Сортировка подсчетом, блочная сортировка, поразрядная сортировка.
- 14 ноября. Рандомизированные алгоритмы. Лас-Вегас и Монте-Карло. Краткое введение в теорию вероятностей: вероятностные пространства, события, случайные переменные, математическое ожидание и его линейность, геометрические случайные переменные. Алгоритмы Bogosort и Quicksort.
- 19 ноября. Таблицы с прямой адресацией. Хеш-таблицы. Хеш-функции. Универсальные семейства хеш-функций. Открытая адресация.
- 21 ноября. Двоичные деревья поиска. Семейства сбалансированных деревьев. Красно-черные деревья.
- 26 ноября. Вставка элемента в красно-черное дерево. Ориентированные и неориентированные графы. Представление графов в памяти компьютера: матрицы смежности и списки смежности. Поиск в ширину и в глубину.
- 28 ноября. Вычисление расстояний при помощи обхода в ширину. Вычисление компонент связности в неориентированном графе и компонент сильной связности в ориентированном графе. Топологическая сортировка.
- 3 декабря Кратчайшие пути во взвешенных графах. Алгоритм Дейкстры.
- 5 декабря Динамическое программирование: алгоритмы Беллмана – Форда и Флойда – Уоршелла.
- 10 декабря. Контрольная работа по материалам осенних лекций (29 октября – 28 ноября). В частности, в контрольной работе могут быть даны задачи на рекуррентные соотношения, хеш-таблицы, рандомизированные алгоритмы, а также задачи, похожие на задачи для подготовки. С собой можно принести "шпаргалку" формата A4. Другими материалами пользоваться не разрешается. Контрольная состоится 10 декабря в 10:30 – 11:50 в ауд. 402 (группы 182 и 184) и в ауд. 622 (группы 185, 186, 187, 188 и 189). Те, кто пропустил контрольную работу по уважительной причине, смогут ее написать 17 декабря в 16:40-18:00 в ауд. 622.
- 12 декабря. Динамическое программирование: задача о рюкзаке, независимое множество максимального веса в дереве.
- 17 декабря. Жадные алгоритмы, способы доказательства их корректности. Минимальные основные деревья. Алгоритм Прима.
Преподаватели и ассистенты
Подгруппа | Преподаватель | Учебные ассистенты | Консультация |
---|---|---|---|
182-1 | София Техажева | Александра Латышева | вт 10:30 – 11:50 |
182-2 | Сергей Брагин | Александра Латышева | вт 10:30 – 11:50 |
184-1 | Валерий Харитонов | Илья Погодаев | |
184-2 | Екатерина Гольцова | Илья Погодаев | |
185-1 | Илья Самоненко, (сайт для семинаров, задать вопрос) |
Антон Родионов | вт 9:00 – 10:20, ауд. 306 |
185-2 | Сергей Объедков | Антон Родионов | вт 9:00 – 10:20, ауд. 306 |
186-1 | Антон Филиппов | Алия Хасанова | пн 13:40 – 15:00 |
186-2 | Святослав Фельдшеров | Алия Хасанова | пн 13:40 – 15:00 |
187-1 | Вильям Саакян | Андрей Чулков | пн 15:10 – 16:30 |
187-2 | Михаил Густокашин | Андрей Чулков | пн 15:10 – 16:30 |
188-1 | Владислав Вершинин | Агзамходжа Турсунходжаев | |
188-2 | Федор Строк | Агзамходжа Турсунходжаев | |
189-1 | Дмитрий Светличный | Алия Хасанова | пн 13:40 – 15:00 |
189-2 | Ярослав Кищенко | Андрей Чулков | пн 13:40 – 15:00 |
Домашние задания
- Простые сортировки, бинарный поиск — с 29 октября по 4 ноября (со штрафом 50% — с 5 по 11 ноября).
- Рекурсия, сортировка слиянием — с 5 по 13 ноября (со штрафом 50% — с 14 по 18 ноября).
- Задачи на асимптотику и рекуррентные соотношения — с 7 по 20 ноября. UPDATE: Задание в пункте 4 несколько упрощено.
- Сортировка подсчетом, поразрядная и др. — с 12 по 18 ноября (со штрафом 50% — с 19 по 25 ноября).
- Быстрая сортировка, порядковые статистики, хеши — с 19 по 25 ноября (со штрафом 50% — с 26 ноября по 2 декабря).
- Бинарные деревья поиска — с 26 ноября по 2 декабря (со штрафом 50% — с 3 по 9 декабря).
- Задачи на сортировку, хеш-функции, структуры данных — с 27 ноября по 9 декабря. Для получения зачета по задачам из листка нужно решить их все письменно и защитить устно. UPDATE: Исправлена опечатка в задаче 2.
- Обход в глубину и ширину — с 3 по 10 декабря (со штрафом 50% — с 11 по 16 декабря).
- Алгоритм Дейкстры — с 10 по 17 декабря.
- Задачи на динамическое программирование — с 11 по 18 декабря. Для получения зачета по задачам из листка нужно решить обе задачи письменно и защитить устно.
Экзамен
Экзамен состоится 19 декабря в 15:10 – 18:00. На экзамене нужно будет решить несколько задач в системе Яндекс.Контест. Желательно прийти со своим ноутбуком. Если у вас нет такой возможности, отметьтесь, пожалуйста, здесь.
Те, кто собирается писать экзамен на своем ноутбуке, приходят в ауд. 317 (группы 182, 184, 185, 186) и в ауд. 205 (группы 187, 188, 189). Те, кому нужны компьютеры, приходят в ауд. 311.
Третий модуль
Лекции
понедельник, четверг 15:10 – 16:30, ауд. 622
- 1 апреля. Приоритетные очереди и их применение в алгоритмах Дейкстры и Прима. Реализация приоритетной очереди при помощи двоичной кучи.
- 4 апреля. Три подхода к амортизационному анализу: групповой анализ, банковский метод и метод потенциалов (на примере двоичного счетчика и очереди на основе двух стеков).
- 8 апреля. Биномиальные кучи.
- 11 апреля. Кучи Фибоначчи.
- 16 апреля. Алгоритм Крускала и система непересекающихся множеств.
- 18 апреля. Наименьшее значение в подмассиве: простые алгоритмы (линейный поиск, предподсчет всех возможных ответов), разбиение на блоки, разреженные таблицы, комбинирование структур данных для вычисления наименьших значений внутри блоков и наименьшего значения в массиве минимумов в блоках.
Домашние задания
- Двоичная куча и ее применение — с 8 по 14 апреля (со штрафом 50% — с 15 по 21 апреля). Требуется реализовать и использовать двоичную кучу при решении хотя бы двух задач.
- Домашнее задание состоит из четырех задач контеста и шести задач, которые нужно решить письменно. Срок выполнения — 30 апреля.
Литература
Дасгупта С., Пападимитриу Х., Вазирани У. Алгоритмы. — М.: МЦНМО, 2014.
Клейнберг Дж., Тардос Е. Алгоритмы: разработка и применение. — СПб.: Питер, 2016.
Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ. — 3-е издание — М.: Вильямс, 2013.
Студенческие конспекты: 2015 г., 2016 г., 2017 г.
Оценки
Второй модуль
Текущая оценка: контрольная работа — 40%, домашние задания — 60%.
Промежуточная оценка: экзамен — 40%, текущая оценка — 60%.
Четвертый модуль
Накопленная оценка: контрольная работа — 50%, домашние задания — 50%.
Итог
Завершающая накопленная оценка: среднее промежуточной оценки за второй модуль и накопленной оценки за четвертый модуль.
Итоговая оценка: экзамен — 25%, завершающая накопленная оценка — 75%.