Vybrané
algoritmické metody
Prof. Dr. Ing.Ivana Kolingerová
1. Úvod, příklady řešených
problémů, aplikační oblasti, degenerovanost a robustnost, složitost a hodnocení
algoritmů, základní techniky, geometrické predikáty
2. Geometrické vyhledávání -
lokace bodu, hledání intervalů, aplikace
3. Konvexní obálky - 2D, 3D, 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, DDT, multikriteriálně optimalizovaná, triangulace
s povinnými hranami, aplikace
6. Triangulace v 3D –
komplikace oproti 2D, vlastnosti, aplikace, Delaunayova 3D triangulace
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
9. Plánování pohybu robota –
pohyb bodového robota, posun disku, konvex. polygonu a žebříku v 2D
10. Další zajímavé geometrické
algoritmy a datové struktury, trendy a novinky ve výpočetní geometrii
Literatura:
1. O' Rourke, Joseph:
Computational Geometry in C, Cambridge University Press,
1.vydání, 1994 nebo 2.vydání, 2000
Tato kniha bude pramenem většiny z toho, co budeme
probírat. Je k prezenčnímu vypůjčení v knihovně (příp."přes
noc") a předpokládám, že každý z vás by měl probírané partie z ní
zvládnout přečíst.
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
Tato kniha je o něco obtížnější a je vhodná spíše
pro vaše případné doplňkové studium, její znalost není předpokládána ke
zkoušce. Některé algoritmy z ní ale budou do studijní látky zařazeny.
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 zkouška.
Cvičení: Hlavním bodem programu je
rozbor a prezentace algoritmů a návrh nových.
Požadavky
k zápočtu:
1. Vyřešíte jednu až dvě úlohy zahrnující především návrh
řešení, obvykle také 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ů. Úlohy si vyberete ze seznamu na domácích
stránkách předmětu anebo se dohodnete na vhodném zadání s vyučující. Bodování
úloh je podle náročnosti zadání a kvalit a úplnosti řešení. Na zadání může také
pracovat společně více lidí, musí být ale schopni specifikovat svůj podíl na
řešení, získané body se pak rozdělí. Na úloze také může samostatně pracovat
několik konkurenčních řešitelů, pak se jejich řešení musí vzájemně podstatně
lišit.
2. 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 a jeho prezentace.)
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. Pozdní odevzdání bude penalizováno
bodovou ztrátou. Pokud bude úloha odevzdána až v náhradním termínu
zápočtu, aniž jste k tomu měli vážný, zejména zdravotní, důvod, bude
bodována jen polovinou původně nabízeného počtu bodů.
Minimální
požadovaný počet bodů na zápočet: 30
Minimální
potřebný počet bodů z písemky u zkoušky: 15, maximální možný počet: 30 z 3
otázek po 10 bodech
Celkové hodnocení (podmínkou je dosažení min. požadovaného
počtu bodů k zápočtu i u zkoušky):
61 bodů a více -
výborně
51 – 60 bodů
- velmi dobře
45 – 50 bodů
- dobře
méně bodů
- nevyhověl