Aplikovaná
výpočetní geometrie
Prof.dr.ing.Ivana Kolingerová
http://afrodita.zcu.cz/~kolinger
Katedra informatiky a
výpočetní techniky
Fakulta aplikovaných věd
Západočeská univerzita v
Plzni
Prerekvizity: nutné:
datové struktury, algoritmizace, znalost programování v libovolném
programovacím jazyce, doporučené:
základní znalost počítačové grafiky – v rozsahu základního kursu.
Vzhledem
k omezenému výběru vhodné české studijní literatury se doporučuje znalost
angličtiny na úrovni dovolující studovat anglické prameny.
1. Výpočetní geometrie jako
nástroj pro geometrické a grafické apliace – pojem výpočetní geometrie, oblasti
aplikací, nejčastěji řešené úlohy, ukázky užití, techniky (paradigmata)
výpočetní geometrie
2. Geometrické vyhledávání -
lokace bodu, hledání intervalů, aplikace
3. Konvexní obálky - 2D, 3D,
polygonu, on-line problém, aplikace
4. Voronoiovy diagramy -
vlastnosti, konstrukce, aplikace, dualizace, méně obvyklé typy Vor. diagramů
5. Triangulace v 2D –
Delaunayova, greedy, MWT, multikriteriálně optimalizovaná, aplikace
6. Triangulace v 3D –
komplikace oproti 2D, vlastnosti, aplikace
7. Triangulace a dělení
polygonu, problém "strážců galérie"
8. Průsečíky a průniky
základních geometrických útvarů – úsečky, polygony, poloroviny
9. Nové směry
v algoritmizaci a výpočetní geometrii
10. Pokud zbyde čas, pak výběr
z následujících témat podle zájmu studentů: kreativita, příprava přednášek
a prezentací, psaní článků.
Literatura:
1. O' Rourke, Joseph:
Computational Geometry in C, Cambridge University Press, 1.vydání, 1994 nebo
2.vydání, 2000
2. de Berg, Mark, van Kreveld,
Marc, Overmars, Mark, Schwarzkopf, Otfried: Computational Geometry, Algorithms
and Applications, Springer Verlag, 1.vydání, 1997 nebo 2.vydání, 2001
3. Preparata, F.P., Shamos, M.I.: Computational Geometry:
An Introduction, Springer-Verlag, New York Berlin Heidelberg Tokyo, 1985
4. Podklady přednášek
v PowerPoint poskytnuté vyučující
Cvičení: Hlavním bodem programu je
rozbor a prezentace algoritmů a návrh nových.
Požadavky
k zápočtu:
Pro každého existuje mnoho cest, jak získat zápočet.
Základní možnosti jsou následující:
1. Řešit řadu menších úloh tak, abyste získali
potřebný počet bodů. Úlohy budou vesměs orientovány na návrh algoritmů (obvykle
bez implementace), sepisování esejí z přečtené literatury, prezentace
algoritmů, implementace drobnějších geometricky orientovaných problémů a budou
zadávány a odevzdávány průběžně po celý semestr. Úlohy se budou vztahovat
k probírané látce.
2. Jedna větší úloha zahrnující návrh řešení,
implementaci, otestování, sepsání popisu a závěrů nějakého obtížnějšího či
pracnějšího problému tak, abyste získali potřebný počet bodů. Téma se určí
dohodou vyučující se studentem podle jeho zájmu a/nebo případné nabídky
vyučující a bude mít vztah k oblasti předmětu. Zároveň se schválením
zadání vyučující určí, kolik bodů za jakou míru splnění úlohy bude stačit na
dosažení zápočtu a za co budou body navíc.
V tématu lze v případě zájmu dále pokračovat v rámci diplomové
práce.
3. Aktivní účast na cvičení a řešení případných
povinných či nepovinných domácích úloh (obvykle jde o promyšlení nějakého
problému či návrh algoritmu.)
Je možné také předchozí formy libovolně kombinovat;
je na vás, jaké práce a kolik na získání potřebného počtu bodů poskládáte.
Úlohy budou bodovány podle předpokládané obtížnosti, nabízený maximální počet
bodů a termín odevzdání budou předem známy.
Ke zkoušce se předpokládá dobrá znalost materiálů z
přednášek, cvičení i zadávaných úloh, orientační znalost literatury 1 a hlavně
schopnost uvažovat a aplikovat probírané metody na konkrétní problémy, dokázat
zvážit vhodnost či nevhodnost daného postupu. Zkouška je písemná a ústní, v
písemné části jsou tři otázky či problémy k řešení, při ústní zkoušce se
především rozebírají studentovy práce a jeho písemná zkouška.
Minimální
potřebný počet bodů na zápočet: 30 za standardní splnění semestrální práce. Počet bodů navíc není nijak omezen a
záleží na pilnosti studenta.
Maximální
počet bodů u zkoušky: 30 bodů za 3 otázky po 10 bodech. Při menším počtu bodů je
zapotřebí zkoušku opakovat.
Celkové hodnocení:
Pokud zkoušku uděláte, sečtou se vám získané
body ze zkoušky a ze cvičení takto:
61 bodů a více
- výborně
51 – 60 bodů
- velmi dobře
45 – 50 bodů
- dobře
méně bodů
- nevyhověl