Algorytmika 2019

Zaliczanie przedmiotu

Egzamin składa się z testu (1,5h) i zadań (2,5h). Test będzie w stylu testu z ASD. Potrzebna jest znajomość przedstawionych w ramach wykładu algorytmów, pojęć i twierdzeń/faktów. Na teście nie można korzystać z żadnych materiałów poza własną głową, podczas części zadaniowej można korzystać z notatek, książek itd.

Ocena będzie zależała wyłącznie od sumy punktów z testu i z egzaminu.

Trochę zadań

Literatura

Wykłady

  1. Przepływy. Definicja przepływu, algorytm Forda-Fulkersona, przekroje w sieciach, tw. o minimalnym przepływie i maksymalnym przekroju.
  2. algorytm Edmondsa-Karpa, algorytm Dinica, analiza algorytmu Dinica w sieciach 0-1 (inaczej algorytm Evena-Tarjana, na ćwiczeniach), algorytm trzech Hindusów (na ćwiczeniach)
    Materiały do wykładów 1-2:
  3. Problem Problem przepływu o minimalnym koszcie.. Algorytm ,,cycle cancelling'' (usuwanie z sieci residualnej cykli o ujemnym koszcie). Algorytm najtańszej ścieżki powiększającej i jego implementacja w czasie O(EV+|f*|(E + V log V)) za pomocą funkcji potencjału. Jako wniosek: algorytm w czasie O(EV+V^2 log V) dla problemu ważonego skojarzenia w grafach dwudzielnych. Funkcje potencjału i algorytm Johnsona dla problemu najkrótszych ścieżek między wszystkimi parami wierzchołków. Na ćwiczeniach: algorytm Bellmana Forda, wyszukiwanie cykli o ujemnej wadze.
    Materiały:
  4. Randomizacja. Algorytmy Monte-Carlo: algorytmy Kargera i Kargera-Steina na minimalny przekrój w grafie; algorytm Freivaldsa na testowanie wyniku mnożenia dwóch macierzy. ćwiczenia: color coding, metoda warunkowej wartości oczekiwanej.
    Materiały:
  5. (2 wykłady) Programowanie liniowe: Program w postaci ogólnej, kanonicznej, standardowej, dopełnieniowej (wzajemna równoważność); informacja o algorytmach wielomianowych; programowanie całkowitoliczbowe; interpretacja geometryczna; równoważność pojęć wierzchołka, punktu ekstremalnego i bazowego rozwiązania dopuszczalnego, istnienie rozwiązania optymalnego, które jest wierzchołkiem; algorytm simplex; programy dualne; twierdzenie o (silnej) dualności. Na ćwiczeniach: unimodularność, twierdzenia minimaksowe (Koniga-Egervarego ) jako wnioski z dualności LP.
    Materiały:
  6. (2 wykłady) Problemy decyzyjne. Klasy złożoności P i NP. NP-trudność i NP-zupełność. Problem SAT. Twierdzenie Cooka-Levina (bez dowodu); NP-zupełność problemów 3-SAT, kilki, zbioru niezależnego, pokrycia wierzchołkowego, subset sum, 3-kolorowanie.
    Materiały:
  7. Algorytm Edmonsa dla problemu maksymalnego skojarzenia w grafach dowolnych
    Materiały:
  8. Kombinatoryczne algorytmy aproksymacyjne: algorytm 2-aproksymacyjny dla najliczniejszego pokrycia wierzchołkowego, algorytmy 2- i 3/2-aproksymacyjne dla metrycznego problemu komiwojażera, algorytm zachłanny dla set cover, nieaproksymowalność ogólnego problemu komiwojażera,
    Materiały:
  9. Algorytmy aproksymacyjne oparte o programowanie liniowe: Zaokrąglanie LP (2-aproksymacja pokrycia wierzchołkowego, f-aproksymacja i logn-aproksymacja pokrycia zbioru), Metoda prymalno-dualna (2-aproksymacja pokrycia wierzchołkowego, f-aproksymacja pokrycia zbioru). Ćwiczenia: Schemat aproksymacyjny dla problemu plecakowego
    Materiały:
  10. Algorytmy parametryzowane I. Rozgałęzianie (branching): pokrycie wierzchołkowe parametryzowane rozmiarem rozwiązania k w czasie O(2^k n^2), Kernelizacja: Proste jądro O(k^2) dla pokrycia wierzchołkowego, twierdzenie Nemhausera-Trottera, jądro o 2k wierzchołkach dla pokrycia wierzchołkowego, rozgałęzianie sterowane programem liniowym (LP guided branching).
    Materiały:
  11. Algorytmy parametryzowane II. Dekompozycja ścieżkowa, wygodna dekompozycja ścieżkowa i szerokość ścieżkowa. Dekompozycja drzewowa, wygodna dekompozycja drzewowa i szerokość drzewowa. Algorytm w czasie O(2^w n^2) dla problemu zbioru niezależnego w grafie z daną dekompozycją drzewową szerokości w.
    Materiały:
  12. Szybka transformata Fouriera i jej zastosowania (m.in. do mnożenia wielomianów i liczb); Szybkie mnożenie macierzy (algorytm Strassena) i przykładowe zastosowanie.
    Materiały: [CLRS, Knuth2], slajdy z wykładu [PDF].