Serwisy internetowe Uniwersytetu Warszawskiego | USOSownia - uniwersyteckie forum USOSoweNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Meta-algorytmy grafowe

Informacje ogólne

Kod przedmiotu: 1000-2M15MAG Kod Erasmus / ISCED: 11.3 / (0612) Database and network design and administration
Nazwa przedmiotu: Meta-algorytmy grafowe
Jednostka: Wydział Matematyki, Informatyki i Mechaniki
Grupy: Przedmioty monograficzne dla III - V roku informatyki
Przedmioty obieralne dla informatyki
Punkty ECTS i inne: (brak)
zobacz reguły punktacji
Język prowadzenia: angielski
Rodzaj przedmiotu:

monograficzne

Założenia (lista przedmiotów):

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

Skrócony opis:

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.

Pełny opis:

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)

Literatura:

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)

Efekty kształcenia:

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

Metody i kryteria oceniania:

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

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.