Grafy rzadkie 1000-2M12GRZ
1. Mierzenie rzadkości, definicje klas o ograniczonej ekspansji i nigdzie-gęstych, relacje pomiędzy płytkimi minorami i płytkimi topologicznymi minorami (2-3 wykłady).
2. Uogólnione liczby chromatyczne: kombinatoryka, aspekty algorytmiczne, zastosowania (2 wykłady).
3. Kolorowania o małej głębokości drzewiastej: kombinatoryka i zastosowania (1 wykład)
4. Problem sprawdzania modelu dla logiki pierwszego rzędu na klasach o ograniczonej ekspansji (1 wykład)
5. Złożoność sąsiedztw (1 wykład)
6. Quasi-szerokość i gra w Rozdzielacza (1-2 wykłady)
7. Wymiar Vapnika-Chervonenkisa i elementy teorii stabilności (2 wykłady)
8. Wielomianowa ekspansja i separatory: zastosowania dla algorytmów aproksymacyjnych (1-2 wykłady)
Rodzaj przedmiotu
Tryb prowadzenia
Wymagania (lista przedmiotów)
Założenia (opisowo)
Koordynatorzy przedmiotu
Efekty kształcenia
Wiedza:
Zna różne, równoważne definicje rzadkości grafów: klas o ograniczonej ekspansji oraz nigdzie-gęstych, rozumie związki pomiędzy tymi definicjami. Potrafi wskazać przykładowe zastosowania teorii grafów rzadkich ze szczególnym uwzględnieniem zastosowań w projektowaniu algorytmów parametryzowanych oraz aproksymacyjnych. (K_W01, K_W02)
Umiejętności:
Potrafi zastosować poznane własności kombinatoryczne pojęć rzadkości do rozwiązywania problemów matematycznych oraz algorytmicznych, również pojawiających się w pracy naukowej. (K_U02, K_U09)
Kompetencje:
Zna ograniczenia własnej wiedzy i rozumie potrzebę dalszego kształcenia, w tym zdobywania wiedzy pozadziedzinowej (K_K01). Potrafi precyzyjnie formułować pytania, służące pogłębieniu własnego zrozumienia danego tematu lub odnalezieniu brakujących elementów rozumowania (K_K02). Rozumie potrzebę systematycznego zapoznawania się z czasopismami naukowymi i popularnonaukowymi w celu poszerzania i pogłębiania wiedzy (K_K08).
Kryteria oceniania
Prace domowe (50%) oraz egzamin ustny (50%).
Przedmiot można zaliczać w ramach studiów doktoranckich jako przedmiot metodologiczny. Wówczas dodatkowym warunkiem zaliczenia jest rozwiązanie co najmniej jednego z trudniejszych zadań z prac domowych, określonych przez prowadzących jako zadania "badawcze".
Literatura
J. Nešetřil, P. Ossona de Mendez, “Sparsity - Graphs, Structures, and Algorithms”.
Notatki z poprzedniej edycji przedmiotu.
Notatki i artykuły badawcze wskazane przez wykładowców.
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: