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

План лекций

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Структуры данных. Расширяющийся массив. Список
• Стек. Очередь. Очередь с приоритетами
• Деревья. Хеш-таблицы
• Балансирующиеся деревья
• Графы. Поиск в глубину
• Кратчайшие пути
• Минимальный остов. Система непересекающихся множеств
• Другие задачи теории графов
• Резерв

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

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

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

Текущий сервер дорешивания — 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);