Aktualności / News > Dydaktyka / Teaching > Historia / History > Algorytmika Problemów Trudnych Obliczeniowo 2020/21
Algorytmika Problemów Trudnych Obliczeniowo 2020/21
Program przedmiotu
- algorytmy dokładne, rozgałęzianie (branching)
- metoda dziel i zwyciężaj i separatory
- aproksymacja, schematy aproksymacyjne
- szerokość drzewowa
- FPT, kernelizacja
- metody randomizowane
Zasady zaliczenia przedmiotu
- W ramach przedmiotu studenci w grupach trzyosobowych opracowują jedno z zagadnień wymienionych w dziale Program przedmiotu.
- Studenci przygotowują:
- prezentację przedstawiającą wprowadzenie teoretyczne do tematu (czas trwania ok. 60 minut)
- dokumentację zawierającą analizę teoretyczną algorytmu
- implementację algorytmu/algorytmów
- raport końcowy z wynikami testów
- prezentację z podsumowaniem projektu i omówieniem wyników
- Łącznie student może uzyskać 100 punktów. Punktacja za poszczególne elementy: 1. 25%, 2. 25%, 3. 20%, 4. 20%, 5. 10%.
- Warunkiem zaliczenia jest uzyskanie co najmniej 50 punktów. Progi punktowe na kolejne oceny są co 10 pkt.
- Każdy tydzień spóźnienia w oddaniu części 2,3,4 skutkuje karą -5 pkt.
Harmonogram przedmiotu
Podstawowe materiały źródłowe
- Fedor V. Fomin and Dieter Kratsch, Exact Exponential Algorithms, Springer, 2010
- Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh, Parameterized Algorithms, Springer, 2015
Obie książki można bezpłatnie ściągnąć, linki znajdują się na stronie F. Fomina.
Opis tematów projektów
- Algorytmy dokładne, rozgałęzianie.
- 3-kolorowanie grafu (na wejściu jest graf G, algorytm ma znaleźć jego 3-kolorowanie wierzchołkowe lub stwierdzić, że takie nie istnieje)
- należy porównać algorytm z podejściem brute-force
- Literatura
- Metoda dziel i zwyciężaj, separatory
- 3-kolorowanie grafu planarnego
- należy porównać algorytm z podejściem brute-force
- Literatura:
- rozdział 10 z książki [1]
- Holzer, Schulz, Wagner, Prasinos, Zaroliagis: Engineering planar separator algorithms. ACM Journal of Experimental Algorithmics 14 (2009) i referencje w tej pracy
- Aproksymacja, schematy aproksymacyjne
- zastosować metodę Baker do zbudowania schematu aproksymacyjnego dla problemu największego zbioru niezależnego w grafie planarnym
- proszę zbadać jakość aproksymacji
- Literatura:
- (trochę związane) rozdział 7.7.2 z książki [2]
- Demaine, Hajiaghayi, Approximation Schemes for Planar Graph Problems (1983, 1994; Baker), Encyclopedia of Algorithms, 2008, pages 59–62 i referencje w tej pracy
- Szerokość drzewowa
- k-kolorowanie grafu o ograniczonej szerokości drzewowej
- proszę zwrócić uwagę na algorytmy znajdowania dekompozycji drzewowej
- Literatura:
- rozdział 5 z książki [1] i rozdział 7 z książki [2]
-
FPT, kernelizacja
- zaimplementować algorytm kernelizacji i algorytm FPT dla problemu pokrycia wierzchołkowego
- Literatura
- rozdziały 1 i 2 z książki [2]
- Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi, Kernelization. Theory of Parameterized Preprocessing, Cambridge University Press, 2019 (wkrótce powinna pojawić się wersja do bezpłatnego ściągnięcia)
-
Metody randomizowane
- metoda color coding dla problemu znajdowania poddrzewa o k wierzchołkach
- należy porównać z algorytmem brute force
- Literatura
- rozdział 5 w książce [2]
Po bardziej szczegółowy opis proszę o kontakt.