Úvod do diskrétní a výpočetní geometrie

Garant předmětu:

Maria Saumell Mendiola

Přednášející:

Maria Saumell Mendiola

Cvičící:

Maria Saumell Mendiola

Předmět zajišťuje:

katedra teoretické informatiky

Anotace:

Cílem předmětu je seznámit studenty s disciplínou diskrétní a výpočetní geometrie. Hlavním cílem kurzu je seznámit se s nejzákladnějšími objekty této disciplíny a umět řešit jednoduché algoritmické úlohy týkající se geometrie.

Požadavky:

Studenti by měli znát základní pojmy kombinatoriky, teorie grafů a analýzy algoritmů.

Osnova přednášek:

– Přednášky 1 a 2: Úvod do diskrétní a výpočetní geometrie. Popis oboru. Výpočetní model. Vzorové problémy.

– Přednáška 3: Konvexita. Definice. Hellyho věta. Radonovo lemma. Farkasova věta.

– Přednáška 4: Konvexní obal ve dvou rozměrech. Definice a charakterizace. Inkrementální algoritmy. Algoritmy rozděl a panuj. Graham algoritmus. Dolní mez.

– Přednáška 5: Průsečík polygonů. Základní pojmy o průsečících úseček. Aplikace na průsečík polygonů.

– Přednáška 6: Triangulace polygonů a množina bodů. Existence. Věta o umělecké galerii. Algoritmy. Trapézový rozklad. Triangulace množin bodů.

– Přednášky 7 a 8: Voroného diagramy a Delauneho triangulace. Definice. Aplikace. Vlastnosti. Algoritmy rozděl a panuj. Další grafy blízkosti.

– Přednáška 9: Uspořádání řádků. Definice. Vlastnosti. Věta o zóně. Algoritmy.

– Přednáška 10: Dualita. Definice. Vlastnosti. Vzorové problémy.

– Přednáška 11: Lineární programování ve dvou rozměrech. Definice. Algoritmus prořezávej a hledej. Randomizovaný algoritmus.

– Přednáška 12: Poloha bodu. Definice. Metoda Kirkpatricka. Aplikace.

– Přednáška 13: Úvod do polytopů. Definice. Cyklické polytopy. Věta o horní hranici.

Osnova cvičení:

- Cvičení 1 a 2: Úvodní úlohy diskrétní a výpočetní geometrie.

– Cvičení 3: Konvexita.

– Cvičení 4: Konvexní obal ve dvou rozměrech.

– Cvičení 5: Průsečík polygonů.

– Cvičení 6: Triangulace polygonů a množina bodů.

– Cvičení 7: Voroného diagramy a Delauneho triangulace.

- Cvičení 8: Semestrální test.

– Cvičení 9: Uspořádání řádků.

– Cvičení 10: Dualita.

– Cvičení 11: Lineární programování ve dvou rozměrech.

– Cvičení 12: Poloha bodu.

– Cvičení 13: Polytopy.

Cíle studia:

Hlavním cílem kurzu je osvojit si nejzákladnější metody používané v geometrických algoritmech.

Studijní materiály:

Geometry: An Introduction. Springer, 1985.

Mark Berg, Marc Kreveld, Mark Overmars, Otfried Cheong Schwarzkopf. Computational Geometry: Algorithms and Applications. Springer, 2000.

Jacob E. Goodman, Joseph O'Rourke, and Csaba D. Tóth (ed.). Handbook of Discrete and Computational Geometry (third edition). CRC Press, 2017.

Poznámka:

Studijní materiály na https://courses.fit.cvut.cz/NI-DVG // Předmět je vyučován v anglickém jazyce.

Další informace:

https://courses.fit.cvut.cz/NI-DVG

Rozvrh na zimní semestr 2024/2025:

Rozvrh není připraven

Rozvrh na letní semestr 2024/2025:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Mgr. specializace Počítačová bezpečnost, 2020 (volitelný předmět)
• Mgr. specializace Návrh a programování vestavných systémů, 2020 (volitelný předmět)
• Mgr. specializace Počítačové systémy a sítě, 2020 (volitelný předmět)
• Mgr. specializace Manažerská informatika, 2020 (volitelný předmět)
• Mgr. specializace Softwarové inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Systémové programování, verze od 2020 (volitelný předmět)
• Mgr. specializace Webové inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Znalostní inženýrství, 2020 (volitelný předmět)
• Mgr. specializace Teoretická informatika, 2020 (volitelný předmět)
• Mgr. program, pro fázi studia bez specializace, ver. pro roky 2020 a vyšší (volitelný předmět)
• Study plan for Ukrainian refugees (volitelný předmět)
• Mgr. specializace Systémové programování, verze od 2023 (volitelný předmět)
• Mgr. specializace Teoretická informatika, 2023 (volitelný předmět)