ALR - ćw - temat A

symulator algorytmów (wszystko co potrzebne)

Zadania

UWAGA: zadania są oznaczone następująco:
(imlp.) zadanie wymaga implementacji w symulatorze
(inż.) zadanie "inżynieryjnej" natury
(*) zadnie trudniejsze, nadające się na mini-referat

Zadanie 0.1 (inż.)(0.5pkt) "polecenie fiber"
Zbadaj w konsola2c, jak działa polecenie fiber,
będące podstawą "symulatora algorytmów rozproszonych" używanego na tych zajęciach...
użyj przykładów: events03.tcl, events03a.tcl

Zadanie 0.2 (impl.)(0.5pkt) "pierwszy test symulatora"
Spróbuj uruchomic w konsoli (konsola2c.tcl)
pierwszy z brzegu przykład z tutoriala symulatora...

Zadanie 1 (impl.) "leader election O(n^2)"
Zaimplementuj w symulatorze algorytm asynchroniczny wyboru lidera,
uzywający O(n^2) komunikatów, dla ringu zorientowanego.
Uwaga: uzyj symulatora algorytmow synchronicznych, mimo że
algorytm jest asynchroniczny! (początkowo tak będziemy postępować stale).
Wszystkie wierzchołki muszą wiedzieć czy są liderami czy nie!

Zadanie 1a (impl.) "leader election O(n^2)"
Zaimplementuj w symulatorze algorytm asynchroniczny wyboru lidera
uzywający O(n^2) komunikatów, dla ringu NIEzorientowanego.
Podobnie jak poprzednio wierz muszą wiedzieć czy są liderami czy nie.

Zadanie 1b (impl.)(1.5pkt) "leader election O(n^2), 2 liderów"
Problem jak w zadaniu 1, ale ma być 2 liderów !

Zadanie 2 (impl.)(1.5pkt) "C&V (8 kolorów)"
Zaimplementuj w symulatorze algorytm synchroniczny C&V
znajdujący 8-kolorowanie wierzchołkowe drzewa ukorzenionego
przydatne procedury do operacji na bitach znajdziesz tutaj

# kod sprawdzający ile jest różnych kolorów w zm. Cv (glob. w fiberach):
set _ {}; iterate i $liczbaWierz {lappend _ [fiber_eval $i {set Cv}]}
llength [lsort -unique $_]

# reset fiberow i zmiana id_los w fiberach:
set_run 0; fiber yield; set_run 1; fiber restart
fiber_iterate {set id_los [expr round(rand()*10000)]}

# sprawdzamy jaka liczbę kolorów dają różne id_los-y:
set_run 0; fiber yield; set_run 1; fiber restart
fiber_iterate {set id_los [expr round(rand()*10000)]}
iterate i 10 {fiber yield; runda}; # 10 rund wystarczy do wszystkiego...
set _ {}; iterate i $liczbaWierz {lappend _ [fiber_eval $i {set Cv}]}
llength [lsort -unique $_]

# obliczanie długości ciągu bitów z kolorem
set L [expr {int(ceil(log($L)/log(2)) + 1)}]

Zadanie 0.3 (impl.)(0.5pkt) "wizualizacja drzewa i 2-kol-kraw nieprawidł."
Używając tych narzędzi, pokaż jak wizualizować
losowe 2-kolorowanie krawędziowe nieprawidłowe,
przy użyciu kolorów czerwony i żółty, drzewa losowego na 50 wierz;
kraw powinny mieć grubość 5;
Wskazówki: poszukaj przykładu z "-width"; użyj "array name tc_edge" aby odwołać się do wsz. kraw

Zadanie 3 (impl.)(6pkt) "leader election O(n logn)"
Zaimplementuj w symulatorze algorytm asynchroniczny wyboru lidera,
uzywający O(n logn) komunikatów, dla ringu zorientowanego.
Podobnie jak poprzednio użyj symulatora synchronicznego! (przyklad)

