Алгоритмы и структуры данных 2016

Лектор: С. Объедков

Расписание лекций:
вторник 13:40 – 15:00, ауд. 622
четверг 10:30 – 11:50, ауд. 622

28 и 30 апреля лекций не будет

Программа дисциплины

Содержание

1 Лекции
2 Домашние задания
3 Экзамен
4 Рекомендуемая литература
5 Преподаватели и ассистенты
6 Учебные контесты

Лекции

12 января. Структура курса, правила выполнения домашних заданий. Рекурсивные алгоритмы: задача о Ханойской башне. Оценка времени работы рекурсивного алгоритма при помощи рекуррентного соотношения. Доказательство оптимальности рекурсивного алгоритма.

14 января. Сортировка вставкой и слиянием. Использование инварианта цикла при доказательстве корректности сортировки вставкой. Θ- и O-обозначения. Оценка сложности алгоритмов.

19 января. О-, o-, Ω-, ω-, Θ-обозначения. Быстрая сортировка, время работы в худшем, лучшем и среднем случаях.

21 января. Сортировка при помощи двоичного дерева поиска и ее связь с быстрой сортировкой. Примеры решения рекуррентных соотношений: решение с использованием дерева рекурсии и методом подстановки. Основная теорема.

26 января. Разбиение массива по опорному элементу на три части (элементы, меньшие опорного, равные опорному и большие опорного). Оптимальность сортировки слиянием. Выбор порядковой статистики за время O(n): рандомизированный и детерминированный алгоритмы.

28 января. Поиск ближайшей пары точек за время O(n logn).

2 февраля. Алгоритм Карацубы для умножения целых чисел. Алгоритм Штрассена для умножения матриц.

4 февраля. Быстрое возведение в степень по модулю. Динамическое программирование: выравнивание абзаца по ширине (рекурсивное решение с мемоизацией).

9 февраля. Динамическое программирование. Задача о планировании взвешенных интервалов: рекурсивное решение с мемоизацией и итеративное решение. Свойства задач, эффективно решаемых при помощи динамического программирования: наличие полиномиального числа подзадач, выразимость исходной задачи в терминах подзадач, сводимость больших подзадач к полиномиальному числу меньших подзадач. Выравнивание абзаца по ширине: итеративное решение. (Контест)

11 февраля. Вычисление редакционного расстояния и выравнивание последовательностей.

16 февраля. Графы: обход в глубину и в ширину, поиск компонент связности в неориентированных графах.

18 февраля. Способы представления графов: матрица смежности и списки смежности. Оценка сложности алгоритмов поиска в ширину и в глубину.

25 февраля. Топологическая сортировка за линейное время: алгоритмы, основанные на удалении вершин без входящих ребер (с доказательством корректности) и на поиске в глубину (без доказательства корректности). Вычисление компонент сильной связности (с незаконченным доказательством корректности).

1 марта. Оценка сложности алгоритма поиска компонент связности в неориентированных графах. Алгоритм проверки сильной связности ориентированного графа. Вычисление компонент сильной связности в ориентированном графе (завершение доказательства корректности алгоритма). Поиск путей возведением в степень матрицы смежности графа, алгоритм Флойда – Уоршелла.

3 марта. Алгоритм Флойда – Уоршелла: формулировка в терминах динамического программирования, оценка сложности, оптимизация по памяти, обнаружение циклов с отрицательным весом, восстановление кратчайших путей. Алгоритм Беллмана – Форда для графов без циклов с отрицательным весом.

10 марта. Приложения алгоритмов на графах: решение систем разностных ограничений при помощи алгоритма Беллмана – Форда, проверка выполнимости 2-КНФ на основе поиска компонент сильной связности.

15 марта. Структуры данных. Массив с операциями инициализации, чтения и записи, выполняемыми за время O(1). Три подхода к амортизационному анализу: групповой анализ, банковский метод и метод потенциалов (на примере двоичного счетчика).

17 марта. Хеш-таблицы. Методы задания хеш-функций. Разрешение коллизий при помощи цепочек. Открытая адресация.

22 марта. Двухуровневое идеальное хеширование. Сбалансированные деревья поиска. Пример — красно-черные деревья.

24 марта. Построение красно-черного дерева. Самоорганизующиеся списки и конкурентный анализ онлайн-алгоритмов.

5 апреля. Деревья отрезков. Динамические порядковые статистики.

7 апреля. Жадные алгоритмы. Примеры: (1) выбор максимального подмножества непересекающихся интервалов; (2) разбиение множества интервалов на минимальное число подмножеств непересекающихся интервалов.

12 апреля. Алгоритм Дейкстры.

14 апреля. Реализация приоритетной очереди при помощи двоичной кучи.

19 апреля. Минимальные остовные деревья. Алгоритм Крускала, алгоритм Прима и алгоритм, удаляющий самые тяжелые ребра.

21 апреля. Система непересекающихся множеств.

28 и 30 апреля лекций не будет.

