Tehnici de Proiectare şi Analiză a Algoritmilor - Tema 1 2009-2010 Termen de predare: 29 ianuarie 2010 (vinerea din săptămâna a XV-a) Reguli

1. Algoritmii vor fi descrişi în limbajul algoritmic utilizat la curs. 2. Algoritmii vor fi însoţiţi de explicaţiile necesare pentru înţelegerea lor. Algoritmii neînsoţiţi de comentarii şi explicaţii nu vor fi luaţi în cosiderare la calculul punctajului.

3. Vor fi apreciate claritatea şi simplitatea soluţiei, corectitudinea, modul de redactare, acurateţea demonstraţiilor şi calculelor, explicaţiile însoţite 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 mână (lizibil)

pe care se vor menţiona numele şi prenumele (complet), anul şi grupa. Temele redactate nelizibil sau neinteligibil nu vor fi corectate şi vor fi notate cu 0 (zero) puncte. Excepţie 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 soluţia sa proprie (e vorba de o temă individuală şi nu de una în echipă). Dacă se constată că două sau mai multe lucrări au fost efectuate în colectiv, atunci acele lucrări vor fi notate cu 0 (zero) puncte.

7. Dacă se utilizează documentaţie suplimentară, atunci aceasta va fi referită în lucrare şi se va menţiona clar care idei au fost preluate şi care este partea originală (proprie) a lucrării.

8. Tema va fi însoţită de următoarea declaraţie: 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 deţin referinţa precisă a sursei;

- reformularea în cuvinte proprii a textelor scrise de către alţi autori deţine referinţa precisă; - codul sursă, imagini etc. preluate din proiecte open-source sau alte surse sunt utilizate cu repsectarea drepturilor de autor şi deţin referinţe precise; - rezumarea ideilor altor autori precizează referinţa precisă la textul original.

9. În cazul în care consideră că e necesar, profesorul corector poate pune întrebări autorului unei teme pentru stabilirea nivelului de contribuţie proprie.

10. Tema va primi un punctaj cuprins între 0 si 20.

Exerciţii

Scopul acestui execiţiu este de a găsi şi evalua algoritmi cat mai eficienţi pentru probleme NP-

complete la care interesează soluţiile exacte, aşa cum este SAT sau 3SAT.

Fie F o formulă în formă normală conjuctivă (FNC) şi fie l un literal care apare în F. Prin F(l = 1) notăm

formula obţinută din F prin următoarele reguli:

Toate clauzele care conţin pe l sunt eliminate.

Dacă o clauză a lui F conţine l (negaţia lui l) şi cel puţin un literal diferit de l, atunci l este

eliminat din clauză.

Dacă o clauză conţine numai l, atunci F(l = 1) este formula 0 (adică o formulă nesatisfiabilă).

Formula F(l = 0) este definită asemănător:

Toate clauzele care conţin pe l sunt eliminate.

Dacă o clauză a lui F conţine cel puţin doi literali şi unul este l, atunci l este eliminat din

clauză.

Dacă o clauză conţine numai l, atunci F(l = 0) este formula 0.

Notaţiile de mai sus se extind în mod natural: F(l1 = 1, l2 = 1, ..., k1 = 0, k2 = 0) desemnează de fapt

formula F(l1 = 1)(l2 = 1)...(k1 = 0)(k2 = 0)... .

Se notează cu 3FNC formulelor în care fiecare clauză are exact trei literali şi cu 3FNC(n, r) mulţimea

formulelor 3FNC cu cel mult n variabile şi cel mult r clauze.

1. Să se arate arate că o formulă F în 3FNC(n, r), ce conţine o clauză (l1 l2 l3), este

satisfiabilă dacă şi numai dacă cel puţin uma dintre formulele F(l1 = 1), F(l1 = 0, l2 = 1) şi F(l1

= 0, l2 = 0, l3 = 1) este satisfiabilă.

2. Să se arate că F(l1 = 1) 3FNC(n – 1, r – 1) , F(l1 = 0, l2 = 1) 3FNC(n – 2, r – 1) şi F(l1 = 0, l2 =

0, l3 = 1) 3FNC(n – 3, r – 1).

3. Utilizând 1. şi 2., să se proiecteze un algoritm divide-et-impera care având la intrare o

formulă 3FNC F, decide dacă F este satisfiabilă.

4. Să se arate că algoritmul de la 3. are complexitatea timp în cazul cel mai nefavorabil

O(r1.84n).

5. Să se implementeze lagoritmul de la 3. şi sa se analizeze timpul de execuţie pentru di ferite

valori ale lui n si r. Descrieţi modul în care au fost aleşi n şi r şi modul în care au fost generate

intrările.