Algoritmi Paraleli si Distribuiti · 2011 · Sesiune
- Profesor
- Valentin Cristea
- Anul examenului
- 2011
- Sesiune
- Sesiune
- Serie
- CB
- Grupă
- 331
- Adăugat
- 20 septembrie 2011 de Bogdan Ivanov
Subiecte examen APD 22ian seria CB
Varianta A (tot de azi)
1. Detectia terminarii in procesele distribuite
1. Enuntarea problemei. Algortimul de terminare pentru o topologie inel.
2. Algortimii Dikstra-Scholten si Huang. Descriere. Pseudocod.
3. Fie algoritmul de detectie terminare, folosind culori si jetoane: (se dadea un pseudocod pentru un proces...).
Sa se determine daca algortimul este corect. Daca da, sa se determine si sa se explice conditia de terimnare.
Daca nu, sa se justifice de ce si sa se spuna ce imbunatatiri se pot aduce pentru a face algortimul corect.
2. Consideram o topologie dinamica de procese, in care dorim stabilirea topologiei.
Nodurile pot “pica” in timpul algoritmului de aflare topologie. Un nod picat face ca toate legaturile sale sa pice, iar un mesaj trimis pe o legatura picata este pierdut fara a se primi avertisment. Sa se determine daca algortimul clasic cu sondaj-ecou da rezultate corecte pentru o astfel de topologie dinamica. Daca da, sa se scrie algoritmul sau partea relevanta din acesta care face ca rezultatele obtinute sa fie corecte si in acest caz. Daca nu, sa se stabileasca un algoritm imbunatatit de aflare a topologiei.
3. 1. Cautarea paralela
a) Descrierea problemei
b) Algoritm (descriere + pseudocod)
c) Complexitate
(sau) 2. Algoritmul pulsatiilor
a) Varianta pentru un diametru D al retelei; b) Varianta pentru o retea conexa.
----------------------------------------------------------------------
Varianta B
1. problema generalilor bizantini
- descrierea problememei
- de toata: conditii de consistenta interactiva
- solutia cu mesaje scrise: conditii, descriere, pseudocod, teorema care dem corectitudinea
- un exemplu practic
2. o problema cu etichetare zonelor, banuiesc ca ai auzit de ea
3. 3.1 sa scrie suma prefix atat ca SIMD cat si ca MIMD
3.2 problema terminarii
- descrierea problemei
- algoritmul Dijkstra - Scholten
- complexitate
------------------------------------------------------------------------------
Varianta C
1. problema generalilor bizantini
- descriere, consistenta interactia, solutia cu mesaje orale, un exemplu practic
2. sa explicam daca merge si in cazul in care nu merge, cum am modifica algoritmul de stabilire a topologiei sondaj-ecou pentru un graf care are topologie dinamica (unele noduri pot sa pice si pot sa revina)
3. 3.1 producator consumator cu buffer limitat, cazul simplu si cazul cu mai multi producatori + consumatori (parca asa suna)
3.2 Lelann-Chang-Roberts
-------------------------------------------------------------------------
Varianta D
1. stabilire topologie
1.1 prezentare
1.2. ambii algoritmi pseudocod + explicatii
1.3. de executat pe un graf
2. o problema cu etichete dar schimbata cumva urat...
3. algoritmi genetici
sau
3. modelul foster (cel pe care e facut algoritmul floyd)
Varianta A (tot de azi)
1. Detectia terminarii in procesele distribuite
1. Enuntarea problemei. Algortimul de terminare pentru o topologie inel.
2. Algortimii Dikstra-Scholten si Huang. Descriere. Pseudocod.
3. Fie algoritmul de detectie terminare, folosind culori si jetoane: (se dadea un pseudocod pentru un proces...).
Sa se determine daca algortimul este corect. Daca da, sa se determine si sa se explice conditia de terimnare.
Daca nu, sa se justifice de ce si sa se spuna ce imbunatatiri se pot aduce pentru a face algortimul corect.
2. Consideram o topologie dinamica de procese, in care dorim stabilirea topologiei.
Nodurile pot “pica” in timpul algoritmului de aflare topologie. Un nod picat face ca toate legaturile sale sa pice, iar un mesaj trimis pe o legatura picata este pierdut fara a se primi avertisment. Sa se determine daca algortimul clasic cu sondaj-ecou da rezultate corecte pentru o astfel de topologie dinamica. Daca da, sa se scrie algoritmul sau partea relevanta din acesta care face ca rezultatele obtinute sa fie corecte si in acest caz. Daca nu, sa se stabileasca un algoritm imbunatatit de aflare a topologiei.
3. 1. Cautarea paralela
a) Descrierea problemei
b) Algoritm (descriere + pseudocod)
c) Complexitate
(sau) 2. Algoritmul pulsatiilor
a) Varianta pentru un diametru D al retelei; b) Varianta pentru o retea conexa.
----------------------------------------------------------------------
Varianta B
1. problema generalilor bizantini
- descrierea problememei
- de toata: conditii de consistenta interactiva
- solutia cu mesaje scrise: conditii, descriere, pseudocod, teorema care dem corectitudinea
- un exemplu practic
2. o problema cu etichetare zonelor, banuiesc ca ai auzit de ea
3. 3.1 sa scrie suma prefix atat ca SIMD cat si ca MIMD
3.2 problema terminarii
- descrierea problemei
- algoritmul Dijkstra - Scholten
- complexitate
------------------------------------------------------------------------------
Varianta C
1. problema generalilor bizantini
- descriere, consistenta interactia, solutia cu mesaje orale, un exemplu practic
2. sa explicam daca merge si in cazul in care nu merge, cum am modifica algoritmul de stabilire a topologiei sondaj-ecou pentru un graf care are topologie dinamica (unele noduri pot sa pice si pot sa revina)
3. 3.1 producator consumator cu buffer limitat, cazul simplu si cazul cu mai multi producatori + consumatori (parca asa suna)
3.2 Lelann-Chang-Roberts
-------------------------------------------------------------------------
Varianta D
1. stabilire topologie
1.1 prezentare
1.2. ambii algoritmi pseudocod + explicatii
1.3. de executat pe un graf
2. o problema cu etichete dar schimbata cumva urat...
3. algoritmi genetici
sau
3. modelul foster (cel pe care e facut algoritmul floyd)