Wybrane zagadnienia kombinatoryki

informatyka

monograficzne

Będziemy omawiać różne zagadnienia kombinatoryczne.

W szczególności, omówimy podstawowe wyniki teorii uczenia maszynowego oraz teorii Vapnika-Chervonenkisa, a także wyniki dotyczące rodzin zbiorów (set systems). Wyniki te są fundamentalne zarówno w teorii uczenia maszynowego, jak i w kombinatoryce geometrycznej i geometrii obliczeniowej, a także mają związek z innymi dziedzinami matematyki i informatyki, m.in. logiką i teorią grafów. Będziemy również omawiać inne ważne wyniki w kombinatoryce (w szczególności, lemat Szemerediego o regularności) i twierdzenie Erdosa-Hajnala.

Tematy:

kombinatoryka rodzin zbiorów, wymiar Vapnika-Chervonenkisa, lemat Sauer-Perles-Shelah (2 wykłady),

twierdzenie Vapnika-Chervonenkisa, zasadnicze twierdzenie uczenia maszynowego, twierdzenie o ε-sieciach dla wymiaru Vapnika-Chervonenkisa

(2 wykłady)

twierdzenie Hausslera (1 wykład)

sample compression schemes (1 wykład)

własność Helly’ego, (p,q)-twierdzenie (1 wykład)

twierdzenie Szemerédi-Trotter (1 wykład)

twierdzenie Szemerediego o regularności, triangle removal lemma, Roth's Theorem (2 wykłady)

twierdzenie Lovasz-Szegedy dla VC (1 wykład)

twierdzenie Erdosa-Hajnala oraz silna własność Erdosa-Hajnala (1 wykład)

Lectures in Discrete Geometry, Jiri Matousek

Geometric Discrepancy, Jiri Matousek

Combinatorial Geometry Janos Pach i Pankaj Agarwal,

Topics in Combinatorics, Artem Chernikov

Understanding Machine Learning: From Theory to Algorithms, Shai Shalev-Shwartz i Shai Ben-David

* Student ma pogłebioną wiedzę z zakresu matematyki dyskretnej (K_W01).

Umiejętności: student potrafi konstruować rozumowania matematyczne

Kompetencje społeczne: student jest gotów do krytycznej oceny posiadanej wiedzy i odbieranych treści

ocena będzie wypadkową ocen z prac domowych, testów domowych, oraz z egzaminu ustnego (dla wybranych osób). Kryteria oceny będą różne dla studentów różnych etapów studiów.