Wybrane Zagadnienia Algorytmiki 2012/13

Notatki

Poniżej udostępnione są notatki do wykładów, przygotowane przez studentów. Notatki do każdego wykładu znajdują się w osobnym pliku pdf, można też ściągnąć archiwum zawierające komplet notatek oraz zadania z wybranych ćwiczeń.

Notatki na stronie umieszczamy po uprzednim sprawdzeniu ich, co nie musi jednak znaczyć, że nie ma w nich błędów. W przypadku znalezienia takowych prosimy o kontakt. Osoby biorące udział w zajęciach mogą też same wprowadzić zmiany w repozytorium (tam też znajdują się najnowsze wersje notatek). Prosimy jednak o korzystanie z tej metody nanoszenia poprawek tylko w sytuacjach, kiedy błąd jest ewidentny.

Części notatek nie otrzymaliśmy i zapewne przed egzaminem nie otrzymamy. Do tych wykładów proponujemy inne źródła, w miarę możliwości zbliżone do wykładu pod względem sposobu prezentacji. Używane tam skróty bibliograficzne:

Przy okazji te dwie pozycje najlepiej pasują tematycznie do wykładu.
Uwaga: Niektóre z linków poniżej prowadzą do artykułów Springera i w związku z tym są dostępne tylko z wydziału. Alternatywą jest dopisanie przed adresem “https://han.buw.uw.edu.pl/han/atoz” i zalogowanie się numerem karty bibliotecznej, np. “https://han.buw.uw.edu.pl/han/atoz/link.springer.com/content/pdf/10.1007/3-540-44985-X_19.pdf”

Wykład 1 Metody algebraiczne
Wykład 2 Metody algebraiczne, c.d. – najkrótsze ścieżki
Wykład 3 Local search. Zamiast notatek: o k-medianie rozdział 4 w tych notatkach, dla nieważonych skojarzeń w hipergrafach nie ma dobrego źródła, ważone są w tej pracy (link działa tylko z wydziału).
Wykład 4 Iterowane zaokrąglanie
Wykład 5 Iterowane zaokrąglanie, c.d. + zaokrąglanie zależne
Wykład 6 Zaokrąglanie zależne, c.d. + zapowiedź zanurzeń metrycznych
Wykład 7 Zanurzenia w metryki drzewowe
Wykład 8 Programowanie półokreślone
Wykład 9 Hierarchie programów liniowych. Zamiast notatek: Rozdział 2 z tej monografii , twierdzenie o dekompozycji z tej pracy (link działa tylko z wydziału), prostsza wersja występuje (jako lemat 2.1) w tej pracy.
Wykład 10 Trudność aproksymacji
Wykład 11 Trudność aproksymacji – hipoteza Unique Games. Zamiast notatek: Szczątkowy opis w rozdziale 14.5 w [SW]
Wykład 12 Algorytm Multiplicative Weights Update
Wykład 13 LP konfiguracji na przykładzie algorytmu Karmarkara-Karpa. Zamiast notatek: rozdział 4.6 w [SW], ew. 13.5 w [LRS] (nieco inne grupowanie i nieco inna analiza).

Zadania z ćwiczeń

Poniżej można znaleźć zadania z niektórych ćwiczeń.

Ćwiczenia 1 Metody algebraiczne
Ćwiczenia 2 Metody algebraiczne, c.d. – najkrótsze ścieżki
Ćwiczenia 10 Trudność aproksymacji
Ćwiczenia 11 Hipoteza Unique Games

Praca domowa 2

Oto druga seria zadań. Rozwiązania należy oddać do końca zajęć w dniu 12.06.2013 w formie papierowej lub elektronicznej. W przypadku formy papierowej prosimy o dostarczanie rozwiązań na osobnych kartkach.

Praca domowa 1

Oto pierwsza seria zadań. Rozwiązania należy oddać do końca zajęć w dniu 15.05.2013 w formie papierowej lub elektronicznej. W przypadku formy papierowej prosimy o dostarczanie rozwiązań na osobnych kartkach.