Přehled studia |
Přehled oborů |
Všechny skupiny předmětů |
Všechny předměty |
Seznam rolí |
Vysvětlivky
Návod
Webová stránka:
https://cw.fel.cvut.cz/wiki/courses/cg/start
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:
Klíčová slova:
Výpočetní geometrie, Diskrétní geometrie, geometrické algoritmy.
Předmět je zahrnut do těchto studijních plánů:
| Stránka vytvořena 13.10.2024 07:50:52, semestry: Z/2025-6, Z/2024-5, L/2023-4, L/2024-5, 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) |