Universitatea Alexandru Ioan Cuza, Ias, i Numele:

Facultatea de Informatică Grupa:

Proiectarea Algoritmilor - Test Scris Săpt. 8 - Seria I

Observat, ii:
1. Nu este permisă consultarea bibliografiei.
2. Toate ı̂ntrebările sunt obligatorii.
3. Fiecare ı̂ntrebare/item este notată cu un număr de puncte indicat ı̂n paranteză.
4. Algoritmii vor fi descris, i ı̂n limbajul Alk (cel utilizat la curs). În formularea solut, iilor se vor utiliza definit, iile s, i
notat, iile predate la curs. Descriet, i conceptele utilizate ı̂n răspunsuri.
5. Nu este permisă utilizarea de foi suplimentare.
6. Răspunsurile deosebite pot primi bonusuri.
7. Timp de răspuns: 1 oră.
8. Specificat, ii criterii: FP: correct formulation of problems, AD: algorithm design, AA: algorithm
analysis. Evaluarea unui criteriu se va face prin considerarea tuturor punctelor relevante pentru acesta.

1. (15p) Proiectare s, i analiză, baza

n(3n − 1)
Numerele pentagonale sunt generate de formule de forma P (n) = , n = 1, 2, . . .. Primele numere
2
pentagonale sunt 1, 5, 12, 22, 35, 51, . . .. Un s, ir de numere este pentagonal dacă toate numerele din s, ir sunt
pentagonale. Problema P1 constă ı̂n determinarea dacă un s, ir este pentagonal.
(a) (3p, FP) Să se precizeze P1 ca pereche (Input, Output). Pentru Input se vor preciza datele de intrare s, i
proprietăt, ile lor. Pentru Ouput se vor preciza datele de ies, ire s, i proprietăt, ile lor. Formulările trebuie să fie
cât mai precise s, i complete (nu sunt notate formulări de forma ”altfel”, ”ı̂n celelalte cazuri”, . . . ). Folosirea
corectă de predicate s, i relat, ii matematice poate primi un bonus.
Input: s = (x0 , x1 , . . . , xn−1 ), n > 0, xi ∈ N pentru i = 0, 1, . . . , n − 1.

Output: true dacă pentru orice i cu 0 ≤ i < n, isPentagonal (xi ). Predicatul isPentagonal (x) are loc
n(3n − 1)
ddacă x este pentagonal, i.e., ∃n ∈ N.x = .
2
false dacă există i cu 0 ≤ i < n a.ı̂. ¬isPentagonal (xi ).

(b) (3p, AD) Să se scrie un algoritm ı̂n Alk, sub formă de funct, ie, care decide dacă un număr natural dat este
pentagonal.
isPentagonalNat(x)
{
if (x <= 0) failure;
a = 1 + 24 * x;
b = int(sqrt(a));
if (b*b == a && (1+b)%6 == 0)
return true; // n = (1 + b)/6
else
return false;
}
(c) (3p, AD) Să se scrie un algoritm ı̂n Alk, sub formă de funct, ie, care rezolvă P1.

isPentagonalStr(s)
{
for (i=0; i < [Link](); ++i)
if (! isPentagonalNat(s[i]))
return false;
return true;
}
(d) (2p) Să se justifice cât mai riguros că algoritmul este corect.
n(3n − 1)
x= este echivalent cu 3n2 − n − 2x = 0. x este pentagonal ddacă ecuat, ia are o rădăcina număr
2 √
1 + 1 + 24x
natural, caz ı̂n care este egală cu . Funct, ia isPentagonalNat(x) asta verifică. Corectitudinea
6
funct, iei isPentagonalStr(s) rezultă din următorul invariant ment, inut de for: pentru orice j cu 0 ≤ j < i,
s[j] este pentagonal.

1
 (e) (4p, AA) Să se determine timpul de execut, ie pentru cazul cel mai nefavorabil pentru algoritmul ce rezolvă
P1:
• (1p) Dimensiunea unei instant, e: n = [Link]()
• (1p) Ce operat, ii sunt analizate s, i care este timpul de execut, ite pentru fiecare: isPentagonalNat(s[i]) cu
timpul O(1)
• (1p) Cazul cel mai nefavorabil: toate numerele din s sunt pentagonale (for parcurge tot tabloul s)

• (1p) Timpul pentru cazul cel mai nefavorabil: Sunt executate n apeluri isPentagonalNat(s[i]). Obt, inem
T (n) = n · O(1) = O(n).

2. (10p) Algoritmi probabilis, ti, complexitate medie.

