460-4038/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ík2Semestrzimní
Jazyk výukyčeština
Rok zavedení2010/2011Rok zrušení
Určeno pro fakultyFEIUrčeno pro typy studianavazující magisterské
Výuku zajišťuje
Os. čís.JménoCvičícíPřednášející
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

Posluchač porozumí technikám konstruování algoritmů efektivně řešících geometrické úlohy. Bude sám umět také algoritmy navrhnout, implementovat a vyhodnotit jejich efektivnost.

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ů. Efektivní datové struktury pro řešení geometrických problémů. 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:

1. de Berg, M., van Kreveld M., Overmars, M., Schwarzkopf, O.: Computational Geometry: Algorithms and Applications (Third edition), Springer-Verlag, ISBN: 978-3-540-77973-5, 2008. 2. Sojka, E.:, Počítačová geometrie, texty přednášek.

Doporučená literatura:

1. Toth, C.D., Joseph O'Rourke, J., Goodman, J.E.: Handbook of Discrete and Computational Geometry, 3rd Edition, CRC Press, ISBN 9781498711395, 2017. 2. Devadoss, S.L., O'Rourke, J.: Discrete and Computational Geometry, Princeton University Press, ISBN: 9780691145532 2011. 3. O'Rourke, J.: Computational Geometry in C, Cambridge University Press, ISBN 0-521-44034-3, ISBN 0-521-44592-2, 1994. 4. Preparata, P.F., Shamos, M.I.: 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í. Zkouška je ústní.

E-learning

Další požadavky na studenta

Další požadavky na studenta nejsou kladeny.

Prerekvizity

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

Korekvizity

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

Osnova předmětu

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.

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

Prezenční forma (platnost od: 2010/2011 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 (100) 51
        Zápočet Zápočet 25  12
        Zkouška Zkouška 75  30
Rozsah povinné účasti:

Zobrazit historii

Výskyt ve studijních plánech

Akademický rokProgramObor/spec.Spec.ZaměřeníFormaJazyk výuky Konz. stř.RočníkZLTyp povinnosti
2022/2023 (N0613A140034) Informatika P čeština Ostrava 2 volitelný odborný stu. plán
2022/2023 (N0613A140034) Informatika K čeština Ostrava 2 volitelný odborný stu. plán
2022/2023 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 povinně volitelný stu. plán
2022/2023 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 povinně volitelný stu. plán
2021/2022 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 povinně volitelný stu. plán
2021/2022 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 povinně volitelný stu. plán
2020/2021 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2020/2021 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 povinně volitelný stu. plán
2020/2021 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2020/2021 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 povinně volitelný stu. plán
2019/2020 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2019/2020 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 povinně volitelný stu. plán
2019/2020 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2019/2020 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 povinně volitelný stu. plán
2018/2019 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2018/2019 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 povinně volitelný stu. plán
2018/2019 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2018/2019 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 povinně volitelný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 povinně volitelný stu. plán
2017/2018 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 povinně volitelný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 povinně volitelný stu. plán
2016/2017 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 povinně volitelný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 povinně volitelný stu. plán
2015/2016 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 povinně volitelný stu. plán
2014/2015 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2014/2015 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2014/2015 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2014/2015 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2013/2014 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2013/2014 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2013/2014 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2013/2014 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2012/2013 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2012/2013 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2012/2013 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2012/2013 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2011/2012 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2011/2012 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2011/2012 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán
2011/2012 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2010/2011 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika P čeština Ostrava 2 volitelný odborný stu. plán
2010/2011 (N2647) Informační a komunikační technologie (1103T031) Výpočetní matematika K čeština Ostrava 2 volitelný odborný stu. plán
2010/2011 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika P čeština Ostrava 2 volitelný odborný stu. plán
2010/2011 (N2647) Informační a komunikační technologie (2612T025) Informatika a výpočetní technika K čeština Ostrava 2 volitelný odborný stu. plán

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

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