Algoritmi Paraleli si Distribuiti · 2014 · Sesiune

Varianta 2

Subiectul 1. Algoritmul de alegere a liderului Hirchberg-Sinclair (2p)

a) Descrierea generala a problemei (0.3p)

b) Descrierea algoritmului si a primitivelor sale (0.4p)

c) Scrierea algorimtului in pseudocod (0.8p)

d) Specificarea complexitatii in numar de mesaje si timp cu justificarea rezultatelor (0.5p)

Subiectul 2. Problema (1p)

Se da o retea de procese sub forma unui graf. Fiecare proces poate comunica doar cu vecinii sai. Fiecare proces dispune de doua valori: una minima - v1 si una maxima - v2. Se cere sa se scrie un algoritm prin care fiecare proces sa ajunga la final sa cunoasca minimul si maximul celor 2n valori.

Subiectul 3. De ales intre:

3.1 Calcul paralel de inmultire a doua matrici

a) Ce operatii pot fi realizate in paralel? (0.3p)

b) Scrieti pseudocodul pentru calculul paralel de inmultire a doua matrici. (0.7p)

3.2 Complexitatea algoritmilor distribuiti

a) Descrieti modelul Foster

b) Scrieti formula pentru n procese a timpului

c) Explicati care este particularitatea modelului