Введение в алгоритмы и структуры данных

merge.	Слияние последовательностей	ps pdf tex
kth.	K-ый минимум	ps pdf tex
sumdist.	Сумма расстояний	ps pdf tex
longpath1.	Длиннейший путь 2	ps pdf tex
longpath2.	Длиннейший путь 2	ps pdf tex
distance1.	Расстояние между вершинами 1	ps pdf tex
distance2.	Расстояние между вершинами 2	ps pdf tex
spantree1.	Минимальное остовное дерево 1	ps pdf tex
spantree2.	Минимальное остовное дерево 2	ps pdf tex
aplusb.	Сложение	ps pdf tex

Повторение

План лекции

Сортировки
1. Быстрая сортировка
  - Реализация
  - Поиск K-го минимума за O(n) в среднем
2. Сортировка слиянием
  - Слияние последовательностей
  - Алгоритм сортировки слиянием
  - Подсчет числа инверсий
3. Сортировки за линейное время
  - Сортировка подсчетом
  - Цифровая сортировка
  - Bucket sort
Представление списков в памяти
1. Списки на нескольких массивах
2. Списки на массиве структур
3. Односвязные списки
4. Двусвязные списки
Представление графа в памяти
1. Матрица смежности
2. Списки смежности
3. Списки инцендентности
4. Список ребер

День 2 (04.08.07)

Задачи на сортировки ps pdf tex

inverse.	Количество инверсий	ps pdf tex
suffarr.	Сортировка суффиксов	ps pdf tex
cycles4.	4-циклы (*)	ps pdf tex
qsort.	Интеллект против QSort	ps pdf tex

Остовные деревья. Система непересекающихся множеств

План лекции

K-ичные кучи
1. Cтруктура k-ичной кучи
2. Свойства кучи
3. Подъем элемента в куче (siftup)
4. Спуск элемента в куче (siftdown)
5. Оценка времени операций над кучей
6. Куча с внешнимим указателями
Поиск минимального остовного дерева
1. Лемма о цикле
2. Теорема о разрезе и минимальном ребре
3. Алгоритм Прима
  - Описание алгоритма
  - Доказательство корректности
  - Наивная реализация за O(V^2)
  - Реализация с кучей за O(E log(V))
  - Связь алгоритма Прима и алгоритма Дейкстры
4. Алгоритм Краскала
  - Описание алгоритма
  - Доказательство корректности
  - Реализация с цветами
Система непересекающихся множеств
1. Реализация на основе списков
  - Наивная реализация. Оценка времени работы
  - Весовая эвристика. Оценка времени работы
2. Реализация на основе деревьев
  - Наивная реализация. Оценка времени работы
  - Весовая эвристика. Оценка времени работы
  - Ранговая эвристика. Оценка времени работы
  - Эвристика сжатия путей
  - Итерированный логарифм. Оценка времени работы для эвристики сжатия путей (без доказательства)

День 3 (05.08.07)

Задачи на хип и СНМ ps pdf tex

distance3.	Расстояние между вершинами	ps pdf tex
minmax.	Минимум/максимум	ps pdf tex
keyins.	Вставка ключей	ps pdf tex

Поиск в глубину и его применения

План лекции

Реализация, времена входа и выхода
Классификация ребер при поиске в глубину
1. Классификация ребер для ориентированного графа
2. Классификация ребер для неориентированного графа
Компоненты связности
Топологическая сортировка
Сильная связность
1. Компоненты сильной связности. Алгоритм поиска
2. Конденсация графа. Алгоритм поиска
3. База и антибаза. Алгоритм поиска
Мосты и компоненты реберной двусвязности
1. Мосты. Определение и алгоритм поиска
2. Компоненты реберной двусвязности. Определение и алгоритм поиска
Точки сочленения. Компоненты вершинной двусвязности
1. Точки сочленения. Определение и алгоритм поиска
2. Компоненты вершинной двусвязности. Определение и алгоритм поиска
Эйлеровы циклы и пути
1. Определение. Эйлеровы графы
2. Нахождение Эйлерова цикла
3. Покрытие путями

День 4 (06.08.07)

Задачи на поиск в глубину ps pdf tex

condense.	Конденсация графа	ps pdf tex
post.	Почтальон	ps pdf tex
bridges.	Мосты	ps pdf tex
optimal.	Оптимальный параметр	ps pdf tex
pref.	Преферанс (*)	ps pdf tex

