PředmětyPředměty(verze: 964)
Předmět, akademický rok 2024/2025
   Přihlásit přes CAS
Základy kombinatorické a výpočetní geometrie - NDMI009
Anglický název: Introduction to Combinatorial and Computational Geometry
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2024
Semestr: zimní
E-Kredity: 5
Rozsah, examinace: zimní s.:2/2, Z+Zk [HT]
Počet míst: neomezen
Minimální obsazenost: neomezen
4EU+: ne
Virtuální mobilita / počet míst pro virtuální mobilitu: ne
Stav předmětu: vyučován
Jazyk výuky: čeština
Způsob výuky: prezenční
Další informace: http://kam.mff.cuni.cz/kvgI
Garant: doc. RNDr. Pavel Valtr, Dr.
doc. Mgr. Jan Kynčl, Ph.D.
Vyučující: doc. Mgr. Jan Kynčl, Ph.D.
Mgr. Jan Soukup
doc. RNDr. Pavel Valtr, Dr.
Třída: Informatika Bc.
Kombinatorická geometrie a geom. algorit
Kategorizace předmětu: Informatika > Diskrétní matematika
Neslučitelnost : NDMX009
Záměnnost : NDMX009
Je neslučitelnost pro: NDMX009, NGEM020
Je záměnnost pro: NDMX009, NGEM020
Anotace -
Výpočetní geometrie se zabývá návrhem efektivních algoritmů pro geometrické problémy v rovině i ve vícedimenzionálním prostoru (např. je-li dáno N bodů v rovině, jak co nejefektivněji najít dvojici bodů s nejmenší vzdáleností). Takové problémy jsou motivovány aplikacemi v počítačové grafice, prostorovém modelování (např. molekul, budov, součástek), geografických informačních systémech apod. Při analýze takových algoritmů se potřebuje kombinatorická geometrie, studující kombinatorické vlastnosti geometrických konfigurací, konvexních množin a pod. Výsledky jsou důležité i z čistě matematického hlediska, např. v teorii čísel. V této úvodní přednášce se probírají základní pojmy a metody, s důrazem na matematický základ (t.j. jen s minimem materiálu o datových strukturách apod).
Poslední úprava: ()
Cíl předmětu -

Slouží jako matematický a algoritmický základ k oborům, v nichž se používají geometrické výpočty (např. počítačová grafika, geometrická optimalizace), a rozvíjí geometrické uvažování a představivost studentů.

Poslední úprava: T_KAM (20.04.2008)
Podmínky zakončení předmětu -

Podmínkou na zápočet je získání aspoň 30 bodů za školní a domácí příklady. Charakter zápočtu neumožňuje jeho opakování. Zápočet je nutnou podmínkou ke zkoušce.

Poslední úprava: Kynčl Jan, doc. Mgr., Ph.D. (12.10.2017)
Literatura -

J. Matoušek: Kombinatorická a výpočetní geometrie, KAM Series 95-289 (preprint), možno vypůjčit v knihovně v Karlíně

J. Matoušek: Lectures on Discrete Geometry, Springer, 2002

J. Pach, P. Agarwal: Combinatorial Geometry, Cambridge University Press 1995

M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: Computational geometry: Algorithms and Applications, Springer-Verlag 1997

Poslední úprava: Kynčl Jan, doc. Mgr., Ph.D. (06.10.2015)
Metody výuky -

Cvičení probíhá formou samostatného řešení příkladů. Více informací: http://kam.mff.cuni.cz/kvg/

Poslední úprava: Kynčl Jan, doc. Mgr., Ph.D. (24.02.2016)
Požadavky ke zkoušce -

Zkouška je ústní s písemnou přípravou. Zkouší se odpřednesená témata a schopnost aplikace na lehčí až středně těžké příklady. Zkouška může mít distanční formu.

Poslední úprava: Kynčl Jan, doc. Mgr., Ph.D. (10.10.2020)
Sylabus -

Základní věty o konvexních množinách (Hellyho, Radonova, o oddělování).

Minkowského věta o mřížkách.

Incidence bodů a přímek.

Geometrická dualita.

Definice a základní vlastnosti konvexních mnohostěnů.

Kombinatorická složitost konvexních mnohostěnů.

Voroného diagramy.

Komplexy indukované nadrovinami.

Arrangementy algebraických ploch, pseudopřímek.

Poslední úprava: Töpfer Pavel, doc. RNDr., CSc. (26.01.2018)
Požadavky k zápisu -

Předmět bude typicky vyučován střídavě česky (2020/2021, ...) a anglicky (2021/2022, ...). V příslušném roce může dojít ke změně, pokud s ní budou všichni posluchači souhlasit.

Poslední úprava: Kynčl Jan, doc. Mgr., Ph.D. (30.07.2020)
 
Univerzita Karlova | Informační systém UK