Meta-algorytmy grafowe

<ul>
<li> Wykład: Poniedziałki 10:15 -- 11:45
<li> Ćwiczenia: Piątki 12:15 -- 13:45
</ul>

Terminarz:
<ul>
<li> Wykład, poniedziałek 27.02: Wstęp do dekompozycji drzewiastych, algorytm aproksymacyjny dla treewidthu
<li> Ćwiczenia, piątek 3.03: Dekompozycje drzewiaste. Materiały na ćwiczenia: <a href="/~mp248287/MAG/cw1.pdf">TUTAJ</a>
<li> Wykład, poniedziałek 6.03: Twierdzenie Courcelle'a
<li> Ćwiczenia, piątek 10.03: Twierdzenie Courcelle'a
<li> Wykład, poniedziałek 13.03: Rozpoznawalność, MSO transdukcje
<li> Ćwiczenia, piątek 17.03: Twierdzenie Courcelle'a, MSO transdukcje. Materiały na ćwiczenia: <a href="/~mp248287/MAG/cw3.pdf">TUTAJ</a>
<li> Wykład, poniedziałek 20.03: Twierdzenie Seese
<li> Ćwiczenia, piątek 24.03: Cliquewidth. Materiały na ćwiczenia: <a href="/~mp248287/MAG/cw4.pdf">TUTAJ</a>
<li> Wykład, poniedziałek 27.03: Twierdzenie Grohe-Segoufin-Schwentick o charakteryzacji złożoności problemów homomorfizmu przez treewidth
<li> Ćwiczenia, piątek 31.03
<li> Wykład, poniedziałek 3.04: Postać normalna Gaifmana, FO na grafach o ograniczonym stopniu
<li> Ćwiczenia, piątek 7.04
<li> Wykład, poniedziałek 10.04: Metoda lokalności, dekompozycje dla grafów H-minor-free
<li> Wykład specjalny, środa 19.04: Hipoteza Courcelle'a
<li> Ćwiczenia, piątek 21.04
<li> Wykład, poniedziałek 24.04: Wstęp do grafów rzadkich (wykład gościnny Sebastiana Siebertza)
<li> Ćwiczenia, piątek 28.04
<li> Ćwiczenia, piątek 5.05
<li> Wykład, poniedziałek 8.05: Grafy rzadkie, początek pracy w stronę model-checkingu FO na grafach rzadkich
<li> Ćwiczenia, piątek 12.05
<li> Wykład, poniedziałek 15.05: Zakończenie dowodu model-checkingu FO na grafach rzadkich
<li> Ćwiczenia, piątek 19.05: Twierdzenie Elberfeld-Grohe-Tantau o charakteryzacji klas na których MSO się kolapsuje do FO. Materiały na ćwiczenia: <a href="/~mp248287/MAG/cw9.pdf">TUTAJ</a>
<li> Wykład, poniedziałek 22.05: Meta-kernelizacja
<li> Ćwiczenia, piątek 19.05: Meta-kernelizacja. Materiały na ćwiczenia: <a href="/~mp248287/MAG/cw10.pdf">TUTAJ</a>
<li> Wykład, poniedziałek 29.05: Meta-kernelizacja, ciąg dalszy
<li> Ćwiczenia, piątek 2.06: Meta-kernelizacja, ciąg dalszy. Materiały na ćwiczenia: <a href="/~mp248287/MAG/cw11.pdf">TUTAJ</a>
</ul>

Prace domowe:
<ul>
<li> Pierwsza seria, deadline 10 kwietnia: <a href="/~mp248287/MAG/seria1.pdf">seria</a>
<li> Druga seria, deadline 19 maja: <a href="/~mp248287/MAG/seria2.pdf">seria</a>
<li> Trzecia seria, deadline 26 maja: <a href="/~mp248287/MAG/seria3.pdf">seria</a>
</ul>