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

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску

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

Лекции

Конспект

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

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

План

  • Сложность алгоритмов. Сортировки
Правила асимптотического анализа алгоритмов. Асимптотические обозначения. Основные классы сложности.
Сортировки: выбором, вставками, слиянием, быстрая. Ω-оценка для сортировок сравнением.
Устойчивость сортировок. Сортировки за линейное время: подсчётом, поразрядная.
  • Бинарный поиск
Бинарный поиск элемента в отсортированном массиве. Поиск первого и последнего вхождения.
Бинарный поиск по ответу.
Вещественный бинарный поиск.
Тернарный поиск.
  • Динамическое программирование. Жадные алгоритмы
Решение задач комбинаторной оптимизации: полный перебор и методы его сокращения.
Жадные алгоритмы. Принцип жадного выбора. Задачи: непрерывный рюкзак, выбор заявок, размен монет, коды Хаффмана.
Динамическое программирование. Критерии применимости ДП. Ленивая рекурсия и просмотр вперёд. Восстановление решения.
Виды одномерной и двумерной динамики.
Краткие видео по динамическому программированию: 1 2 3 4 5 6 7
  • Структуры данных. Расширяющийся массив. Список
Смежные и связные структуры данных. Работа с классами и динамической памятью.
Понятие амортизированной сложности. Стратегии реализации динамического массива.
Реализации списков.
Сравнение быстродействия основных операций для массивов и списков.
  • Стек. Очередь. Очередь с приоритетами
Стек LIFO: реализация на массиве и связном списке. Классические приложения стека.
Очередь FIFO: реализация на циклическом массиве и связном списке. Классические приложения очереди. Дек.
Интерфейс очереди с приоритетами. Двоичная куча.
  • Деревья. Хеш-таблицы
Интерфейс АТД «Множество» и «Словарь».
Двоичные деревья поиска. Поиск, добавление и удаление элементов: рекурсивная и нерекурсивная реализация.
Принципы функционирования хеш-таблиц. Разрешение коллизий: метод цепочек, открытая адресация.
  • Балансирующиеся деревья
Недостатки наивной реализации двоичного дерева поиска.
Обзор балансирующихся деревьев: 2-3-, красно-чёрные и AA-деревья.
Декартово дерево. Реализация интерфейса АТД «Множество» и «Словарь».
Множественные операции в декартовом дереве.
  • Графы. Поиск в глубину
Представление графа. Матрица смежности, списки смежности, список рёбер.
Поиск в глубину.
Компоненты связности.
Поиск циклов.
Топологическая сортировка.
Компоненты сильной связности.
Поиск мостов.
  • Кратчайшие пути
Кратчайшие пути в невзвешенном графе. Поиск в ширину.
Кратчайшие пути в графе с неотрицательными весами. Алгоритм Дейкстры за O(V2) и за O(ElogV).
Кратчайшие пути в ациклических орграфах.
Кратчайшие пути в графе с отрицательными весами. Алгоритм Форда-Беллмана.
Кратчайшие пути между всеми парами вершин. Алгоритм Флойда.
Проверка графа на наличие отрицательного цикла.
  • Минимальный остов. Система непересекающихся множеств
Алгоритм Прима.
Алгоритм Краскала.
Структура данных «Система непересекающихся множеств» и её эвристики.

Практика

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

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

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

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

Экзамен

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