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

План лекций

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Резерв

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

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

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

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

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

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

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

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