456-0108/01 – Konstruování efektivních algoritmů v počítačové grafice a geometrii (KEA)

Garantující katedraKatedra informatikyKredity4
Garant předmětudoc. Dr. Ing. Eduard SojkaGarant verze předmětudoc. Dr. Ing. Eduard Sojka
Úroveň studiapregraduální nebo graduálníPovinnostpovinně volitelný
RočníkSemestrzimní
Jazyk výukyčeština
Rok zavedení1998/1999Rok zrušení2002/2003
Určeno pro fakultyFEIUrčeno pro typy studiamagisterské
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 2+2

Cíle předmětu vyjádřené dosaženými dovednostmi a kompetencemi

Předmět se zaměřuje na otázku jak konstruovat efektivní algoritmy řešící geometrické úlohy.

Vyučovací metody

Anotace

Předmět se zaměřuje na otázku jak konstruovat geometrické algoritmy, které vykazují nízkou časovou a paměťovou složitost. Probírány jsou zejména tyto okruhy otázek: Složitost problému a složitost algoritmu. Problém lokalizace bodu v planární mapě. Problém vyhledání bodů padnoucích do dané oblasti. Konvexní obal. Problémy vzdálenosti a blízkosti. Voronoiův diagram. Triangulace. Problémy protínání. Problémy viditelnosti.

Povinná literatura:

E.Sojka, Počítačová geometrie, texty přednášek, 1994-9. M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry: Algorithms and Applications, Springer, 1997 (ISBN 3-540-61270-X).

Doporučená literatura:

J. O'Rourke, Computational Geometry in C, Cambridge University Press, 1994 (ISBN 0-521-44034-3, ISBN 0-521-44592-2). P.F. Preparata and M.I. Shamos, Computational geometry: An Introduction, Springer, 1985 (ISBN 0-387-96131-3).

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 ve cvičení.

E-learning

Další požadavky na studenta

Prerekvizity

Předmět nemá žádné prerekvizity.

Korekvizity

Předmět nemá žádné korekvizity.

Osnova předmětu

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.

Podmínky absolvování předmětu

Prezenční forma (platnost od: 1960/1961 letní semestr)
Název úlohyTyp úlohyMax. počet bodů
(akt. za podúlohy)
Min. počet bodů
Zápočet a zkouška Zápočet a zkouška 100 (145) 51
        Zkouška Zkouška 100  0
        Zápočet Zápočet 45  0
Rozsah povinné účasti:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.FormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2002/2003 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2002/2003 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 5 povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (10) Elektrické stroje a přístroje P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (2642T004) Elektrické stroje, přístroje a pohony (20) Elektrické pohony a výkonová elektronika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2001/2002 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 5 povinně volitelný stu. plán
2000/2001 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 5 povinně volitelný stu. plán

Výskyt ve speciálních blocích

Název blokuAkademický rokForma studiaJazyk výuky RočníkZLTyp blokuVlastník bloku