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.
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.