PředmětyPředměty(verze: 902)
Předmět, akademický rok 2022/2023
   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 2020
Semestr: zimní
E-Kredity: 5
Rozsah, examinace: zimní s.:2/2 [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Virtuální mobilita / počet míst: 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.
Mgr. Jan Kynčl, Ph.D.
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
Výsledky anket   Termíny zkoušek   Rozvrh   Nástěnka   
Anotace -
Poslední úprava: ()
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).
Cíl předmětu -
Poslední úprava: T_KAM (20.04.2008)

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ů.

Podmínky zakončení předmětu -
Poslední úprava: Mgr. Jan Kynčl, Ph.D. (12.10.2017)

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.

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

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

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

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

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

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.

Sylabus -
Poslední úprava: doc. RNDr. Pavel Töpfer, CSc. (26.01.2018)

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.

Požadavky k zápisu -
Poslední úprava: Mgr. Jan Kynčl, Ph.D. (30.07.2020)

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.

 
Univerzita Karlova | Informační systém UK