10 мая. Жадный алгоритм на матроиде.

12 мая. Конечные автоматы. Регулярные языки. Замкнутость регулярных языков по объединению. Минимизация конечного автомата.

17 мая. Регулярные выражения. Недетерминированные конечные автоматы. Замкнутость регулярных языков относительно регулярных операций. Построение конечного автомата по регулярному выражению.

19 мая. Эквивалентность регулярных выражений и конечных автоматов. Нерегулярные языки. Лемма о накачке.

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

Первое домашнее задание

Первое домашнее задание стоит из двух частей.

К 15 февраля нужно решить три задачи на асимптотику (две — из пункта 1 и одну — из пункта 2) и две задачи на рекуррентные соотношения (одну — из пункта 1 и одну — из пункта 2). Какие именно задачи нужно решить, уточните, пожалуйста, у преподавателя, ведущего практические занятия. Крайний срок выполнения задач может немного различаться в разных подгруппах.

К 20 февраля нужно решить две задачи из контеста (одну — типа A и одну — типа B; какие именно, определяет преподаватель, ведущий практические занятия). Решение необходимо снабдить описанием алгоритма, обоснованием корректности и анализом асимптотической сложности.

Второе домашнее задание

Ко 2 марта (!) нужно решить две задачи из контеста (одну — типа A и одну — типа B; какие именно, определяет преподаватель, ведущий практические занятия). Решение необходимо снабдить описанием алгоритма, обоснованием корректности и анализом асимптотической сложности. Начало контеста — 22 февраля, 20:00.

К 15 марта (!) нужно решить две задачи из контеста (одну — типа A и одну — типа B; какие именно, определяет преподаватель, ведущий практические занятия). Решение необходимо снабдить описанием алгоритма, обоснованием корректности и анализом асимптотической сложности. Начало контеста — 4 марта, 20:00.

Разбор задачи B1 есть здесь: https://yadi.sk/i/9E41IqipqSF6h.

Третье домашнее задание

К 3 апреля нужно решить две задачи из контеста (одну — типа A и одну — типа B; какие именно, определяет преподаватель, ведущий практические занятия). Решение необходимо снабдить описанием алгоритма, обоснованием корректности и анализом асимптотической сложности.

К 28 апреля (!) нужно решить две задачи из контеста (одну типа A и одну — типа B; какие именно, определяет преподаватель, ведущий практические занятия). Решение необходимо снабдить описанием алгоритма, обоснованием корректности и анализом асимптотической сложности.

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

Четвертое домашнее задание

К 22 мая нужно решить задачи из контеста (по одной каждого типа; какие именно, определяет преподаватель, ведущий практические занятия). Решение необходимо снабдить описанием алгоритма, обоснованием корректности и анализом асимптотической сложности. За каждую из четырех задач можно получить до трех баллов (но максимальная оценка за всю домашнюю работу — десять баллов).

Проверка стиля

Используется следующий cpplint, флаги: --filter=-,+build/include,+build/include_alpha,+build/include_order,+build/include_what_you_use,+build/namespaces,+build/storage_class, +dangerous/digits_in_names,+dangerous/no_braces_for, +readability/braces,+readability/casting,+readability/fn_size,+readability/macros,+readability/preincrement,+readability/utf8, +restrictions/defines,+restrictions/forbidden_class_usage, +runtime/arrays,+runtime/casting, +whitespace/blank_line,+whitespace/blank_line_between_globals,+whitespace/braces,+whitespace/comma,+whitespace/comments, +whitespace/empty_loop_body,+whitespace/end_of_line,+whitespace/ending_newline,+whitespace/forcolon,+whitespace/indent, +whitespace/line_length,+whitespace/newline,+whitespace/operators,+whitespace/parens,+whitespace/semicolon,+whitespace/tab.

Набор запрещенных классов зависит от пройденных тем. На данный момент это std::set, std::map (а также их multi версии) и std::priority_queue.

Экзамен

Преподаватели и ассистенты

Подгруппа	Преподаватель	Учебные ассистенты	Семинары	Консультации
152-1	Михаил Нокель	Андрей Атанов
152-2	Сергей Объедков	Андрей Климкин	Страница семинаров	Понедельник, 10:30 – 11:50, ауд. 511
154-1	Илья Макаров	Владимир Гончаров
154-2	Алексей Умнов	Павел Белов	Страница семинаров	Четверг, 13:40 - 15:00
155-1	Михаил Дектярев	Александр Тиунов
155-2	Павел Мельничук	Александр Тиунов	Страница семинаров
156-1	Филипп Синицын	Максим Сабянин
156-2	Алексей Умнов	Павел Белов	Страница семинаров	Четверг, 9:00 - 10:20
157-1	Михаил Густокашин	Андрей Климкин
157-2	Яна Кашинская	Андрей Атанов		Понедельник, 10:30 – 11:50
158-1	Николай Субоч	Максим Сабянин
158-2	Денис Симагин	Владимир Гончаров	Страница семинаров