Přednášky:
Složitost problému a složitost algoritmu. Složitost nejhoršího případu a střední složitost. Modely výpočtu. RAM. Lineární rozhodovací strom.
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.
Metoda "zametání roviny". Metoda "rozděl a panuj".
Problém lokalizace bodu. Stanovení vzájemné polohy bodu a jednoduchého polygonu. Stanovení polohy bodu v planární mapě.
Randomizovaný přístup k řešení problému lokalizace bodu v planární mapě. Randomizovaná lichoběžníková metoda.
Vyhledání bodů padnoucích do dané ortogonální oblasti. Metoda vícerozměrného binárního vyhledávání. Metoda využívající stromu intervalů.
Konvexní obal. Algoritmy určení konvexního obalu v rovině.
Konvexní obal ve vícerozměrných prostorech. Metoda "balení dárku". Konvexní obal v E3. Aplikace konvexního obalu.
Problémy vzdálenosti a blízkosti. Nalezení dvojice vzájemně nejbližšších bodů v E2 a v En. Problém detekce jedinečnosti bodů.
Voronoiův diagram. Výpočet Voronoiova diagramu. Aplikace Voronoiova diagramu k řešení úloh blízkosti.
Triangulace. Deloneho triangulace a její vlastnosti. Randomizovaný algoritmus výpočtu Deloneho triangulace. Triangulace jednoduchého polygonu.
Protínání. Nalezení průsečíků množiny úseček v E2. Nalezení průniku dvou polygonů.
Viditelnost. Graf viditelnosti. Výpočet grafu viditelnosti v rovinném případě. Aplikace.
K aplikaci úloh probraných v předmětu: Plánování dráhy mobilního robota.
Cvičení:
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. U jedné zvolené úlohy provedou též detailní implementaci.
Složitost problému a složitost algoritmu. Složitost nejhoršího případu a střední složitost. Modely výpočtu. RAM. Lineární rozhodovací strom.
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.
Metoda "zametání roviny". Metoda "rozděl a panuj".
Problém lokalizace bodu. Stanovení vzájemné polohy bodu a jednoduchého polygonu. Stanovení polohy bodu v planární mapě.
Randomizovaný přístup k řešení problému lokalizace bodu v planární mapě. Randomizovaná lichoběžníková metoda.
Vyhledání bodů padnoucích do dané ortogonální oblasti. Metoda vícerozměrného binárního vyhledávání. Metoda využívající stromu intervalů.
Konvexní obal. Algoritmy určení konvexního obalu v rovině.
Konvexní obal ve vícerozměrných prostorech. Metoda "balení dárku". Konvexní obal v E3. Aplikace konvexního obalu.
Problémy vzdálenosti a blízkosti. Nalezení dvojice vzájemně nejbližšších bodů v E2 a v En. Problém detekce jedinečnosti bodů.
Voronoiův diagram. Výpočet Voronoiova diagramu. Aplikace Voronoiova diagramu k řešení úloh blízkosti.
Triangulace. Deloneho triangulace a její vlastnosti. Randomizovaný algoritmus výpočtu Deloneho triangulace. Triangulace jednoduchého polygonu.
Protínání. Nalezení průsečíků množiny úseček v E2. Nalezení průniku dvou polygonů.
Viditelnost. Graf viditelnosti. Výpočet grafu viditelnosti v rovinném případě. Aplikace.
K aplikaci úloh probraných v předmětu: Plánování dráhy mobilního robota.
Cvičení:
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. U jedné zvolené úlohy provedou též detailní implementaci.