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