Школа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. Поиск максимальных повторов