Předmět Algoritmizace geometrických úloh (AGU)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu AGU - Algoritmizace geometrických úloh, Vysoká škola báňská - Technická univerzita Ostrava (VŠB-TU).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Cíl
Posluchač porozumí technikám konstruování algoritmů efektivně řešících geometrické úlohy. Bude sám umět také algoritmynavrhnout, implementovat a vyhodnotit jejich efektivnost.
Osnova
Přednášky:1. Složitost problému a složitost algoritmu. Složitost nejhoršího případu, střední složitost. Modely výpočtu. RAM,algebraický rozhodovací strom. 2. Odhad dolní meze časové složitosti v nejhorším případě pomocí transformace na úlohu lokalizace bodu v En. Odhaddolní meze časové složitosti pomocí transformace mezi problémy. 3. Základní techniky konstruování efektivních algoritmů: Metoda "zametání roviny", metoda "rozděl a panuj", metoda"prohledávání a vylučování", "randomizované" algoritmy. 4. Problém lokalizace bodu. Stanovení vzájemné polohy bodu a jednoduchého polygonu. Stanovení polohy bodu v planárnímapě. Identifikace bodů padnoucích do dané obdélníkové oblasti. Aplikace.5. Konvexní obal. Algoritmy určení konvexního obalu v dvojrozměrném prostoru. 6. Konvexní obal ve vícerozměrných prostorech. Konvexní obal v E3. Aplikace konvexního obalu. 7. Problémy vzdálenosti a blízkosti. Nalezení dvojice vzájemně nejbližších bodů v E2 a v En. Problém detekce jedinečnostibodů. 8. Voronoiův diagram. Výpočet Voronoiova diagramu. Aplikace Voronoiova diagramu k řešení úloh blízkosti. 9. Triangulace. Deloneho triangulace a její vlastnosti. Randomizovaný algoritmus výpočtu Deloneho triangulace.Triangulace jednoduchého polygonu. 10. Protínání. Nalezení průsečíků množiny úseček v E2. Nalezení průniku dvou polygonů. 11. Binární dělení prostoru. BSP stromy. Aplikace. 12. Relace viditelnosti. Graf viditelnosti. Výpočet grafu viditelnosti pro rovinnou úlohu. Aplikace. 13. K aplikaci úloh probraných v předmětu: Plánování dráhy mobilního robota.14. Aplikace modelování terénu v geografických systémech.Cvičení (PC učebna):Ve cvičení posluchači navrhují algoritmy řešící zadané úlohy, formou diskuse svá řešení obhajují, vyhodnocují jejichčasovou a paměťovou složitost.1. Transformace mezi úlohami a odhad dolní meze časové složitosti.2. Metoda zametání roviny a její použití pro úlohu hledání průsečíků úseček.3. Algoritmy lokalizace bodu v polygonu a planární mapě.4. Konvexní obal v dvojrozměrném prostoru.5. Konvexní obal ve vícerozměrných prostorech.6. Problémy vzdálenosti a blízkosti. Nalezení dvojice vzájemně nejbližších bodů.7. Výpočet Voronoiova diagramu a jeho aplikace.8. Deloneho triangulace a její vlastnosti.9. Nalezení průniku dvou polygonů.10. BSP, AVL, red-black stromy a jejich aplikace.11. Výpočet grafu viditelnosti pro rovinnou úlohu.12. Plánování dráhy mobilního robota.13. Aplikace modelování terénu v geografických systémech.14. Diskuse k tématům z přednášek. Shrnutí.
Literatura
1. M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry: Algorithms and Applications(Third edition), Springer-Verlag, 2008, ISBN: 978-3-540-77973-5. 2. E.Sojka, Počítačová geometrie, texty přednášek.
Požadavky
Žádné
Garant
doc. Dr. Ing. Eduard Sojka
Vyučující
Ing. Jan Gaura, Ph.D.doc. Dr. Ing. Eduard Sojka