PředmětyPředměty(verze: 802)
Předmět, akademický rok 2016/2017
   Přihlásit přes CAS
Kombinatorická a výpočetní geometrie I - NDMI009
Anglický název: Combinatorial and Computational Geometry I
Zajišťuje: Katedra aplikované matematiky (32-KAM)
Fakulta: Matematicko-fyzikální fakulta
Platnost: od 2016 do 2016
Semestr: zimní
E-Kredity: 6
Rozsah, examinace: zimní s.:2/2 Z+Zk [hodiny/týden]
Počet míst: neomezen
Minimální obsazenost: neomezen
Stav předmětu: vyučován
Jazyk výuky: čeština, angličtina
Způsob výuky: prezenční
Další informace: http://kam.mff.cuni.cz/kvgI
Garant: Mgr. Jan Kynčl, Ph.D.
doc. RNDr. Pavel Valtr, Dr.
RNDr. Martin Tancer, Ph.D.
Třída: Informatika Bc.
Kategorizace předmětu: Informatika > Diskrétní matematika
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ů.

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/

Sylabus -
Poslední úprava: RNDr. Martin Balko, Ph.D. (25.02.2016)

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 (Voronoi diagrams).

Komplexy indukované nadrovinami (hyperplane arrangements).

Úvod do algoritmů výpočetní geometrie. Pravděpodobnostní inkrementální algoritmy.

Požadavky k zápisu -
Poslední úprava: RNDr. Martin Tancer, Ph.D. (14.10.2016)

Předmět bude typicky vyučován střídavě česky (ak. roky 2017/2018, 2019/2020, ...) a anglicky (ak. roky 2016/2017, 2018/2019, ...). 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