AZ (algorytmika i złożoność obliczeniowa)PD (przetwarzanie danych)
Opis przedmiotu:
W przypadku niektórych rzeczywistych zagadnień, takich jak szeregowanie zadan
(scheduling), zarządzanie pamięcią podręczną, routing pakietów czy buforowanie
danych w internecie (web caching), algorytm je rozwiazujacy musi działać w
sposób online i dokonywać decyzji bez wiedzy lub z częściową wiedzą o
przyszłości. Tematem wykładu będą takie właśnie zagadnienia i ich analiza.
Podobnie jak w przypadku algorytmów aproksymacyjnych, interesować nas będą
rozwiązania przybliżone. Pokażemy, jak dowodzić konkretnych gwarancji o
jakości takich przybliżeń. Wykład prowadzony będzie w oparciu o podane poniżej
książki i aktualne prace naukowe.
**Wymagania:**
* Algorytmy i struktury danych (M)
* Rachunek prawdopodobieństwa
**UWAGA:** Osoby, które nie spełniają powyższych wymagań, będą musiały
zaliczyć niepunktowany egzamin wstępny i zostaną zapisane tylko w przypadku
wolnych miejsc.
* Wstęp do algorytmów online, definicja konkurencyjności, przykładowe zagadnienia.
* Algorytmy zaznaczające: problem pamięci podręcznej, algorytm Least-Recently-Used, wpływ randomizacji, metryczne systemy zadań.
* Analiza zamortyzowana za pomocą funkcji potencjału: problem reorganizacji listy, algorytm Move-To-Front.
* Funkcje potencjału dla algorytmów randomizowanych.
* Dolne ograniczenia dla algorytmów randomizowanych, zasada minimaksowa.
* Metoda podwajania: zastosowania do problemów eksploracji terenu i szeregowania.
* Problem k-server: dolne ograniczenia, algorytm Double-Coverage dla drzew.
* Adwersarze adaptujący się: problem migracji pliku, dolne ograniczenia, porównanie adwersarzy.
* Funkcje pracy: optymalny algorytm dla metrycznych systemów zadań.
* Techniki programowania liniowego: problem pokrywania zbiorami.
* Problem routingu i rozłącznych ścieżek.
* Przybliżanie dowolnych metryk za pomocą drzew, zastosowania.
**Literatura:**
* Alan Borodin, Ran El-Yaniv: "Online Computation and Competitive Analysis". Cambridge University Press, 1998.
* Rajeev Motwani, Prabhakar Raghavan: "Randomized Algorithms". Cambridge University Press, 1995.
* Amos Fiat, Gerhard J. Woeginger: "Online Algorithms, The State of the Art". Springer, 1998
