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

План лекций

Конспект лекций, составляемый студентами

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

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

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

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

• Бинарный поиск (19.09.2016)

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

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

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

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

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

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

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

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

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

Видео: План решения задачи методом динамического программирования

Видео: Одномерная динамика. Количество путей в полосе

Видео: Одномерная динамика. Оптимальный путь в полосе

Видео: Одномерная динамика с привязкой. Наибольшая возрастающая подпоследовательность

Видео: Двумерная динамика. Задача о рюкзаке

Видео: Двумерная динамика. Наибольшая общая подпоследовательность

Видео: Двумерная динамика: Редакционное расстояние

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблицы успеваемости групп

• Успеваемость группы АП
• Успеваемость группы ВМ

Таблицы обновляются после практических занятий.

Текущий сервер дорешивания — vtcloud9

Сайты, помогающие улучшить навык программирования

• Цикл задач «Язык программирования C++» на acmp.ru (множество простых задач, решение каждой из которых можно уточнить у Владимира Александровича)
• Открытый курс «Введение в программирование» от Яндекса и Высшей школы экономики на stepik.org (видеолекции и задачи по разным темам, от простых до сложных)

Задания на курсовые работы

Задания на курсовые работы и требования к выполнению описаны в отдельной статье.

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

1. Правила асимптотического анализа алгоритмов. Асимптотические обозначения.
2. Сортировка выбором. Сортировка вставками.
3. Сортировка слиянием.
4. Быстрая сортировка.
5. Сортировка подсчётом. Поразрядная сортировка.
6. Бинарный поиск. Бинарный поиск по ответу.
7. Вещественный бинарный поиск. Тернарный поиск.
8. Жадные алгоритмы. Примеры. Принцип жадного выбора.
9. Динамическое программирование. Примеры. Критерии применимости ДП.
10. Массивы и списки: сравнение. Расширяющийся массив.
11. Стек. Очередь.
12. Очередь с приоритетами. Куча.
13. Сортировка кучей.
14. Реализация ассоциативных массивов. Деревья, хеш-таблицы.
15. Основные определения теории графов. Способы задания графов. Поиск в глубину.
16. Поиск компонент связности. Поиск циклов.
17. Топологическая сортировка. Поиск компонент сильной связности.
18. Поиск в ширину.
19. Алгоритм Дейкстры.
20. Алгоритм Форда-Беллмана.
21. Поиск кратчайших путей в ациклических ориентированных графах.
22. Алгоритм Флойда.

Решение проблем с локалью при вводе/выводе вещественных чисел

На сервере по умолчанию используется русская локаль, что может порождать Runtime Error при чтении и Wrong Answer при выводе вещественных чисел на C# и Java (так как в качестве разделителя вместо точки ожидается запятая).

Для восстановления локали на C# следует использовать следующий код:

/* добавить в начало файла: */
using System.Threading;
using System.Globalization;

/* добавить в основной функции: */
Thread.CurrentThread.CurrentCulture = CultureInfo.InvariantCulture;

Для восстановления локали на Java следует использовать следующий код:

/* пример ввода: */
Scanner in = new Scanner(System.in);
in.useLocale(new Locale("US"));
double x = in.nextDouble();

/* пример вывода: */
System.out.printf(Locale.US, "%.4f", x);