Aplikovaná výpočetní geometrie

Prof.dr.ing.Ivana Kolingerová

kolinger@kiv.zcu.cz

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