Wybrane zagadnienia kombinatoryki

Informacje ogólne

Kod przedmiotu:	1000-2M22WZK
Kod Erasmus / ISCED:	11.3 Kod klasyfikacyjny przedmiotu składa się z trzech do pięciu cyfr, przy czym trzy pierwsze oznaczają klasyfikację dziedziny wg. Listy kodów dziedzin obowiązującej w programie Socrates/Erasmus, czwarta (dotąd na ogół 0) – ewentualne uszczegółowienie informacji o dyscyplinie, piąta – stopień zaawansowania przedmiotu ustalony na podstawie roku studiów, dla którego przedmiot jest przeznaczony. / (0612) Database and network design and administration Kod ISCED - Międzynarodowa Standardowa Klasyfikacja Kształcenia (International Standard Classification of Education) została opracowana przez UNESCO.
Nazwa przedmiotu:	Wybrane zagadnienia kombinatoryki
Jednostka:	Wydział Matematyki, Informatyki i Mechaniki
Grupy:	Przedmioty obieralne dla informatyki i ML Przedmioty obieralne na studiach drugiego stopnia na kierunku bioinformatyka
Punkty ECTS i inne:	(brak) Podstawowe informacje o zasadach przyporządkowania punktów ECTS: roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS; tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h; 1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się; tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS; nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta. zobacz reguły punktacji
Język prowadzenia:	angielski
Kierunek podstawowy MISMaP:	informatyka
Rodzaj przedmiotu:	monograficzne
Skrócony opis:	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.
Pełny opis:	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)
Literatura:	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
Efekty uczenia się:	* 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
Metody i kryteria oceniania:	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.

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Warszawski.