Паросочетания и вершинные покрытия

План лекции

Паросочетания, вершинные покрытия и независимые множества
1. Паросочетания
  - Определение
  - Задача о максимальном паросочетании
2. Вершинные покрытия
  - Определение
  - Задача о минимальном вершинном покрытии
  - Связь задач о минимальном вершинном покрытии и максимальном парсочетании
3. Независимые множества
  - Определение
  - Задача о максимальном независимом множестве
  - Связь задач о минимальном вершинном покрытии и максимальном независимом множестве
Двудольные графы
1. Определение
2. Теорема о циклах нечетной длины
3. Проверка графа на двудольность
4. Выделение долей
Паросочетания в двудольных графах
1. Удлиняющие цепи
2. Теорема об удлиняющей цепи
3. Классический алгоритм. Оценка времени работы
4. Алгоритм Куна. Оценка времени работы

День 5 (07.08.06)

Практика на паросочетания и кратчайшие пути ps pdf tex

factory.	Фабрика	ps pdf tex
negcycle.	Отрицательный цикл	ps pdf tex
floyd.	Pink Floyd	ps pdf tex
king.	Король	ps pdf tex

Кратчайшие пути

План лекции

Алгоритм Форда-Беллмана
1. Описание алгоритма Форда-Беллмана
2. Работа с отрицательными весами
3. Отрицательные циклы
4. Доказательство корректности
5. Реализация с квадратным массивом
6. Реализация с линейным массивом
7. Восстановление путей
Алгоритм Флойда
1. Описание алгоритма Флойда
2. Работа с отрицательными весами
3. Отрицательные циклы
4. Доказательство корректности
5. Восстановление путей с сохранением промежуточной вершины
6. Восстановление путей с сохранением следующей вершины
Поиск кратчайших путей за линейное время
1. Кратчайшие пути в 1-k графе за O(kE)
2. Кратчайшие пути в 0-k графе за O(kE)

День 6 (08.08.07)

Дополнительные задачи ps pdf tex

redhat.	Красная шапочка (*)	ps pdf tex
hilander.	Горец (*)	ps pdf tex

Задачи на отрезках

План лекции

Range Sum Query (RSQ)
1. Постановка задачи
2. Реализация за <O(1), O(n)>
3. Реализация за <O(n^2), O(1)>
4. Реализация за <O(n), O(1)> с использованием частичных сумм
Range Min Query (RMQ)
1. Постановка задачи
2. Реализация за <O(1), O(n)>
3. Реализация за <O(n^2), O(1)>
4. Реализация за <O(n log(n)), O(1)> с использованием разреженных таблиц
Типы задач
1. Offline-задачи
2. Online-задачи
3. Задачи с изменением элементов
Деревья интервалов (отрезков)
1. Структура дерева интервалов и представление в памяти
2. Построение дерева интервалов за линейное время
3. Решение задач RMQ и RSQ на дереве интервалов за O(log(n))
  - Реализация сверху вниз (рекурсивная)
  - Реализация снизу вверху (итеративная)
4. Изменение элементов
  - Изменение одного элемента
  - Установка элементов на отрезке
  - Добавление и вычитание на отрезке
  - Техника проталкивания информации
Ассоциативные операции
1. Определение ассоциативной операции
2. Минимум и сумма как ассоциативные операции
3. Примеры ассоциативных операций
4. Ассоциативные операции и деревья отрезков
Обобщение на многомерный случай

День 7 (10.08.07)

Задачи на деревья отрезков ps pdf tex

rvq.	Range Variation Query	ps pdf tex
house36.	36 домик	ps pdf tex
mobiles.	Мобильные телефоны (*)	ps pdf tex

Деревья поиска

План лекции

Двоичные деревья поиска
1. Определение
2. Представление в памяти
3. Поиск элемента
4. Поиск минимума и максимума
5. Поиск порядковых статистик
6. Обход дерева. Получение элементов в отсортированном порядке
7. Вставка элемента
8. Удаление элемента
9. Оценка времени работы в зависимости от высоты дерева
Сбалансированные деревья поиска. Определение
АВЛ деревья
1. Определение
2. Оценка высоты
3. Повороты
4. Балансировка при добавлении элемента (4 случая)
5. Балансировка при удалении элемента (4 случая)
Декартовы деревья
1. Определение
2. Вставка элемента. Реализация с поворотами
3. Удаление элемента. Реализация с поворотами
4. Разделение декартовых деревьев
  - Реализация с помощью вставки
  - Непосредственная реализация
  - Реализация вставки через разделение
