• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Computational Geometry

2020/2021
Academic Year
RUS
Instruction in Russian
4
ECTS credits
Delivered at:
Department of Informatics
Course type:
Elective course
When:
4 year, 1, 2 module

Instructor


Ковалев Антон Сергеевич

Программа дисциплины

Аннотация

Является дисциплиной по выбору. Студенты получат представление об основных алгоритмах вычислительной геометрии. Научатся создавать эффективные программы для решения характерных задач в этой области В результате освоения дисциплины студент должен:  знать алгоритмы вычислительной геометрии;  уметь создавать эффективные по времени и памяти программы для решения задач данной области;  владеть математическим аппаратом и инструментальными средствами, используемым в вычислительной геометрии.
Цель освоения дисциплины

Цель освоения дисциплины

  • Целями освоения дисциплины «Вычислительная геометрия» являются формирование у студентов теоретических знаний и практических навыков по основам вычислительной геометрии. Студенты получат представление об основных алгоритмах вычислительной геометрии. Научатся создавать эффективные программы для решения характерных задач в этой области.
Планируемые результаты обучения

Планируемые результаты обучения

  • Владеет понятиями: принадлежность точки многоугольнику; выпуклые оболочки; пересечение отрезков и многоугольников.
  • Владеет понятиями: триангуляция простого многоугольника. Владеет понятиями: разбиение многоугольника на монотонные многоугольники; триангуляция монотонного многоугольника. Знает: метод детализации триангуляции Киркпатрика.
  • Владеет понятием: трапецоидальная карта (основные свойства, построение) Знает диаграмму Вороного: основные свойства, построение.
  • Владеет понятиями: триангуляция множества точек на плоскости; триангуляция Делоне; планирование пути.
Содержание учебной дисциплины

Содержание учебной дисциплины

  • Принадлежность точки многоугольнику, пересечение отрезков
  • Триангуляция простого многоугольника. Разбиение на монотонные многоугольники.
  • Трапецоидальная карта и диаграмма Вороного
  • Триангуляция множества точек, планирование пути
Элементы контроля

Элементы контроля

  • неблокирующий Домашнее задание 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