Algoritmi Paraleli si Distribuiti · 2014 · Sesiune
- Profesor
- Valentin Cristea
- Anul examenului
- 2014
- Sesiune
- Sesiune
- Serie
- CA
- Grupă
- 334&331
- Adăugat
- 21 ianuarie 2014 de anonim
V1
1. Generali bizantini cu mesaje orale. Schema pentru 3 generali. Pseudocod.
2. Algoritmi pentru intrarea intr-o regiune critica. Se emit mesaje de tip request. Se asteapta primirea merajelor de tip reply de la toti vecinii. Idee si pseudocod.
3. 3.1. Sincronizare si excludere mutuala in Java. Cum functioneaza. Exemplu de cod.
3.2. Algoritmi unda pe topologii inel. Complexitate si pseudocod.
V2
1. Stabilirea topologiei prin mesaje de sondaj cu ecou - cazul general. De ce sunt potriviti algoritmii unda? Idee. Pseudocod. Complexitate. Ce alte variante mai cunoasteti de stabilire a topologiei?
2. Se considera o topologie de procesoare, fiecare continand un numar. Sa se gaseasca o modalitate prin care fiecare procesor cunoaste maximul din retea. Idee si pseudocod(s-a punctat rezolvarea prin mesaje de sondaj cu ecou, in care se transmit numerele in ecouri, iar initiatorul difuzeaza maximul).
3. 3.1. Complexitatea algoritmilor paraleli. Metrici folosite. Exemplificare pe sortarea pe un vector de procesoare(exemplul din curs).
3.2. Terminarea prin algoritmul Huang. Idee, tipuri de mesaje folosite, pseudocod.
V3
1. Algoritm unda - topologie arbore
1.1. Descriere generala, de ce este potrivit algoritmul unda?
1.2. Explicatie algoritm, pseudocod, justificarea corectitudinii, complexitate
1.3. Aplicatie pe un graf dat
2. Se da o matrice de procesoare, fiecare continand un numar. Trebuia scris un algoritm care sa gaseasca regiuni de noduri adiacente ce aveau aceleasi valori, astfel incat la final fiecare nod sa stie din ce regiune face parte.
3. 3.1. Problema producator-consumator cu tampon unitar. Descriere problema, pseudocod, explicatie notatii de sincronizare.
3.2 Modelul Foster
V4
1. Producatori consumatori cu buffer limitat.
1.1 Prezentarea problemei (0.3)
1.2 Algoritmul folosind primitivele P, V (de explicat primitivele) + pseudocod (1.2)
1.3 explicat algoritmul (0.5)
2. Avand un graf cu N noduri, fiecare isi cunoaste vecinii, sa se gaseasca arborele minim de acoperire fara a se calcula topologia. La sfarsitul algoritmului fiecare nod stie care din legaturile cu vecinii sai sunt in arborele minim de acoperire. Idee 0.3 + algoritm 0.7
3. 3.1. LeLann Chang Robert
a) Prezentarea problemei 0.3p
b) pseudocod + explicatii 0.5p
c) calcul complexitate 0.2p
3.2.Sume prefix
1. Generali bizantini cu mesaje orale. Schema pentru 3 generali. Pseudocod.
2. Algoritmi pentru intrarea intr-o regiune critica. Se emit mesaje de tip request. Se asteapta primirea merajelor de tip reply de la toti vecinii. Idee si pseudocod.
3. 3.1. Sincronizare si excludere mutuala in Java. Cum functioneaza. Exemplu de cod.
3.2. Algoritmi unda pe topologii inel. Complexitate si pseudocod.
V2
1. Stabilirea topologiei prin mesaje de sondaj cu ecou - cazul general. De ce sunt potriviti algoritmii unda? Idee. Pseudocod. Complexitate. Ce alte variante mai cunoasteti de stabilire a topologiei?
2. Se considera o topologie de procesoare, fiecare continand un numar. Sa se gaseasca o modalitate prin care fiecare procesor cunoaste maximul din retea. Idee si pseudocod(s-a punctat rezolvarea prin mesaje de sondaj cu ecou, in care se transmit numerele in ecouri, iar initiatorul difuzeaza maximul).
3. 3.1. Complexitatea algoritmilor paraleli. Metrici folosite. Exemplificare pe sortarea pe un vector de procesoare(exemplul din curs).
3.2. Terminarea prin algoritmul Huang. Idee, tipuri de mesaje folosite, pseudocod.
V3
1. Algoritm unda - topologie arbore
1.1. Descriere generala, de ce este potrivit algoritmul unda?
1.2. Explicatie algoritm, pseudocod, justificarea corectitudinii, complexitate
1.3. Aplicatie pe un graf dat
2. Se da o matrice de procesoare, fiecare continand un numar. Trebuia scris un algoritm care sa gaseasca regiuni de noduri adiacente ce aveau aceleasi valori, astfel incat la final fiecare nod sa stie din ce regiune face parte.
3. 3.1. Problema producator-consumator cu tampon unitar. Descriere problema, pseudocod, explicatie notatii de sincronizare.
3.2 Modelul Foster
V4
1. Producatori consumatori cu buffer limitat.
1.1 Prezentarea problemei (0.3)
1.2 Algoritmul folosind primitivele P, V (de explicat primitivele) + pseudocod (1.2)
1.3 explicat algoritmul (0.5)
2. Avand un graf cu N noduri, fiecare isi cunoaste vecinii, sa se gaseasca arborele minim de acoperire fara a se calcula topologia. La sfarsitul algoritmului fiecare nod stie care din legaturile cu vecinii sai sunt in arborele minim de acoperire. Idee 0.3 + algoritm 0.7
3. 3.1. LeLann Chang Robert
a) Prezentarea problemei 0.3p
b) pseudocod + explicatii 0.5p
c) calcul complexitate 0.2p
3.2.Sume prefix