Zadanie 4 (impl.)(1.5pkt) "C&V (3 kolory)"
Dodaj ulepszenie do algorytmu z zadania "C&V (8 kolorów)",
dzięki któremu otrzymujemy 3-kolorowanie wierzchołkowe;
podaj także dowód, że istotnie otrzymamy 3 kolory.
Algorytm ma nadal działać w czasie O(log^*n).

Zadanie 5 "kolorowanie grafu stałego stopnia"
Wymyśl algorytm kolorujący wierzchołkowo, stałą liczbą kolorów, grafy stałego stopnia,
działający w czasie O(log^*n) ...
... niech to NIE będzie algorytm opisywany na wykladzie, a jedynie
proste rozszerzenie algorytmu C&V ...
Proszę opisać algorytm naturalnym językiem!
Wskazówka: na początek spróbuj opisać algorytm znajdujący kolorowanie ringu (niezorientowanego)
podobny do alg. C&V dla drzew ukorzenionych.

Zadanie 5a (impl.)(2pkt) "kolorowanie ringu"
Zaimplementuj algortym z zadania 5 dla ringu (=cyklu).
Być może trochę się uprości w porównaniu z 5 !!.
Ma to być algorytm znajdujący 3-kolorowanie wierzchołkowe w "kilku" rundach...
ring jest NIEzorientowany w tym zadaniu !!!
Wskazówka: zastanów się jak ogólny algorytm C&V działa dla cyklu (Delta==2)

Zadanie 6 (impl.)(*)(6pkt) "skojarzenie w cyklu dwubarwnym"
Wymyśl algorytm rozproszony znajdujący (1-eps) aproksymacje skojarzenia
w cyklu, w którym dane jest 2-kolorowanie wierzchołkowe;
algorytm ten MUSI działać w stalym czasie (O(1/eps))!!!
Wskazówka: aby uzyskać (1-eps) aproksymację wystarczy, że znajdziemy w cyklu
segmenty o długości >1/eps, a w każdym segmencie "prawie doskonałe skojarzenie"
(tj co druga kraw wybrana, jedynie końcowy wierz nieskojarzony...)

Zadanie 7 (impl.)(5pkt) "LE w ringu, synch, jednorodny, O(n) kom."
Zaimplementuj algorytm synch, jednorodny wyboru lidera w ringu, wysyłający O(n) komunikatów.
Wskazówka: Biorąc pod uwagę, że ten algorytm działa w n2^i rundach, gdzie i = min ID,
zamiast id_los generowanych przez symulator lepiej użyc losowej permutacji liczb ze zbioru {0,...,n-1};
pomoc.

Zadanie 8 (impl.)(1.5pkt) "suma ID"
Zaimplementuj algorytmy synchroniczne obliczające sumę ID w ringu (ma być znana na wszystkich wierz!),
   alg 1: wysyłający O(n) komunikatów,
   alg 2: działający w O(n) rundach.
Nie zakłada się niczego szczególnego o ID wierzchołków;
oba algorytmy powinny się konczyć "równocześnie" na wszystkich wierzchołkach;
zakłada się, że ring jest zorientowany, a wierzchołki znają "n".
Jeśli to konieczne to można założyć, że wcześniej uruchomiono algorytm LE
(wtedy jego czas działania/ liczbę komunikatów dodajemy do naszego algorytmu!!)

Zadanie 9a (impl.)
Zaimplementuj algorytm synchroniczny obliczający max i min ID w cyklu zorientowanym;
te liczby mają być znane na wsz wierz po zakończeniu działania;
założenie: jest znany (pojedynczy) lider w cyklu (może to być wierz z id = 0)
algorytm ma używać min. liczby komunikatów
oszacuj także liczbę rund (czyli czas działania alg)
jako ID uzywaj zm id_los

Zadanie 9b (impl.)
Zaimplementuj algorytm synchroniczny obliczający max i min ID w cyklu zorientowanym;
te liczby mają być znane na wsz wierz po zakończeniu działania;
w przeciwieństwie do poprzedniego zadania lider nie jest znany;
algorytm ma używać min. liczby komunikatów

