AAL260 - ćw - temat C1

Najkrótsze ścieżki

Zadanie 40 "BFS"
Zaimplementuj algorytm przeszukiwania grafu "wszerz" (BSF) + wizualizacja przy pomocy grdraw01.

Zadanie 41 "algorytm Dijkstry"
Dla digrafu z wagami na krawędziach (>=0) zaimplementuj algorytm Dijkstry
znajdujący najkrótsze ścieżki skierowane od źródła "s" do wszystkich innych (osiągalnych) wierzchołków;
jako kolejki priorytetowej użyj zwykłej tablicy;
+ wizualizacja przy pomocy grdraw01.
(patrz też wiki.tcl.tk/22393)

Zadanie 42 "algorytm Dijkstry + kopiec Fib."
Tym razem jako kolejki priorytetowej użyj kopca Fibonacciego;
zademonstruj wyższość tej implementacji nad impl. z poprzedniego zadania
dla grafów rzadkich!

Algorytmy rozproszone

Obecnie zajmujemy się algorytmami w modelu obliczeń:
  * z przesyłaniem komunikatów
  * synchronicznym (obliczania to ciąg rund ...)

Symulator algorytmów rozproszonych: symul.tar.gz;
poręczny, windowsowy interp tcl-a: tclkit-win32.upx.exe;
przyklady aal260_*.tcl nalezy uruchamiac w konsola2c (załączona w zip-ie);
trzeba uruchomic fragment kodu od początku do zaznaczonego miejsca,
a następnie wielokrotnie uruchamiać linię kodu wykonującą pojedynczą runde;
można zaglądać do zmiennych/ procedur danego wierzchołka
przy pomocy fiber$nr eval {...kod...};

Zadanie 50 "C&V (8 kolorów)"
Zaimplementuj w symulatorze algorytm C&V
znajdujący 8-kolorowanie wierzchołkowe drzewa ukorzenionego.

Zadanie 51 "C&V (3 kolory)"
Dodaj ulepszenie do algorytmu z poprzedniego zadania,
dzięki któremu otrzymujemy 3-kolorowanie wierzchołkowe
(+ implementacja w symulatorze).

Zadanie 52 "kolorowanie grafu stałego stopnia"
Zaimplementuj w symulatorze algorytm kolorujący wierzchołkowo
grafy stałego stopnia (działający w czasie O(log^*n));
wypróbuj go dla kraty ...

Zadanie 53 "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))!!!
(+ implementacja w symulatorze).