Algorytmy rozproszone

UWAGA

Kolokwium na wykładzie 8 stycznia 2015.

Wykład będzie prowadzony na podstawie wykładu PODC.

UWAGA Pierwsze ćwiczenia i laboratorium zostały zamienione na wykład. W styczniu zrobimy odwrotnie - konkretnie 22 stycznia na wykładzie są ćwiczenia.

Było:

• 1. Vertex coloring

  2. Leader election

  3. Tree algorithms

  4. Sorting networks

  5. Shared memory

  6. Shared objects

  7. Maksimal independent set (MIS)

  8. Social networks

  9. Synchronization

  10. Graphs as networks

  11. Peer-to-Peer Networks

  12. Self-stabilization

  13. Wireless Protocols

  14. Multi-core computing

Laboratorium

Można robić w grupach 2-3 osobowych, ale nie można być dwa razy w grupie z tą samą osobą.

• 1. Zaprogramować symulator do algorytmów na grafach i na nim kolorowanie drzew. Termin: 16 listopada. Symulatora nie trzeba programować od zera, można wykorzystać narzędzia, jakie uda się Państwu znaleźć.

  2. 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.

  3. 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 (wolne i rezerwacje ostatnio uzupełnione po zajęciach 27 listopada)

• 1. Lista 1 zrobione: 1, 2, 3, 4, 5; zarezerwowane: 6

  2. Lista 2 zrobione: 1, 2, 3, 4, 5; wolne: 6

1. Lista 3 zrobione: 1, 2, 3; zarezerw: 4

2. Lista 4 (pół punktu za podpunkt); zrobione: a, b, c, d, e, f, g

3. Lista 4a

   1. Lista 5 zrobione: 1(a,b,c,d)

4. Lista 6 zrobione: 1(a,b), zarezerwowane: 2, wolne: 1c

5. Lista 7 zrobione: 1(a,b), 2a,b,c zarezerwowane: 1c

• 1. Lista 8, zrobione: 1a, 3a,b zarezerwowane: 1bcd, 2

6. Lista 9 zrobione: 1a, rez: 1c, olne: 1bd

7. Lista 10, zrobione: 1, 2

8. Lista 11, wszystkie wolne

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%.