Куликов А.С., Дворкин М.Э. | Курс «Алгоритмы и структуры данных 1, 2» [2011-2012] HDRip

Содержание 1 части:
Лекции курса

13.09.2011, 18:30
Лекция 1 «Введение»
Вычисление чисел Фибоначчи: экспоненциальный рекурсивный алгоритм, полиномиальный алгоритм, более детальный анализ. Время работы алгоритма, O-символика. Скорость роста функций: логарифм, полином, экспонента.

20.09.2011, 18:30
Лекция 2 «Рекуррентные соотношения»
Метод "разделяй и властвуй". Умножение n-битовых чисел: простой рекурсивный алгоритм, улучшенный рекурсивный алгоритм. Рекуррентные соотношения: основная теорема. Двоичный поиск.

27.09.2011, 18:30
Лекция 3 «Алгоритмы сортировки»
Сортировка слиянием: с рекурсией и без. Сортировка с помощью кучи. Нижняя оценка (nlogn) для сортировки. Быстрая сортировка: анализ среднего времени работы, анализ глубины рекурсии, элиминация хвостовой рекурсии.

04.10.2011, 18:30
Лекция 4 «Алгоритмы сортировки»
Быстрая сортировка (продолжение). Порядковые статистики: нахождение за линейное в среднем время.

11.10.2011, 18:30
Лекция 5 «Элементарные структуры данных»
Абстрактные типы данных, интерфейс и реализация. Массивы переменного размера: аддитивная и мультипликативная схемы реаллокации. Анализ учётных стоимостей операций: функция потенциала, истинные и учётные стоимости. Стек, очередь, дек. Реализация на основе массива переменного размера и на основе связанного списка. Моделирование очереди с помощью двух стеков. Корневое дерево: бинарное дерево, дерево с произвольным ветвлением, представление "левый ребёнок — правый сосед".

18.10.2011, 18:30
Лекция 6 «Динамическое программирование»
Предварительные сведения: ациклические ориентированные графы. Общие принципы динамического программирования, часто используемые подзадачи. Кратчайшие пути в ациклических ориентированных графах. Наибольшая возрастающая подпоследовательность: подзадачи, порядок на подзадачах, граф подзадач, сравнение с рекурсивным алгоритмом; нахождение не только длины, но и самой подпоследовательности. Стоимость редактирования: граф на подзадачах, нахождение кратчайшего пути в данном графе.

25.10.2011, 18:30
Лекция 7 «Динамическое программирование»
Задача о рюкзаке: рюкзак с повторениями и без, ленивые вычисления. Перемножение последовательности матриц: представление порядка перемножения в виде дерева, оценка на количество порядков. Независимые множества в деревьях. О времени и памяти алгоритмов, основанных на методе динамического программирования.

01.11.2011, 18:30
Лекция 8 «Двоичные деревья поиска»
Дерево поиска: поиск, вставка, удаление, поиск следующего и предыдущего элемента за время, пропорциональное высоте. АВЛ-дерево (или какое-нибудь другое сбалансированное дерево): верхняя оценка на высоту, малое и большое вращение.

15.11.2011, 18:30
Лекция 9 «Декартовы деревья»
Декартовы деревья, операции split и merge, реализация стандартных операций деревьев поиска через split и merge.

22.11.2011, 18:30
Лекция 10 «Сплей-деревья»
Верхняя оценка O(logn) на среднюю стоимость операций.

29.11.2011, 18:30
Лекция 11 «Декомпозиция графов»
Графы и способы их представления, способы использования графов. Поиск в глубину в неориентированных графах, выделение компонент связности.

06.12.2011, 18:30
Лекция 12 «Декомпозиция графов (продолжение)»
Поиск в глубину в ориентированных графах: ориентированные ациклические графы, топологическая сортировка вершин, наличие стока и истока в ациклическом графе, выделение компонент сильной связности.

13.12.2011, 18:30
Лекция 13 «Пути в графах»
Расстояния в графе. Поиск в ширину: обход, дерево кратчайших путей, сравнение с поиском в глубину. Алгоритм Дейкстры: адаптация поиска в ширину введением дополнительных вершин; установка будильников; алгоритм Дейкстры; альтернативный взгляд на алгоритм: последовательное расширение множества вершин, до которых расстояние уже посчитано; время работы алгоритма при различных реализациях очереди с приоритетами.

Содержание 2 части:
Лекции курса

13.02.2012, 18:30
Лекция 1 «Пути в графах»
Кратчайшие пути при наличии рёбер отрицательного веса: алгоритм Беллмана-Форда; определение наличия цикла отрицательного веса в графе. Кратчайшие пути в ациклических ориентированных графах. Кратчайшие пути между всеми парами вершин: алгоритм Флойда-Уоршолла, алгоритм Джонсона.

13.02.2012, 18:30
Лекция 2 «Жадные алгоритмы»
Общие принципы жадного метода. Непрерывная и дискретная задачи о рюкзаке. Задача о выборе заявок. Минимальное покрывающее дерево: свойство разреза, жадная стратегия.

20.02.2012, 18:30
Лекция 3 «Алгоритм Крускала, система непересекающихся множеств»
Алгоритм Крускала, система непересекающихся множеств.

05.03.2012, 18:30
Лекция 4 «Числовые алгоритмы»
Система непересекающихся множеств: доказательство оценки на время работы алгоритма с эвристикой сжатия путей. Числовые алгоритмы. Основные арифметические операции: сложение, умножение, деление, нахождение наибольшего общего делителя.

12.03.2012, 18:30
Лекция 5 «Проверка простоты числа»
Арифметика сравнений: сложение, умножение, возведение в степень, нахождение обратного по модулю. Вероятностный тест на простоту.

19.03.2012, 18:30
Лекция 6 «RSA»
Генерация случайных простых чисел. Криптография: схемы с закрытым ключом, RSA.

26.03.2012, 18:30
Лекция 7 «Быстрое преобразование Фурье»
Быстрое вычисление значений многочлена в точках: два способа задания многочленов — коэффициентами и значениями в точках; вычисление значений многочлена в точках методом "разделяй и властвуй"; дискретное преобразование Фурье; быстрое преобразование Фурье. Интерполяция: интерполяция в терминах матриц; матрица Вандермонда; интерполяция как домножение на обратную матрицу.

02.04.2012, 18:30
Лекция 8 «Линейное программирование»
Линейное программирование: общий вид задачи, двойственность. Задача о максимальном потоке. Задача о паросочетании в двудольном графе.

09.04.2012, 18:30
Лекция 9 «Симплекс-метод»
Подробнее о двойственности, симплекс-метод.

16.04.2012, 18:30
Лекция 10 «Алгоритм Кнута-Морриса-Пратта»
Задача поиска подстроки в строке. Наивный алгоритм, алгоритм Карпа-Рабина, алгоритм Кнута-Морриса-Пратта.

04.05.2012, 18:30
Лекция 11 «Суффиксные деревья»
Построение суффиксного дерева за линейное время.

11.05.2012, 18:30
Лекция 12 «NP-полные задачи»
Задачи поиска, классы P и NP. Сведения. Доказательство NP-полноты задач выполнимости, 3-выполнимости, выполнимости схемы, задачи о независимом множестве.