Kernelizacja

semestr letni 2012/2013

Spis treści


Aktualności


Informacje ogólne

Przedmiot oferowany w semestrze letnim 2012/2013.
Strona przedmiotu w USOSie.
Polecamy też przedmiot w semestrze zimowym Algorytmy parametryzowane i umiarkowanie wykładnicze.

Prowadzący

dr Marek Cygan, cygan@mimuw.edu.pl
dr Marcin Pilipczuk, malcin@mimuw.edu.pl

Warunki zaliczenia

  1. Podstawą zaliczenia są zadania domowe, udział w tworzeniu notatek z wykładu i egzamin ustny.
  2. W trakcie semestru będzie sześć serii po trzy zadania każda. Na każdą serię będzie przewidziany czas ok. 2-3 tygodni. Po upływie terminu zadania będą omawiane na ćwiczeniach i nie będzie można ich oddawać.
  3. Rozwiązania zadań należy oddawać pisemnie, najlepiej mailem do prowadzącego.
  4. Każde rozwiązanie oceniane jest jak na Olimpiadzie Matematycznej, tj może dostać 0, 2, 5 lub 6 pkt.
  5. W trakcie semestru będziemy tworzyli notatki (w języku angielskim) z wykładów (i być może części ćwiczeń), tak jak to np. miało miejsce na tym wykładzie. Notowanie będzie podzielone po równo między uczestników przedmiotu.
  6. Notatki z n-tego wykładu należy: spisać w ciągu pięciu dni "roboczych" (czyli takich, w czasie których są zajęcia na MIMie), wysłać prowadzącym i następnie nanieść ich poprawki tak, by notatki były dostępne najpóźniej na wykładzie n+2, a możliwie wcześniej, jeśli po drodze z jakiś powodu nie ma wykładów.
  7. Za udział w tworzeniu notatek będzie można otrzymać do 36 punktów.
  8. Spóźnienie w notatkach jest oceniane następująco: spóźnienie do 2 tygodni: 90% punktów; oddanie przed egzaminem w czerwcu 70% punktów; oddanie przed egzaminem we wrześniu 50% punktów.
  9. Na koniec semestru, na podstawie liczby punktów przyznajemy ocenę z ćwiczeń. Gwarantujemy następujące progi: Możliwym jest, że zadania okażą się za trudne i te progi zostaną obniżone, jednak gwarantujemy, że ich nie podwyższymy.
  10. Na egzaminie ustnym można zmodyfikować ocenę z ćwiczeń o jedną z wartości -1, -0.5, 0, +0.5, +1.0, +1.5. Nieprzyjście na egzamin ustny skutkuje -1. Ocena mniejsza niż 3 po egzaminie ustnym traktowana jest jako 2. Ocena większa niż 5 po egzaminie ustnym traktowana jest jako 5.
  11. Egzamin ustny będzie wyglądał następująco. Opublikujemy listę tematów z wykładu, podzieloną na kilka działów. Na egzaminie ustnym trzeba wybrać jeden z działów jako swój ulubiony. Trzeba będzie mieć zgrubne pojęcie o całym materiale oraz bardzo dokładne pojęcie o ulubionym dziale. Na egzaminie ustnym będzie się losować kilka pytań, po jednym z każdego działu, przy czym oczekujemy bardzo dokładnej odpowiedzi na pytanie z ulubionego działu.
  12. Egzamin w sesji poprawkowej (wrześniowej) będzie składał się z części pisemnej (zadaniowej) i ustnej. Wynik części zadaniowej zastępuje punkty z prac domowych. Egzamin ustny odbywa się na tych samych zasadach, co w sesji czerwcowej. Część pisemna nie jest obowiązkowa: można przyjść poprawić jedynie egzamin ustny, używając oceny z ćwiczeń jako oceny modyfikowanej na egzaminie ustnym.

Plan przedmiotu

