Algorytmy Rozproszone

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:

• 1. Vertex coloring

  2. Leader election

  3. Tree algorithms

  4. Distributed sorting

  5. Shared memory

  6. Maximal Independent Set

  7. Social Networks

  8. Small Worlds + Quicksort randomized analysis

  9. Self-* (especially self-stabilization)

  10. Shared objects

  11. Radio networks (aka wireless communication)

  12. Peer-to-peer

  13. Dynamic networks

  14. Multicore computing

Laboratorium

Można robić w grupach 2-3 osobowych.

• 1. 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źć.

  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

1. Lista 1

2. Lista 2

3. Lista 3

4. Lista 4, dodatek do listy 4

5. Lista 5

6. Lista 6

7. Lista 7

8. Lista 8

9. Lista 9

10. Lista 10

11. Lista 11

12. Lista 12

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