Se consideră următorul algoritm:
alg2(S)
{
k = uniformNat([Link]()+1);
A = {};
for (i=0; i < k; ++i) {
uniform x from S;
if (x % 2 == 1) x = x+1;
A = A U {x};
S = S \ {x};
}
return A;
}

(a) (3p, FP) Să se descrie problema rezolvată de algoritm.

Input: O mult, ime S = {x0 , . . . , xn−1 } cu elementele xi numere naturale. S poate fi s, i mult, imea vidă.

Output: A cu proprietatea că există o submult, ime B ⊆ S a.ı̂. A = {x | x ∈ B, x par} ∪ {x + 1 | x ∈

B, x impar}.

(b) (2p) Ment, ionat, i o implementare a mult, imilor ı̂n care operat, iile de adăugare s, i eliminare a unui element se
realizează ı̂n O(1).
Presupunând S ⊆ {0, 1, 2, . . . , N }, se va considera reprezentarea lui S prin vectorul caracteristic: S[i] = 1
dacă i ∈ S, S[i] = 0 altfel.

(c) (5p, AA) Să se calculeze complexitatea medie (as, teptată) a algoritmului. Se vor considera doar operat, iile
peste mult, imi cu complexităt, ile de la punctul precedent.

Valorile ti posibile pentru timp: 0 (A submult, imea vidă), 3 (A submult, ime cu 1 element), 6 (A submult, ime
cu 2 elemente), . . . , 3 · [Link]() (A = S).
Presupunem dimensiunea unei instant, e n = [Link](), n > 0.
1
Probabilitatea pk ca execut, ia sa aibă timpul tk : pk = (= probabilitatea alegerii lui k).
n+1
Pn 1 1 1 3
Timpul mediu: exp-time(n) = k=1 tk ·pk = 3· +6· +· · ·+3·n· = (1+2+· · ·+n) =
n+1 n+1 n+1 n+1
3·n
.
2

2
3. (15p) Probleme NP-complete.
(a) (4p, AA) Dacă P 6= NP s, i există cel put, in o problemă din clasa NP cu o rezolvare polinomială, atunci sigur
există o rezolvare polinomială pentru orice problemă din clasa NP.
Justificat, i că DA sau justificat, i că NU.
NU.
Contraexemplu:
Fie problema 2-SAT, care are o rezolvare polinomială (s, tim din fis, a de exercit, ii de la seminar).
Fie problema 3-SAT, care este NP-completă (Cook, 1961). 3-SAT nu are rezolvare polinomială, des, i este
ı̂n NP (dacă 3-SAT ar avea o rezolvare polinomială, cum orice problemă din NP se reduce (R) ı̂n timp
polinomial la 3-SAT, obt, inem că avem rezolvări polinomiale pentru toate problemele din NP s, i deci P =
NP).

(b) (3p, FP) Definit, i problemele VERTEX-COVER s, i INDEPENDENT-SET.

VERTEX-COVER
Input: G = (V, E), k ∈ N
Output: există V 0 ⊆ V a.ı̂. |V 0 | ≤ k s, i pentru orice muchie {u, v} ∈ E avem u ∈ V 0 sau v ∈ V 0 ?

INDEPENDENT-SET
Input: G = (V, E), k ∈ N
Output: există V 0 ⊆ V a.ı̂. |V 0 | ≥ k s, i pentru orice muchie {u, v} ∈ E avem u 6∈ V 0 s, i v 6∈ V 0 ?

(c) (4p, AD, AA) Arătat, i că problema VERTEX-COVER este ı̂n NP.
Următorul algoritm nedeterminist rezolvă VERTEX-COVER ı̂n O(n3 ), unde n este numărul de noduri:
i. ghicim o submult, ime V 0 ⊆ V de noduri (ı̂n timp O(n), câte un bit pentru fiecare nod – dacă face sau
nu parte din V 0 );
ii. verificăm dacă |V 0 | ≤ k s, i ∀u ∈ V · ∀v ∈ V · {u, v} ∈ E → u ∈ V 0 ∨ v ∈ V 0 (două for-uri imbricate;
timp O(n3 ) presupunând că E este implementat sub forma unei matrice de adiacent, ă s, i deci testul
{u, v} ∈ E este ı̂n O(1), iar testul u ∈ V 0 ∨ v ∈ V 0 ı̂n O(n) ).

(d) (4p, AD, AA) Găsit, i o reducere polinomială de tip Karp de la VERTEX-COVER la INDEPENDENT-SET.
Considerăm G = (V, E), k ∈ N date de intrare pentru VERTEX-COVER.
Calculăm k 0 = |V | − k.
VERTEX-COVER(G, k) = INDEPENDENT-SET(G, k’)
(complementul unei mult, imi stabile este o acoperire)

3
Ciornă