Základy kombinatorické a výpočetní geometrie - NDMX009

• Anglický název: Introduction to Combinatorial and Computational Geometry
• Zajišťuje: Studijní oddělení (32-STUD)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2020
• Semestr: zimní
• E-Kredity: 6
• 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í
• Způsob výuky: prezenční
• Je zajišťováno předmětem: NDMI009
• Další informace: http://kam.mff.cuni.cz/kvgI
• Garant: doc. RNDr. Pavel Valtr, Dr.; doc. Mgr. Jan Kynčl, Ph.D.
• Třída: Informatika Bc.; Kombinatorická geometrie a geom. algorit
• Kategorizace předmětu: Informatika > Diskrétní matematika
• Prerekvizity : {NXXX007, NXXX009, NXXX014, NXXX015, NXXX016, NXXX017, NXXX022, NXXX023, NXXX024, NXXX025, NXXX033}
• Neslučitelnost : NDMI009
• Záměnnost : NDMI009
• Je neslučitelnost pro: NDMI009
• Je záměnnost pro: NDMI009

Anotace

čeština

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: ()

angličtina

Discrete geometry investigates combinatorial properties of geometric objects such as finite point sets or convex sets in Euclidean spaces. Computational geometry considers the design of efficient algorithms for computing with geometric configurations, and discrete geometry serves as its mathematical foundation. Part I of the course is a concise introduction. The contents of Part II varies among the years, each year covering a few selected topics in more depth.

Poslední úprava: T_MUUK (31.01.2001)

Cíl předmětu

čeština

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)

angličtina

Serves as a mathematical foundation for areas using geometric computations (e.g., computer graphics, geometric optimization) and develops geometric intuition and imagination.

Poslední úprava: T_KAM (20.04.2008)

Podmínky zakončení předmětu

čeština

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)

angličtina

The credit for the exercise is given after obtaining at least 30 points for solving the school and home problems. The nature of the conditions do not allow repeated attempts for obtaining the credit. Obtaining the credit is necessary before the exam.

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

Literatura

čeština

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)

angličtina

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

čeština

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)

angličtina

The exercises consist in individual solving of problems assigned during the semester. More information: http://kam.mff.cuni.cz/kvg/eng.html

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

Požadavky ke zkoušce

čeština

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)

angličtina

There will be oral exam with time for preparation of the answers. The material required for the exam will be the same as taught in the lecture. The exam may include easier or moderately difficult problems from these topics. The exam can also be in a distance form.

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

Sylabus

čeština

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)

angličtina

Basic theorems on convex sets (Helly, Radon, Caratheodory, separation).

Minkowski's theorem on lattice points in convex bodies.

Line-point incidences.

Geometric duality. Convex polytopes: definition, basic properties,

maximum number of faces.

Voronoi diagrams.

Hyperplane arrangements.

Arrangements of algebraic surfaces, pseudolines.

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

Požadavky k zápisu

čeština

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)

angličtina

The lecture will be taught alternatingly in Czech (2020/2021, ...) and in English (2021/2022, ...) The language may be changed in a particular year if all attendants agree with the change.

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