Algorytmika 1000-2N00ALG
1. Problemy ścieżkowe w grafach:
- algorytm Bellmana-Forda
- problemy ścieżkowe i mnożenie macierzy
- algorytm Floyda-Warshalla
- algorytm Johnsona
2. Problemy przepływowe.
- twierdzenie o minimalnym przekroju i maksymalnym przepływie
- algorytmy Forda-Fulkersona, Edmondsa-Karpa, Dinica, trzech Hindusów
- problem przepływu o najmniejszym koszcie, algorytm najtańszej ścieżki powiększającej
- redukcje do problemów przepływu
3. Klasy zlozonosci P, NP, dowodzenie NP-trudnosci
4. Programowanie liniowe
- geometria programów liniowych,
- algorytm simplex, dualność
5. Algorytmy aproksymacyjne
- algorytm 2-aproksymacyjny dla pokrycia wierzchołkowego
- nieaproksymowalność problemu komiwojażera
- algorytm Christofidesa dla metrycznego problemu komiwojażera
- zastosowania programowania liniowego w aproksymacji
6. Algotytmy parametryzowane
- definicje klas złożoności FPT, XP
- algorytmy przez rozgałęzianie,
- kernelizacja: liniowe jądro dla problemu pokrycia wierzchołkowego
- pojęcia szerokości ścieżkowej i drzewowej
- programowanie dynamiczne po dekompozycji drzewowej
7. Randomizacja
- algorytmy Monte Carlo i Las Vegas
- technika color coding
- algorytm Monte-Carlo dla problemu największych skojarzeń w grafach
- algorytmy podliniowe
Koordynatorzy przedmiotu
W cyklu 2024L: | W cyklu 2023L: |
Rodzaj przedmiotu
Założenia (lista przedmiotów)
Efekty kształcenia
Wiedza
1. Zna najważniejsze problemy optymalizacji kombinatorycznej
2. Zna pojęcia klas złożoności P i NP, pojęcie problemów NP-trudnych
3. Zna efektywne algorytmy dla najważniejszych problemów optymalizacji kombinatorycznej z klasy P (problemy ścieżkowe, przepływy, programowanie liniowe)
4. Zna najważniejsze problemy NP-trudne.
5. Zna pojęcie algorytmu aproksymacyjnego oraz przykłady takich algorytmów używające podejścia kombinatoryczne oraz oparte o teorię programowania liniowego
6. Zna pojęcie algorytmu parametryzowanego oraz przykłady różnych parametryzacji. Zna pojęcie kernelizacji.
7. Zna pojęcie szerokości drzewowej i technikę programowania dynamicznego po dekompozycji drzewowej
8. Zna przykłady algorytmów randomizowanych typu Monte-Carlo i Las-Vegas
Umiejętności:
1. Potrafi sprowadzać nowe problemy do znanych problemów przepływowych, ścieżkowych, programowania liniowego
2. Potrafi przeprowadzać dowody NP-trudności
3. Potrafi projektować algorytmy aproksymacyjne i analizować jakość aproksymacji
4. Potrafi wskazać naturalne parametryzowane wersje problemów oraz stosuje techniki takie jak: rozgałęzianie, kernelizacja, programowanie dynamiczne po dekompozycji drzewowej.
5. Potrafi stosować podstawowe techniki randomizacyjne (zaokrąglanie randomizowane, lemat Zippela-Schwartza, color coding) oraz umie stosować derandomizację metodą warunkowej wartości oczekiwanej
Kryteria oceniania
Po każdym wykładzie przez Moodle ogłaszany jest krótki test wielokrotnego wyboru, dotyczący materiału z wykładu. By zaliczyć przedmiot w pierwszym terminie, należy uzyskać przynajmniej 75% punktów z wszystkich testów.
Ponadto w ciągu semestru będą 3-4 serie prac domowych, każda składająca się z 1-2 zadań. Egzamin będzie testowy, 90-minutowy, sprawdzający wiedzę i twórcze jej wykorzystanie. Ocena końcowa będzie zależeć od wyników prac domowych i egzaminu.
W przypadku zaliczania przedmiotu przez doktoranta, dodatkowym elementem zaliczenia będzie zapoznanie się z oryginalnym, będącym blisko aktualnego frontu badań, artykułem naukowym i rozmowa z wykładowcą na temat tego artykułu.
By podejść do egzaminu w terminie zerowym, wymaga się powyżej 90% punktów z testów i powyżej 90% punktów z prac domowych.
Literatura
1. Wprowadzenie do algorytmów, T.H. Cormen, C. E. Leiserson, R.L.Rivest, WNT 1998, 2004.
2. Algorytmy aproksymacyjne, V. V. Vazirani, WNT 2005.
3. Metody probabilistyczne i obliczenia, M. Mitzenmacher, E. Upfal, WNT 2009.
4. The Design and Analysis of Algorithms, D. C. Kozen, Springer 1991.
5. Parameterized Algorithms, Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, Saurabh, Springer 2015