Дисциплина «Алгоритмы и структуры данных» ИВТ УлГТУ: различия между версиями
Перейти к навигации
Перейти к поиску
Ctrlalt (обсуждение | вклад) Нет описания правки |
Ctrlalt (обсуждение | вклад) Нет описания правки |
||
| Строка 7: | Строка 7: | ||
: Устойчивость сортировок. Сортировки за линейное время: подсчётом, поразрядная. | : Устойчивость сортировок. Сортировки за линейное время: подсчётом, поразрядная. | ||
* Бинарный поиск (07.09.2015) | * Бинарный поиск (07.09.2015) | ||
* Динамическое программирование. Жадные алгоритмы | : Бинарный поиск элемента в отсортированном массиве. Поиск первого и последнего вхождения. | ||
: Бинарный поиск по ответу. | |||
: Вещественный бинарный поиск. | |||
: Тернарный поиск. | |||
* Динамическое программирование. Жадные алгоритмы (16.09.2015) | |||
: Решение задач комбинаторной оптимизации: полный перебор и методы его сокращения. | |||
: Жадные алгоритмы. Принцип жадного выбора. Задачи: непрерывный рюкзак, выбор заявок, размен монет, коды Хаффмана. | |||
: Динамическое программирование. Критерии применимости ДП. Ленивая рекурсия и просмотр вперёд. Восстановление решения. | |||
: [[Динамическое программирование|Виды одномерной и двумерной динамики.]] | |||
:: [http://www.youtube.com/watch?v=SFeCrCme4tk Видео: План решения задачи методом динамического программирования] | |||
:: [http://www.youtube.com/watch?v=1h_3VYrpHFc Видео: Одномерная динамика. Количество путей в полосе] | |||
:: [http://www.youtube.com/watch?v=wuXC13OqcJ8 Видео: Одномерная динамика. Оптимальный путь в полосе] | |||
:: [http://www.youtube.com/watch?v=t2DpD9GnhfU Видео: Одномерная динамика с привязкой. Наибольшая возрастающая подпоследовательность] | |||
:: [http://www.youtube.com/watch?v=HtrgxH3feME Видео: Двумерная динамика. Задача о рюкзаке] | |||
:: [http://www.youtube.com/watch?v=-yiKNcjcK0Y Видео: Двумерная динамика. Наибольшая общая подпоследовательность] | |||
:: [http://www.youtube.com/watch?v=r6LRslQvveQ Видео: Двумерная динамика: Редакционное расстояние] | |||
* Структуры данных. Расширяющийся массив. Список | * Структуры данных. Расширяющийся массив. Список | ||
* Стек. Очередь. Очередь с приоритетами | * Стек. Очередь. Очередь с приоритетами | ||
Версия от 11:06, 17 сентября 2015
План лекций
- Сложность алгоритмов. Сортировки (02.09.2015)
- Правила асимптотического анализа алгоритмов. Асимптотические обозначения. Основные классы сложности.
- Сортировки: выбором, вставками, слиянием, быстрая. Ω-оценка для сортировок сравнением.
- Устойчивость сортировок. Сортировки за линейное время: подсчётом, поразрядная.
- Бинарный поиск (07.09.2015)
- Бинарный поиск элемента в отсортированном массиве. Поиск первого и последнего вхождения.
- Бинарный поиск по ответу.
- Вещественный бинарный поиск.
- Тернарный поиск.
- Динамическое программирование. Жадные алгоритмы (16.09.2015)
- Решение задач комбинаторной оптимизации: полный перебор и методы его сокращения.
- Жадные алгоритмы. Принцип жадного выбора. Задачи: непрерывный рюкзак, выбор заявок, размен монет, коды Хаффмана.
- Динамическое программирование. Критерии применимости ДП. Ленивая рекурсия и просмотр вперёд. Восстановление решения.
- Виды одномерной и двумерной динамики.
- Видео: План решения задачи методом динамического программирования
- Видео: Одномерная динамика. Количество путей в полосе
- Видео: Одномерная динамика. Оптимальный путь в полосе
- Видео: Одномерная динамика с привязкой. Наибольшая возрастающая подпоследовательность
- Видео: Двумерная динамика. Задача о рюкзаке
- Видео: Двумерная динамика. Наибольшая общая подпоследовательность
- Видео: Двумерная динамика: Редакционное расстояние
- Структуры данных. Расширяющийся массив. Список
- Стек. Очередь. Очередь с приоритетами
- Деревья. Хеш-таблицы
- Балансирующиеся деревья
- Графы. Поиск в глубину
- Кратчайшие пути
- Минимальный остов. Система непересекающихся множеств
- Другие задачи теории графов
- Резерв
Таблицы успеваемости групп
Таблицы обновляются после практических занятий.
Текущий сервер дорешивания — vtcloud9