Видеолекции курса Алгоритмы и структуры данных. Часть 1.
Лектор: Александр Куликов.
Лекция 1. Введение.
Вычисление чисел Фибоначчи: экспоненциальный рекурсивный алгоритм, полиномиальный алгоритм, более детальный анализ. Время работы алгоритма, O-символика. Скорость роста функций: логарифм, полином, экспонента.
Посмотреть видео на сайте Лекториума
Лекция 2. Рекуррентные соотношения.
Метод "разделяй и властвуй". Умножение n-битовых чисел: простой рекурсивный алгоритм, улучшенный рекурсивный алгоритм. Рекуррентные соотношения: основная теорема. Двоичный поиск.
Посмотреть видео на сайте Лекториума
Лекция 3. Алгоритмы сортировки.
Сортировка слиянием: с рекурсией и без. Сортировка с помощью кучи. Нижняя оценка
(n log n) для сортировки. Быстрая сортировка: анализ среднего времени работы, анализ глубины рекурсии, элиминация хвостовой рекурсии.Посмотреть видео на сайте Лекториума
Лекция 4. Алгоритмы сортировки (продолжение).
Быстрая сортировка (продолжение). Порядковые статистики: нахождение за линейное в среднем время.
Посмотреть видео на сайте Лекториума
Лекция 5. Элементарные структуры данных.
Абстрактные типы данных, интерфейс и реализация. Массивы переменного размера: аддитивная и мультипликативная схемы реаллокации. Анализ учётных стоимостей операций: функция потенциала, истинные и учётные стоимости. Стек, очередь, дек. Реализация на основе массива переменного размера и на основе связанного списка. Моделирование очереди с помощью двух стеков. Корневое дерево: бинарное дерево, дерево с произвольным ветвлением, представление "левый ребёнок — правый сосед".
Посмотреть видео на сайте Лекториума
Лекция 6. Динамическое программирование.
Предварительные сведения: ациклические ориентированные графы. Общие принципы динамического программирования, часто используемые подзадачи. Кратчайшие пути в ациклических ориентированных графах. Наибольшая возрастающая подпоследовательность: подзадачи, порядок на подзадачах, граф подзадач, сравнение с рекурсивным алгоритмом; нахождение не только длины, но и самой подпоследовательности. Стоимость редактирования: граф на подзадачах, нахождение кратчайшего пути в данном графе.
Посмотреть видео на сайте Лекториума
Лекция 7. Динамическое программирование (продолжение).
Задача о рюкзаке: рюкзак с повторениями и без, ленивые вычисления. Перемножение последовательности матриц: представление порядка перемножения в виде дерева, оценка на количество порядков. Независимые множества в деревьях. О времени и памяти алгоритмов, основанных на методе динамического программирования.
Посмотреть видео на сайте Лекториума
Лекция 8. Двоичные деревья поиска.
Дерево поиска: поиск, вставка, удаление, поиск следующего и предыдущего элемента за время, пропорциональное высоте. АВЛ-дерево (или какое-нибудь другое сбалансированное дерево): верхняя оценка на высоту, малое и большое вращение.
Лекция 9. Декартовы деревья.
Декартовы деревья, операции split и merge, реализация стандартных операций деревьев поиска через split и merge.
Лекция 10. Сплей-деревья.
Верхняя оценка O(log n) на среднюю стоимость операций.
Лекция 11. Декомпозиция графов.
Графы и способы их представления, способы использования графов. Поиск в глубину в неориентированных графах, выделение компонент связности.
Посмотреть видео на сайте Лекториума
Лекция 12. Декомпозиция графов (продолжение).
Поиск в глубину в ориентированных графах: ориентированные ациклические графы, топологическая сортировка вершин, наличие стока и истока в ациклическом графе, выделение компонент сильной связности.
Посмотреть видео на сайте Лекториума
Лекция 13. Пути в графах.
Расстояния в графе. Поиск в ширину: обход, дерево кратчайших путей, сравнение с поиском в глубину. Алгоритм Дейкстры: адаптация поиска в ширину введением дополнительных вершин; установка будильников; алгоритм Дейкстры; альтернативный взгляд на алгоритм: последовательное расширение множества вершин, до которых расстояние уже посчитано; время работы алгоритма при различных реализациях очереди с приоритетами.
Посмотреть видео на сайте Лекториума
Немає коментарів:
Дописати коментар