Metody probabilistyczne w algorytmice

Łukasz Kowalik i Marcin Mucha,

semestr zimowy 2010/11

Egzamin I termin z rozwiązaniami

Materiały

Głównym podręcznikiem do wykładu jest:

[MU] Michael Mitzenmacher, Eli Upfal "Metody probabilistyczne i obliczenia" (ang. "Probability and Computing")

Czasami będziemy się odwoływali do innych materiałów, w tym:

[MR] Rajeev Motwani, Prabhakar Raghavan "Randomized Algorithms"

[DP] Devdatt Dubhashi, Alessandro Panconesi "Concentration of Measure for the Analysis of Randomized Algorithms"

[PR] Palka, Ruciński “Niekonstruktywne metody matematyki dyskretnej”, WNT 1996.

[V] Vazirani, “Algorytmy aproksymacyjne”, WNT 2005.

NOTATKI CEZAREGO BARTOSZUKA 

Co dotychczas było?

1. Przypomnienie wiadomośći z rachunku prawdopodobieństwa ze szczególnym naciskiem na zastosowania natury algorytmicznej. (MM)

• Ta część wykładu prawie idealnie pokrywa się z rozdziałami 1-3 z książki Mitzenmachera.
• Jako przykład na zastosowanie liniowości wartości oczekiwanej pojawiły się drzewa BSP. Można to znaleźć w pozycji 2. i w wydanej po polsku książce Geometria Obliczeniowa, de Berg i inni.

2. Nierówność Chernoffa z zastosowaniami. (MM)
   Jest to tematem rozdziału 4 książki Mitzenmachera, ale:

• W ksiązce Mitzenmachera teorii jest zdecydowanie mniej niż na wykładzie. Nie należy się tym specjalnie przejmować, na egzaminie wystarczy znajomość tekstu Mitzenmachera. Wykład był prowadzony na podstawie pozycji 3, zainteresowanym tematyką postaramy się dostarczyć dodatkowych materiałów ;)
• U Mitzenmachera jest parę przykładów, których nie było na wykładzie, przede wszystkim routing w sieciach motylkowych i równoważenie zbiorów. Nie jest konieczna znajomość tych fragmentów, ale gorąco zachęcamy do zapoznania się z nimi.
• Routing na hiperkostce jest u Mitzenmachera zrobiony nieco inaczej niż na wykładzie (wersja z wykładu pochodzi z pozycji 2). Zamiast "kluczowego lematu" korzysta się tam z argumentu probabilistycznego.
• U Mitzenmachera nie ma części przykładów, ew. są w postaci ćwiczeń. Chodzi tu przede o zastosowania "strukturo-danowe": treapy i skiplisty, oraz analizę algorytmu Quicksort. Pochodzą one z pozycji 3. Można o nich poczytać też w notatkach Jeffa Eriksona:

• Treapy i skip-listy: opis analiza czasu oczekiwanego
• Treapy: high-probability results

• Nierówność Chernoffa dla zmiennych ujemnie skorelowanych. Ze względu na to, że prezentacja tego tematu na wykładzie nie przebiegła szczególnie płynnie, oraz na to, że nie jest on omówiony w pozycji 1, pozwoliłem sobie przygotować krótki szkic dowodu.

3. Rozmieszczenia kul w urnach (ŁK)

• Prawdopodobieństwo, że pewne 2 kule trafią do tej samej urny (paradoks dnia urodzin)
• Dla n kul i n urn, maksymalna liczba kul w urnie wynosi O(logn/loglogn) z d. p.
• Aproksymacja poissonowska (przybliżenie rozkładu kul w urnach n niezależnymi zmiennymi o rozkładzie Poissona)
• Dla n kul i n urn, maksymalna liczba kul w urnie wynosi Ω(logn/loglogn) z d. p.
• Siła podwójnego wyboru: dowód, że dla 8n urn i n kul, dla każdej kuli losując 2 urny i wybierając tę o mniejszej liczbie kul, uzyskujemy maksymalna liczbę kul w urnie rzędu O(loglog n).
• Wszystko to jest w Mitzenmacherze, ale siła podwójnego wyboru jest tam w dość niestrawnej formie (na wykładzie był fikuśny dowód grafowy wg pracy Karp, Luby, Meyer auf der Heide -- zobacz np [tu]).

4. Haszowanie (ŁK)

• k-niezależność zdarzeń i zmiennych losowych. Przykłady: konstrukcja 2^n losowych bitów niezależnych parami na podstawie n losowych bitów z zastosowaniem do derandomizacji algorytmu dla MAX-CUT o oczekiwanym współczynniku aproksymacji >= 1/2. [MU]
• k-niezależne rodziny funkcji haszujących

• 2-uniwersalna rodzina Cartera-Wegmana: ha,b(x)=((ax+b) mod p) mod m; a,b ∈ Zp, a ≠ 0.
• k-niezależna rodzina wielomianów stopnia k-1 nad Zp
• j.w. tylko na koniec robimy mod m: (1+epsilon, k)-niezależność.

        Literatura: [skrypt1], [MU].

