ČeskyEnglish

Popis předmětu - A4M39VG

Přehled studia | Přehled oborů | Všechny skupiny předmětů | Všechny předměty | Seznam rolí | Vysvětlivky               Návod
A4M39VG Výpočetní geometrie Rozsah výuky:2+2s
Garanti:Felkel P. Role:PO,V Zakončení:Z,ZK
Vyučující:Felkel P.
Zodpovědná katedra:13139 Kreditů:6 Semestr:Z

Anotace:

Cílem výpočetní geometrie je analýza a návrh efektivních algoritmů pro určování vlastností a vztahů geometrických objektů. Řeší se problémy geometrického vyhledávání, problém polohy bodu, hledání konvexní obálky množiny bodů v d-rozměrném prostoru, problém hledání blízkých bodů, výpočet průniků polygonálních oblastí a poloprostorů, geometrie rovnoběžníků. Seznámíme se s novými směry návrhu algoritmů. Výpočetní geometrie nachází uplatnění nejen v geometrických aplikacích, ale i v obecných vyhledávacích problémech.

Výsledek studentské ankety předmětu je zde: A4M39VG

Cíle studia:

Předmět je neformálním pokračováním předmětů seznamujících se základními datovými strukturami a algoritmy. Seznámíte se s geometrickými algoritmy a datovými strukturami umožňujícími efektivní výpočty, například lokalizaci oblasti zasažené paprskem, výpočet průsečíků či triangulaci. Na cvičeních se procvičíte v prezentaci a odborné diskusi. To vše by nemělo chybět ve výbavě vzdělaného moderního inženýra. Těžištěm práce studentů na cvičeních je samostatné studium zadaného tématu, přednáška na zadané téma a následné zpracování tématu ve formě odborného článku. Po přednášce následuje odborná diskuse, obdobně jako na specializované konferenci. Poté se úlohy vymění, plénum hodnotí kvalitu prezentovaných materiálů a projev přednášejícího a upozorňuje na místa, která je třeba lépe vysvětit či vylepšit. Díky tomu mají přednášky velmi vysokou kvalitu, což je užitečné pro obě strany - přednášející se učí technikám prezentace a posluchači se detailně seznámí s daným tématem. Získané zkušenosti uplatní nejen při obhajobě diplomové práce, ale i při přípravě prezentací v praxi.

Osnovy přednášek:

1. Výpočetní geometrie, typické aplikace, techniky návrhu efektivních algoritmů
2. Geometrické vyhledávání - lokalizace oblasti pro zadaný bod
3. Geometrické vyhledávání - range search
4. Konvexní obálka množiny bodů v rovině
5. Konvexní obálka množiny bodů v prostoru
6. Voronoiův diagram množiny bodů
7. Voronoiův diagram úseček, Voronoiovy diagramy vyšších řádů
8. Triangulace
9. Algoritmy výpočtu průsečíků úseček a polygonů
10. Průsečík množiny úseček s obdélníkovým oknem
11. Arrangementy
12. Duální algoritmy
13. Nové směry v návrhu algoritmů
14. Rezerva

Osnovy cvičení:

Každý student podrobně nastuduje jedno téma a na cvičení přednese referát o tomto tématu. Pro přednesení referátu na cvičení si připraví prezentaci v programu Power-Point či OpenOffice Impress. Po vystoupení a zodpovězení dotazů posluchačů následuje hodnocení prezentace ostatními studenty s náměty na vylepšení. Dále naprogramuje zadané domácí úlohy (bude zadávány průběžně, první úloha 2. týden) Prezentace i domácí úkoly se odevzdávají v elektronické podobě (Adresář k odevzdávání projektů je shodný s Vaším uživatelským jménem):
1. Seznámení s formou cvičení a tématy referátů. Základní matematické postupy použitelné ve výpočetní geometrii.
2. Přesnost geometrických predikátů a konstruktů. Zadání 1. domácího úkolu (DL 4. týden).
3. Vystoupení na zadané téma, diskuse. Hodnocení materiálů a projevu ostatními studenty, náměty na vylepšení.
4. Vystoupení na zadané téma. Zadání 2. domácího úkolu (DL 6. týden)
5. Vystoupení na zadané téma
6. Vystoupení na zadané téma. Zadání 3. domácího úkolu (DL 9. týden)
7. Vystoupení na zadané téma
8. Vystoupení na zadané téma
9. Vystoupení na zadané téma.Zadání 4. domácího úkolu (DL 13. týden)
10. Vystoupení na zadané téma
11. Vystoupení na zadané téma
12. Vystoupení na zadané téma
13. Zápočet
14. Rezerva

Literatura:

1. Berg, M. de, Cheong, O., Kreveld, M. van, Overmars, M.: Coputational Geometry. Algorithms and Applications, Springer-Verlag, Berlin, 3rd ed., 2008. ISBN: 978-3-540-77973-5
2. O' Rourke, Joseph: Computational Geometry in C, Cambridge University Press, 1.vydání, 1994 nebo 2.vydání, 2000
3. Preperata F.P.- M.I.Shamos: Computational Geometry An Introduction. Berlin, Springer-Verlag,1985.

Požadavky:

Znalost základních algoritmů řazení a vyhledávání, operační a paměťové složitost algoritmů. Výhodou je i znalost lineární algebry, základů počítačové grafiky a schopnost číst materiály v angličtině. Znalost programování v jazyce C++.

Poznámka:

https://cw.fel.cvut.cz/wiki/courses/ae4m39vg/start

Webová stránka:

https://cw.fel.cvut.cz/wiki/courses/ae4m39vg/start

Klíčová slova:

Výpočetní geometrie, Diskrétní geometrie, geometrické algoritmy.

Předmět je zahrnut do těchto studijních plánů:

Plán Obor Role Dop. semestr
MPIB Před zařazením do oboru V
MPOI3 Počítačové vidění a digitální obraz PO 3
MPKME2 Multimediální technika V 3
MPKME4 Sítě elektronických komunikací V 3
MPKME1 Bezdrátové komunikace V 3
MPKME3 Elektronika V 3
MPKME5 Komunikační systémy V 3
MPEEM5 Ekonomika a řízení elektrotechniky V 3
MPEEM4 Ekonomika a řízení energetiky V 3
MPEEM2 Elektrické stroje, přístroje a pohony V 3
MPEEM1 Technologické systémy V 3
MPEEM3 Elektroenergetika V 3
MPOI4NEW Počítačová grafika a interakce PO 3
MPKYR4 Letecké a kosmické systémy V 3
MPKYR1 Robotika V 3
MPKYR2 Senzory a přístrojová technika V 3
MPKYR3 Systémy a řízení V 3


Stránka vytvořena 22.9.2017 17:47:52, semestry: L/2016-7, Z,L/2017-8, Z/2018-9, připomínky k informační náplni zasílejte správci studijních plánů Návrh a realizace: I. Halaška (K336), J. Novák (K336)
Za obsah odpovídá: doc. Ing. Ivan Jelínek, CSc.