Algorytmy parametryzowane 1000-2M12APW
Wykład poświęcony będzie ponadwielomianowym algorytmom dla problemów NP-trudnych, ze szczególnym uwzględnieniem algorytmów parametryzowanych.
Planujemy następujące tematy:
1. Algorytmy parametryzowane: definicja i motywacja.
2. Algorytmy rozgałęziające się. Analiza Mierz i Zwyciężaj.
3. Przegląd technik stosowanych w algorytmach ponadwielomianowych:
iterative compression, color coding, split&list, dziel i zwyciężaj, ważne separatory.
4. Zastosowania zasady włączeń i wyłączeń, algorytmy szybkiego splotu podzbiorów.
5. Techniki algebraiczne (Schwarz-Zippel oraz lemat o izolacji).
6. Algorytmy w grafach o ograniczonej szerokości drzewiastej.
7. Algorytmy podwykładnicze w grafach planarnych: bidimensionality.
8. Ograniczenia dolne: hierarchia W oraz Hipoteza Czasu Wykładniczego.
Rodzaj przedmiotu
Koordynatorzy przedmiotu
Efekty kształcenia
Wiedza:
Ma zaawansowaną wiedzę z zakresu projektowania i analizy algorytmów dokładnych dla problemów NP-trudnych oraz wyznaczania granic ich możliwości (K_W01, K_W02). W szczególności, po zajęciach student jest w stanie rozpocząć (samodzielną lub w zespole) pracę naukową nad ww. zagadnieniami.
Umiejętności:
* potrafi opracować dokładny algorytm dla średnio-trudnego problemu kombinatorycznego NP-trudnego (K_U04)
* potrafi (w rygorystyczny, formalny sposób) zanalizować algorytm, dowodząc jego poprawność i określając złożoność (K_U04)
* rozumie bardziej szczegółowe klasy złożoności wewnątrz klasy NP, w tym W-hierarchię, potrafi umieścić w niej zadany problem i przeprowadzić prostą redukcję trudności (K_U05)
* potrafi korzystać z tekstów źródłowych i podręczników w języku angielskim (K_U14)
* potrafi przygotować krótkie opracowanie wykładu w języku angielskim (K_U13)
Kompetencje
* rozumie potrzebę systematycznego zapoznawania się z czasopismami naukowymi i popularnonaukowymi w celu poszerzania i pogłębiania wiedzy (K_K08).
* potrafi precyzyjnie formułować pytania, służące pogłębieniu własnego zrozumienia danego tematu lub odnalezieniu brakujących elementów rozumowania (K_K02).
Kryteria oceniania
Testy po każdym wykładzie (przez Moodle, na zaliczenie, 75% quizów daje modyfikator 0.5 do oceny z egzaminu ustnego), prace domowe z zadaniami (łączna suma punktów daje modyfikator do oceny z egzaminu ustnego) oraz egzamin ustny (na ocenę). Szczegółowe zasady w sekcji ogólnej w moodle.
Literatura
- Marek Cygan, Fedor Fomin, Łukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh, Parameterized Algorithms, Springer, 2015.
- Fedor V. Fomin and Dieter Kratsch, Exact Exponential Algorithms, Springer, 2010.
- Rolf Niedermeier, Invitation to Fixed Parameter Algorithms, Oxford University Press, 2006.
- Jorg Flum, Martin Grohe, Parameterized Complexity Theory, Springer, 2006.
- Rod Downey, Mike Fellows, Parameterized Complexity, Springer, 1999.
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: