Algorytmy Sekwencyjne II
Podstawowe źródła treści wykładów
Tematy poruszane na wykładzie
- Algorytmy randomizowane
- Algorytmy aproksymacyjne
- Algorytmy optymalizacyjne
- Algorytmy online
Materiały dodatkowe
- Pojęcia [Cormen, rozdział "Algorytmy aproksymacyjne"]:
- problem optymalizacyjny
- algorytm aproksymacyjny
- ograniczenie względne, algorytm ρ-aproksymacyjny, algorytm ze stałą aproksymacji ρ
- ograniczenie błędu względnego
- schemat aproksymacji
- wielomianowy schemat aproksymacji
- w pełni wielomianowy schemat aproksymacji
- Problem pokrycia wierzchołkowego
- Problem komiwojażera TSP [Cormen, rozdział "Problem komiwojażera"]
- nieaproksymowalność ogólnego problemu komiwojażera [Cormen, rozdział "Ogólny problem komiwojażera"]
- problem komiwojażera z nierównością trójkąta
- algorytm 2-aproksymacyjny
- algorytm 3/2-aproksymacyjny
- Problem sumy podzbioru [Cormen, rozdział "Problem sumy podzbioru"]
- algorytm wykładniczy
- w pełni wielomianowy schemat aproksymacji
Materiały dodatkowe
- Problem maksymalnego przepływu [Cormen, rozdział "Maksymalny przepływ"]
- Sieć przepływowa - podstawowe pojęcia
- sieć przypływowa
- przepływ (warunki przepustowości, skośnej symetrii i zachowania przepływu)
- Sieć rezydualna
- Ścieżka powiększająca
- Przekrój w sieci
- Twierdzenie o maksymalnym przepływie i minimalnym przekroju
- Algorytm Forda-Fulkersona
- Przykład długiego czasu działania
- Poprawka - algorytm Edmondsa-Karpa
- Problem maksymalnego skojarzenia w grafie dwudzielnym
- Podstawowe pojęcia
- skojarzenie i maksymalne skojarzenie w grafie
- graf dwudzielny
- ścieżka powiększająca
- operacja ⊕
- Twierdzenie Berge'a o ścieżkach powiększających
- Algorytm ścieżek powiększających
- Równoznaczność maksymalnego skojarzenia w grafach dwudzielnych z przepływami [Cormen, rozdział "Najliczniejsze skojarzenia w grafach dwudzielnych"]
- Algorytm Hopcrofta-Karpa - szukanie maksymalnego zbioru najkrótszych ścieżek powiększających
Materiały dodatkowe
- Podstawowe pojęcia
- algorytm online
- R-konkurencyjność algorytmu deterministycznego
- R-konkurencyjność algorytmu randomizowanego
- Problem wypożyczania nart
- algorytm deterministyczny 2-konkurencyjny
- przykład algorytmu randomizowanego o lepszym współczynniku konkurencyjności
- Problem sprzedaży puli akcji na giełdzie
- algorytm deterministyczny sprzedaży całej puli na raz
- algorytm deterministyczny sprzedaży w kawałkach
- dla zainteresowanych: algorytm randomizowany sprzedaży całej puli na raz
- Reorganizacja listy
- definicja problemu
- algorytm Move-To-Front (MTF)
- dowód 2-konkurencyjności algorytmu MTF
Materiały