Школа179: /Сборы//Сборы / Архив?//Сборы / Архив / 2006 Весна/ПрочитанныеЛекции ...

Лекции прочитанные на сборах

20 марта

Лекция D: Структуры данных – 1

1. Списки. Односвязные и двусвязные. Добавление/удаление. Кольцевые списки.
2. Стеки. Стеки на массивах и списках. Примеры простейших задач на стеки.
3. Очереди. Очереди на списках. Очереди на массивах в виде циклического буфера.
4. Деки. Задачи на деки. Лабиринты.
5. Сортированные массивы. Бинарный поиск.
6. Хэш-таблицы.

Лекция С: Структуры данных -1

1. Простые структуры данных.
   1. Очереди и стеки.
   2. Списковые структуры, представление списков в массиве.
   3. Списки в динамической паматью
2. Бинарный поиск, поиск k-го по величине в массиве
3. Heap, Heap-sort и очередь с приоритетами
4. Дерево отрезков
   1. Обзор
   2. Init
   3. Update
   4. Запросы
   5. Обобщение на многомерный случай
5. Двойчные деревья поиска
   1. Поиск
   2. Добавление и удаление
   3. Сбалансированные деревья.

Лекция B: Геометрия

1. Систематизация подходов к решению задач на вычислительную геометрию
   1. Метод границ
   2. Метод деления пополам
   3. Примеры
      1. Пример 1 – Задача о самолётах (см. ниже)
      2. Пример 2 – Задача о бассейне (см. ниже)
   4. Теорема Хэлли и её использование
2. Разбиения плоскости
   1. Двоичное деление пространства (BSP-Trees)
      1. Построение BSP-Tree
      2. Алгоритмы на BSP-Tree и их эффективность
      3. Пример использования : точки, отдалённые от данной не более, чем на R
   2. Области Вороного
      1. Определение
      2. Свойства
      3. Использование областей Вороного в задачах
      4. Разбор задачи «Области Вороного на плоскости при использовании Матхэттенской метрики расстояния»
   3. Триангуляции
      1. Определение триангуляции
      2. Триангуляция Делоне
      3. Свойства триангуляции Делоне
      4. О двойственности триангуляции Делоне областям Вороного
      5. Алгоритмы построения триангуляции Делоне
      6. Алгоритм «Разделяй и Властвуй» для построения триангуляции Делоне : разбор
      7. Разбор задачи «Стол в колоннах»
3. Стереометрия
   1. Эффективное использование скалярного и векторного произведений в пространстве
   2. Yet another алгоритм решения задачи об объёме общей части выпуклых тел 
   3. Подробный разбор решения задачи «Пересечение кубов»

Лекция A: Суффиксные деревья. Алгоритм Мак-Крейта построения суффиксного дерева за линейное время

1. Суффиксное дерево, наивный алгоритм
2. Сжатое суффиксное дерево, детали реализации
3. Суффиксные ссылки
4. Общий шаг алгоритма Мак-Крейта
5. Добавление следующего суффикса, «скачок по счетчику»
6. Сохранение структуры суффиксных ссылок
7. Оценка количества действий O(n)
8. Использование суффиксных деревьев
   1. Поиск подстроки в строке
   2. Обобщенное суффиксное дерево
   3. Количество различных подстрок в строке
   4. Наибольшая общая подстрока
   5. Поиск максимальных повторов

Программа сборов на 21 марта

Лекция D: Структуры данных – 2

1. Двоичные деревья поиска
   1. Основные определения
   2. Обход дерева и печать элементов в неубывающем порядке
   3. Поиск элемента по ключу
   4. Нахождение минимального и максимального элементов
   5. Нахождение следующего и предыдущего
   6. Добавление элемента
   7. Удаление элемента
2. Вектор (саморасширяющийся массив)
   1. Понятие вектора
   2. Оценка времени добавления элемента двумя способами
3. Двоичная куча (Heap)
   1. Понятие двоичной кучи и ее основное свойство
   2. Процедура Heapify поддержания основного свойства кучи
   3. Построение кучи. Линейная оценка сложности
   4. Heap Sort — сортировка с помощью кучи
   5. Приоритетная очередь: операции добавления и извлечения максимального элемента
   6. Разбор задачи «Тупики» с Московской Городской олимпиады

Лекция С: Структуры данных – 2

1. Декартовы деревья
2. Хеш-таблицы
   1. Хеш-функции
   2. Методы разрешения коллизий
   3. Хеширование с открытой адресацией
   4. Двойное хеширование
3. Системы непересекающихся множеств
   1. Операции
   2. Реализация с помощью массивов
   3. Реализация с помощью списков
   4. Лес непересекающихся множеств

Лекция AB: LCA и RMQ за O(1)

1. Манипуляции с битами: обнуление/установка единичных битов справа и т. п., округление к ближайшей степени 2, подсчет единичных и нулевых битов в слове.
2. Постановка задачи LCA: Least common accessor в дереве, постановка задачи RMQ: Range Minimum Query, сведение задачи LCA к RMQ за O(n), где n – число узлов в дереве.
3. Решение задачи RMQ с предвычислением за O(n log n) (n – размер массива) и стоимостью запроса O(1) методом динамического программирования.
4. Задача ±1 RMQ, решение задачи с предвычислением за O(n) и стоимостью запроса O(1). Таким образом получаем алгоритм решения LCA с предвычислением O(n) и запросом O(1).
5. Сведение задачи RMQ к задаче LCA за O(n). В итоге получаем RMQ с предвычислением O(n) и запросом O(1).