Бакалавриат
2020/2021
Вычислительная геометрия
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Кто читает:
Департамент информатики
Когда читается:
4-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Преподаватели:
Ковалев Антон Сергеевич
Язык:
русский
Кредиты:
4
Контактные часы:
60
Программа дисциплины
Аннотация
Является дисциплиной по выбору. Студенты получат представление об основных алгоритмах вычислительной геометрии. Научатся создавать эффективные программы для решения характерных задач в этой области В результате освоения дисциплины студент должен: знать алгоритмы вычислительной геометрии; уметь создавать эффективные по времени и памяти программы для решения задач данной области; владеть математическим аппаратом и инструментальными средствами, используемым в вычислительной геометрии.
Цель освоения дисциплины
- Целями освоения дисциплины «Вычислительная геометрия» являются формирование у студентов теоретических знаний и практических навыков по основам вычислительной геометрии. Студенты получат представление об основных алгоритмах вычислительной геометрии. Научатся создавать эффективные программы для решения характерных задач в этой области.
Планируемые результаты обучения
- Владеет понятиями: принадлежность точки многоугольнику; выпуклые оболочки; пересечение отрезков и многоугольников.
- Владеет понятиями: триангуляция простого многоугольника. Владеет понятиями: разбиение многоугольника на монотонные многоугольники; триангуляция монотонного многоугольника. Знает: метод детализации триангуляции Киркпатрика.
- Владеет понятием: трапецоидальная карта (основные свойства, построение) Знает диаграмму Вороного: основные свойства, построение.
- Владеет понятиями: триангуляция множества точек на плоскости; триангуляция Делоне; планирование пути.
Содержание учебной дисциплины
- Принадлежность точки многоугольнику, пересечение отрезков
- Триангуляция простого многоугольника. Разбиение на монотонные многоугольники.
- Трапецоидальная карта и диаграмма Вороного
- Триангуляция множества точек, планирование пути
Элементы контроля
- Домашнее задание 1
- Домашнее задание 2
- Домашнее задание 3
- Домашнее задание 4
- Устный экзамен
Промежуточная аттестация
- Промежуточная аттестация (2 модуль)0.125 * Домашнее задание 1 + 0.125 * Домашнее задание 2 + 0.125 * Домашнее задание 3 + 0.125 * Домашнее задание 4 + 0.5 * Устный экзамен
Список литературы
Рекомендуемая основная литература
- Boissonnat, J.-D., & Teillaud, M. (2006). Effective Computational Geometry for Curves and Surfaces. Berlin: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=176637
Рекомендуемая дополнительная литература
- Computational geometry : algorithms and applications. (2008). Springer. https://doi.org/10.1007/978-3-540-77974-2