456-0301/01 – Algoritmizace geometrických úloh (AGU)

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í2003/2004Rok zrušení2009/2010
Určeno pro fakultyFEIUrčeno pro typy studianavazující magisterské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
GAU01 Ing. Jan Gaura, Ph.D.
SOJ10 doc. Dr. Ing. Eduard Sojka
Rozsah výuky pro formy studia
Forma studiaZp.zak.Rozsah
prezenční Zápočet a zkouška 2+2
kombinovaná Zápočet a zkouška 10+0

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

Předmět seznamuje posluchače s technikami konstruování algoritmů efektivně řešících geometrické úlohy.

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

Povinná: 1. Devadoss, S., L., O'Rourke, J.: Discrete and Computational Geometry, Princeton University Press, ISBN: 978-0691145532, 2011 2. M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Computational Geometry: Algorithms and Applications (Third edition), Springer-Verlag, ISBN: 978-3-540-77973-5, 2008 3. E.Sojka, Počítačová geometrie, texty přednášek Doporučená: 1. J. O'Rourke, Computational Geometry in C, Cambridge University Press, ISBN-10: 0521649765, ISBN-13: 978-0521649766, 1998 2. P.F. Preparata and M.I. Shamos, Computational geometry: An Introduction, Springer, ISBN: 0-387-96131-3, 1985

Doporučená literatura:

1. J. O'Rourke, Computational Geometry in C, Cambridge University Press, ISBN-10: 0521649765, ISBN-13: 978-0521649766, 1998 2. P.F. Preparata and M.I. Shamos, Computational geometry: An Introduction, Springer, ISBN: 0-387-96131-3, 1985

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

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

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

Prezenční forma (platnost od: 1990/1991 zimní 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 (100) 51
        Zápočet Zápočet 25 (25) 0
                Soubor příkladů Písemka 25  0
        Zkouška Zkouška 75 (75) 0
                Ústní zkouška Ústní zkouška 75  40
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
2009/2010 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2009/2010 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2009/2010 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2009/2010 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2008/2009 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 3 povinně volitelný stu. plán
2008/2009 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2008/2009 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2008/2009 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2008/2009 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2008/2009 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinný stu. plán
2008/2009 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 3 povinně volitelný stu. plán
2007/2008 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 3 povinně volitelný stu. plán
2007/2008 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2007/2008 (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
2007/2008 (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
2007/2008 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2007/2008 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 3 povinně volitelný stu. plán
2007/2008 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2007/2008 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2007/2008 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2007/2008 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2006/2007 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 3 povinně volitelný stu. plán
2006/2007 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2006/2007 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2006/2007 (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
2006/2007 (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
2006/2007 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2006/2007 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2006/2007 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 3 povinně volitelný stu. plán
2006/2007 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2006/2007 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2006/2007 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2006/2007 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2005/2006 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 3 povinně volitelný stu. plán
2005/2006 (N2646) Informační technologie (1103T021) Počítačová matematika P čeština Ostrava 3 povinně volitelný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (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
2005/2006 (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
2005/2006 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2005/2006 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 3 povinně volitelný stu. plán
2005/2006 (N2646) Informační technologie (1103T021) Počítačová matematika K čeština Ostrava 3 povinně volitelný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 5 povinně volitelný stu. plán
2004/2005 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 3 povinně volitelný stu. plán
2004/2005 (N2646) Informační technologie (1103T021) Počítačová matematika P čeština Ostrava 3 povinně volitelný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (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
2004/2005 (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
2004/2005 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2004/2005 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 3 povinně volitelný stu. plán
2004/2005 (N2646) Informační technologie (1103T021) Počítačová matematika K čeština Ostrava 3 povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava 5 povinně volitelný stu. plán
2003/2004 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 3 povinně volitelný stu. plán
2003/2004 (N2646) Informační technologie (1103T021) Počítačová matematika P čeština Ostrava 3 povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (2601T004) Měřicí a řídicí technika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (2612T018) Elektronika a sdělovací technika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (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
2003/2004 (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
2003/2004 (M2612) Elektrotechnika a informatika (3902T023) Inženýrská informatika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (M2612) Elektrotechnika a informatika (3907T001) Elektroenergetika P čeština Ostrava povinně volitelný stu. plán
2003/2004 (N2646) Informační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 3 povinně volitelný stu. plán
2003/2004 (N2646) Informační technologie (1103T021) Počítačová matematika K čeština Ostrava 3 povinně volitelný stu. plán
2003/2004 (B2612) Elektrotechnika a informatika (1801R001) 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