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

План лекций

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Другие задачи теории графов

• Резерв

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

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

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

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

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

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

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

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

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

На сервере по умолчанию используется русская локаль, что может порождать 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);