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:
- [LRS] Lap Chi Lau, R. Ravi, Mohit Singh Iterative Methods in Combinatorial Optimization
- [SW] David Shmoys, David Williamson Design of Approximation Algorithms
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.