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:
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ą):
Do wyboru (z prostą ilustracją graficzną):
spin-block, najlepiej puszczony na danych wyciągniętych z prawdziwego systemu
poszukiwanie krowy - jedno- i dwu-wymiarowe
maksymalne skojarzenie: na przykładzie robotników i maszyn
Cache (bez ilustracji graficznej)
wykonanie kilku algorytmów na tych samych danych i wyświetlenie kosztów na końcu
algorytmy: LRU, FIFO, LFU, FWF, LFD (offline)
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)
Page migration (z prostą ilustracją graficzną)
na losowym grafie planarnym, niewielkim, może być kilka grafów wprogramowanych w kod
algorytm deterministyczny i losowy (FLIP oraz Move-To-Min ze skryptu)
obliczenie kosztu algorytmu offline na podstawie "work-functions" czyli dynamicznie dla końca w każdym wierzchołku i najtańszy wyróżniony
zapytania mogą się pojawiać w wierzchołkach losowych, ale dużym plusem będą zapytania przez klikanie