Algorytmy OnLine 2023

Środa 9¹⁵ - 11⁰⁰ C-16/D3.1 wykład

Poniedziałek 17⁰⁵ - 18⁴⁵ C-16/D1.2 TP ćwiczenia

Poniedziałek 15¹⁵ - 16⁵⁵ D-1/317.2 TN/TP laboratorium (mgr inż. Marcel Jackiewicz)

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. (01-03-2023)
   [Podstawowe pojęcia - współczynnik konkurencyjności. Problem wypożyczania nart; Problem szukania krowy.]
2. Samoorganizujące się listy. (08-03-2023)
   [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. (15-03-2023)
   [Średni przypadek dla list. Algorytmy zrandomizowane Bit i TimeStamp(p). Drzewa Splay.]
4. Paging problem. (22-03-2023)
   [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. (29-03-2023)
   [Randomized Marking Algorithm. Oczekiwany współczynnik konkurencyjności RMA. Dolna granica na algorytmy losowe.]
6. Równoważenie obciążeń. (5-04-2023)
   [Różne modele maszyn: identyczne, różnej prędkości, ograniczone i dowolne. Algorytmy zachłanne. Algorytm SlowFit.]
7. Bin packing. (12-04-2023)
   [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. (19-04-2023)
   [Definicja przestrzeni metrycznej. Problem k-serwisantów - dolne i górne granice. Problem na prostej.]
9. Page migration. (26-04-2023)
   [Definicja problemu. Algorytm deterministyczny Move-To-Min. Algorytm Flip.]
10. Page migration. Page replication (10-05-2023)
    [Algorytm zrandomizowany Counter dla PM. Algorytm Counter i Flip dla Page Replication.]
11. Page allocation. (17-05-2023)
    [Algorytm Count dla sieci jednostajnych. Algorytm Coin-Flip.]
12. Zrandomizowane algorytmy online - Yao's Principle. (24-05-2023)
    [Yao's Principle zastosowane do dolnych granic algorytmów zrandomizowanych. Dolna granica na zrandomizowany algorytm wypożyczania nart.]
13. Kolorowanie grafów dwudzielnych. (31-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. (07-06-2023)
    []
15. Kolokwium. (14-06-2023)
    []

Ćwiczenia

Pierwsze zadania domowe (termin oddania 15 maja)

Drugie zadania domowe (termin oddania 21 czerwca)

• 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: trzecie 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)
• Lista dodatkowa (nieobowiązkowa) (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 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.

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).