Algorytmika

fakultatywne

Algorytmy i struktury danych 1000-213aASD

Wykład jest kontynuacją wykładu "Algorytmy i struktury danych". Celem zajęć jest zaznajomienie studentów z technikami konstrukcji efektywnych algorytmów dla różnych rodzajów problemów kombinatorycznych.

Wymagania wstępne: Algorytmy i struktury danych

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

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

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

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.