Úvod do diskrétní a výpočetní geometrie
| 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:
-
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:
-
06:00–08:0008:00–10:0010:00–12:0012:00–14:0014:00–16:0016:00–18:0018:00–20:0020:00–22:0022:00–24:00
Po Út St Čt Pá - 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)