Zadanie 10 (impl.)
Zaimplementuj algorytm synchroniczny obliczający 2-kolorowanie-wierzchołkowe cyklu zorientowanego
tj kolejne wierz powinny mieć kolory: czerwony, niebieski, czerwony, niebieski, ...
(cykl musi mieć parzystą długość)
założenie: jest znany (pojedynczy) lider w cyklu (może to być wierz z id = 0)

Zadanie 11 "LE w ringu, synch, dolne oszacowanie na czas dzialania"
Przypominam, że skrót LE = Leader Election czyli wybór lidera...
Podaj dolne oszacowanie na czas działania algorytmów synchronicznych LE
   + dowód !!!
Nie robi się żadnych założeń co do sposobu używania ID przez te algorytmy;
nie zakłada się, że chodzi tylko o alg. jednorodne;
NIE zakłada się, że nie-liderzy mają znać ID lidera!!

Zadanie 12 (impl.)(1.5pkt) "ściąganie obrazu grafu do wierzchołka"
Dane jest drzewo T.
Zaimplementuj algorytm, w którym pewien wierzchołek (jeden!) drzewa T
"ściąga obraz" całego drzewa...
Algorytm powinien być synchroniczny oraz powinien działać w czasie O(Diam(T)).
Zakładamy, że wierz znają Diam(T).

# użyj pakietu struct::set z tclib, materiały o j. Tcl, tcllib.tar.gz rozpakuj do ./tcllib 
fiber_iterate {lappend auto_path ./tcllib; package re struct::set}
  # ładowanie pakietu we wszystkich fiberach
fiber_eval 0 {struct::set union {1 2 3} {5 6 3}}
  #% 5 1 6 2 3
  # obliczanie sumy zbiorów (test w fiberze nr 0)
# uwaga, 10.10.2017, jest problem z czasem ładowania pkg; patrz rozszerzenie symulatora...

Zadanie 13 (impl.)(1.5pkt) "frakcyjne skojarzenie"
Proszę zaimpl. algorytm obliczający skojarzenie frakcyjne (algorytm M.Fischer),
które jak wiadomo jest 1/4 aproksymacją skojarzenia maximum.
Algorytm proszę wypróbować na grafie "dowolnym" (tzn. niekoniecznie cyklu czy drzewie).
Jak tworzyć wagi krawędzi? patrz wskazówki tutaj.

Zadanie 14 (impl.)(2pkt) "gossiping w kracie"
Kazdy wierzchołek chce poznać ID wszystkich innych wierzchołków w sieci;
zaimplementuj algorytm synchroniczny, który to zapewnia ...
Jest oczywiste, że w tym algorytmie będą wysyłane długie komuniakty
zawierające wiele ID! Postaraj się aby nie przesyłać 2x tej samej informacji!!!
Zbadaj maksymalną długość komunikatu (liczbę ID które on przenosi),
gdy uruchamiamy go w kracie k x k wierzchołków
(algorytm ma być testowany i napisany tylko dla takiej kraty).

# tworzenie kraty k x k
source symul_lib.tcl
set k 3
set liczbaWierz [expr $k*$k]
iterate i $liczbaWierz {set sasiedzi($i) {}}
set k1 [expr $k-1]
proc nr {x y} {global k; expr $x*$k+$y}
iterate x $k1 {
  iterate y $k1 { 
    set i [nr $x $y]; DodajKraw $i [expr {$i+1}]; DodajKraw $i [expr {$i+$k}]
 }
}
iterate x $k1 {
  set i [nr $x $k1]; DodajKraw $i [expr $i+$k]
}
iterate y $k1 {
  set i [nr $k1 $y]; DodajKraw $i [expr $i+1]
}
# pokazujemy efekty...
array get sasiedzi
  #% 8 {5 7} 4 {1 3 5 7} 0 {1 3} 5 {4 2 8} 1 {0 2 4} 6 {3 7} 2 {1 5} 7 {4 6 8} 3 {0 4 6}