Předmět je základní jednotka výuky, jejímž prostřednictvím si student osvojí ucelenou část souboru znalostí a dovedností, potřebnou pro zvládnutí studijního oboru/specializace. Za věcný obsah předmětu zodpovídá garant předmětu. Časovou náročnost předmětu zhruba vyjadřuje atribut předmětu rozsah kontaktní výuky. Například rozsah = 2+2 značí, že předmět bude mít týdně dvě hodiny přednášek a dvě hodiny cvičení týdně. Na závěr semestru musí vyučující provést vyhodnocení, nakolik si ten který student osvojil poznatky a dovednosti, kterých měl během výuky nabýt. Jakým způsobem toto hodnocení vyučující provedou určuje atribut způsob zakončení. U předmětu lze definovat, že předmět je zakončen pouze zápočtem(Z), klasifikovaným zápočtem(KZ), pouze zkouškou(ZK), nebo zápočtem a zkouškou(Z,ZK). Náročnost úspěšného absolvování předmětu je vyjádřena ECTS kreditními body. Výuka předmětu probíhá během semestru. Opakovaně se předmět vyučuje vždy v zimním(Z), nebo v letním(L) semestru každého akademického roku. Výjimečně může předmět být nabízen studentům v obou semestrech(Z,L). Za organizační zajištění výuky zodpovídá přiřazená katedra, která zejména vytvoří časový rozvrh předmětu a zajistí pro předmět vyučující. Někteří přednáší a zkouší, jiní vedou cvičení a udělují zápočty.
Obsahová náplň a další organizační informace, týkající se předmětu je popsána pomocí různých popisných textů(anotace, týdenní osnova, literatura, apod.)
$DODATEK_POPIS
NI-DVG | Úvod do diskrétní a výpočetní geometrie | Rozsah kontaktní výuky: | 2P+1C | ||
---|---|---|---|---|---|
Vyučující: | Saumell Mendiola M. | Způsob zakončení: | Z,ZK | ||
Zodpovědná katedra: | 18101 | ECTS Kredity: | 5 | Semestr: | L |
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.
Osnovy 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.
Osnovy 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.
Literatura:
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.
Požadavky:
Studenti by měli znát základní pojmy kombinatoriky, teorie grafů a analýzy algoritmů.
|
Předmět je zahrnut do těchto studijních plánů:
|
Stránka vytvořena 27. 4. 2024, semestry: L/2023-4, L/2021-2, Z/2023-4, Z,L/2019-20, Z/2024-5, Z/2021-2, Z/2020-1, Z/2022-3, L/2020-1, L/2022-3, připomínky k informační náplni zasílejte správci studijních plánů | Návrh a realizace: J. Novák, I. Halaška |