Princip inkluze a exkluze pro geometricky zadané množiny

• Název práce v češtině: Princip inkluze a exkluze pro geometricky zadané množiny
• Název v anglickém jazyce: Inclusion - exclusion principle for geometric sets
• Klíčová slova: princip inkluze a exkluze, simpliciální komplex, konvexní množina, Vapnik - Červonenkisova dimenze, integrace funkce na geometricky zadané množině
• Klíčová slova anglicky: Inclusion - exclusion principle, simplicial complex, convex set, Vapnik - Chervonenkis dimension, integration on geometric set
• Akademický rok vypsání: 2011/2012
• Typ práce: diplomová práce
• Jazyk práce: čeština
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: doc. RNDr. Martin Tancer, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 01.11.2011
• Datum zadání: 01.11.2011
• Datum potvrzení stud. oddělením: 04.11.2011

Zásady pro vypracování

Základní využití principu inkluze a exkluze je pro počítání velikosti sjednocení množin, známe-li velikosti průniků. V případě, že jsou množiny zadané geometricky, se tento princip používá spíše k počítání objemu, nebo obecněji k výpočtu integrálu nějaké funkce definované na sjednocení množin. Základní formule pro princip inkluze a exkluze je ale poměrně složitá z výpočetního hlediska, pro n množin obsahuje přibližně 2^n členů. U některých geometricky zadaných množin je známo, že lze takovou formuli výrazně zjednodušit, většinou se k tomu využívá topologických metod.
Úkolem studenta je seznámit se s různými známými zjednoušeními v geometrické situaci a poté je přehledně popsat. Dále se pokusí o nové výsledky v jiných geometrických situacích. Například se zdá, že pro systémy množin s omezenou Vapnik-Červonenkisovou dimenzí lze taková zjednodušení nalézt.

Seznam odborné literatury

J. Matoušek: Lectures on Discrete Geometry, Springer 2002
J. Matoušek: Using the Borsuk-Ulam theorem, Springer 2003
D. Attali and H. Edelsbrunner: Inclusion-exclusion formulas from independent complexes. Discrete and Computational Geometry. Vol. 37, No. 1, January, pages 59--77, 2007.
H. Edelsbrunner: The union of balls and its dual shape. Discrete Comput. Geom. 13 (1995), 415–440.
Další literatura bude doplněna podle potřeby a podle postupu práce.