8 października

Wykład 1. Wstęp do algorytmów online: konkurencyjność, przykładowe problemy i algorytmy online: wypożyczanie nart, spin-block, eksploracja prostej, pakowanie pojemników.

• A. Borodin, R. El-Yaniv: Online Computation and Competitive Analysis. Cambridge University Press, 1998
• R. Karp: On-line algorithms versus off-line algorithms: How much is it worth to know the future? IFIP World Computer Congress, 1992
• A. Karlin, M. Manasse, L. McGeoch, S. Owicki: Competitive Randomized Algorithms for Non-Uniform Problems, Algorithmica, 1994
• R. Baeza-Yates, J. Culberson, G. Rawlins: Searching in the plane. Information and Computation, 1993
  
  

Brak ćwiczeń w tym dniu.