Wszystkie zajęcia odbywają się normalnie, również laboratoria i ćwiczenia przed pierwszym wykładem.
Zajęcia grupy bezpieczeństwowej będą się odbywać w tygodniach nieparzystych w środę w godzinach 9 - 11 w sali D1.215, ale jeszcze 2go października są normalnie przez godzinę o 9:15.
Wykład będzie prowadzony na podstawie wykładu PODC.
Było:
Vertex coloring
Leader election
Tree algorithms
Distributed sorting
Shared memory
Maximal Independent Set
Social Networks
Small Worlds + Quicksort randomized analysis
Self-* (especially self-stabilization)
Shared objects
Radio networks (aka wireless communication)
Peer-to-peer
Dynamic networks
Multicore computing
Laboratorium
Można robić w grupach 2-3 osobowych.
Zaprogramować symulator do algorytmów na grafach i na nim kolorowanie drzew. Termin: 15 listopadaSymulatora nie trzeba programować od zera, można wykorzystać narzędzia, jakie uda Wam się znaleźć.
Zaprogramować, w symulatorze, przetestować i porównać dwa algorytmy liczenia MIS. Użyć obu do kolorowania grafu na d+1 kolorów, gdzie d to maksymalny stopień wierzchołka. Termin: 31 grudnia.
Zaprogramować grę w życie Conwaya w sposób asynchroniczny. Wierzchołek może przejść do rundy i+1, jeśli on i wszyscy jego sąsiedzi są w rundzie przynajmniej i. Komórki powinny być kolorowane w zależności od numeru rundy (jakaś skala szarości zamiast czarno-białego obrazu). Co się stanie, jeśli któryś wierzchołek będzie kilka razy szybszy od innych? A co, jeśli któryś będzie kilka razy wolniejszy? Termin: 31 stycznia, ale lepiej wcześniej.
Ćwiczenia
New Ja mogę omówić wszystkie zadania na ćwiczeniach, ale: jeśli ktoś (nie mający / mający ułamek) zgłosi się do jakiegoś zadania z kolokwium, może dostać za nie punkt. Za zadanie 4 są dwa punkty: a) za pokazanie, jak pokolorować graf o stałym stopniu, b) za pokazanie jak za pomocą poprzedniego pokolorować graf planarny. W sprawie zadania 4 proponuję się ze mną skonsultować przed ćwiczeniami. Link z zadaniami z kolokwium poniżej.
ZASADY ZALICZANIA:
Suma punktów (z kolokwium i ćwiczeń):
6 => bdb
5 => db+
4 => db
3 => dst+
2 => dst
Laboratorium: dst, db, bdb przy oddanych 1, 2, 3 kodach.
Ważenie: ćwiczenia i kolokwium: 70%, lab: 30%.