Дисциплина «Алгоритмы и структуры данных» ИВТ УлГТУ

Новости и замечания

Для более быстрой связи лучше использовать v.folunin@gmail.com вместо v.folunin@ulstu.ru (со второго адреса пересылка выполняется не так оперативно).

Ответы редакции на письма читателей

О компараторах

Вопрос: Когда для сортировки я использую компаратор вида return a.x < b.x;, всё работает, но стоит мне изменить компаратор на return a.x <= b.x;, как я получаю ошибку «invalid comparator». С чем это связано?

Ответ: Компаратор f(a, b) для функции sort() (а также для set и map) должен определять строгий частичный порядок (strict weak ordering) на элементах множества. Это означает, что должны выполняться следующие свойства:

Антирефлексивность: всегда f(a, a) == false (ни один элемент не может идти до самого себя);
Антисимметричность: если f(a, b) == true, то f(b, a) == false (если a идёт до b, то b не может идти до a);
Транзитивность: если f(a, b) == true и f(b, c) == true, то f(a, c) == true (если a идёт до b, а b — до c, то a идёт до c).

Функция sort() использует компаратор так:

Если f(a, b), то a «меньше» b;
Если !f(a, b) и f(b, a), то a «больше» b;
Если !f(a, b) и !f(b, a), то a «равно» b.

Сортировка не сможет упорядочить элементы правильно, если одновременно будут истинны f(a, b) и f(b, a). Если используется компаратор вида return a.x <= b.x;, то при одинаковых значениях x у разных элементов эти элементы не смогут быть упорядочены, так как получается, что каждый из них должен идти перед другим (не говоря уже о сравнении элемента с самим собой). Поэтому возникает исключение.

Материалы по программированию на C++

Лекции

Конспект

Конспект лекций

В 2016 г. составлялся студентами. В настоящее время неспешно переписывается преподавателем.

План

Сложность алгоритмов. Сортировки

Правила асимптотического анализа алгоритмов. Асимптотические обозначения. Основные классы сложности.

Сортировки: выбором, вставками, слиянием, быстрая. Ω-оценка для сортировок сравнением.

Устойчивость сортировок. Сортировки за линейное время: подсчётом, поразрядная.

Бинарный поиск

Бинарный поиск элемента в отсортированном массиве. Поиск первого и последнего вхождения.

Бинарный поиск по ответу.

Вещественный бинарный поиск.

Тернарный поиск.

Динамическое программирование. Жадные алгоритмы

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

Жадные алгоритмы. Принцип жадного выбора. Задачи: непрерывный рюкзак, выбор заявок, размен монет, коды Хаффмана.

Динамическое программирование. Критерии применимости ДП. Ленивая рекурсия и просмотр вперёд. Восстановление решения.

Виды одномерной и двумерной динамики.

Краткие видео по динамическому программированию: 1 2 3 4 5 6 7

Структуры данных. Расширяющийся массив. Список

Смежные и связные структуры данных. Работа с классами и динамической памятью.

Понятие амортизированной сложности. Стратегии реализации динамического массива.

Реализации списков.

Сравнение быстродействия основных операций для массивов и списков.

Стек. Очередь. Очередь с приоритетами

Стек LIFO: реализация на массиве и связном списке. Классические приложения стека.

Очередь FIFO: реализация на циклическом массиве и связном списке. Классические приложения очереди. Дек.

Интерфейс очереди с приоритетами. Двоичная куча.

Деревья. Хеш-таблицы

Интерфейс АТД «Множество» и «Словарь».

Двоичные деревья поиска. Поиск, добавление и удаление элементов: рекурсивная и нерекурсивная реализация.

Принципы функционирования хеш-таблиц. Разрешение коллизий: метод цепочек, открытая адресация.

Балансирующиеся деревья

Недостатки наивной реализации двоичного дерева поиска.

Обзор балансирующихся деревьев: 2-3-, красно-чёрные и AA-деревья.

Декартово дерево. Реализация интерфейса АТД «Множество» и «Словарь».

Множественные операции в декартовом дереве.

Графы. Поиск в глубину

Представление графа. Матрица смежности, списки смежности, список рёбер.

Поиск в глубину.

Компоненты связности.

Поиск циклов.

Топологическая сортировка.

Компоненты сильной связности.

Поиск мостов.

Кратчайшие пути

Кратчайшие пути в невзвешенном графе. Поиск в ширину.

Кратчайшие пути в графе с неотрицательными весами. Алгоритм Дейкстры за O(V²) и за O(ElogV).

Кратчайшие пути в ациклических орграфах.

Кратчайшие пути в графе с отрицательными весами. Алгоритм Форда-Беллмана.

Кратчайшие пути между всеми парами вершин. Алгоритм Флойда.

Проверка графа на наличие отрицательного цикла.

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

Алгоритм Прима.

Алгоритм Краскала.

Структура данных «Система непересекающихся множеств» и её эвристики.

Практика

К каждой лекции прилагается комплект задач на vtcloud9. Задачи можно решать на C++ или Java.

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

Курсовая работа

Экзамен

Таблица результатов дисциплины

О выставлении бонусных баллов за плагиат

По каждой задаче, кроме 8E, автоматически формируется сводка данных об идентичности решений (пример).

