English version of this page
На главную страницу
Официальный сайт кафедры Математической теории интеллектуальных систем и
лаборатории Проблем теоретической кибернетики
механико-математического факультета МГУ им. М. В. Ломоносова
На первую страницу сервера Новости Кафедра Сотрудники Учеба Наука Исследования Журнал Культура Полнотекстовый поиск по серверу
 ТДФ Теория дискретных функций – лекции и семинары для студентов 1 курса (II поток)
 Ташкентский филиал Ташкентский филиал МГУ им. М.В. Ломоносова
 Семинары расписание специальных семинаров кафедры МаТИС
 Курсы расписание специальных курсов кафедры, программа курсов
 Практикум cпециальный математический практикум кафедры МаТИС, III курс
 Студенты список студентов кафедры по курсам и группам, расписание занятий, выпускники
 Магистратура информация для поступающих в магистратуру
 Аспирантура информация для аспирантов и поступающих в аспирантуру; списки аспирантов
  1. Приоритетная очередь. Пирамидальная сортировка. Алгоритм быстрой сортировки. Алгоритм нахождения к-го наименьшего элемента. Красные-Черные деревья данных.
  2. Метод заметающей прямой. Алгоритм Бентли-Отмана нахождения пересечений отрезков на плоскости.
  3. Алгоритм локализации точки на планарном подразбиении методом полос.
  4. Алгоритм локализации точки на планарном подразбиении методом цепей.
  5. Алгоритм триангуляции простого многоугольника. Задача об оптимальном освещении (The Art Gallery problem).
  6. Алгоритм локализации точки на планарном подразбиении методом детализации триангуляции.
  7. Алгоритм локализации точки на планарном подразбиении методом трапеций.
  8. Дерево отрезков.
  9. Алгоритм нахождения площади объединения прямоугольников.
  10. 2-D-деревья. Алгоритм регионального поиска с помощью 2-D-дерева.
  11. Дерево регионов. Алгоритм регионального поиска с помощью дерева регионов. Техника частичного каскада.
  12. Дерево интервалов. Алгоритм нахождения всех интервалов, содержащих заданную точку.
  13. Алгоритм нахождения всех отрезков на плоскости, пересекающих заданное окно.
  14. Алгоритм перечисления всех пересекающихся пар изотетичных прямоугольников.
  15. Построения выпуклой оболочки методом обхода Грэхема.
  16. Построения выпуклой оболочки методом обхода Джарвиса.
  17. Быстрый метод построения выпуклой оболочки.
  18. Построения выпуклой оболочки методом «разделяй и властвуй».
  19. Алгоритм построения выпуклой оболочки в реальном времени.
  20. Структура данных для поддержки динамической выпуклой оболочки.
  21. Структура данных «Пирамида Фибоначчи». Алгоритм Дийкстры .
  22. Алгоритм построения кратчайшего пути в простом многоугольнике с препятствиями.
  23. Алгоритм И.Балабана нахождения пересечений отрезков на плоскости.
  24. Построение графа видимости для М точек, лежащих в простом многоугольнике без дыр.

 

Список литературы

  1. Ф.Препарата, М.Шеймос, Вычислительная геометрия. Введение. Изд. «Мир», 1989.
  2. M.Berg, M. van Kreveld, M.Overmars, O.Schwarzkopf, Computational Geometry. Algorithms and Applications. Springer-Verlag, 1998.
  3. T.H.Cormen, C.E.Leiserson, R.L.Rivest, C.Stein, Introduction to Algorithms, MIT Press, 2001. Имеется русский перевод.
  4. А.Ахо, Дж.Хопкрофт, Дж.Ульман, Построение и анализ вычислительных алгоритмов. Изд. «Мир», 1979.

Наверх

Перейти к полному списку специальных курсов кафедры

Программа полугодового спецкурса "Алгоритмы вычислительной геометрии"

Алгоритмы вычислительной геометрии
   © 2001-2015 г. Кафедра Математической теории интеллектуальных систем, лаборатория Проблем теоретической кибернетики Написать вебмастеру   
XWare
 Полнотекстовый поиск
 
Только точная форма слов      Выводить по результатов на странице
Rambler's Top100 Рейтинг@Mail.ru