Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2024/2025

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

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
NI-DVG Z,ZK 5 2P+1C anglicky
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ů:
Platnost dat k 4. 12. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet7436006.html