AZ (algorytmika i złożoność obliczeniowa)PD (przetwarzanie danych)
Opis przedmiotu:
**Przedmiot nie będzie odbywać się w trybie zdalnym**
W przypadku niektórych rzeczywistych zagadnień, takich jak szeregowanie zadań (scheduling), zarządzanie pamięcią podręczną, routing pakietów czy buforowanie danych w internecie (web caching), algorytm je rozwiązujacy 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.
* Definicja konkurencyjności, przykładowe zagadnienia.
* Algorytmy zaznaczające: problem pamięci podręcznej, wpływ randomizacji, metryczne systemy zadań.
* Analiza zamortyzowana za pomocą funkcji potencjału: problem reorganizacji listy.
* Funkcje potencjału dla algorytmów randomizowanych.
* Zasada minimaksowa dla dowodzenia dolnych ograniczeń.
* Metoda podwajania: zastosowania do problemów eksploracji
terenu i szeregowania.
* Techniki programowania liniowego: problem pokrywania zbiorami, routing.
* Problem k-server: dolne ograniczenia, algorytm dla drzew.
* Technika factor-revealing LP: problem migracji pliku.
* Funkcje pracy: optymalny algorytm dla metrycznych systemów zadań.
* 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
* Niv Buchbinder, Joseph Naor: "The Design of Competitive Online Algorithms via a Primal–Dual Approach". Foundations and Trends in Theoretical Computer Science, 2007
