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

О курсе

Лектор: Объедков Сергей Александрович

Лекции

Конспект Ярослава Сергиенко.

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

16 января: О-, o-, Ω-, ω-, Θ-обозначения. Быстрая сортировка, время работы в худшем, лучшем и среднем случаях. Оптимальность сортировки слиянием. Сортировка при помощи двоичного дерева поиска и ее связь с быстрой сортировкой.

20 января: Примеры решения рекуррентных соотношений: решение с использованием дерева рекурсии и методом подстановки. Формулировка и интуитивное объяснение основной теоремы. (Конспект.)

23 января: Выбор порядковой статистики за время O(n): рандомизированный и детерминированный алгоритмы.

27 января: Быстрое возведение в степень по модулю. Алгоритм Карацубы для умножения целых чисел. Алгоритм Штрассена для умножения матриц.

30 января: Поиск ближайшей пары точек за время O(nlog n). Задача о планировании взвешенных интервалов: рекурсивное решение.

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

6 февраля: Лекция отменяется из-за болезни преподавателя, но будет компенсирована 11 апреля.

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

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

17 февраля: Способы представления графов: матрица смежности и списки смежности. Оценка сложности алгоритмов поиска в ширину и глубину, поиска компонент связности в неориентированных графах. Связность в ориентированных графах, алгоритм проверки сильной связности ориентированного графа.

20 февраля: Топологическая сортировка. Вычисление компонент сильной связности в ориентированном графе.

24 февраля: Поиск кратчайших путей во взвешенном графе: алгоритмы Беллмана – Форда и Флойда – Уоршелла.

27 февраля: Выполнимость 2-КНФ и компоненты сильной связности. Перемножение матриц, поиск пути через промежуточную точку и алгоритм Флойда – Уоршелла.

3 марта: Лекция переносится на 11 апреля.

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

10 марта: Алгоритм Дейкстры.

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

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

20 марта: Минимальные основные деревья. Алгоритмы Крускала, Прима и Reverse-Delete.

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

3 апреля: Сжатие путей в системе непересекающихся множеств. Кластеризация и алгоритм Крускала.

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

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

11 апреля: Алгоритм Эдмондса – Карпа.

14 апреля: Двойственность задач о максимальном потоке и минимальном разрезе. Сведение задачи о максимальном паросочетании в двудольном графе к задаче о максимальном потоке.

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

21 апреля: Рандомизированный алгоритм поиска минимального разреза (алгоритм Каргера). Простой рандомизированный алгоритм для вычисления означивания переменных, максимизирующего число истинных дизъюнктов в 3-КНФ: случайное означивание гарантирует истинность 7/8 всех дизъюнктов в среднем.

24 апреля: Хеш-таблицы. Разрешение коллизий при помощи цепочек. Открытая адресация.

28 апреля: Сбалансированные деревья поиска. Красно-черные деревья.

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

15 мая: Конечные автоматы. Регулярные языки. Эквивалентность детерминированных и недетерминированных автоматов. Замкнутость регулярных языков относительно регулярных операций.

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

22 мая: Доказательство леммы о накачке и ее использование для доказательства нерегулярности языков. Полиномиальные сведения. Задачи о вершинном покрытии графа, покрытии множества и независимом множестве.

26 мая: Классы P и NP. Понятие NP-полной задачи. Теорема Кука – Левина, идея доказательства. Доказательство NP-полноты задачи о независимом множестве сведением к ней задачи о выполнимости 3-КНФ.

29 мая: Приближенные алгоритмы. 2-аппроксимация минимального вершинного покрытия и кратчайшего циклического маршрута. Существование задач, для которых константная аппроксимация возможна, только если P = NP (максимальное независимое множество, максимальная клика). PTAS для задачи о рюкзаке.

2 июня: Введение в архитектуру ЭВМ.

5 июня: Низкоуровневое программирование.

9 июня: Взаимодействие с внешними устройствами.

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

Задание 1

Необходимо сдать все 6 задач в данном контесте. На выполнение задания даётся 2 недели (см. точное время окончания в контесте). Условия ревью определяют семинаристы.

Задание 2

Контест. В домашнем задании пять задач, из которых нужно решить три, назначенные преподавателем, ведущим семинарские занятия в вашей группе. На выполнение задания даётся примерно 2 недели (см. точное время окончания в контесте). Условия ревью определяют семинаристы. Дорешивание.

Задание 3

Контест. В домашнем задании пять задач. Они разделены на два варианта, помеченные римскими цифрами I и II. Свой вариант нужно узнать у семинариста. Третья задача — общая для двух вариантов; ее решение необходимо снабдить доказательством корректности алгоритма. На выполнение задания даётся примерно 2 недели (см. точное время окончания в контесте). Условия ревью определяют семинаристы.

Задание 4

Контест. В домашнем задании четыре задачи. Обязательны первые три. Вместо одной из первых трёх можно сделать последнюю (только для первых 10 решивших 4-ую!). На выполнение задания даётся примерно 2 недели (см. точное время окончания в контесте). Условия ревью определяют семинаристы.

Задание 5

Контест. На выполнение задания даётся примерно 2 недели (см. точное время окончания в контесте). Условия ревью определяют семинаристы. Также до 25 июня необходимо решить задачи и прислать решение своему семинаристу и его учебному ассистенту.

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

Контрольная работа состоится 11 апреля в 13:40 – 15:00 в ауд. 622. Примеры задач (и решений)].

Контрольная работа на получение зачёта по программистской части экзамена

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

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

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

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

Что будет, если я её напишу?

1. Если решение получило OK в контесте, студент получает зачёт по программистской части, которая составляет 20% от оценки за экзамен. На экзамене будут даны другие задачи на программирование. В отличие от контрольной, алгоритм напоминаться НЕ будет, поэтому проще сдать задачу на контрольной.

Что будет, если я её не напишу?

1. Вам придётся решать задачу на программирование на экзамене. Вы также сможете получить за неё максимальное число баллов (2).

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

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

Советы

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

Экзамен

Экзамен состоит из двух частей: “программирование” (2 балла из 10) и “теория” (8 баллов из 10).

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

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

Расписание экзамена 29 июня

Группа 101: 10:30 теория (ауд. 622), 13:40 программирование (ауд. 513)

Группа 102: 10:30 теория (ауд. 622), 13:40 программирование (ауд. 501)

Группа 103: 10:30 теория (ауд. 622), 13:40 программирование (ауд. 605)

Группа 104: 10:30 теория (ауд. 622), 13:40 программирование (ауд. 505)

Группа 105: 10:30 программирование (ауд. 501), 13:40 теория (ауд. 622)

Группа 106: 10:30 программирование (ауд. 513), 13:40 теория (ауд. 622)

Группа 107: 10:30 программирование (ауд. 505), 13:40 теория (ауд. 622)

Группа 108: 10:30 программирование (ауд. 605), 13:40 теория (ауд. 622)

Семинары

Подгруппа 101-1.
Подгруппа 101-2.
Подгруппа 102-1.
Подгруппа 102-2.
Подгруппа 103-1.
Подгруппа 105-1.
Подгруппа 106-1.
Подгруппа 106-2.
Подгруппа 107-1.
Подгруппа 107-2.

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

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

Полезные ссылки

1. Инструкция по использованию Review Board.