Princip inkluze a exkluze pro geometricky zadané množiny

• Thesis title in Czech: Princip inkluze a exkluze pro geometricky zadané množiny
• Thesis title in English: Inclusion - exclusion principle for geometric sets
• Key words: princip inkluze a exkluze, simpliciální komplex, konvexní množina, Vapnik - Červonenkisova dimenze, integrace funkce na geometricky zadané množině
• English key words: Inclusion - exclusion principle, simplicial complex, convex set, Vapnik - Chervonenkis dimension, integration on geometric set
• Academic year of topic announcement: 2011/2012
• Thesis type: diploma thesis
• Thesis language: čeština
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: doc. RNDr. Martin Tancer, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 01.11.2011
• Date of assignment: 01.11.2011
• Confirmed by Study dept. on: 04.11.2011

Guidelines

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.

References

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.