Algoritmi Paraleli si Distribuiti · 2011 · Sesiune
- Profesor
- Valentin Cristea
- Anul examenului
- 2011
- Sesiune
- Sesiune
- Serie
- CA/CB/CC
- Adăugat
- 20 septembrie 2011 de Bogdan Ivanov
Jan 17
S-a dat pe patru numere(V1, V2, V3, V4), postez aici numarul meu:
V3
1. Algoritmi unda: arbore
a) Explicatia alegerii algoritmului unda. Descrierea algoritmului.
(0.5p)
b) Descrierea algoritmului in pseudocod. Justificarea corectitudinii.
Complexitate. (1.1p)
c) Era un desen langa enunt. Se cerea aplicarea algoritmului pe acel
desen (desen identic cu cel din notitele de curs). (0.4p)
2. Etichetarea regiunilor
Se da un tablout[1:n,1:n] cu valoarea inte pixelului respectiv. Sa se
descrie un algoritm heartbeat care eticheteaza regiunile cu
intensitati egale.
Descriere = 0.3p
Pseudocod = 0.7p
3.1 Modelul work-depth
- nu am retinut defalcarea
- Trebuia să zici ceva despre modelul respectiv și complexitate și să
exemplifici printr-un algoritm de calculare a sumei elementelor unui
vector. Ceva de genul.
3.2 Hirschberg-Sinclair:
- Descriere 0.3 p
- Pseducod 0.4p
- Complexitate 0.3p
----------------------------------------------------------------------
Numarul meu,varianta 4:
1.1. Problema producatori-consumatori. Descriere.
1.2. De explicat primitivele P siV cu notatiile de atomicitate si sincronizare.
1.3. Pseudocod cu comentarii
2. De aflat un arbore de acoperire fara a afla mai intai topologia (un fel de sonda-ecou zic eu...) .
3. 1. Complexitate: numar de mesaje. Descriere si aplicatie pe algoritmul pulsatiilor.
la alegere cu:
3.2 Problema produs prefix ,implementare SIMD si MIMD si de explicat diferentele intre ele.
---------------------------------------------------------------------
Varianta 2:
1. Comunicari sincrone si asincrone prin mesaje
a) Prezentarea generala a problemei. Cum se realizeaza partajarea datelor? Cum se realizeaza sincronizarea? (0.5p)
b) Constructii pseudocod pt transmitere sincrona si asincrona. Exemple (1p)
c) Cum se reprezinta transmiterea sincrona si asincrona a mesajului in MPI. (0.5p)
2. Se dau doua seturi S si T cu valori intregi. La fiecare pas, se interschimba o valoare din S cu una din T. Descrieti (0.3p) si scrieti (0.7p) algoritmul astfel incat, la final, valorile din S sa fie mai mari decat orice valoare din T.
3.1 Algoritmul de detectare a terminarii folosind confirmarile mesajelor - Dijkstra-Scholten.
a) Descrierea problemei (0.3p)
b) Pseudocod (0.4p)
c) Complexitate (0.3p)
3.2 Algoritmul lui Finn.
a) Descrierea algoritmului (0.3p)
b) Pseudocod (0.4p)
c) Complexitate (0.3p)
--------------------------------------------------------------------------
Iata si ultima varianta (1) :)
1. Problema generalilor bizantini
a) Prezentarea generala a problemei (0.5 p)
b) Prezentarea solutiei ce foloseste mesaje orale (aici cerea cam tot : teoreme, pseudocod, demonstratie ca algoritmul functioneaza, etc. 1.2 p)
c) De reprezentat grafic problema generalilor pentru 3 generali (unul din locotenenti, la alegere, era neloial) (0.3 p)
2. Se dau n numere si o secventa de n procesoare organizate in linie de asamblare (de fapt se dorea o structura vectoriala). Prezenta functionarea algoritmului:
P[0] are toate cele n numere, pastreaza valoarea cea mai mica si trimite mai departe restul numerelor lui P[1]. Procesul se repeta pana cand la procesorul P[n] ajungea ultima variabila (cea mai mica valoarea).
Cerinte :
2.1 Prezentarea solutiei (care, paradoxal, era prezenta in enunt :D - mi s-a spus sa fac un desen, sa detaliez putin pe pasi) (0.5 sau 0.3 p)
2.2 Implementarea algoritmului in limbaj pseudocod
3.1 Complexitatea algoritmilor paraleli.
a) Metrici
b) Exemplificare pe sortarea unui vector, folosind o structura de N procesoare
3.2 Huang
Explicarea mesajelor, a modului de functionare, pseudocod (Nu am citit cu mare atentie)
----------------------------------------------------------------------------
S-a dat pe patru numere(V1, V2, V3, V4), postez aici numarul meu:
V3
1. Algoritmi unda: arbore
a) Explicatia alegerii algoritmului unda. Descrierea algoritmului.
(0.5p)
b) Descrierea algoritmului in pseudocod. Justificarea corectitudinii.
Complexitate. (1.1p)
c) Era un desen langa enunt. Se cerea aplicarea algoritmului pe acel
desen (desen identic cu cel din notitele de curs). (0.4p)
2. Etichetarea regiunilor
Se da un tablout[1:n,1:n] cu valoarea inte pixelului respectiv. Sa se
descrie un algoritm heartbeat care eticheteaza regiunile cu
intensitati egale.
Descriere = 0.3p
Pseudocod = 0.7p
3.1 Modelul work-depth
- nu am retinut defalcarea
- Trebuia să zici ceva despre modelul respectiv și complexitate și să
exemplifici printr-un algoritm de calculare a sumei elementelor unui
vector. Ceva de genul.
3.2 Hirschberg-Sinclair:
- Descriere 0.3 p
- Pseducod 0.4p
- Complexitate 0.3p
----------------------------------------------------------------------
Numarul meu,varianta 4:
1.1. Problema producatori-consumatori. Descriere.
1.2. De explicat primitivele P siV cu notatiile de atomicitate si sincronizare.
1.3. Pseudocod cu comentarii
2. De aflat un arbore de acoperire fara a afla mai intai topologia (un fel de sonda-ecou zic eu...) .
3. 1. Complexitate: numar de mesaje. Descriere si aplicatie pe algoritmul pulsatiilor.
la alegere cu:
3.2 Problema produs prefix ,implementare SIMD si MIMD si de explicat diferentele intre ele.
---------------------------------------------------------------------
Varianta 2:
1. Comunicari sincrone si asincrone prin mesaje
a) Prezentarea generala a problemei. Cum se realizeaza partajarea datelor? Cum se realizeaza sincronizarea? (0.5p)
b) Constructii pseudocod pt transmitere sincrona si asincrona. Exemple (1p)
c) Cum se reprezinta transmiterea sincrona si asincrona a mesajului in MPI. (0.5p)
2. Se dau doua seturi S si T cu valori intregi. La fiecare pas, se interschimba o valoare din S cu una din T. Descrieti (0.3p) si scrieti (0.7p) algoritmul astfel incat, la final, valorile din S sa fie mai mari decat orice valoare din T.
3.1 Algoritmul de detectare a terminarii folosind confirmarile mesajelor - Dijkstra-Scholten.
a) Descrierea problemei (0.3p)
b) Pseudocod (0.4p)
c) Complexitate (0.3p)
3.2 Algoritmul lui Finn.
a) Descrierea algoritmului (0.3p)
b) Pseudocod (0.4p)
c) Complexitate (0.3p)
--------------------------------------------------------------------------
Iata si ultima varianta (1) :)
1. Problema generalilor bizantini
a) Prezentarea generala a problemei (0.5 p)
b) Prezentarea solutiei ce foloseste mesaje orale (aici cerea cam tot : teoreme, pseudocod, demonstratie ca algoritmul functioneaza, etc. 1.2 p)
c) De reprezentat grafic problema generalilor pentru 3 generali (unul din locotenenti, la alegere, era neloial) (0.3 p)
2. Se dau n numere si o secventa de n procesoare organizate in linie de asamblare (de fapt se dorea o structura vectoriala). Prezenta functionarea algoritmului:
P[0] are toate cele n numere, pastreaza valoarea cea mai mica si trimite mai departe restul numerelor lui P[1]. Procesul se repeta pana cand la procesorul P[n] ajungea ultima variabila (cea mai mica valoarea).
Cerinte :
2.1 Prezentarea solutiei (care, paradoxal, era prezenta in enunt :D - mi s-a spus sa fac un desen, sa detaliez putin pe pasi) (0.5 sau 0.3 p)
2.2 Implementarea algoritmului in limbaj pseudocod
3.1 Complexitatea algoritmilor paraleli.
a) Metrici
b) Exemplificare pe sortarea unui vector, folosind o structura de N procesoare
3.2 Huang
Explicarea mesajelor, a modului de functionare, pseudocod (Nu am citit cu mare atentie)
----------------------------------------------------------------------------