Algorytmy parametryzowane i umiarkowanie wykładnicze

semestr zimowy 2012/2013

Strona edycji w semestrze letnim 2015/16

Spis treści

Aktualności

Informacje ogólne

Przedmiot oferowany w semestrze zimowym 2012/2013.
Strona przedmiotu w USOSie.
Polecamy też przedmiot w semestrze letnim Kernelizacja.

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. 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. 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ć do późniejszej z dat (tydzień po wykładzie, 48h przed wykładem n+1), wysłać prowadzącym i nanieść ich poprawki. Celem jest, by notatki były dostępne do późniejszej z dat: wykład n+1, dwa tygodnie po wykładzie n.
  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

Dokładny plan wykładów:
Nr Data Co na wykładzie Co na ćwiczeniach Uwagi
1 05.10. Algorytmy parametryzowane: definicja i motywacja. Algorytmy rozgałęziające się (branching) na przykładzie pokrycia wierzchołkowego. Measure & Conquer
Notatki spisał: Arkadiusz Socała 		Algorytmy rozgałęziające się. Opublikowanie 1. serii zadań domowych.
2 12.10. Zastosowania teorii minorów w złożoności parametryzowanej. Iterative compression. Algorytm dla problemu Odd Cycle Transversal.
Notatki spisał: Kamil Yurtsever 		Inne zastosowania iterative compression. Problem Feedback Vertex Set.  
3 19.10. Colour-coding. Derandomizacja, rodziny doskonałe, splittery.
Notatki spisał: Mateusz Baranowski 		Inne przykłady zastosowań techniki colour-coding. Opublikowanie 2. serii zadań domowych.
4 26.10. Zasada włączen i wyłączeń. Fast Subset Convolution. Algorytm liczenia liczby chromatycznej grafu.
Notatki spisał: Michał Kawiak 		Zastosowania i uogólnienia FSC.  
5 9.11. Treewidth. Programowanie dynamiczne po treewidthie. Twierdzenie Courcelle'a.
Notatki spisał: Robert Rosołek 		Różne dynamiki po treewidthie. MSOL. Algorytmy w grafach subkubicznych. Termin oddania 1. serii zadań domowych.
6 16.11. Randomizacja: lemat Schwartza-Zippela i lemat o izolacji. Znajdowanie k-ścieżki w czasie 2k.
Notatki spisał: Paweł Walczak 		Inne zastosowania: Cut & Count. Opublikowanie 3. serii zadań domowych.
7 23.11. Przegląd innych technik w algorytmach umiarkowanie wykładniczych. Split & list, divide & conquer, memoization. Algorytmy dla problemów Bandwidth i Max-Cut.
Notatki spisał: Jarosław Błasiok 		Inne przykłady zastosowań poznanych technik. Termin oddania 2. serii zadań domowych.
8 30.11. Bidimensionality i dekompozycje sferyczne.
Notatki spisał: Jakub Oćwieja 		Bidimensionality. Opublikowanie 4. serii zadań domowych.
9 7.12. Problemy rozcinania grafu. Ważne separatory.
Notatki spisał: Michał Włodarczyk 		Algorytm dla problemu Almost 2-SAT. Algorytm dla problemu Multiway Cut przez programowanie liniowe.  
10 14.12. Parametryzacja powyżej i poniżej oczekiwań.
Notatki spisał: Łukasz Marecik 		Prostsze przypadki problemów z parametryzacją powyżej i poniżej oczekiwań.  
11 21.12. W-Hierarchia. Dowód zupełności problemów maksymalnej kliki i minimalnego zbioru dominującego.
Notatki spisał: Tomasz Gogacz 		Redukcje W[t]-trudności. Termin oddania 3. serii zadań domowych. Opublikowanie 5. serii zadań domowych.
12 11.01. Wyższe poziomy W-Hierarchii. Exponential Time Hypothesis.
Notatki spisał: Jakub Pachocki 		Redukcje W[t]-trudności. Opublikowanie 6. serii zadań domowych.
Termin oddania 4. serii zadań domowych.
13 18.01. Teoria wokół Exponential Time Hypothesis.
Notatki spisał: Tomasz Kociumaka 		Redukcje oparte o ETH.  
14 25.01. Strong Exponential Time Hypothesis i wnioski z niej.
Notatki spisał: Marcin Wrochna 		Redukcje oparte o SETH. 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 początku ćwiczeń (godzina 18: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 05.10. (ćwiczenia 1) 09.11. (ćwiczenia 5)
Seria 2 26.10. (ćwiczenia 3) 23.11. (ćwiczenia 7)
Seria 3 16.11. (ćwiczenia 6) 21.12. (ćwiczenia 11)
Seria 4 30.11. (ćwiczenia 8) 11.01. (ćwiczenia 12)
Seria 5 21.12. (ćwiczenia 11) 25.01. (ćwiczenia 14)
Seria 6 11.01. (ćwiczenia 12) 01.02. (środek sesji)

Materiały

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.