Přednášky:
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.
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.
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.
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.
Konvexní obal. Algoritmy určení konvexního obalu v dvojrozměrném prostoru.
Konvexní obal ve vícerozměrných prostorech. 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ů.
Binární dělení prostoru. BSP stromy. Aplikace.
Relace viditelnosti. Graf viditelnosti. Výpočet grafu viditelnosti pro rovinnou úlohu. Aplikace.
K aplikaci úloh probraných v předmětu: Plánování dráhy mobilního robota.
Aplikace modelování terénu v geografických systémech.
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.
Počítačové laboratoře:
U jedné zvolené úlohy z předchozího bodu posluchači provedou též detailní implementaci.
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.
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.
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.
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.
Konvexní obal. Algoritmy určení konvexního obalu v dvojrozměrném prostoru.
Konvexní obal ve vícerozměrných prostorech. 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ů.
Binární dělení prostoru. BSP stromy. Aplikace.
Relace viditelnosti. Graf viditelnosti. Výpočet grafu viditelnosti pro rovinnou úlohu. Aplikace.
K aplikaci úloh probraných v předmětu: Plánování dráhy mobilního robota.
Aplikace modelování terénu v geografických systémech.
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.
Počítačové laboratoře:
U jedné zvolené úlohy z předchozího bodu posluchači provedou též detailní implementaci.