Школа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).

22 марта

Лекция D: Длинная арифметика

1. Хранение длинных чисел.
2. Сравнение длинных чисел.
3. Арифметические операции над длинными числами:
   а. Сложение
   б. Вычитание
   в. Умножение
   г. Деление длинного числа на короткое
   д. Деление длинного числа на длинное

Лекция С: Базовые строковые алгоритмы

1. Алгоритм Кнута-Морриса-Пратта
   1. Введение, обозначения, наивный алгоритм
   2. Префикс – функция
   3. КМП 
   4. Интерпретация с использованием конечного автомата
2. Алгоритм Ахо-Корасик
   1. Бор, сжатый бор 
   2. Построение бора по набору слов
   3. Интерпретация с использованием конечного автомата, суффиксные ссылки
   4. Ахо-Корасик

Лекция AB: Теорема Геделя о неполноте

23 марта

Лекция D: Вычислительная геометрия на плоскости

1. Векторы
   1. Понятие вектора
   2. Координаты вектора
   3. Операции над векторами
   4. Скалярное произведение векторов
   5. Векторное (косое) произведение векторов
2. Нахождение полярного угла
3. Типы данных для программирования задач вычислительной геометрии
4. Взаимное расположение точек и фигур
   1. Принадлежность точки прямой
   2. Принадлежности точки лучу
   3. Принадлежность точки отрезку
   4. Расстояние от точки до прямой
5. Определение факта пересечения двух отрезков
6. Уравнение прямой
7. Уравнение окружности
8. Уравнение биссектрисы угла
9. Уравнение касательной к окружности (геометрический метод)
10. Нахождение точек пересечения окружности и прямой (геометрический метод)
11. Нахождение точек пересечения двух окружностей (алгебраический и геометрический методы)
12. Нахождение площади простого многоугольника
13. Определение принадлежности точки простому многоугольнику
14. Примеры решения задач прошлых Всероссийских олимпиад рассмотренными методами
    1. Задача «Лесной пожар»
    2. Задача «Раздел царства»

Лекция С: Перебор

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

Лекция AB: Игры и стратегии

1. Игры на графах
   1. выигрышные/проигрышные позиции
   2. игры на ациклических графах
   3. игры на циклических графах, ничья
2. Число Спрага-Гранди
   1. определение
   2. теорема Спрага-Гранди
   3. примеры (Grundy's game, Withoff's game, Euclid, Nim, Hackenbush)
3. Теория игр 
   1. антагонистические игры в нормальной форме
   2. матричные игры
   3. максмин и минимакс
   4. значение игры и оптимальные стратегии
   5. смешанные стратегии
   6. существование решения матричной игры в смешанных стратегиях
   7. итеративный метод решения матричных игр 
4. Позиционные игры n игроков в общем случае
   1. существование решения конечной игры n лиц с полной информацией (центральная теорема)