• haszowanie doskonałe (Fredman, Komlos, Szemeredi 1984). [skrypt1], [MU].
• haszowanie kukułkowe (Pagh, Rodler 2001). [skrypt1], [artykuł], [artykuł]
• haszowanie liniowe z użyciem rodziny 5-niezależnej (Pagh, Pagh, Ruzic 2007). [skrypt2], [blog Patrascu]
• color coding: algorytm dla k-ścieżki i jego derandomizacja z użyciem k-doskonałej rodziny funkcji haszujących (Alon, Yuster, Zwick 1995). [artykuł]
• (2,2)-uniwersalna rodzina Dietzfelbingera: ha(x)=(ax mod 2k) div 2k-l. [skrypt1], strona 9 w [artykuł],

5. Łańcuchy Markowa i zliczanie (na podstawie Mitzenmachera z jednym wyjątkiem)

• łańcuchy Markowa (podstawowe definicje)
• średnie czasy przejścia i zastosowanie: znajdowanie wartościowania spełniającego formułe 2-CNF, a następnie 3-CNF
• klasyfikacja stanów i tw. ergodyczne -> zastosowanie: st-spójność w pamięci O(logn)
• znajdowanie rozkładów stacjonarnych: przykłady i pojęcie czasowej odwracalności
• zliczanie, klasa #P
• definicje algorytmów typu FPTRAS i FPAUS
• równoważność zliczania i próbkowania na przykładzie problemu zliczania zbiorów niezależnych (UWAGA: Dowódu implikacji “przybliżone zliczanie -> niemal jednostajne próbkowanie” nie ma w Mitzenmacherze, można go znaleźć na stronie Alana Frieze.
• szybko mieszające łańcuchy Markowa (definicje)
• coupling (sprzężenie) łańcuchów Markowa
• przykłady couplingu w akcji: tasowanie kart, losowy spacer po hiperkostce, zbiory niezależne ustalonego (małego) rozmiaru.

6. Metoda Probabilistyczna (ŁK)

• Metoda naiwna (P(A)>0): 2-kolorowanie zbioru, liczby van der Waerdena, dolne oszacowanie liczb Ramseya R(k,k) > k/(e√2) * 2k/2 [PR]
• Metoda wartości oczekiwanej

• Istnieje turniej który ma n!/2n-1 ścieżek Hamiltona [PR]
• Konstrukcja turnieju który ma n!/3n ścieżek Hamiltona [PR]
• Derandomizacja metodą warunkowej wartości oczekiwanej [MU, V]
• MAX-SAT: ¾-aproksymacja + derandomizacja [V]
• Równoważenie zbioru, przy okazji wyprowadziliśmy nierówność Chernoffa dla zmiennych sumy niezależnych zmiennych przyjmujących wartości -1/1 z rozkładem jednostajnym [MU, 79-81] + derandomizacja.

• Zaawansowana metoda wartości oczekiwanej (“próbkuj i modyfikuj”)

• Każdy graf zawiera zbiór niezależny o mocy |V|2/4|E|. [MU]
• R(k,k) > 1/e*k*2k/2 (1+o(1)) [PR]

• istnieją grafy o >1/4*n1+1/k krawędziach i talii ≥k (tzn gęste bez małych cykli) [PR]

• Lokalny Lemat Lovasza

• wersja symetryczna i ogólna, dowód wersji ogólnej [PR, MU] (uwaga: w książce [MU] wersja symetryczna występuje z trochę gorszą stałą niż to było na wykładzie i w [PR], ale to jest mało istotny szczegół)
• zastosowanie: k-SAT [MU]
• zastosowanie: ścieżki krawędziowo-rozłączne [MU]

• zastosowanie: R(k,k) > √2/e*k* 2k/2 (1+o(1)) [PR]

• algorytmiczny LLL dla k-SAT -- szkic (nieoptymalnej) metody, która rozrzedza graf na małe spójne składowe [MU]

• algorytmiczny LLL (Moser, Tardos 2009), sformułowanie wersji ogólnej i dowód w przypaku dla k-SAT, wg [notatek Uriela Feige]. Patrz też [wikipedia], [oryginalny-artykuł]

• Metoda 2-go momentu: przykład progu w grafach losowych [MU, PR]

7. Zastosowania lematu Zippela-Schwartza

• skojarzenia w czasie mnożenia macierzy (początek rozdziału 7 w [MR], ale zdecydowanie najlepiej rozprawa doktorska M.M., a w niej rozdział 3 i 2.4, dla zainteresowanych 2.2 (algebra liniowa) i 5 (jak zrobić algorytm Las Vegas), ale tych dwóch rzeczy nie robiliśmy na wykładzie),
• testowanie/znajdowanie skojarzeń w czasie polilogarytmicznym na PRAM (oryginalny artykuł <- naprawdę elementarny),
• dokładne (czerwono-niebieskie) skojarzenia na PRAM-ie (j.w. <- uwaga, tam autorzy starają się optymalizować liczbę procesorów i dlatego liczą ten Pfaffian, prostsze rozwiązanie można uzyskać metodą zaproponowaną przez Jakuba na wykładzie, t.j. na każdą krawędź niezależnie napuszczamy grupę procesorów i w ogóle nie liczymy żadnych adjA),
• znajdowanie k-ścieżki w czasie 2kpoly(n).

8. Algorytm Luby’ego (znajdowanie maksymalnego zbioru niezależnego na PRAM)

Egzamin

środa, 2.2.10, godz 10-13 sala 3120.

Egzamin składa się z dwóch częsci:

1) pytania “teoretyczne” i krótkie/standardowe zadania - NIE można korzystać z materiałów

2) zadania -- można korzystać z materiałów