Aktualności / News > Dydaktyka / Teaching > Lato/Summer 2018/2019 > Algorytmika Problemów Trudnych Obliczeniowo

Algorytmika Problemów Trudnych Obliczeniowo

Program przedmiotu

  1. algorytmy dokładne, rozgałęzianie (branching) (2)
  2. metoda dziel i zwyciężaj i separatory
  3. aproksymacja, schematy aproksymacyjne
  4. szerokość drzewowa
  5. FPT, kernelizacja (2)
  6. metody randomizowane

Zasady zaliczenia przedmiotu

  1. W ramach przedmiotu studenci w grupach dwu- lub trzyosobowych opracowują jedno z zagadnień wymienionych w dziale Program przedmiotu.
  2. Studenci przygotowują:
    1. prezentację przedstawiającą wprowadzenie teoretyczne do tematu (czas trwania ok. 60 minut)
    2. dokumentację zawierającą analizę teoretyczną algorytmu
    3. implementację algorytmu/algorytmów
    4. raport końcowy z wynikami testów
    5. prezentację z podsumowaniem projektu i omówieniem wyników
  3. Łącznie student może uzyskać 100 punktów. Punktacja za poszczególne elementy: 1. 25%, 2. 25%, 3. 20%, 4. 20%, 5. 10%.
  4. Warunkiem zaliczenia jest uzyskanie co najmniej 50 punktów. Progi punktowe na kolejne oceny są co 10 pkt.
  5. Każdy tydzień spóźnienia w oddaniu części 2,3,4 skutkuje karą -5 pkt.

Harmonogram przedmiotu


Grupa poniedziałkowa, pierwsza prezentacja

18.03 separatory. Szczegóły dowodu twierdzenia o separatorach w grafach planarnych (K. Więcław)
25.03 aproksymacja. Prezentacja
01.04 szerokość drzewowa. Prezentacja
08.0 FPT
15.04 randomizacja. Prezentacja

Grupa wtorkowa, pierwsza prezentacja

25.03 branching. Prezentacja
02.04 aproksymacja. Prezentacja
09.04 FPT
16.04 randomizacja


Druga prezentacja
  1. 10-11.06 grupy 1,2,3
  2. 17-18.06 grupy 4,5,6
Harmonogram projektu
  1. 02.04, godz. 23.59 analiza teoretyczna
  2. 27-28.05 aplikacja (należy zaprezentować aplikację podczas zajęć)
  3. przed końcem maja obowiązkowa kontrola postępów pracy
  4. 04.06, godz. 23.59 raport z testów

Podstawowe materiały źródłowe

  1. Fedor V. Fomin and Dieter Kratsch, Exact Exponential Algorithms, Springer, 2010
  2. 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

  1. Algorytmy dokładne, rozgałęzianie.
    1. 3-kolorowanie grafu (na wejściu jest graf G, algorytm ma znaleźć jego 3-kolorowanie wierzchołkowe lub stwierdzić, że takie nie istnieje)
    2. należy porównać algorytm z podejściem brute-force
    3. Literatura
  2. Metoda dziel i zwyciężaj, separatory
    1. 3-kolorowanie grafu planarnego
    2. należy porównać algorytm z podejściem brute-force
    3. Literatura:
  3. Aproksymacja, schematy aproksymacyjne
    1. zastosować metodę Brendy Baker do zbudowania schematu aproksymacyjnego dla problemu największego zbioru niezależnego w grafie planarnym
    2. proszę zbadać jakość aproksymacji
    3. Literatura:
  4. Szerokość drzewowa
    1. k-kolorowanie grafu o ograniczonej szerokości drzewowej
    2. proszę zwrócić uwagę na algorytmy znajdowania dekompozycji drzewowej
    3. Literatura:
      • rozdział 5 z książki [1] i rozdział 7 z książki [2]
  5. FPT, kernelizacja
    1. zaimplementować algorytm kernelizacji i algorytm FPT dla problemu pokrycia wierzchołkowego
    2. 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)
  6. Metody randomizowane
    1. metoda color coding dla problemu znajdowania poddrzewa o k wierzchołkach
    2. należy porównać z algorytmem brute force
    3. Literatura
      • rozdział 5 w książce [2]
Po bardziej szczegółowy opis proszę o kontakt.

Przykładowe źródła danych do testów