Algorytmika 2020

wykład: Łukasz Kowalik i Marcin Pilipczuk

[Ta strona nie jest aktualizowana. Wszystkie informacje o aktualnym wykładzie są w moodle.]

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.

Moodle

Nagrania wykładów, prace domowe, zadania na ćwiczenia itp: w kursie moodle Algorytmika (ZOB) 19/20

Cwiczenia

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).
    Materiały do wykładów 1-2:
  3. 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. (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:
  5. (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, 3-kolorowania, kilki, zbioru niezależnego, pokrycia wierzchołkowego.
    Materiały:
  6. Kombinatoryczne algorytmy aproksymacyjne: algorytm 2-aproksymacyjny dla najliczniejszego pokrycia wierzchołkowego, algorytmy 2- i 3/2-aproksymacyjne dla metrycznego problemu komiwojażera, nieaproksymowalność ogólnego problemu komiwojażera,
    Materiały:
  7. Algorytmy aproksymacyjne oparte o programowanie liniowe: Zaokrąglanie LP (2-aproksymacja pokrycia wierzchołkowego), Metoda prymalno-dualna (2-aproksymacja pokrycia wierzchołkowego, 2-aproksymacja problemu Lasu Steinera). Ćwiczenia: Schemat aproksymacyjny dla problemu plecakowego
    Materiały:
  8. Algorytmy parametryzowane I. 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:
  9. Algorytmy parametryzowane II. Klasy XP, FPT. Rozgałęzianie (branching): pokrycie wierzchołkowe parametryzowane rozmiarem rozwiązania k w czasie O(2^k n^2), Feedback Vertex Set in Tournaments w czasie O(3^k n^3). 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:
  10. Algorytmy randomizowane typu Monte Carlo. Algorytmy dla problemu k-ścieżki: w czasie O(k!E) oraz O((2e)^kE) przez color coding. Algorytmy Kargera i Kargera-Steina na minimalny przekrój w grafie. ćwiczenia: derandomizacja metodą warunkowej wartości oczekiwanej, doskanałe rodziny haszujące.
    Materiały:
  11. Algorytm Edmonsa dla problemu maksymalnego skojarzenia w grafach dowolnych
    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].