Nr Data Co na wykładzie Co na ćwiczeniach Uwagi
1 22.02 Kernelizacja - definicja, motywacje, przykłady. Lemat o słoneczniku i zastosowania.
Notatki spisał: Arkadiusz Socała.
Różne elementarne jądra. Opublikowanie 1. serii zadań domowych
2 1.03 Dekompozycja koronna. Lemat o c-ekspansji. Liniowe jądro dla problemu pokrycia wierzchołkowego.
Notatki spisał: Arkadiusz Socała.
Twierdzenie Halla, twierdzenie Tutte, zastosowania dekompozycji koronnej.  
3 08.03 Kwadratowe jądro dla problemu Feedback Vertex Set.
Notatki spisał: Tomasz Stróżak.
Uzupełnianie dowodów z wykładu. Analiza twierdzenia Madera o S-ścieżkach. Opublikowanie 2. serii zadań domowych
4 15.03 Inne zastosowania lematu o c-ekspansji i pokrewnych technik.
Notatki spisał: Tomasz Stróżak.
Uzupełnianie drobiazgów z wykładu, inne zastosowania. Termin oddania 1. serii zadań domowych.
- 22.03 Wykład odwołany.
5 05.04 Dolne ograniczenia w kernelizacji: wstęp.
Notatki z wykładu i tutoriala A. Druckera spisał: Mateusz Baranowski.
Redukcje trudności kernelizacji. Opublikowanie 3. serii zadań domowych
- 09-12.04 Warsztaty o Kernelizacji. Zapraszamy na całość, a wymagać będziemy znajomości materiału z tutoriala Andrew Druckera.
6 19.04 Kernelizacja przez dekompozycję modularną, część pierwsza. Cluster Editing.
Notatki prowadzi: Piotr Lewandowski.
Dekompozycja modularna Opublikowanie 4. serii zadań domowych
Termin oddania 2. serii zadań domowych.
7 26.04 Kernelizacja przez dekompozycję modularną, część druga. Feedback Arc Set in Tournaments.
Notatki prowadzi: Piotr Lewandowski.
Inne zastosowania dekompozycji modularnej  
8 10.05 Kernelizacja przez matroidy (skrót). Odd Cycle Transversal.
Notatki z wykładu i z tutoriala spisał: Tomasz Kociumaka.
Matroidy. Opublikowanie 5. serii zadań domowych
9 17.05 Kernelizacja w grafach planarnych. Problem minimalnego zbioru dominującego.
Notatki prowadzi: Jarosław Błasiok.
Inne algorytmy kernelizacyjne w grafach planarnych. Termin oddania 3. serii zadań domowych.
10 24.05 Meta-kernelizacja. Protruzje.
Notatki prowadzi: Jarosław Błasiok.
Zastosowania poznanych meta-twierdzeń. Opublikowanie 6. serii zadań domowych.
Termin oddania 4. serii zadań domowych.
11 07.06 Perełki kernelizacji: jądro dla problemu umieszczania k wierzchołków na cyklu.
Notatki spisał: Mateusz Baranowski.
Różne zadania Termin oddania 5. serii zadań domowych.
Na przedmiocie będzie wyraźny podział na wykład i ćwiczenia, ale nie będzie wyraźnego podziału na wykładowcę i ćwiczeniowcę. Każdy z prowadzących będzie prowadził trochę wykładów i trochę ćwiczeń.

Serie zadań domowych

Zadania domowe należy oddawać mailem do obu prowadzących do godziny 12:00 odpowiedniego piątku, lub w formie pisemnej przez pierwsze piętnaście minut odpowiednich ćwiczeń.
Plan serii:
Numer Termin opublikowania Termin oddania
Seria 1 22.02 (ćwiczenia 1) 15.03 (ćwiczenia 4)
Seria 2 08.03 (ćwiczenia 3) 19.04 (ćwiczenia 6)
Seria 3 05.04 (ćwiczenia 5) 17.05 (ćwiczenia 9)
Seria 4 19.04 (ćwiczenia 6) 24.05 (ćwiczenia 10)
Seria 5 10.05 (ćwiczenia 8) 07.06 (ćwiczenia 11)
Seria 6 24.05 (ćwiczenia 9) 14.06 (pierwszy tydzień sesji)

Literatura

Poniżej lista kilku książek lub artykułów, które mogą być przydatne. Lista będzie się powiększać.
  1. Fedor V. Fomin and Dieter Kratsch, Exact Exponential Algorithms, Springer, 2010.
  2. Rolf Niedermeier, Invitation to Fixed Parameter Algorithms, Oxford University Press, 2006.
  3. Jorg Flum, Martin Grohe, Parameterized Complexity Theory, Springer, 2006.
  4. Rod Downey, Mike Fellows, Parameterized Complexity, Springer, 1999.