|
Vyučující
|
-
Orlíčková Helena, prof. Dr. Ing.
|
|
Obsah předmětu
|
1. 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. -3. Geometrické vyhledávání - lokace bodu, hledání intervalů, aplikace 4. Konvexní obálky - 2D, 3D, on-line problém, aplikace 5.-6. Voronoiovy diagramy - vlastnosti, konstrukce, aplikace, dualizace, méně obvyklé typy Vor. diagramů 7.-8. Triangulace v 2D - Delaunayova, greedy, MWT, DDT, multikriteriálně optimalizovaná, triangulace s povinnými hranami, aplikace 9. Triangulace v 3D - komplikace oproti 2D, vlastnosti, aplikace, Delaunayova 3D triangulace 10. Triangulace a dělení polygonu, problém "strážců galérie" 11. Průsečíky a průniky základních geometrických útvarů - úsečky, polygony 12. Plánování pohybu robota - pohyb bodového robota, posun disku, konvex. polygonu a žebříku v 2D 13. Další zajímavé geometrické algoritmy a datové struktury, trendy a novinky ve výpočetní geometrii
|
|
Studijní aktivity a metody výuky
|
Přednáška s aktivizací, Projektová výuka, Výuka podporovaná multimédii, Prezentace práce studentů, Seminární výuka, Samostatná práce studentů, Samostudium studentů
- Příprava prezentace (referátu) [3-8]
- 5 hodin za semestr
- Příprava na zkoušku [10-60]
- 35 hodin za semestr
- Kontaktní výuka
- 52 hodin za semestr
- Projekt individuální [40]
- 40 hodin za semestr
|
| Předpoklady |
|---|
| Odborné znalosti |
|---|
| rozumět algoritmům i je sám tvořit |
| vybírat datové struktury vhodné pro řešení zadaného problému |
| aktivně užívat znalosti z analytické geometrie |
| pasivního využívání angličtiny |
| Odborné dovednosti |
|---|
| programovat v nějakém běžném programovacím jazyku (C nebo C++ nebo C# nebo Java nebo Pascal/Delphi) |
| využívat při algoritmizaci běžné datové struktury, jako je pole, strom, fronta, zásobník |
| číst odborný text anglicky |
| Obecné způsobilosti |
|---|
| mgr. studium: samostatně a odpovědně se na základě rámcového zadání rozhodují v souvislostech jen částečně známých, |
| mgr. studium: samostatně získávají další odborné znalosti, dovednosti a způsobilosti na základě především praktické zkušenosti a jejího vyhodnocení, ale také samostatným studiem teoretických poznatků oboru., |
| Výsledky učení |
|---|
| Odborné znalosti |
|---|
| znalost základních algoritmů a datových struktur obecně využívaných pro úlohy výpočetní geometrie |
| znalost speciálních algoritmů vhodných pro různé konkrétní problémy v oblasti výpočetní geometrie |
| znalost různých datových struktur vhodných pro geometricky formulované úlohy |
| Odborné dovednosti |
|---|
| umí vybrat nebo navrhnout algoritmus a datové struktury pro řešení daného geometricky formulovaného problému |
| umí odhadnout složitost algoritmu nebo ji změřit na základě jeho implementace a testování |
| umí posoudit výhody a nevýhody daného algoritmu |
| umí navržené řešení geometricky formulovaného problému implementovat a otestovat |
| Obecné způsobilosti |
|---|
| mgr. studium: používají své odborné znalosti, odborné dovednosti a obecné způsobilosti alespoň v jednom cizím jazyce, |
| mgr. studium: dle vyvíjejících se souvislostí a dostupných zdrojů vymezí zadání pro odborné činnosti, koordinují je a nesou konečnou odpovědnost za jejich výsledky, |
| Vyučovací metody |
|---|
| Odborné znalosti |
|---|
| Přednáška s aktivizací studentů, |
| Samostudium, |
| Samostatná práce studentů, |
| Prezentace práce studentů, |
| Odborné dovednosti |
|---|
| Cvičení (praktické činnosti), |
| Projektová výuka, |
| Samostatná práce studentů, |
| Hodnotící metody |
|---|
| Odborné znalosti |
|---|
| Kombinovaná zkouška, |
| Výstupní projekt, |
| Odborné dovednosti |
|---|
| Výstupní projekt, |
| Individuální prezentace, |
| Demonstrace dovedností (praktická činnost), |
|
Doporučená literatura
|
-
De Berg, Mark. Computational geometry : algorithms and applications. 2., rev. ed. Berlin : Springer, 2000. ISBN 3-540-65620-0.
-
O'Rourke, Joseph. Computational geometry in C. 2nd ed. Cambridge : Cambridge University Press, 1998. ISBN 0-521-64976-5.
|