Ребята, Попов 2 часа назад прислал письмо об альтернативных курсах для геоинформатике.
Насколько я поняла, можно заменить этот курс некоторыми лекционными курсами, читающимися в ПОМИ,
т.к. произошла накладка, и нам читают не совсем то, что хотелось.
Вот оригинальное письмо.
-----Original Message-----
From: eugene stepanov
Sent: Monday, September 20, 2010 7:56 PM
To: I. Yu. Popov
Subject: курсы в физматклубе
Добрый день,
как и обещал, посылаю сведения о курсах, читаемых в физматклубе
сотрудниками каф. ММ. Будем рады. если Ваши студенты туда придут.
Зачет, естественно, преподаватели смогут принять.
Еще раз прошу извинить за накладку с курсом Капралова по
геоинформатике. Я как-то понял при обсуждении в прошлом семестре, что
речь шла о весне
(и основы маткартографии Капралов как раз и будет читать весной), но,
увы, для 6 курса это не подойдет.
С уважением, Е Ст
------------------------------------------
Ф. Петров (ПОМИ), "Концентрация меры"
Занятия будут по вторникам в 18-30,
Первое занятие 21го сентября.
Концентрация меры - явление в теории вероятностей, анализе и
комбинаторике, состоящее в том, что при достаточно общих и не слишком
обременительных ограничениях значение функции большого числа
переменных почти постоянно. Классический пример: почти вся поверхность
многомерной сферы сосредоточена вблизи экватора. В 1970-е Виталий
Мильман нашел применение этого факта в локальной геометрии банаховых
пространств, предъявив новое доказательство знаменитой теоремы
Дворецкого (исходно - гипотезы Гротендика): любое
центрально-симметричное выпуклое тело достаточно большой размерности
имеет почти круглое центральное сечение заданной размерности. С тех
пор идея концентрации меры нашла множество ярких и эффектных
приложений, которые мы собираемся обсудить.
Желательно минимальное знакомство слушателей с основами анализа и
теории вероятностей.
-----------------------------------------------
Курс лекций "Основы вычислительной геометрии" (2 семестра, 64 часа)
Лектор: Вяткина К.В.,
начало 25 сентября в 10:00
(это 2 семестровый курс, но каждый семестр - вполне самостоятельный курс).
В рамках данного курса будут рассмотрены основные методы современной
вычислительной геометрии и возможности их применения для решения
практических задач, возникающих при разработке систем компьютерной
графики и географических информационных систем, а также в ряде других
областей.
Первый семестр
I. Введение: 2 ч.
Предмет вычислительной геометрии. Используемая модель вычислений.
Индивидуальные и массовые запросы. Сложность алгоритма: время ответа
на запрос, затраты памяти, время на предварительную обработку.
Многоугольники: простые, выпуклые, звездные. Ядро звездного
многоугольника. Задача о принадлежности точки простому, выпуклому,
звездному многоугольнику.
II. Выпуклые оболочки на плоскости: 4 ч.
Определение выпуклой оболочки (ВО) множества точек на плоскости.
Нижняя оценка сложности ее построения. Наивный алгоритм построения ВО
множества точек на плоскости. Понятие общего положения. Вырожденные
случаи. Понятие устойчивости алгоритма (robustness). Модифицированный
метод Грэхема. Нижняя оценка сложности построения ВО множества точек
на плоскости. Другие алгоритмы построения ВО множества точек на
плоскости: метод обхода Грэхема; метод заворачивания подарка (метод
Джарвиса) - алгоритм, чувствительный к выходу (output sensitive);
инкрементный алгоритм; метод <разделяй и властвуй> (с предварительной
сортировкой точек и без нее); <быстрая оболочка>; алгоритм Чена. Выбор
наиболее подходящего алгоритма с учетом конкретной ситуации.
III. Пересечение отрезков и наложение планарных подразбиений: 4 ч.
Задача о нахождении всех пересечений отрезков из заданного множества.
Нижняя оценка сложности: проверка наличия двух пересекающихся отрезков
в заданном множестве. Нахождение пересечений отрезков методом плоского
заметания. Реберный список с двойными связями (РСДС). Плоский
прямолинейный граф (ППЛГ). Планарное подразбиение. Задача наложения
(overlay) планарных подразбиений и алгоритм ее решения. Частные
случаи: пересечение выпуклых многоугольников; пересечение простых
многоугольников.
IV. Триангуляция многоугольника: 4 ч.
Диагональ простого многоугольника: определение и лемма о
существовании. Триангуляция простого многоугольника: определение,
лемма о существовании, сложность (количество треугольников в
триангуляции). Наивный алгоритм построения триангуляции простого
многоугольника. Граф, двойственный триангуляции: определение и
свойства. Построение триангуляции простого многоугольника путем
<отрезания ушей>. 3-раскрашиваемость графа триангуляции простого
многоугольника. Задача о картинной галерее. Монотонные многоугольники.
Разбиение простого многоугольника на y-монотонные. Построение
триангуляции монотонного многоугольника. Триангуляция произвольных
многоугольников и ППЛГ.
V. Локализация точки на планарном подразбиении: 4 ч.
Постановка задачи. Метод полос и оценка его сложности. Метод
детализации триангуляции Киркпатрика и оценка его сложности.
Трапецоидальная карта (trapezoidal map): определение, сложность,
представление. Вероятностный алгоритм построения трапецоидальной
карты. Оценка ожидаемого времени построения трапецоидальной карты,
ожидаемого размера поисковой структуры данных (search structure) и
ожидаемого времени обработки запроса на локализацию точки.
VI. Диаграмма Вороного и триангуляция Делоне: 8 ч.
Определение и основные свойства диаграммы Вороного множества точек на
плоскости. Наивный алгоритм построения диаграммы Вороного. Нижняя
оценка сложности построения диаграммы Вороного. Оптимальные алгоритмы
построения диаграммы Вороного: метод плоского заметания, метод
<разделяй и властвуй>. Возможности обобщения понятия диаграммы
Вороного.
Определение и свойства триангуляций множества точек на плоскости.
Легальные (legal) триангуляции: определение и построение. Граф Делоне
и его свойства. Триангуляция Делоне. Вероятностный алгоритм построения
триангуляции Делоне и анализ его сложности.
VII. Конфигурации прямых на плоскости и двойственность: 4 ч.
Задача о вычислении расхождения (discrepancy). Двойственность точек и
прямых. Конфигурации (arrangements) прямых на плоскости: определение,
сложность, инкрементный алгоритм построения. Понятие зоны прямой в
конфигурации; теорема о зоне (Zone Theorem). Оценка сложности
инкрементного алгоритма построения конфигурации. Понятие уровня
(level) точки в конфигурации прямых. Вычисление уровней вершин
конфигурации и их связь с величиной расхождения.
VIII. Видимость и кратчайшие пути: 2 ч.
Кратчайшие пути на плоскости при наличии полигональных препятствий.
Приближенный метод построения кратчайшего пути с использованием
трапецоидальной карты. Понятие графа видимости (visibility graph).
Нахождение кратчайших путей с использованием графа видимости.
Построение графа видимости. Возможные обобщения понятия видимости.
Второй семестр
IX. Ортогональный региональный поиск: 4 ч.
Ортогональные региональные запросы (orthogonal range queries). Задача
одномерного регионального поиска. Kd-деревья: определение, размер,
построение, использование для обработки запросов на плоскости;
обобщение на случай d-мерного пространства. Деревья регионов (range
trees): определение, размер, построение, использование для обработки
запросов на плоскости; обобщение на случай d-мерного пространства.
Частичное каскадирование (fractional cascading) и его применение для
ускорения обработки запросов с использованием дерева регионов.
X. Линейное программирование: 4 ч.
Пересечение полуплоскостей: алгоритм <разделяй и властвуй>. Решение
двумерной задачи линейного программирования: детерминированный
(инкрементный) и вероятностный алгоритмы. Обобщение на случай
пространств высшей размерности.
XI. Выпуклые оболочки в трехмерном пространстве: 4 ч.
Выпуклая оболочка (ВО) множества точек в трехмерном пространстве:
определение и комбинаторная сложность. Структуры данных для
представления многогранников. Детерминированные алгоритмы и
вероятностный алгоритм построения ВО множества точек в трехмерном
пространстве. Связь с задачей нахождения пересечения полупространств.
XII. Планирование движения: 4 ч.
Задача планирования движения робота (robot motion planning) на
плоскости при наличии полигональных препятствий. Рабочее и
конфигурационное пространства. Случай точечного робота. Суммы
Минковского: определение и использование для нахождения препятствий в
конфигурационном пространстве. Оптимальный алгоритм построения суммы
Минковского двух выпуклых многоугольников на плоскости. Случай
полигонального робота.
XIII. Дополнительные геометрические структуры данных: 16 ч.
Оконные запросы (windowing queries). Дерево интервалов (interval
tree): определение, размер, построение, использование для обработки
одномерных запросов о прокалывании (stabbing queries) и двумерных
оконных запросов для множества отрезков, параллельных осям координат.
Дерево поиска с приоритетом (priority search tree): определение,
размер, построение, использование для обработки двумерных
неограниченных ортогональных региональных запросов. Дерево отрезков
(segment tree): определение, размер, построение, использование для
обработки одномерных запросов о прокалывании и двумерных оконных
запросов для множества попарно непересекающихся отрезков.
BSP-дерево: определение, применение, построение, размер.
Задача генерации сетки (mesh generation). Квадродерево (quadtree) для
множества точек на плоскости и его использование для генерации сетки.
Симплициальный региональный поиск (simplex range search). Дерево
разбиения (partition tree): определение, размер, построение,
использование для обработки двумерных запросов симплициального
регионального поиска. Многоуровневое дерево разбиения (multi-level
partition tree): определение, размер, построение и применение. Дерево
разрезов (cutting tree): определение, размер, построение,
использование для обработки двумерных запросов симплициального
регионального поиска.
Литература
1.M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, "Computational
Geometry: Algorithms and Applications", Third Edition, Springer,
Heidelberg, 2008.
2.J-D. Boissonnat and M. Yvinec, "Geometrie algorithmique". Ediscience
international, Paris, 1995.
3.J. O'Rourke, "Computational Geometry in C", Second Edition,
Cambridge University Press, 1998.
4.Ф. Препарата, М. Шеймос, "Вычислительная геометрия: введение", пер.
с англ., М., Мир, 1989.
---------------------------------
Еще планируем курс по биоинформатике. Но об этом не раньше след. недели.