5. Слияние декартовых деревьев
  - Реализация с помощью удаления
  - Непосредственная реализация
  - Реализация удаления через слияние
6. Рандомизированные декартовы деревья

День 8 (11.08.07)

Деревья поиска ps pdf tex

kthmax.	K-ый максимум	ps pdf tex
firesafe.	Противопожарная безопасность	ps pdf tex
diameter.	Диаметр дерева	ps pdf tex

Вычислительная геометрия

План лекции

Точность вычислений с плавающей точкой
Геометрические примитивы
1. Точка
2. Вектор
  - Сложение векторов
  - Скалярное произведение векторов
  - Векторное произведение векторов
3. Прямая
  - Способы задания прямых на плоскости
  - Нахождение точки пересечения двух прямых
  - Принадлежность точки прямой
  - Проверка параллельности и перпендикулярности прямых
  - Расстояние от точки до прямой
  - Расстояние между параллельными прямыми
4. Отрезок
  - Параметрическое задание отрезка
  - Расстояние от точки до отрезка
5. Окружность
  - Задание окружности на плоскости
  - Взаимное расположение точки и окружности
  - Взаимное расположение двух окружностей
  - Взаимное расположение прямой и окружности
  - Пересечение прямой и окружности
  - Пересечение двух окружностей
6. Треугольник
  - Площадь треугольника
  - Ориентированная площадь треугольника
  - Ориентация треугольника
7. Многоугольник
  - Площадь многоугольника
  - Принадлежность точки произвольному многоугольнику
  - Выпуклый многоугольник
    - Проверка выпуклости многоугольника
    - Принадлежность точки выпуклому многоугольнику
Построение выпуклой оболочки множества точек
1. Определение выпуклой оболочки
2. Алгоритм Джарвиса
3. Алгоритм Грэхема
Метод сканирующей прямой
1. Пересечение двух выпуклых многоугольников

День 9 (12.08.06)

Вычислительная геометрия ps pdf tex

distance.	Расстояние от точки до отрезка	ps pdf tex
circle.	Окружность и прямая	ps pdf tex
circles.	Две окружности	ps pdf tex
tangent.	Касательная к окружности	ps pdf tex
bisector.	Биссектриса	ps pdf tex
convex.	Выпуклая оболочка	ps pdf tex
point.	Точка в многоугольнике	ps pdf tex
polygon.	Выпуклый многоугольник	ps pdf tex
area.	Площадь многоугольника	ps pdf tex
intersec.	Пересечение отрезков	ps pdf tex
windows.	Окна	ps pdf tex
maxdist.	Автопробег	ps pdf tex
intersect.	Пересечение отрезков	ps pdf tex

Семинар по динамическому программированию

План лекции

Решение задач динамического программирования при помощи рекуррентных соотношений
1. Определение вычисляемой функции
2. Запись рекуррентного соотношения
3. Задание начальных значений
4. Определение порядка вычисления функции
5. Вычисление ответа
Задачи
1. Задача построения оптимального объекта
2. Задача подсчета объектов
3. Задача о рюкзаке
4. Комбинация задач
5. Динамическое программирование на подотрезках
6. Динамическое программирование на деревьях

День 10 (14.08.07)

Динамическое программирование 1 ps pdf tex

threeseq.	Три последовательности	ps pdf tex
sumcubes.	Сумма кубов	ps pdf tex
palindr.	Палиндром	ps pdf tex
pattern.	Шаблон	ps pdf tex

Нетривиальное динамическое программирование

План лекции

Динамическое программирование на подотрезках
1. Задача об удалении кубиков
2. Описание общего подхода
Динамическое программирование на деревьях
1. Задача о диаметре дерева
2. Задача о максимальном паросочетании
3. Описание общего подхода
4. Решение сверху вниз (поиск в глубину)
5. Решение снизу вверх
Матрицы
1. Задача о шахматном телефоне
2. Запись перехода в виде матрицы
3. Умножение матрицы на вектор
  - Формула
  - Вывод формулы
  - Линейность
4. Сумма матриц
  - Определение и формула
  - Вывод формулы
  - Линейность
