Algorytmy Sekwencyjne II (jesień 2007)

Tematy na egzamin

1. Algorytmy randomizowane - Definicja, Motywacja, Definicje algorytmów Monte Carlo i Las Vegas (i różnice) Liczenie całek i pól powierzchni figur metodą Monte Carlo, przykłady: stwierdzanie, czy tablica ma same 'a', czy po połowie 'a' i 'b', test pierwszości Millera-Rabina (bez szczegółów teorioliczbowych). Skip Listy - co to jest, do czego służy, algorytmy wstawiania, usuwania i znajdowania elementów, złożoność, policzenie średniej wysokości elementu, średnia wysokość skip-listy (bez dowodu), policzenie średniego rozmiaru skip-listy, złożoności operacji (dowód z "machaniem rękami").
2. Algorytmy randomizowane 2 - randomizowany QuickSort (losowy punkt podziału) - w jakich przypadkach jest lepszy, maksymalny przekrój (z dowodem, że jest to 1/2-aproksymacja), problem długiej ścieżki (algorytm i idea dowodu - można pominąć pewne obliczenia w dowodzie), definicja algorytmu randomizowanego. Uwaga: nie trzeba znać zastosowań praktycznych problemu maksymalnego przekroju.
3. Algorytmy aproksymacyjne - definicja aproksymacji, 2-aproksymacji, itp., po co aproksymować, pokrycie wierzchołkowe (trzeba wiedzieć, że algorytm zachłanny, w którym bierzemy wierzchołek najwyższego stopnia nie będzie gwarantował 2-aproksymacji, patrz ważniak, przykład 3.2), problem komiwojażera z nierównością trójkąta (tylko 2-aproksymacja, ale z dowodem; można nie znać sposobu na 3/2 aproksymacje), dowód, że ogólnego problemu komiwojażera nie da się aproksymować.
4. Schemat aproksymacyjny - definicja aproksymacji, definicja schematu aproksymacyjnego, błąd względny, schemat aproksymacyjny dla problemu sumy podzbioru (z dowodem, że schemat jest wielomianowy i że działa; można pominąć dowód lematu: "dla każdego y istnieje z ... ", ale trzeba umieć z niego skorzystać). Uwaga! tego nie bedzie do wylosowania
5. Maksymalny przepływ - definicja sieci przepływowej, przepływu, grafu residualnego, przepustowości, ścieżki powiększającej, twierdzenie o maksymalnym przepływie i minimalnym przekroju, Algorytm Forda-Fulkersona, jego złożoność; Trzeba wiedzieć, że algorytm Forda-Fulkersona dla liczb rzeczywistych może się nie zatrzymać, ale można nie pamiętać przykładu. Trzeba pamiętać, że algorytm Edmondsa-Karpa (wybieranie najkrótszych ścieżek powiększających) ma lepszą złożoność - i wiedzieć jaką (dowodu tego nie było na wykładzie, więc nie jest wymagany).
6. Maksymalne skojarzenie - definicja skojarzenia, ścieżka naprzemienna, ścieżka powiększająca, twierdzenie Berge'a i Hopcrofta-Karpa (z dowodem), algorytm na skojarzenia w grafach dwudzielnych - poprawność, złożoność i związek z przepływami
7. Maksymalne skojarzenie - definicja skojarzenia, ścieżka naprzemienna, ścieżka powiększająca, Algorytm na Hopcrofta-Karpa (szukanie maksymalnego zbioru najkrótszych ścieżek powiększających minimalnej długości), jego złożoność (z dowodem). Trzeba wiedzieć, że w tym algorytmie długość najkrótszej ścieżki powiększającej stale rośnie, ale można nie znać dowodu. Trzeba mniej więcej wiedzieć jak szukać zbioru ścieżek powiększających
8. Algorytmy online - definicje, przyklad: przydzielanie zadan (z dowodem) przyklad: narty (z dowodem) przyklad: wyszukiwanie liniowe (Uwaga: prosze zwrocic uwage jak jest liczony koszt przestawien! - bez dowodu) przyklad: stronnicowanie (bez dowodu)