Если два автора имеют по некоторой задаче два решения, совпадающие на 80% или более, то каждый из авторов получает по этой задаче 1 бонусный балл.

Каждый бонусный балл сокращает итоговую оценку за практическую работу в семестре на 2 (другими словами, нивелирует 2 сданные задачи).

Важно: преподаватель намеренно воздержался от того, чтобы самостоятельно анализировать подозрительные случаи. Получить 1-2 бонусных балла — это нормально, и ожидается, что сдавшие большую часть задач не пострадают, даже если антиплагиат ошибётся. Если у вас есть претензии к результатам, готовьтесь обсуждать их на консультации.

Оценки

Оценка за практическую работу в семестре рассчитывается по количеству сданных задач (с учётом баллов антиплагиата). Всего в семестре было предложено 64 задачи.

70% сданных задач (45 и более) — оценка «Отлично»;
50% сданных задач (32 и более) — оценка «Хорошо»;
30% сданных задач (19 и более) — оценка «Удовлетворительно»;

Оценка за курсовую работу учитывает выбранную сложность работы и выставляется по результатам защиты.

Для допуска к экзамену необходимо иметь оценки не ниже «Удовлетворительно» за практическую работу в семестре и за курсовую работу.

Максимальная оценка, которую можно получить на экзамене, рассчитывается как сумма оценок за практическую работу в семестре и за курсовую работу, делённая на 2 и округлённая вверх.

Примерный список экзаменационных вопросов

В любом билете может быть задан дополнительный вопрос вида:

Какое назначение у этого алгоритма (структуры данных)?
Какая асимптотическая оценка у этого алгоритма (этой операции)?

Асимптотический анализ алгоритмов.

Отсортируйте оценки сложности от наиболее эффективных к наименее эффективным
Дайте O-оценку для следующего кода
Дайте оценки для следующего графика
Какую сложность должен иметь алгоритм, если размер входных данных равен <...>, а ограничение времени составляет около 1 с?

Квадратичные сортировки

Нарисуйте шаги сортировки выбором (вставками) для заданного массива
Напишите (псевдо)код и дайте оценки сортировки выбором (вставками)

Эффективные сортировки

Нарисуйте шаги сортировки слиянием (быстрой) для заданного массива
Нарисуйте шаги слияния двух заданных массивов
Напишите (псевдо)код процедуры слияния
Нарисуйте шаги разделения заданного массива по опорному элементу
Составьте контрпример к быстрой сортировке, если опорный элемент выбирается указанным образом
Напишите (псевдо)код сортировки подсчётом

Бинарный поиск. Тернарный поиск.

Напишите (псевдо)код поиска первого (последнего) вхождения элемента в отсортированный массив
Решите с помощью бинарного поиска следующую задачу: <...>
Напишите (псевдо)код поиска минимума (максимума) функции с одним экстремумом
Решите с помощью тернарного поиска следующую задачу: <...>

Жадные алгоритмы и динамическое программирование

Задача <...> решается следующим жадным алгоритмом: <...>. Составьте контртест
Решите с помощью динамического программирования следующую задачу: <...>. Нарисуйте таблицу мемоизации
Покажите, как по таблице мемоизации восстановить оптимальный ответ (например, оптимальный путь)

Массивы и списки. Стек. Очередь

Нарисуйте таблицу основных операций массивов и списков с оценками
Напишите (псевдо)код реализации расширяющегося массива
Напишите (псевдо)код реализации стека (очереди) на односвязном списке

Очередь с приоритетами. Куча.

Нарисуйте таблицу основных операций очереди с приоритетами с оценками
Нарисуйте шаги добавления в кучу следующих ключей: <...>
Нарисуйте шаги извлечения из кучи трёх элементов
Напишите (псевдо)код операции up (down)

Реализация ассоциативных массивов. Деревья, хеш-таблицы.

Нарисуйте таблицу основных операций деревьев и хеш-таблиц с оценками для лучшего и худшего случаев
Нарисуйте шаги добавления в небалансирующееся двоичное дерево поиска следующих ключей: <...>
Нарисуйте шаги поиска в дереве следующих ключей: <...>
Нарисуйте шаги добавления в хеш-таблицу с указанной хеш-функцией следующих ключей: <...>
Нарисуйте шаги поиска в хеш-таблице следующих ключей: <...>
Покажите различные стратегии разрешения коллизий в хеш-таблицах

Основные определения теории графов. Способы задания графов

Составьте матрицу смежности, списки смежности и список рёбер для указанного графа
В задаче требуется производить с графом следующие операции: <...> Какой способ хранения графа следует выбрать?

Поиск в глубину и его приложения

Нарисуйте шаги поиска в глубину на указанном графе
Напишите (псевдо)код поиска в глубину для указанной задачи (подсчёта компонент связности, поиска циклов и т. п.)
Найдите топологическую сортировку указанного графа

Кратчайшие пути

Какой алгоритм следует применить для поиска кратчайших путей на указанном графе?
Нарисуйте шаги поиска в ширину на указанном графе
Напишите (псевдо)код поиска в ширину
Нарисуйте шаги алгоритма Дейкстры на указанном графе
Нарисуйте шаги алгоритма Форда-Беллмана на указанном графе
Покажите, как восстановить оптимальный путь