Код: 315437

Назва:

Обчислювальна геометрія

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

Тип дисципліни: вибіркова (професійно-орієнтована)

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

Семестр: 5

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

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

Викладач(і): ст. в., к. н. Тимошкевич Л.М.

Результати навчання: у результаті вивчення дисципліни студент повинен:
- знати різні методи побудови опуклої оболонки скінченної множини точок;
- знати метод прямої-прибиральника пошуку точок перетину відрізків на площині;
- застосовувати метод прямої прямої-прибиральника до задач знаходження перетину областей, триангуляції многокутників, побудови діаграм Вороного.


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

Необхідні обовязкові попередні й супутні модулі: дискретна математика; алгебра та геометрія; програмування

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


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


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

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

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