Oferta dydaktyczna Instytutu Informatyki

Poniższa lista przedstawia przedmioty, które są uczone w Instytucie Informatyki, niektóre z nich co roku, niektóre z mniejszą częstotliwością Każdy student Instytutu Informatyki studiuje wg indywidualnego toku studiów, wybierając (zgodnie z pewnymi zasadami) z tej listy swoje przedmioty.

Jeżeli zastanawiasz się nad studiami u nas, jeżeli chcesz wiedzieć, czy na Uniwersytecie można zostać inżynierem, jeżeli interesuje Cię 1000 zł stypendium miesięcznie - zapraszamy na naszą stronę główną

Algorytmy online

Nazwa angielska (title in English): Online algorithms
Prowadzący (lecturer): Marcin Bieńkowski
Liczba punktów (ECTS): 9
Liczba punktów 2007 (ECTS since 2007): 6
Rodzaj (type): zaawansowany
Rodzaj od 2007 (type since 2007): informatyczny.I2
Liczba godzin (hours in semester):
wykład:30
ćwiczenia:30
Egzamin (exam): tak
Możliwe zajęcia w języku angielskim (can be taught in English): nie
Przedmiot zostal uaktualniony na biezacy rok (updated): nie
Semestr (semester): zimowy

Wymagania (prerequisites)

Opis (description)

W przypadku niektórych rzeczywistych zagadnień, takich jak np. routing w sieciach, pamięć podręczna procesorów, buforowanie danych w internecie (web caching), czy szeregowanie zadan (scheduling), algorytm je rozwiazujacy musi działać w sposób online i dokonywać decyzji bez wiedzy lub z częściową wiedzą o przyszłości. Tematem wykładu będą takie właśnie zagadnienia i ich analiza.

Podobnie jak w przypadku algorytmów aproksymacyjnych, interesować nas będą rozwiązania przybliżone. Pokażemy, jak dowodzić konkretnych gwarancji o jakości takich przybliżeń.

Wykład prowadzony będzie w oparciu o podane poniżej książki, aktualne prace naukowe i o materiały z podobnych wykładów prowadzonych na innych uniwersytetach na świecie.

Program (program)

  1. Wstęp do algorytmów online. Problem wypożyczania nart (Ski Rental Problem), jako przykład problemu "wypożyczyć czy kupić" (rent-or-buy), analiza konkurencyjności (competitive analysis), k-konkurencyjność.
  2. Analiza zamortyzowana i funkcje potencjału w przykładach.
  3. Wyszukiwanie obiektów: poszukiwanie krowy i brzegu oceanu.
  4. Algorytmy stronicowania (paging) czyli np. zarządzania pamięcią podręczną procesora. Analiza algorytmów LRU (Least-Recently-Used) i FIFO (First-In-First-Out). Zrandomizowane algorytmy stronicowania, algorytm "Random Marking".
  5. Problem uaktualniania list (List Update). Algorytmy Move-to-Front, BIT i Timestamp.
  6. Porównanie adwersarzy adaptujących się i nieświadomych (oblivious). Zasada min-max Yao do dowodzenia dolnych ograniczeń.
  7. Problemy replikacji i migracji danych w sieciach (Page Migration, Page Replication, File Allocation). Technika work-functions.
  8. Problem k-server. Przykładowe algorytmy. Hipoteza k-server.
  9. Algorytmy szeregowania zadań (scheduling), identyczne maszyny (algorytm Grahama), nieidentyczne maszyny.
  10. Algorytmy finansowe, zamiana walut.

Literatura (references)

Jeżeli jesteś zainteresowany studiowaniem w naszym instytucie, zapraszamy na stronę poświęconą tegorocznej rekrutacji.

Nazwa użytkownika (user name):
Hasło (password):