Algorytmy OnLine 2018

Czwartek 7³⁰ - 9⁰⁰ D-1/312B wykład

Piątek 15¹⁵ - 16⁵⁵ TN/TP D-1/312B ćwiczenia

Czwartek 9¹⁵ - 11⁰⁰ TN D-20/305 laboratorium

Czwartek 11¹⁵ - 13⁰⁰ TN/TP D-20/305 laboratorium

Literatura

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

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

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

Ćwiczenia

• Lista nr 1 (notatki do zadania 3)
• Lista nr 2
• Lista nr 3
• Lista nr 4
• Lista nr 5
• Lista nr 6
• Lista nr 7

Laboratorium

• Lista nr 1 (termin oddania przed 19 marca)
• Lista nr 2 (termin oddania przed 21 kwietnia)
• Lista nr 3 (termin oddania przed 26 maja)
• Lista nr 4 (termin oddania przed 16 czerwca)

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.

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 prowadzący ćwiczenia. Oddanie zadań na następnych ćwiczeniach (pierwszych po tych na których zadanie zostało wykonane przy tablicy) jest traktowane jako aktywność.

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