Tehnici de Proiectare i Analiz a Algoritmilor - Tema 2008-2009 (ID) Termen de predare: ziua de examen din sesiunea ordinar.

Reguli

1. Algoritmii vor fi descrii n limbajul algoritmic utilizat la curs.

2. Algoritmii vor fi nsoii de explicaiile necesare pentru nelegerea lor. Algoritmii nensoii de comentarii i

explicaii nu vor fi luai n cosiderare la calculul punctajului.

3. Vor fi apreciate claritatea i simplitatea soluiei, corectitudinea, modul de redactare, acurateea

demonstraiilor i calculelor, explicaiile nsoite de exemple.

4. Dac se cere implementarea unor algoritmi, aceasta se va realiza ntr-un limbaj de programare la alegere.

5. Tema va fi prezentat cadrului didactic care conduce seminarul sub forma unui referat scris de mn (lizibil) pe

care se vor meniona numele i prenumele (complet), anul i grupa. Temele redactate nelizibil sau neinteligibil

nu vor fi corectate i vor fi notate cu 0 (zero) puncte. Excepie fac programele ce implementeaz algoritmii

ntr-un limbaj de programare i rezultatele raportate de acestea, care vor fi listate la imprimant i anexate la

referat.

6. Fiecare student va prezenta soluia sa proprie (e vorba de o tem individual i nu de una n echip). Dac se

constat c dou sau mai multe lucrri au fost efectuate n colectiv, atunci acele lucrri vor fi notate cu 0

(zero) puncte.

7. Dac se utilizeaz documentaie suplimentar, atunci aceasta va fi referit n lucrare i se va meniona clar

care idei au fost preluate i care este partea original (proprie) a lucrrii.

8. Tema va fi nsoit de urmtoarea declaraie semnat:

Declar c toate sursele utilizate, inclusiv cele preluate de pe Internet, sunt indicate n lucrare, cu respectarea regulilor de evitare a plagiatului:

- toate fragmentele de text reproduse exact, chiar i n traducere proprie din alt limb, sunt scrise ntre ghilimele i dein referina precis a sursei;

- reformularea n cuvinte proprii a textelor scrise de ctre ali autori deine referina precis;

- codul surs, imagini etc. preluate din proiecte open-source sau alte surse sunt utilizate cu repsectarea drepturilor de autor i dein referine precise;

- rezumarea ideilor altor autori precizeaz referina precis la textul original.

9. n cazul n care consider c e necesar, profesorul corector poate pune ntrebri autorului unei teme pentru

stabilirea nivelului de contribuie proprie.

10. Tema va primi un punctaj cuprins ntre 0 si 40.

Exerciii

Se consider digrafuri ponderate pe arce (D, w), unde D = (V, A) este digraful i w : A R este funcia de pondere care asociaz un numr real fiecrui arc. Peste un astfel de graf se consider urmtoarele operaii:

addEdge(i, j, x) adaug arcul (i, j) cu ponderea x;

removeEdge(i, j) elimin arcul (i, j)

distance(i, j) ntoarce lungimea celui mai scurt drum de la i la j;

path(i, j) ntoarce cel mai scurt drum de la i la j. Se cere:

1. S se proiecteze un algoritm care pentru un arc dat (i, j), decide dac arcul face parte dintr-un drum minim ntors de path(). S se arate corectitudinea algoritmului i s se calculeze timpul de execuie n cazul cel mai nefavorabil.

2. S se investigheze dac exist un algoritm care decide dac un arc nou adugat de addEdge() modific sau nu funciile path() i distance(). Motivai rspunsul.

3. S se proiecteze o structur de date eficient pentru reprezentarea acestor digrafuri i s se proiecteze algoritmi eficieni pentru calculul operaiilor. S se arate corectitudinea algoritmilor i s se calculeze timpul de execuie n cazul cel mai nefavorabil pentru fiecare algoritm.

4. S se implementeze structura de date de mai sus i s se determine timpii de execuie pentru secvene de 10.000 (zece mii) operaii generate aleator. Descriei cum ai generat secvenele i comentai rezultatele obinute.