Дисциплина «Алгоритмы и структуры данных» ИВТ УлГТУ: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Строка 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 Видео: Двумерная динамика: Редакционное расстояние]
 
* Структуры данных. Расширяющийся массив. Список
 
* Структуры данных. Расширяющийся массив. Список
 
* Стек. Очередь. Очередь с приоритетами
 
* Стек. Очередь. Очередь с приоритетами

Версия 15:06, 17 сентября 2015

План лекций

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

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

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

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