Algorytmy OnLine 2025

Środa 13¹⁵ - 15⁰⁰ C-4/34 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)
   [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)
   [Średni przypadek dla list. Algorytmy zrandomizowane Bit i TimeStamp(p). Drzewa Splay.]

Ćwiczenia

• Lista nr 1

Laboratorium

• Lista nr 1 (termin oddania: drugie 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).