(in Polish) Wybrane zagadnienia kombinatoryki
General data
Course ID: | 1000-2M22WZK |
Erasmus code / ISCED: |
11.3
|
Course title: | (unknown) |
Name in Polish: | Wybrane zagadnienia kombinatoryki |
Organizational unit: | Faculty of Mathematics, Informatics, and Mechanics |
Course groups: |
(in Polish) Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka Elective courses for Computer Science |
ECTS credit allocation (and other scores): |
(not available)
|
Language: | English |
Main fields of studies for MISMaP: | computer science |
Type of course: | elective monographs |
Short description: |
(in Polish) 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. |
Full description: |
(in Polish) 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) |
Bibliography: |
(in Polish) 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 |
Learning outcomes: |
(in Polish) * 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 |
Assessment methods and assessment criteria: |
(in Polish) 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. |
Copyright by University of Warsaw.