460-4038/02 – Algoritmizace geometrických úloh (AGU)
| Garantující katedra | Katedra informatiky | Kredity | 4 |
| Garant předmětu | doc. Dr. Ing. Eduard Sojka | Garant verze předmětu | doc. Dr. Ing. Eduard Sojka |
| Úroveň studia | pregraduální nebo graduální | Povinnost | volitelný odborný |
| Ročník | 2 | Semestr | zimní |
| | Jazyk výuky | angličtina |
| Rok zavedení | 2015/2016 | Rok zrušení | |
| Určeno pro fakulty | FEI | Určeno pro typy studia | navazující magisterské |
Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi
Posluchač porozumí technikám konstruování algoritmů efektivně řešících geometrické úlohy. Bude sám umět také algoritmy navrhnout, implementovat a vyhodnotit jejich efektivnost.
Vyučovací metody
Přednášky
Cvičení (v učebně)
Anotace
Probírány jsou zejména tyto okruhy otázek: Složitost problému a složitost algoritmu. Techniky konstruování efektivních algoritmů. Efektivní datové struktury pro řešení geometrických problémů. Algoritmizace vybraných geometrických úloh: Problém lokalizace bodu v planární mapě. Konvexní obal. Problémy vzdálenosti a blízkosti. Voronoiův diagram. Triangulace. Problémy protínání. Problémy viditelnosti.
Povinná literatura:
1. de Berg, M., van Kreveld M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications (Third edition), Springer-Verlag, ISBN: 978-3-540-77973-5, 2008.
2. Sojka, E.:, Počítačová geometrie, texty přednášek.
Doporučená literatura:
Forma způsobu ověření studijních výsledků a další požadavky na studenta
Podmínky udělení zápočtu: Vypracování úloh zadaných na cvičení.
Zkouška je ústní.
E-learning
Další požadavky na studenta
Další požadavky na studenta nejsou kladeny.
Prerekvizity
Předmět nemá žádné prerekvizity.
Korekvizity
Předmět nemá žádné korekvizity.
Osnova předmětu
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. Odhad dolní meze časové složitosti pomocí transformace mezi problémy.
3. Datové struktury pro práci s body ve vícerozměrných prostorech (k-d stromy, kvadrantové a oktantové stromy, BSP stromy, intervalové stromy, rozsahové stromy).
4. 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.
5. Problém lokalizace bodu. Stanovení vzájemné polohy bodu a jednoduchého polygonu. Stanovení polohy bodu v planární mapě. Aplikace.
6. Konvexní obal. Algoritmy určení konvexního obalu v dvojrozměrném prostoru.
7. Konvexní obal ve vícerozměrných prostorech. Aplikace konvexního obalu.
8. Problémy vzdálenosti a blízkosti. Nalezení nejbližších sousedů v E2 a v En.
9. Voronoiův diagram. Výpočet Voronoiova diagramu. Aplikace Voronoiova diagramu k řešení úloh blízkosti.
10. Triangulace. Deloneho triangulace a její vlastnosti. Algoritmy výpočtu Deloneho triangulace. Triangulace jednoduchého polygonu.
11. Protínání. Nalezení průsečíků množiny úseček v E2. Nalezení průniku dvou polygonů.
12. 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. Vyhledávací stromy pro práci s body ve vícerozměrných prostorech.
3. Metoda zametání roviny a její použití.
4. Algoritmy lokalizace bodu v polygonu a planární mapě.
5. Konvexní obal v dvojrozměrném prostoru.
6. Konvexní obal ve vícerozměrných prostorech.
7. Problémy vzdálenosti a blízkosti. Nalezení nejbližších sousedů.
8. Výpočet Voronoiova diagramu a jeho aplikace.
9. Deloneho triangulace a její vlastnosti a výpočet.
10. Nalezení průniku dvou polygonů.
11. Výpočet grafu viditelnosti pro rovinnou úlohu.
12. Plánování dráhy mobilního robota.
13. Modelování terénu v geografických systémech.
14. Shrnutí a zápočet.
Podmínky absolvování předmětu
Výskyt ve studijních plánech
Výskyt ve speciálních blocích
Hodnocení Výuky
Předmět neobsahuje žádné hodnocení.