Algorytmy Sekwencyjne II - wykład dla MSUI

Plan Wykładu

• Algorytmy randomizowane
• Algorytmy aproksymacyjne
• Algorytmy optymalizacyjne
• Algorytmy online

Literatura podstawowa

• [Cormen] Cormen, Leiserson, Rivest, "Wprowadzenie do algorytmów" Wnt, 2000; wybrane rozdziały.
• [Wazniak] Wazniak - Zaawansowane algorytmy i struktury danych; wybrane wykłady.

Co było na wykładzie:

Wykład 1 (2007-10-02) - Algorytmy randomizowane

• Definicja [Cormen]
• Motywacja
• Definicje algorytmów Monte Carlo i Las Vegas
• Trochę historii
• Liczenie całek i pól powierzchni metodą Monte Clarlo
• Trochę o liczbach losowych
• Przykłady (warto je pamiętać!)
  • znajdowanie dowolnego 'a' w tablicy z taką samą liczbą 'a' i 'b' [Wikipedia]
  • sprawdzanie, który przypadek zachodzi: tablica ma same 'a' lub tablica ma tyle samo 'a' i 'b'.
  • randomizowany QuickSort (i dlaczego jest lepszy) [Cormen]
  • test pierwszości Millera-Rabina [Cormen]
  • używanie losowości do łamania symetrii - Ethernet

Literatura

• [Cormen], rozdział "Probabilistyczne wersje algorytmu Quicksort"
• [Cormen], [Wazniak] - poczatek wykladu 15 "Algorytmy randomizowane"
• Wikipedia - dla uzupełnienia wiadomości - polecam wersję angielską

Wykład 2 (2007-10-10) - Randomizowane struktury danych - Skip listy

• Skip listy
• Przykłady algorytmów randomizowanych - maksymalny przekrój i problem długiej ścieżki

Literatura

• William Pugh, Skip Lists: A probabilistic Alternative to Balanced Trees
• Michiel Smid, "Skip lists: a randomized dictionary" (chyba nie dostępne online)
• [Wazniak], wykład 15

Wykład 3 (2007-10-17) - Randomizowane algorytmy 2

• problem długiej ścieżki
• dokończenie skip-list - algorytmy znajdowania, wstawiania i usuwania.
• Wstęp do algorytmów aproksymacyjnych - definicja problemu optymalizacyjnego

Literatura

• [Cormen] (alg. aproksymacyjne)
• [Wazniak], wykład 15 (problem długiej ścieżki)
• William Pugh, Skip Lists: A probabilistic Alternative to Balanced Trees - skip listy

Wykład 4 (2007-10-24) - Algorytmy aproksymacyjne 1

• definicje: algorytmy (alfa)-aproksymacyjne dla problemu minimalizacji i maksymalizacji, oganiczenie względne
• pokrycie wierzchołkowe - algorytm dodający do pokrycia kolejne nie pokryte jeszcze krawędzie (2-aproksymacja)
• problem komiwojażera z nierównością trójkąta (2-aproksymacja i 3/2-aproksymacja przy uzyciu minimalnego drzewa rozpinającego)

Literatura

• [Cormen] - rozdział "algorytmy aproksymacyjne"
• [ważniak]

Wykład 5 (2007-10-31) - Algorytmy aproksymacyjne 2

• Dowód, że ogólnego problemu komiwojażera nie da się aproksymować.
• Problem sumy podzbioru - schemat aproksymacyjny

Literatura

• [Cormen] - rozdział "algorytmy aproksymacyjne"

Wykład 6 (2007-11-06) - Aproksymacja i maksymalny przepływ

• dokończenie dowodu poprawności schematu aproksymacyjnego dla problemu sumy podzbiorów
• Maksymalny przepływ: definicje: sieć przepływowa, przepływ, przekrój, przepustowość przekroju, wartość przepływu przez przekrój, przepływ maksymalny, graf rezidualny, ścieżka powiększająca

Literatura

• [Cormen] - rozdział "algorytmy aproksymacyjne"
• [ważniak], wykład 9

Wykład 7 (2007-11-13) - Maksymalny przepływ

• Twierdzenie o maksymalnym przepływie i minimalnym przekroju
• Algorytm Forda-Fulkersona
• Złożoność algorytmu Forda-Fulkersona, przykład na dużą złożoność
• Przykład, że dla wag wymiernych alg. FF. nie ma własności stopu.
• Heurystyka Edmondsa-Karpa - wybieranie najkrótszych ścieżek powiększających (bez dowodu)

Literatura

• [Cormen] - rozdział "algorytmy aproksymacyjne"
• [ważniak], wykład 9
• dla zainteresowanych: [wazniak], wykład 10

Wykład 8 (2007-11-20) - Maksymalne skojarzenie

• maksymalny przepływ - przypadek z wieloma źródłami/ujściami
• definiecje: skojarzenie, ścieżka naprzemienna, ścieżka rozszerzająca (powiększająca)
• Twierdzenie Hopcrofta-Karpa
• Algorytm
• skojarzenia w grafach dwudzielnych - równoważność z algorytmami na przepływy.

Literatura

• [Cormen] - rozdział "Maksymalny Przepływ - Maksymalne skojarzenie w grafach dwudzielnych"
• [wazniak] wykład 7

Wykład 9 (2007-11-27) - Maksymalne skojarzenie + dokonczenie

• Algorytm Hopcrofta-Karpa - dowód złożoności + szczegóły implementacji.

Wykład 10 (2007-12-05) - Algorytmy onlinee

• Definicje
• przyklad: przydzielanie zadan
• przyklad: narty
• przyklad: wyszukiwanie liniowe
• przyklad: stronnicowanie

Literatura

• [Advanced algorithms na MIT] - algorytmy online i algorytmy aproxymacujne (przydzial zadan).