Meta-algorytmy grafowe

monograficzne

Języki, automaty i obliczenia 1000-214bJAO
Logika dla informatyków 1000-217bLOG
Złożoność obliczeniowa 1000-218bZO

Przedmiot stanowi wprowadzenie do szerokiego nurtu badań na styku algorytmiki, logiki i strukturalnej teorii grafów, zajmującego się konstrukcją meta-algorytmów na grafach: algorytmów, które za jednym zamachem rozwiązują efektywnie każdy problem wyrażalny w pewnym języku logicznym, o ile graf na którym pracujemy ma odpowiednie własności. Skoncentrujemy się na najważniejszych modelach logiki na grafach: MSO1, MSO2, oraz FO. Wykażemy, że klasy grafów dla których da się skonstruować efektywne meta-algorytmy dla tych logik da się opisać w ścisły sposób, oraz odpowiadają one naturalnym koncepcjom kombinatorycznym takim jak “drzewiastość” czy “rzadkość”. Będziemy również prezentować szerokie zastosowania wprowadzonych meta-narzędzi w algorytmice, głównie w kontekście algorytmów ustalonego parametru oraz kernelizacji.

1. Wstęp do kombinatorycznej teorii treewidthu (1 wykład)

2. Logika MSO2 i treewidth – problemy ewaluacji oraz spełnialności formuł (2 wykłady)

3. Logika MSO1 i cliquewidth – problem ewaluacji formuł (1 wykład)

4. Ograniczenia dolne: twierdzenie Seese o nierozstrzygalności teorii MSO2 na klasach grafów o nieograniczonym treewidthie (1 wykład)

5. Ograniczenia dolne: twierdzenie Frick-Grohe o nieelementarności złożoności problemu ewaluacji formuł FO na słowach (1 wykład)

6. Ewaluacja formuł FO na grafach rzadkich: planarnych, o ograniczonym stopniu, o ograniczonym genusie, o ograniczonym lokalnym treewidthie, wykluczającym dany minor, o ograniczonej ekspansji (3 wykłady)

7. Związki problemu ewaluacji formuł z problemem izomorfizmu grafów; logika IFP (1,5 wykładu)

8. Meta-kernelizacja (1,5 wykładu)

Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, Saurabh, Parameterized Algorithms, Springer 2015 (w druku, wersja elektroniczna do udostępnienia studentom)

Nešetřil, Ossona de Mendez, Sparsity, Springer 2012

Fomin, Lokshtanov, Saurabh, Kernelization, książka w przygotowaniu (wersja elektroniczna do udostępnienia studentom)

Wiedza:

Zna i potrafi wytłumaczyć związki pomiędzy problemami ewaluacji i spełnialności dla logik FO, MSO1 , MSO2 a różnymi dekompozycjami i klasami grafów. (K_W01, K_W02). W szczególności, jest w stanie podjąć pracę naukową nad prostymi problemami związanymi z tymi zagadnieniami (samodzielnie lub w zespole), choćby na poziomie pracy magisterskiej.

Umiejętności:

Potrafi zastosować poznane meta-narzędzia do efektywnego rozwiązywania konkretnych problemów algorytmicznych. (K_U02, K_U09) Potrafi sformułować proste meta-narzędzia oparte o poznane podejścia w celu rozwiązywania konkretnych zagadnień napotkanych w pracy naukowej (K_U01, K_U04).

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

Ocena końcowa na podstawie zadań domowych oraz oceny z egzaminu ustnego