AZ (algorytmika i złożoność obliczeniowa)PD (przetwarzanie danych)
Opis przedmiotu:
W przypadku niektórych rzeczywistych zagadnień, takich jak np. routing w
sieciach, pamięć podręczna procesorów, buforowanie danych w internecie (web
caching), czy szeregowanie zadan (scheduling), 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, aktualne prace naukowe i o materiały z podobnych wykładów
prowadzonych na innych uniwersytetach na świecie.
##### 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.
##### Zawartość przedmiotu:
* Wstęp do algorytmów online. Problem wypożyczania nart (Ski Rental Problem), jako przykład problemu "wypożyczyć czy kupić" (rent-or-buy), analiza konkurencyjności (competitive analysis), k-konkurencyjność.
* Analiza zamortyzowana i funkcje potencjału w przykładach.
* Wyszukiwanie obiektów: poszukiwanie krowy i brzegu oceanu.
* Algorytmy stronicowania (paging) czyli np. zarządzania pamięcią podręczną procesora. Analiza algorytmów LRU (Least-Recently-Used) i FIFO (First-In-First-Out). Zrandomizowane algorytmy stronicowania, algorytm "Random Marking".
* Problem uaktualniania list (List Update). Algorytmy Move-to-Front, BIT i Timestamp.
* Porównanie adwersarzy adaptujących się i nieświadomych (oblivious). Zasada min-max Yao do dowodzenia dolnych ograniczeń.
* Problemy replikacji i migracji danych w sieciach (Page Migration, Page Replication, File Allocation). Technika work-functions.
* Problem k-server. Przykładowe algorytmy. Hipoteza k-server.
* Algorytmy szeregowania zadań (scheduling), identyczne maszyny (algorytm Grahama), nieidentyczne maszyny.
* Algorytmy finansowe, zamiana walut.
* Wykorzystanie programowania liniowego; algorytm dla problemu pokrywania zbiorami.
##### 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