5. Произведение матриц
  - Определение и формула
  - Вывод формулы
  - Некоммутативность произведения матриц
  - Умножение прямоугольных матриц. Согласованные матрицы
  - Ассоциативность произведения матриц
  - Степень матрицы. Связь с динамическим программированием
6. Быстрое возведение в степень
  - Быстрое возведение в степень чисел
  - Быстрое возведение в степень матриц
  - Вычисление значений линейных рекуррентных формул
7. Решение задачи о шахматном телефоне на основе матриц
Динамическое программирование по профилю
1. Профили. Переход между профилями
2. Задача о шахматном телефоне как задача на динамическое программирование по профилю
  - Вид профиля
  - Переход между профилями
3. Задача о замощении доминошками
  - Вид профиля
  - Переход между профилями
4. Расстановка шахматных фигур
  - Виды профилей
  - Переход между профилями
  - Сжатое представление профилей
  - Списки переходов
5. Оценка времени работы
Динамическое программирование по изломанному профилю
1. Изломанный профиль
  - Переход к следующему излому
  - Переход между последним и первым изломом
  - Порядок вычисления с изломанным профилем
2. Решение задачи о замощении доминошками с изломанным профилем
  - Решение
  - Оценка времени работы
Динамическое программирование с разбиением на подзадачи
1. Свойство оптимальности для подзадач
2. Итеративное вычисление
3. Ленивое вычисление
4. Алгоритм Форда-Беллмана как алгоритм динамического программирования

День 11 (16.08.07)

Динамическое программирование 2 ps pdf tex

fib1.	Числа Фибоначчи 1	ps pdf tex
fib2.	Числа Фибоначчи 2	ps pdf tex
fib3.	Числа Фибоначчи 3 (*)	ps pdf tex
fib5.	Числа Фибоначчи 5 (*)	ps pdf tex
network.	Сеть	ps pdf tex
ones.	Три единицы	ps pdf tex
nice.	Симпатичные узоры	ps pdf tex
nice2.	Симпатичные узоры 2 (*)	ps pdf tex

Поиск подстрок

План лекции

Основные понятия
1. Префикс строки
2. Суффикс строки
3. Подстрока
Наивный алгоритм
1. Описание
2. Реализация
3. Оценка времени работы
Алгоритм Кнута-Морриса-Пратта
1. Префикс-функция
  - Определение
  - Алгоритм построения
  - Оценка времени работы
2. Поиск с применением префикс-функции
  - Алгоритм
  - Оценка времени работы
Бор
1. Определение
2. Построение за линейное время
3. Поиск строки в боре за линейное время
4. Представление в памяти
  - Массив детей
  - Список детей
Алгоритм Ахо-Корасик
1. Задача о поиске множества строк
2. Суффиксные связи
  - Определение
  - Применение при поиске
3. Листовые связи
  - Определение
  - Применение при поиске
4. Алгоритм построения
  - Обходом в ширину
  - Ленивые вычисления (рекурсивно)
5. Оценка времени работы

День 12 (17.08.07)

Поиск подстрок ps pdf tex

console1.	Поиск набора образцов 1	ps pdf tex
console2.	Поиск набора образцов 1	ps pdf tex
kthstr.	K-ая строка	ps pdf tex
yandex.	Яндекс	ps pdf tex

Задачи на строках

План лекции

Суффиксное дерево
1. Суффиксное дерево как бор
2. Построение суффиксного дерева за квадратичное время
3. Задачи, решаемые суффиксными деревьями
  - Поиск строки
  - Количество различных подстрок
  - Подстроки, встречающиеся k раз
  - Подстроки, встречающиеся без наложений
4. Сжатое суффиксное дерево
Алгоритм Рабина-Карпа
1. Хэширование и коллизии
2. Полиномиальное хэширование
3. Пересчет хэша при сдвиге
4. Алгоритм Кнут-Морриса-Пратта как разновидность хэш-функции

Хэш-таблицы

План лекции

Хэш-таблицы с закрытой адресацией
1. Структура
2. Поиск
3. Вставка
4. Удаление
5. Степень загрузки (load factor) и выбор размера хэш-таблицы
6. Изменение размера хэш-таблицы и рехэширование
Хэш-таблицы с открытой адресацией
1. Структура
  - Переход к следующему элементу
  - Переход в зависимости от хэша
2. Поиск
3. Вставка
4. Удаление
Выбор хэш-функции
1. Полиномиальное хэширование
2. Хэширование чисел