Код: 318373

Назва:

Алгоритмічна геометрія

Анотація: Метою курсу є ознайомлення з алгоритмічними підходами розв'язання геометричних задач, що мають застосування в комп'ютерній графіці, географічних інформаційних системах, робототехніці, інтегральних схемах (IC дизайн геометрії і перевірки) тощо. В курсі розглядаються: перетин відрізків та областей, тріангуляції многокутників, діаграми Вороного, тріангуляції Делоне, пошук найкоротшого шляху. Обговорюються плюси і мінуси алгоритмів, оцінюється їх складність.

Тип дисципліни: ви біркова

Рік навчання: 1

Семестр: 2д (додатковий період весняного семестру)

Кількість кредитів: 4

Форма контролю: залік

Викладач(і): проф. , д. ф-м.н. Олійник Б.В.

Результати навчання: у результаті вивчення курсу студенти повинні оволодіти знаннями про алгоритми розв'язання геометричних задач та їх застосування в комп'ютерній графіці, географічних інформаційних системах, робототехніці тощо.

Спосіб навчання: дистанційний

Зміст дисципліни: Перетин відрізків та областей. Проблема накладання тематичних карт. Алгоритм прямої-прибиральника. Триангуляція многокутників. Задача охорони художньої галереї. Теорема про кількість трикутників при триангуляції. Діаграми Вороного та їх застосування. Алгоритм Форчуна. Триангуляція Делоне.


Рекомендована література: 1. Mark de Berg, Otfrid Cheong, Mark van Kreveld, Mark Overmars. Computational Geometry. Algorithms and Applications. - Springer-Verlag Berlin Heidelberg - 2008, 2000, 1997.
2. Препарата Ф., Шеймос М. Вычислительная геометрия. - М.: Мир, 1989.
3. А.В. Анісімов, В.М. Терещенко, І.В. Кравченко Основні алгоритми обчислювальної геометрії. Навчально-методичний посібник. - ВПЦ "Київський університет" - 2002.
4. Т. Кортмен, Ч. Лейзерсон, Р. Ривест. Алгоритмы построение и анализ. _ М.: МЦНО -2001.

Форми та методи навчання: лекції, семінари, самостійна робота

Методи й критерії оцінювання: рейтингова система оцінювання за 100-бальною шкалою: - робота в семестрі (контрольна робота, індивідуальні завдання, активність на практичних заняттях) - 70%; - залік - 30%.

Мова навчання: українська