Дисциплина «Алгоритмы и структуры данных» ИВТ УлГТУ
Перейти к навигации
Перейти к поиску
План лекций
- Сложность алгоритмов. Сортировки (02.09.2015)
- Правила асимптотического анализа алгоритмов. Асимптотические обозначения. Основные классы сложности.
- Сортировки: выбором, вставками, слиянием, быстрая. Ω-оценка для сортировок сравнением.
- Устойчивость сортировок. Сортировки за линейное время: подсчётом, поразрядная.
- Бинарный поиск (07.09.2015)
- Бинарный поиск элемента в отсортированном массиве. Поиск первого и последнего вхождения.
- Бинарный поиск по ответу.
- Вещественный бинарный поиск.
- Тернарный поиск.
- Динамическое программирование. Жадные алгоритмы (16.09.2015)
- Решение задач комбинаторной оптимизации: полный перебор и методы его сокращения.
- Жадные алгоритмы. Принцип жадного выбора. Задачи: непрерывный рюкзак, выбор заявок, размен монет, коды Хаффмана.
- Динамическое программирование. Критерии применимости ДП. Ленивая рекурсия и просмотр вперёд. Восстановление решения.
- Виды одномерной и двумерной динамики.
- Видео: План решения задачи методом динамического программирования
- Видео: Одномерная динамика. Количество путей в полосе
- Видео: Одномерная динамика. Оптимальный путь в полосе
- Видео: Одномерная динамика с привязкой. Наибольшая возрастающая подпоследовательность
- Видео: Двумерная динамика. Задача о рюкзаке
- Видео: Двумерная динамика. Наибольшая общая подпоследовательность
- Видео: Двумерная динамика: Редакционное расстояние
- Структуры данных. Расширяющийся массив. Список
- Стек. Очередь. Очередь с приоритетами
- Деревья. Хеш-таблицы
- Балансирующиеся деревья
- Графы. Поиск в глубину
- Кратчайшие пути
- Минимальный остов. Система непересекающихся множеств
- Другие задачи теории графов
- Резерв
Таблицы успеваемости групп
Таблицы обновляются после практических занятий.
Текущий сервер дорешивания — vtcloud9