Algorytmy on-line

TERMIN KOLOKWIUM: 4 czerwca zamiast wykładu (12:00 - 14:00 - można wchodzić do momentu opuszczenia sali przez pierwszą osobę, można wychodzić od 12:30)

NA KOLOKIUM MOŻNA MIEĆ NOTATKI. NIE MOŻNA MIEĆ ŻADNYCH POMOCY ELEKTRONICZNYCH ANI NAWET ELEKTRYCZNYCH.

Zasady zaliczania:

• • kolokwium + ćwiczenia = 70% oceny

    • kolokwium = 0-4 pkt

    • ćwiczenia = 1 pkt za zadanie

    • ocena = 2+pkt/2 (ale min = 3, max = 5)

  • laboratorium = 30% oceny

    • trzy zadania po 5 pkt

    • ocena = 2+pkt/5

  • ale min(kol+ćw, lab) musi być >=dst

Obecność obowiązkowa na lab i ćw, na wykładzie nie

Literatura:

• • A. Borodin, R. El-Yaniv: Online Computation and Competitive Analysis

  • publikacje naukowe

  • wykład Marcina Bieńkowskiego

Listy zadań na ćwiczenia:

1. Lista 1

2. Lista 2

3. Lista 3

4. Lista 4

5. Lista 5

6. Lista 6

7. Lista 7

8. Lista 8

9. Lista 9

UWAGA Od 19 marca zajęcia zaczynamy godzinę wcześniej - ćwiczenia o 11:15, a wykład o 12:15, sala bez zmian. Pracuję nad uaktualnieniem tych danych w edukacji.cl.

Zadania do zrobienia na laboratorium (można programować w grupach 2-3 osobowych, ale żadne dwa zadania z tą samą osobą):

• 1. Do wyboru (z prostą ilustracją graficzną):

     1. spin-block, najlepiej puszczony na danych wyciągniętych z prawdziwego systemu

     2. poszukiwanie krowy - jedno- i dwu-wymiarowe

     3. maksymalne skojarzenie: na przykładzie robotników i maszyn

  2. Cache (bez ilustracji graficznej)

• • 1. wykonanie kilku algorytmów na tych samych danych i wyświetlenie kosztów na końcu

    2. algorytmy: LRU, FIFO, LFU, FWF, LFD (offline)

    3. dane do symulacji: losowe drzewo (nie binarne, większe stopnie) o wybranej wysokości (poniżej k, dokładnie k, powyżej k), na tym drzewie DFS (przechodzenie w głąb)

• 3. Page migration (z prostą ilustracją graficzną)

• • 1. na losowym grafie planarnym, niewielkim, może być kilka grafów wprogramowanych w kod

    2. algorytm deterministyczny i losowy (FLIP oraz Move-To-Min ze skryptu)

    3. obliczenie kosztu algorytmu offline na podstawie "work-functions" czyli dynamicznie dla końca w każdym wierzchołku i najtańszy wyróżniony

    4. zapytania mogą się pojawiać w wierzchołkach losowych, ale dużym plusem będą zapytania przez klikanie