Algorytmiczna teoria modeli

Matematyka dyskretna 1000-212bMD

Wiedza z przedmiotów Logika dla Informatyków

1000-217bLOG oraz Grafy Rzadkie 1000-2M12GRZ będzie pomocna w niektórych częściach materiału, ale nie jest wymagana.

Wykład ten łączy elementy strukturalnej teorii grafów, algorytmów parametryzowanych, oraz teorii modeli skończonych.

Wątkiem przewodnim wykładu są wyniki algorytmiczne, nazywane “algorytmicznymi meta-twierdzeniami”, które mówią, że całe rodziny problemów algorytmicznych można rozwiązać efektywnie na instancjach o szczególnej strukturze. Zazwyczaj będziemy rozważali problemy grafowe dla grafów o szczególnej strukturze. Przykładowo, każdy problem obliczeniowy, który można opisać zdaniem logiki pierwszego rzędu, można rozwiązać w czasie liniowym na wszystkich grafach planarnych, lub na wszystkich grafach o ustalonym maksymalnym stopniu wierzchołków. Wynik ten można uogólnić na różne inne klasy grafów (w tym klasy nigdziegęste, oraz klasy monadycznie stabilne) czy inne logiki.

Wykład prowadzony po angielsku.

1. Problem ewaluacji formuł logicznych na grafach – złożoność obliczeniowa

2. Grafy o ograniczonej szerokości drzewiastej oraz o ograniczonej szerokości klikowej; ewaluacja formuł logiki MSO

3. Lokalność logiki pierwszego rzędu

4. Grafy o ograniczonym stopniu; ewaluacja formuł logiki pierwszego rzędu

5. Grafy o lokalnie ograniczonej szerokości drzewiastej

6. Klasy nigdziegęste; ewaluacja formuł logiki pierwszego rzędu

7. Klasy monadycznie stabilne i monadycznie NIP

8. Elementy kombinatoryki rodzin zbiorów – wymiar Vapnika-Chervonenkisa, lemat Sauer-Shelah, porządki Welzla

Szymon Toruńczyk, Lecture Notes in Finite Model Theory

Martin Grohe, Stephan Kreutzer, Methods for Algorithmic Meta Theorems

Notatki i artykuły badawcze wskazane przez wykładowcę

Wiedza:

Zna różne własności klas grafów oraz ich algorytmiczne meta-twierdzenia: dla klas o ograniczonej szerokości klikowej, dla klas nigdziegęstych, dla klas monadycznie stabilnych; rozumie związki pomiędzy tymi pojęciami. Potrafi wskazać przykładowe zastosowania teorii grafów rzadkich ze szczególnym uwzględnieniem zastosowań w projektowaniu algorytmów parametryzowanych. (K_W01, K_W02)

Umiejętności:

Potrafi zastosować poznane własności kombinatoryczne 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).

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".