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

Garant předmětu:

Přednášející:

Cvičící:

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:

Předmět je vyučován v anglickém jazyce.

Další informace:

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

Pro tento předmět se rozvrh nepřipravuje

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)
• Kvantová informatika (volitelný předmět)