Бакалавриат
2025/2026
Вычислительная геометрия
Статус:
Курс по выбору (Прикладная математика и информатика)
Кто читает:
Базовая кафедра Яндекс
Где читается:
Факультет компьютерных наук
Когда читается:
2-й курс, 3, 4 модуль
Охват аудитории:
для своего кампуса
Язык:
русский
Кредиты:
6
Контактные часы:
80
Программа дисциплины
Аннотация
«В рамках изучения дисциплины студенты получат представление об основных алгоритмах вычислительной геометрии и научатся создавать эффективные программы для решения характерных задач в этой области. Для освоения дисциплины студентам необходимы знания, полученные в результате изучения линейной алгебры и геометрии, основ программирования.»
Цель освоения дисциплины
- Знать основные алгоритмы построения выпуклых оболочек для конечного множества точек в 2D и 3D. Уметь использовать следующие техники и приемы для решения геометрических задач: scan line, разделяй и властвуй, метод видимых граней, сумма Минковского. Знать алгоритмы построения триангуляции Делоне, диаграммы Вороного. Знать структуры данных для индексирования геометрических объектов. Уметь использовать геохеширование для поиска точек на Земле. Знать сложности и ограничения, возникающие при решении логистических задач, основные эвристические приемы.
Планируемые результаты обучения
- Знание и умение писать основные алгоритмы вычислительной геометрии
- Умение эффективно решать задачи поиска точек и многоугольников среди заданного множества по некоторым критериям
- Умение эффективно решать задачи перемещения на карте
Содержание учебной дисциплины
- Введение
- Выпуклая оболочка 2D
- Диаметр, выпуклая оболочка 3D
- Выпуклая оболочка 3D
- Алгоритм Чана. Принадлежность многоугольнику
- Сумма Минковского. Scan line
- Триангуляция Делоне
- Планарные графы близости
- Диаграмма Вороного
- Алгоритм Форчуна
- KD-дерево
- Квадродерево
- R-дерево
- Геохеш
- Сетки
- Кластеризация
- Задача коммивояжера
- Vehicle Routing Problem
- Притягивание и сглаживание треков
- Подведение итогов
