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- г. Кафедра Математической теории интеллектуальных систем, лаборатория ПТК, лаборатория МПИИ Написать вебмастеру   
Последние новости - в телеграм-канале кафедры МаТИС: Канал кафедры МаТИС в Телеграм Rambler's Top100 Рейтинг@Mail.ru