Meta-algorytmy grafowe
- WykĹad: PoniedziaĹki 10:15 -- 11:45
- Äwiczenia: PiÄ
tki 12:15 -- 13:45
Terminarz:
- WykĹad, poniedziaĹek 27.02: WstÄp do dekompozycji drzewiastych, algorytm aproksymacyjny dla treewidthu
- Äwiczenia, piÄ
tek 3.03: Dekompozycje drzewiaste. MateriaĹy na Äwiczenia: TUTAJ
- WykĹad, poniedziaĹek 6.03: Twierdzenie Courcelle'a
- Äwiczenia, piÄ
tek 10.03: Twierdzenie Courcelle'a
- WykĹad, poniedziaĹek 13.03: RozpoznawalnoĹÄ, MSO transdukcje
- Äwiczenia, piÄ
tek 17.03: Twierdzenie Courcelle'a, MSO transdukcje. MateriaĹy na Äwiczenia: TUTAJ
- WykĹad, poniedziaĹek 20.03: Twierdzenie Seese
- Äwiczenia, piÄ
tek 24.03: Cliquewidth. MateriaĹy na Äwiczenia: TUTAJ
- WykĹad, poniedziaĹek 27.03: Twierdzenie Grohe-Segoufin-Schwentick o charakteryzacji zĹoĹźonoĹci problemĂłw homomorfizmu przez treewidth
- Äwiczenia, piÄ
tek 31.03
- WykĹad, poniedziaĹek 3.04: PostaÄ normalna Gaifmana, FO na grafach o ograniczonym stopniu
- Äwiczenia, piÄ
tek 7.04
- WykĹad, poniedziaĹek 10.04: Metoda lokalnoĹci, dekompozycje dla grafĂłw H-minor-free
- WykĹad specjalny, Ĺroda 19.04: Hipoteza Courcelle'a
- Äwiczenia, piÄ
tek 21.04
- WykĹad, poniedziaĹek 24.04: WstÄp do grafĂłw rzadkich (wykĹad goĹcinny Sebastiana Siebertza)
- Äwiczenia, piÄ
tek 28.04
- Äwiczenia, piÄ
tek 5.05
- WykĹad, poniedziaĹek 8.05: Grafy rzadkie, poczÄ
tek pracy w stronÄ model-checkingu FO na grafach rzadkich
- Äwiczenia, piÄ
tek 12.05
- WykĹad, poniedziaĹek 15.05: ZakoĹczenie dowodu model-checkingu FO na grafach rzadkich
- Äwiczenia, piÄ
tek 19.05: Twierdzenie Elberfeld-Grohe-Tantau o charakteryzacji klas na ktĂłrych MSO siÄ kolapsuje do FO. MateriaĹy na Äwiczenia: TUTAJ
- WykĹad, poniedziaĹek 22.05: Meta-kernelizacja
- Äwiczenia, piÄ
tek 19.05: Meta-kernelizacja. MateriaĹy na Äwiczenia: TUTAJ
- WykĹad, poniedziaĹek 29.05: Meta-kernelizacja, ciÄ
g dalszy
- Äwiczenia, piÄ
tek 2.06: Meta-kernelizacja, ciÄ
g dalszy. MateriaĹy na Äwiczenia: TUTAJ
Prace domowe:
- Pierwsza seria, deadline 10 kwietnia: seria
- Druga seria, deadline 19 maja: seria
- Trzecia seria, deadline 26 maja: seria