Предмет: Комбинаторни и геометријски алгоритми (17.D0M32Z )
Студијски програми предмета:
| Степен и врста студија | Назив |
|---|---|
| Докторске студије | Математика у техници (Година: 1, Семестар: Зимски) |
| Докторске студије | Математика у техници (Година: 2, Семестар: Зимски) |
Усвајање знања из области теорије геометријских алгоритама, као и њихова примена на решавање стандардних геометријских проблема.
Очекује се да успешан студент усвоји основне концепте складиштења геометријских објеката коришћењем одговарајућих структура података, као и ефикасних алгоритама који се на њих могу применити. Такође, од студента се очекује да буде способан да модификује познате алгоритме и прилагоди их за решавање нових проблема.
Структуре података за складиштење геометријских објеката. Детерминистичке методе за рад са скуповима тачака, подели-и-освоји, чишћење. Најближи пар, најдаљи пар. Методе случајног узорка. Теорема узорка, теорема момента. Вероватносни алгоритми, онлајн алгоритми, динамички алгоритми. Конвексна обвојница, политопи. Разни алгоритми надоградње за рачунање конвексне обвојнице. Конвексна обвојница у две димензије. Веза са сортирањем низа. Конвексна обвојница скупа лопти. Најмања лопта која садржи скуп тачака. Тријангулације у две димензије, са и без ограничења. Делони тријангулације, тријангулације у три димензије. Симплекс и комплекс. Чување галерије. Бинарне поделе простора, Молеров алгоритам. Квадрво и октдрво. Уређења хиперравни, разуђеност. Теорема зоне. Конструкција надоградњом. Уређења правих у равни, дуалност, уређења дужи у равни.
Предавања су аудиторна. На предавањима се излажу основни принципи, као и могућности примене усвојених алгоритамских техника на решавање разних геометријских проблема. Студент је обавезан да напише семинарски рад.
| Аутори | Назив | Година | Издавач | Језик |
|---|---|---|---|---|
| 2008 | Енглески | |||
| 2002 | Енглески |
| Предметна активност | Предиспитна | Обавезна | Број поена |
|---|---|---|---|
| Предметна активност Семинарски рад |
Предиспитна Да |
Обавезна Да |
Број поена 20.00 |
| Предметна активност Усмени део испита |
Предиспитна Не |
Обавезна Да |
Број поена 70.00 |
| Предметна активност Присуство на предавањима |
Предиспитна Да |
Обавезна Да |
Број поена 10.00 |
