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