Algorytmy parametryzowane

semestr letni 2015/16

Strona poprzedniej edycji

Spis treści

Aktualności

Informacje ogólne

Przedmiot oferowany w semestrze letnim 2015/2016.
Strona przedmiotu w USOSie.

Prowadzący

dr Marcin Pilipczuk, malcin@mimuw.edu.pl
dr Michał Pilipczuk, michal.pilipczuk@mimuw.edu.pl

Warunki zaliczenia

  1. Podstawą zaliczenia są zadania domowe i egzamin ustny.
  2. W trakcie semestru będzie osiem 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. Ostateczną godziną oddania zadań jest początek ćwiczeń ostatniego dnia oddawania odpowiedniej serii.
  4. Każde rozwiązanie oceniane jest jak na Olimpiadzie Matematycznej, tj może dostać 0, 2, 5 lub 6 pkt.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
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ń.

Plan przedmiotu

Dokładny plan wykładów:
Nr Data Wykładowca Co na wykładzie Co na ćwiczeniach Uwagi
1 29.02. Michał Algorytmy parametryzowane: definicja i motywacja. Algorytmy rozgałęziające się (branching) na przykładzie pokrycia wierzchołkowego przy różnych parametryzacjach. Measure & Conquer Algorytmy rozgałęziające się. Opublikowanie 1. serii zadań domowych.
2 07.03. Marcin Kernelizacja. Lemat o słoneczniku. Crown decomoposition. Różne proste algorytmy kernelizacyjne. Opublikowanie 2. serii zadań domowych.
3 14.03. Michał Iterative compression. Programowanie dynamiczne po kracie podzbiorów. Integer Linear Programming. Przykłady zastosowań iterative compression Opublikowanie 3. serii zadań domowych.
4 21.03. Marcin Color coding. Zastosowania losowości w algorytmach parametryzowanych. Różne przykłady użycia techniki color coding. Opublikowanie 4. serii zadań domowych.
5 04.04. Michał Treewidth. Programowanie dynamiczne po treewidthie. Twierdzenie Courcelle'a. Różne dynamiki po treewidthie. MSOL. Termin oddania 1. serii zadań domowych.
6 11.04. Marcin Zasada włączeń i wyłączeń. Transformata zeta i transformata Moebiusa. Zastosowania, m.in. przyspieszanie dynamików po dekompozycjach drzewiastych. Opublikowanie 5. serii zadań domowych.
Termin oddania 2. serii zadań domowych.
7 18.04. Marcin Randomizacja: lemat Schwartza-Zippela i lemat o izolacji. Znajdowanie k-ścieżki w czasie 2k. Inne zastosowania: Cut & Count. Termin oddania 3. serii zadań domowych.
8 25.04. Michał Matroidy. Representative sets. Zastosowania poznanych technik. Opublikowanie 6. serii zadań domowych.
Termin oddania 4. serii zadań domowych.
9 09.09. Marcin Problemy rozcinania grafu. Ważne separatory. Algorytm dla problemu Almost 2-SAT. Algorytm dla problemu Multiway Cut przez programowanie liniowe. Termin oddania 5. serii zadań domowych.
10 16.05. Michał Grafy planarne: bidimensionality, kernelizacja. Bidimensionality. Opublikowanie 7. serii zadań domowych.
11 23.05. Marcin W-Hierarchia. Redukcje W[t]-trudności. Termin oddania 6. serii zadań domowych.
12 30.05. Marek Cygan
(zastępstwo)		 Exponential Time Hypothesis. Redukcje przy założeniu ETH. Opublikowanie 8. serii zadań domowych.
13 06.06. Michał Strong Exponential Time Hypothesis. Redukcje przy założeniu Strong ETH.  
14 13.06. Marcin Przegląd najnowszych odkryć w dziedzinie złożoności parametryzowanej. Dyskusja problemów otwartych. Termin oddania 7. 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 początku ćwiczeń (godzina 16:00) odpowiedniego poniedziałku, lub w formie pisemnej przez pierwsze piętnaście minut odpowiednich ćwiczeń.
Plan serii:
Numer Termin opublikowania Termin oddania
Seria 1 29.02. (ćwiczenia 1) 04.04. (ćwiczenia 5)
Seria 2 07.03. (ćwiczenia 2) 11.04. (ćwiczenia 6)
Seria 3 14.03. (ćwiczenia 3) 18.04. (ćwiczenia 7)
Seria 4 21.03. (ćwiczenia 4) 25.04. (ćwiczenia 8)
Seria 5 11.04. (ćwiczenia 6) 09.05. (ćwiczenia 9)
Seria 6 25.04. (ćwiczenia 8) 30.05. 23.05. (ćwiczenia 1211)
Seria 7 16.05. (ćwiczenia 10) 13.06. (ćwiczenia 14)
Seria 8 30.05. (ćwiczenia 12) 20.06. (środek sesji)

Literatura

Poniżej lista kilku książek lub artykułów, które mogą być przydatne.
  1. Marek Cygan, Fedor Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh, Parameterized Algorithms, Springer, 2015.
  2. Fedor V. Fomin and Dieter Kratsch, Exact Exponential Algorithms, Springer, 2010.
  3. Rolf Niedermeier, Invitation to Fixed Parameter Algorithms, Oxford University Press, 2006.
  4. Jorg Flum, Martin Grohe, Parameterized Complexity Theory, Springer, 2006.
  5. Rod Downey, Mike Fellows, Parameterized Complexity, Springer, 1999.