Algorytmy OnLine 2021

Wtorek 13¹⁵ - 15⁰⁰ wykład

Wtorek 11¹⁵ - 13⁰⁰ TN/TP ćwiczenia

Środa 13¹⁵ - 15⁰⁰ TN/TP laboratorium

Wtorek 9¹⁵ - 11⁰⁰ TN laboratorium

Literatura podstawowa

1. A. Fiat, G.J. Woeginger: Online Algorithms: The State of the Art. Springer-Verlag, 1998
2. D. Komm: An Introduction to Online Computation. Springer, 2016
3. A. Borodin, R. El-Yaniv: Online Computation and Competitive Analysis. Cambridge University Press, 1998
4. S. Albers: Competitive online algorithms. Optima, 54:1-8, 1997.
5. S. Albers: Lecture notes on competitive online algorithms. BRICS Lecture Series LS-96-2, AArhus University, Denmark, 1996.

Literatura dodatkowa

1. K. Andrew, D.F. Gleich: Mtf, bit, and comb: A guide to deterministic and randomized online algorithms for the list access problem. Advanced Algorithms, Harvey Mudd College, Final Project, 2004.
2. D.D. Sleator, R.E. Tarjan: Self-Adjusting Binary Search Trees. Journal of the Association for Computing Machinery, Vol. 32, No. 3, 1985, pp. 652-686.
3. D.D. Sleator, R.E. Tarjan: Amortized Efficiency Of List Update and Paging Rules. Communications of the ACM, Vol. 28, No. 2, 1985.
4. A. Fiat, R.M. Karp, M. Luby, L.A. McGeoch, D.D. Sleator, N.E. Young: Competitive Paging Algorithms. Journal of Algorithms 12, 685-699 (1991).
5. M. S. Manasse, L. A. McGeoch, D. D. Sleator: Competitive Algorithms for Server Problems. Journal of Algorithms 11, 208-230 (1990).
6. D. L. Black, D. D. Sleator: Competitive Algorithms for Replication and Migration Problems. Carnegie Mellon University, Computer Science, CMU-CS-89-201, 1989.

Tematy wykładów (w przybliżeniu)

1. Wprowadzenie. (02-03-2021)
   [Podstawowe pojęcia - współczynnik konkurencyjności. Problem wypożyczania nart; Problem szukania krowy.]
2. Samoorganizujące się listy. (09-03-2021)
   [Algorytmy Move-to-Front, Transpose, Frequency-Count. Dolna granica na współczynnik konkurencyjności dla algorytmów deterministycznych.]
3. Samoorganizujące się listy. Inne samoorganizujące struktury. (16-03-2021)
   [Średni przypadek dla list. Algorytmy zrandomizowane Bit i TimeStamp(p). Drzewa Splay.]
4. Paging problem. (23-03-2021)
   [Paging problem - definicja. Algorytmy FIFO, FWF, LRU, LFU. Algorytm oznaczający. Dolne ograniczenie algorytmów deterministycznych. Optymalność algorytmów oznaczających.]
5. Paging problem - algorytmy losowe. (13-04-2021)
   [Randomized Marking Algorithm. Oczekiwany współczynnik konkurencyjności RMA. Dolna granica na algorytmy losowe.]
6. Równoważenie obciążeń. (20-04-2021)
   [Różne modele maszyn: identyczne, różnej prędkości, ograniczone i dowolne. Algorytmy zachłanne. Algorytm SlowFit.]
7. Bin packing. (27-04-2021)
   [Algorytm Next-Fit. Dolna granica na wsp. konkurencyjności. Algorytmy First-Fit i Best-Fit. Ogranicznie pojemników - algorytm Harmonic.]
8. Problem k serwisantów w przestrzeniach metrycznych. (4-05-2021)
   [Definicja przestrzeni metrycznej. Problem k-serwisantów - dolne i górne granice. Problem na prostej.]
9. Page migration. (11-05-2021)
   [Definicja problemu. Algorytm deterministyczny Move-To-Min. Algorytm Flip.]
10. Page migration. Page replication (18-05-2021)
    [Algorytm zrandomizowany Counter dla PM. Algorytm Counter i Flip dla Page Replication.]
11. Page allocation. (25-05-2021)
    [Algorytm Count dla sieci jednostajnych. Algorytm Coin-Flip.]
12. Zrandomizowane algorytmy online - Yao's Principle. (1-06-2021)
    [Yao's Principle zastosowane do dolnych granic algorytmów zrandomizowanych. Dolna granica na zrandomizowany algorytm wypożyczania nart.]
13. Kolorowanie grafów dwudzielnych. (8-06-2021)
    [Dolna granica dla algorytmów online. Algorytm zachłanny. Algorytm ze współczynnikiem konkurencyjności O(log n).]
14. Szukanie punktu w przestrzeniach dwuwymiarowych. (15-06-2021)
    []
15. Kolokwium. (22-06-2021)
    []

Ćwiczenia

• Lista nr 1
• Lista nr 2
• Lista nr 3
• Lista nr 4
• Lista nr 5
• Lista nr 6
• Lista nr 7

Laboratorium

• Lista nr 1 (termin oddania: drugie pełne zajęcia)
• Lista nr 2 (termin oddania: czwarte pełne zajęcia)
• Lista nr 3 (termin oddania: piąte pełne zajęcia)
• Lista nr 4 (termin oddania: szóste pełne zajęcia) (Uwagi do konstrukcji grafów w zadaniu)
• Lista nr 5 (termin oddania: siódme pełne zajęcia)

Zasady zaliczenia kursu

Kurs będzie zaliczany na podstawie kolokwium końcowego, które odbędzie się na ostatnim wykładzie, oraz na podstawie średniej z ocen za listy na laboratorium i aktywności na ćwiczeniach ocenianej w skali od 0 do 5. jakości oraz terminowości oddawania pisemnie (PDF) przydzielonych na ćwiczeniach zadań, traktowanych jako aktywność oceniana w skali od 0 do 5.

Na kolokwium jedyną dopuszczalną pomocą naukową jest kartka formatu A4, wyraźnie podpisana.

Warunkiem zaliczenia ćwiczeń jest oddanie przez studenta w formie pisemnej (PDF) wyznaczonych zadań. Oddawane zadanie powinno być rozwiązane dokładnie, w sposób formalny i przejrzysty. Zadania wyznacza i ocenia prowadzący ćwiczenia.

Ocena końcowa

Ocena końcowa jest jest wyliczana według wzoru: 0.4 oceny z kolokwium + 0.3 oceny z laboratorium + 0.3 aktywności na ćwiczeniach, zaokrąglonej w górę do najbliższej oceny (2.5 zaokrągla się jednak do 2.0).