Алгоритмы и структуры данных 2016 — различия между версиями

Текущая версия на 17:47, 9 мая 2017

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

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

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

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

Лекции

• 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 мая. Эквивалентность регулярных выражений и конечных автоматов. Нерегулярные языки. Лемма о накачке.

• 24 мая. Контекстно-свободные грамматики. Автоматы с магазинной памятью.

• 26 мая. Эквивалентность контекстно-свободных грамматик и автоматов с магазинной памятью. Построение автомата по грамматике. Лемма о накачке для контекстно-свободных языков.

• 31 мая. Три подхода к реализации регулярных выражений: детерминированный автомат, поиск с возвратами в недетерминированном автомате, имитация детерминированного автомата по недетерминированному. Поиск подстрок при помощи конечного автомата. Разбор слов по контекстно-свободной грамматике: алгоритм динамического программирование для грамматики в нормальной форме Хомского.

• 2 июня. Максимальный поток. Алгоритм Форда – Фалкерсона.

• 7 июня. Алгоритм Эдмондса – Карпа. Двойственность задач о максимальном потоке и минимальном разрезе.

• 9 июня. Сведение задачи о максимальном паросочетании в двудольном графе к задаче о максимальном потоке. Устойчивые паросочетания и алгоритм Гейла – Шепли.

• 14 июня. Минимальный разрез в неориентированном графе. Алгоритм Каргера. Задача о назначениях (поиск совершенного паросочетания с минимальным весом во взвешенном двудольном графе). Алгоритм, последовательно находящий самые дешевые увеличивающие пути.

• 16 июня. Приближенные алгоритмы. PTAS для задачи о рюкзаке.

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

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

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

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

Если к 22 мая вы не успели решить все задачи, то вы еще можете прислать решения до истечения 27 мая, однако за каждую задачу, решенную после 22 мая, можно получить лишь один балл.

Пятое домашнее задание

К 6 (!) июня нужно решить четыре задачи на конечные автоматы (по одной из каждого пункта; какие именно, определяет преподаватель, ведущий практические занятия).

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

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

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

Используется следующий 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.

UPD 04.06.16: разрешены все классы.

Контрольная работа

Что будет на контрольной?

1. Будет одна задача на программирование.
2. Задача будет или на написание известного (вам) алгоритма, или на небольшую модификацию.

Как будет проходить контрольная?

1. Контрольная пройдёт на одном из последних семинаров по АиСД. Продолжительность: 1 час 20 минут, продлеваться НЕ будет. Форма: контест.
2. Задача выдается в начале пары, её сразу же можно начать решать, а для тех, кто не знает нужный алгоритм, семинарист параллельно на доске рассказывает идею алгоритма.
3. Запрещается использовать телефоны, планшеты и другие мобильные устройства.
4. Можно писать на своём ноутбуке.
5. На время пары, возможно, будет ограничен доступ к интернету, будeт доступен только Яндекс.Contest, cppreference.com.
6. Тесты будут открыты.

Какие правила? Чем можно пользоваться?

1. Работа индивидуальная.
2. Нельзя пользоваться никакими ресурсами, в том числе книгами (электронными или нет), pdf-ками, презентациями, распечатками, конспектом, своим старым кодом (в том числе в Яндекс.Contest) и пр.
3. Можно писать на своём ноутбуке.
4. Можно открывать только следующие сайты: Яндекс.Contest, cppreference.com.
5. За первое нарушение указанных правил работа аннулируется.
6. Если по какой-то причине вам необходимо воспользоваться почтой, телефоном и т.п., поднимите руку и спросите/предупредите семинариста.

Советы

1. Подготовьтесь к занятию, повторите все пройденные алгоритмы.
2. Заранее выпишите свои логин-пароль от Яндекс.Контеста, возможно, мы отключим интернет и у вас не будет доступа к ресурсу, где они сохранены.
3. Зайдите в класс пораньше, включите компьютер и залогиньтесь, чтобы не терять время.

Экзамен

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

Рекомендуемая литература

1. Кормен, Лейзерсон, Ривест, Штайн. Алгоритмы: построение и анализ
2. Дасгупта, Пападимитриу, Вазирани. Алгоритмы

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

Учебные контесты

Сортировки

Разделяй и властвуй + длинная арифметика

Динамическое программирование

Обход в глубину

Обход в ширину

Число путей

Кратчайшие расстояния

Хеширование

Красно-черные деревья

Минимальные остовные деревья

Максимальный поток