Algorytmy OnLine 2025

Środa 13¹⁵ - 15⁰⁰ D-1/29 wykład

Środa 17⁰⁵ - 18⁴⁵ C-3/22 TN ćwiczenia

Czwartek 13¹⁵ - 15⁰⁰ D-1/317.4 TN/TP laboratorium (mgr inż. Dawid Dworzański)

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. (05-03-2025 - szkic notatek)
   [Podstawowe pojęcia - współczynnik konkurencyjności. Problem wypożyczania nart; Problem szukania krowy.]
2. Samoorganizujące się listy. (12-03-2025 - szkic notatek)
   [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. (19-03-2025)
   [Algorytmy zrandomizowane Bit i TimeStamp(p). Drzewa Splay.]
4. Paging problem. (26-03-2025 - szkic notatek (poprawione 3 kwietnia))
   [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. (2-04-2025)
   [Randomized Marking Algorithm. Oczekiwany współczynnik konkurencyjności RMA. Dolna granica na algorytmy losowe.]
6. Równoważenie obciążeń. (9-04-2025 - szkic notatek)
   [Różne modele maszyn: identyczne i różnej prędkości. Algorytmy zachłanne. Algorytm SlowFit.]
7. Bin packing. (16-04-2025 - szkic notatek)
   [Algorytm Next-Fit. Dolna granica na wsp. konkurencyjności. Algorytmy First-Fit i Best-Fit. Ogranicznie liczby pojemników - algorytm Harmonic.]
8. Problem k serwisantów w przestrzeniach metrycznych. (23-04-2025 - szkic notatek)
   [Definicja przestrzeni metrycznej. Problem k-serwisantów - dolne i górne granice. Algorytm na prostej.]
9. Page migration. (30-04-2024 - szkic notatek)
   [Definicja problemu. Algorytm deterministyczny Move-To-Min. Algorytm CoinFlip.]
10. Page migration. Page replication (7-05-2025)
    [Algorytm zrandomizowany Counter dla PM. Algorytm Counter i CoinFlip dla Page Replication.]
11. Page allocation. (14-05-2025)
    [Algorytm Count dla sieci jednostajnych. Algorytm CoinFlip.]

Ćwiczenia

Pierwsze zadania domowe (termin oddania 30 kwietnia na MS Teams)

• Lista nr 1 (12-03-2025)
• Lista nr 2 (26-03-2025)
• Lista nr 3 (9-04-2025)
• Lista nr 4 (23-04-2025)
• Lista nr 5 (30-04-2025)

Laboratorium

• Lista nr 1 (termin oddania: drugie pełne zajęcia)
• Lista nr 2 (termin oddania: trzecie pełne zajęcia)
• Lista nr 3 (termin oddania: czwarte 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 aktywność będzie oceniana również jakość oraz terminowość oddawania przydzielonych na ćwiczeniach zadań.

Na kolokwium jedyną dopuszczalną pomocą naukową jest kartka formatu A4, wyraźnie podpisana. Kolokwium jest oceniane w skali od 0 do 5.5.

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.4 oceny z laboratorium + 0.2 aktywności na ćwiczeniach, zaokrąglonej w górę do najbliższej oceny (2.5 zaokrągla się jednak do 2.0).