Algorytmika 1000-2N00ALG

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.

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

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:

• Informatyka, stacjonarne, pierwszego stopnia
• Informatyka, stacjonarne, drugiego stopnia

Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb:

• Strona przedmiotu 1000-2N00ALG w USOSweb