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

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

Лекции

Конспект

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

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

План

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Практика

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

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

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

(будет добавлено позднее)

Экзамен