SEMINAR PROIECTAREA ALGORITMILOR

Seminar 1 - Input/Ouput
Input si output pentru o problema data:
- input = datele de intare, ce se da;
- output = datele de iesire, ce se cere;

1. primele n nr date de un nr n;
Input: n € N;
Ouput: a1, a2, …, an, ai € N, Pirm(ai) ^ ai < ai+1, oricarearfi i =1,n
Prim(x) = oricarearfi d( (d>1 ^ d<x)→(x%d !=0)

def este_prim(numar):
if numar < 2:
return false
for i in range(2, int(numar**0.5) +1):
if numar % i == 0;
return flase
return true

def primele_n_nr_prime(n):
numere_prime = []
numar = 2
while len(numere_prime) < n:
if este_prim(numar):
numere_prime.append(numar)
numar += 1
print (numere_prime)

n = int(input(“Introduceti numarul de numere prime dorit: ”))

primele_n_nr_prime(n)

2. primele n nr prime mai mici decat n, folosind ciurul lui Eratostene;

void ciur(bool&a, int n) {

a[0]=a[1]=1
for(int i=2;i<n;i++) {
if(a[i]==0) {
for(int j=2;j*i<=n;j++) {
a[i*j] =1;
}
}
}
}

lista f(int n) {
if(n==0) {
return [Link];
}
bool a[1000] = {0};
ciur(a[], n);
 [Link](a);
for(int i=3; i<=n; i++){
if(a[i]==0) [Link](i);
return lista;
}
}

3. primele n nr palindroame, a caror patrate sunt mai mici sau egale cu n;

Input: n € N;
Ouput: a1, a2, …, ak unde Pal(ai) ^ Pal(ai*ai) ^ ai <=n ^ ai < ai+1, i=1,n;
Pal(ai) = Pal(c1c2...cm): I (i>=1 ^ I<=m/2) → (ai = am-i+1)

bool palindrom (int n) {

int aux=n; aux=0; p=1;
while(aux) {
int i = aux%10;
aux = aux/10;
aux = n * aux +p +c;
}
if( aux == n) return true;
return false;
}

Seminar 2 - Demonstrarea ca un algoritm rezolva corect o problema.

Pași pentru demonstrarea corectitudinii unui algoritm

1. Definirea problemei și a soluției corecte
• Se specifică clar ce trebuie să facă algoritmul (input-output).
• Se descrie condițiile pe care trebuie să le satisfacă rezultatul.

2. Corectitudinea parțială (dacă algoritmul produce un rezultat corect)

Aceasta se verifică de obicei prin:
• Inducție matematică (dacă algoritmul este recursiv).
• Invarianți de buclă (pentru algoritmi iterativi).
• Analiza fiecărei etape a algoritmului, arătând că transformă datele corect.
✅ Exemplu: Într-un algoritm de sortare, putem demonstra că fiecare pas al algoritmului păstrează
proprietatea că secvența parțial sortată rămâne validă.

3. Corectitudinea totală (dacă algoritmul se termină întotdeauna)

• Se demonstrează că algoritmul nu intră în bucle infinite.
• Se folosește o funcție de progres, care arată că algoritmul face pași către finalizare.
• Se verifică dacă algoritmul are o condiție de oprire validă.
✅ Exemplu: Pentru căutarea binară, dimensiunea intervalului de căutare se înjumătățește la fiecare
pas, ceea ce asigură că algoritmul se termină în O(log n) pași.
Metode de demonstrare
1. Inducția matematică (pentru algoritmi recursivi)
Se verifică două aspecte:
• Cazul de bază – Se demonstrează că algoritmul funcționează pentru cele mai mici intrări
posibile.
• Pasul inductiv – Se presupune că funcționează pentru o intrare de dimensiune k, și se arată
că funcționează pentru k+1.
✅ Exemplu: Corectitudinea recursivă a algoritmului de calculare a factorului factorial:
f(n)=n⋅f(n−1)
Se verifică că:
• Caz de bază: f(1) = 1, ceea ce este corect.
• Pas inductiv: Dacă presupunem că f(k) = k!, trebuie să arătăm că f(k+1) = (k+1)!. Relația
este corectă, deci algoritmul funcționează.

2. Invarianți de buclă (pentru algoritmi iterativi)

Un invariant de buclă este o proprietate care rămâne adevărată la fiecare iterație a unei bucle.
✅ Exemplu: Algoritmul lui Euclid pentru cel mai mare divizor comun (GCD)
Se folosește formula:
gcd(a,b)=gcd(b,amodb)
Invariant: La fiecare iterație, valoarea corectă a GCD rămâne neschimbată. Deoarece b scade,
algoritmul se termină.

3. Analiza cazurilor (pentru algoritmi cu mai multe scenarii)

Se verifică toate posibilele cazuri și se arată că algoritmul funcționează corect în fiecare dintre ele.
✅ Exemplu: Căutare binară
• Cazul 1: Elementul căutat este în mijloc → algoritmul returnează direct.
• Cazul 2: Elementul căutat este mai mic → căutăm în jumătatea stângă.
• Cazul 3: Elementul căutat este mai mare → căutăm în jumătatea dreaptă.
În fiecare caz, dimensiunea problemei scade, deci algoritmul se termină și este corect

1. un vector, doi indici pentru cele mai mici doua nr din vector consective
a. Input: Un vector V de numere naturale cu cel puțin două elemente.
Fie V=[v0,v1,...,vn−1], unde vi∈N, i∈[0, n-1] și n≥2.
Output: i, j unde ai <= aj, oricare k != i,j avem ak>=aj, i,j,k∈0,n-1, i!=j
b. Corectitudine algoritm
Inițializarea corectă a celor mai mici două elemente
• Primele două elemente sunt comparate și se inițializează sml (indicele celui mai mic
element) și nxtsml (indicele celui de-al doilea cel mai mic element).
• Aceasta este o metodă validă și corectă.
Parcurgerea vectorului și actualizarea indicilor
• Se parcurge vectorul de la al treilea element (i = 2) până la n - 1.
• Dacă a[i] este mai mic decât a[sml], atunci sml trebuie actualizat, iar vechiul sml devine
nxtsml.
Problemă: Algoritmul nu verifică dacă a[i] este mai mare decât a[sml], dar mai mic decât
a[nxtsml]. Dacă a[i] nu este cel mai mic, dar este al doilea cel mai mic, acesta trebuie să
actualizeze nxtsml.
 Lipsa actualizării corecte pentru nxtsml
• Dacă a[i] nu este cel mai mic, dar este mai mic decât a[nxtsml], nxtsml ar trebui să fie
actualizat, dar algoritmul NU face acest lucru.
• De exemplu, pentru inputul [3, 5, 2, 7, 4, 1], algoritmul va găsi corect sml = 5, dar nu va
actualiza corect nxtsml = 2.
2. Input: A=(a0, a1, … an-1), ai∈Z, i=0,n-1, oricare i,j, ai<aj
Output: i, 0<=i<=n-1, ai==i, daca exista un astfel de element
-1, daca pt oricare i=0,n-1 avem ai!=i

Setăm doi indici: st = 0 și dr = n - 1.

Cât timp st ≤ dr:
• Calculăm mijlocul: mid = (st + dr) // 2.
• Dacă arr[mid] == mid, am găsit punctul fix → returnăm mid.
• Dacă arr[mid] < mid, înseamnă că toate valorile din stânga sunt prea mici (deoarece
elementele sunt distincte și sortate).
→ Căutăm în dreapta: st = mid + 1.
• Dacă arr[mid] > mid, înseamnă că toate valorile din dreapta sunt prea mari.
→ Căutăm în stânga: dr = mid - 1.
Dacă nu găsim un punct fix, returnăm -1.

def gaseste_punct_fix(arr):
st, dr = 0, len(arr) - 1

while st <= dr:

mid = (st + dr) // 2

if arr[mid] == mid:
return mid
elif arr[mid] < mid:
st = mid + 1
else:
dr = mid - 1

return -1 # Dacă nu există punct fix

Este corect algoritmul?

Proprietate invariant: pct fix, daca exista, se afla intre st si dr.
Initial: st=0, dr=n-1, daca exista pct fix, sigur e in A[0,n-1] (tot vectorul)
Proprietatea de mentinere: Pp ca pana la pasul curent, proprietatea se pastreaza
Daca a[x] e pct fix, se returneaza.
Daxa a[x]>x, pt ca vectorul e sortat, pct fix poate exista doar la st.
Daca a[x]<x, pt ca A e sortat, pct fix poate exista doar la dr, pct fix daca exista se va afla in
noul spatiu de cautare.
Proprietatea de terminare: daca returnam dr, pct fix exista; pt<dr, daca pct fix nu exista,
proprietatea e pastrata
3. (a) Este algoritmul corect?
Da, algoritmul este corect. Acesta folosește algoritmul lui Boyer-Moore pentru găsirea unui
candidat și apoi îl verifică printr-o a doua parcurgere a vectorului.
Algoritmul se bazează pe două observații:
1. Dacă există un element majoritar, atunci acesta va fi identificat ca singurul posibil
candidat în prima fază.
2. Chiar dacă algoritmul identifică un candidat, acesta trebuie verificat în a doua parcurgere,
deoarece prima fază doar găsește un posibil element majoritar, dar nu confirmă dacă apare
de mai mult de ⌊n/2⌋ ori.

Algoritmul rezolva corect problmea?

Loop invariant (4-12): daca elem majoritar exista, atunci fie candidat = elem majoritar, fie
candidat != elem majoritar, dar au ramas suficiente aparitii ale acestuia pt a ajunge la candidat ==
elem majoritar;
Init: candidat != elem majoritar, daca elem majoritar, ne-au ramas toate aparitiile sale, care sunt
suficiente;
Mentinere: Pp ca pana la pas i-1 se respecta proprietatea, la pas i: daca count=0, candidat =A[i],
daca A[i]==elem majoritar=> bifat; daca A[i]!=elem majoritar=> mai sunt suficiente aparitii ale
elem majoritar;
daca count !=0 si candidat == elem majoritar => bifat; count!=0 si cand != elem majoritar=> exista
inca suficiente aparitii ale elem majoritar;
Terminare: i=n=> daca exista elem majoritar, pt ca invariantul se respecta si nu mai exista elemente
de parcurs, trebuie ca candidat= elem majoritar;

(b) De ce se folosesc două parcurgeri ale vectorului?

1. Prima parcurgere (liniile 4-12) folosește algoritmul Boyer-Moore pentru a selecta un
candidat.
• Ideea de bază este că elementele care nu sunt majoritare se vor anula reciproc.
• Dacă există un element majoritar, acesta va rămâne la final ca singurul posibil
candidat.
2. A doua parcurgere (liniile 13-20) este necesară pentru a verifica dacă elementul ales
apare de mai mult de ⌊n/2⌋ ori.
• Algoritmul Boyer-Moore garantează doar un candidat, dar nu garantează că acesta
este majoritar.
• Fără această verificare, ar putea returna un element greșit.
(c) Care este complexitatea timp a algoritmului?
• Prima parcurgere (liniile 4-12): O(n)
• A doua parcurgere (liniile 13-20): O(n)
• Complexitatea totală: O(n) + O(n) = O(n)
Deoarece algoritmul face doar două parcurgeri liniare, acesta este eficient, având complexitate
O(n).

4. (a) Enunțarea problemelor

Avem două numere naturale foarte mari, reprezentate ca șiruri de cifre. Vrem să calculăm:
1. Adunarea celor două numere.
2. Înmulțirea celor două numere.
 Aceste operații trebuie realizate eficient, având în vedere că numerele pot avea mii sau
milioane de cifre, ceea ce depășește capacitatea numerică a tipurilor de date standard (ex. int în
majoritatea limbajelor de programare).

(b) Algoritmi pentru adunare și înmulțire

1. Algoritmul pentru adunare
Adunarea se realizează ca în cazul adunării pe hârtie, de la ultima cifră spre prima, ținând
cont de transportul dintre poziții.
Input: (a0, …, an-1), (b0, …, bn-1), ai,bj ∈N, 0<=ai,bj<=9, oricare i=1..n-1, j=1..m-1,
a0,b0∈1..9, n,m>=1
Output: (c0, ..., cn-1), unde c0c1...ck = a0a1...an-1 + bob1...bm-1

def adunare_numere_mari(a, b):

a, b = a[::-1], b[::-1] # Inversăm șirurile pentru a aduna de la dreapta la stânga
carry = 0
rezultat = []

max_len = max(len(a), len(b))

for i in range(max_len):
cifra_a = int(a[i]) if i < len(a) else 0
cifra_b = int(b[i]) if i < len(b) else 0

suma = cifra_a + cifra_b + carry

[Link](str(suma % 10))
carry = suma // 10

if carry:
[Link](str(carry))

return ''.join(rezultat[::-1]) # Inversăm din nou pentru rezultatul corect

2. Algoritmul pentru înmulțire (Metoda clasică – "școală")

În această metodă, fiecare cifră a primului număr este înmulțită cu fiecare cifră a celui de-al doilea
număr, apoi se aplică suma produselor ponderate corespunzător pozițiilor.
def inmultire_numere_mari(a, b):
a, b = a[::-1], b[::-1] # Inversăm pentru a opera de la dreapta la stânga
rezultat = [0] * (len(a) + len(b)) # Vector pentru rezultat

for i in range(len(a)):
for j in range(len(b)):
produs = int(a[i]) * int(b[j])
rezultat[i + j] += produs
rezultat[i + j + 1] += rezultat[i + j] // 10 # Transport
rezultat[i + j] %= 10
 # Eliminăm zerourile din față
while len(rezultat) > 1 and rezultat[-1] == 0:
[Link]()

return ''.join(map(str, rezultat[::-1])) # Inversăm înapoi

(c) Timpul de calcul în cazul cel mai nefavorabil

• Adunare: O(n)
• Înmulțire clasică: O(n²)
Dacă avem două numere de m cifre fiecare:
• Adunarea rulează în O(m).
• Înmulțirea clasică rulează în O(m²), ceea ce devine ineficient pentru numere foarte mari.

d) Algoritmul lui Karatsuba pentru înmulțire – O(n^log2(3)) ≈ O(n^1.585)

Algoritmul lui Karatsuba împarte numerele în două părți și folosește recursivitatea pentru a reduce
numărul de înmulțiri necesare. Se bazează pe identitatea matematică:
XY=102mAC+10m(AD+BC)+BD
unde:
• X=A⋅10m+B
• Y=C⋅10m+D
• Se înlocuiește calculul AD + BC cu o singură înmulțire:(A+B)(C+D)=AC+BD+
(AD+BC)De unde rezultă că trebuie să facem doar 3 înmulțiri în loc de 4.

5. Problema sortarii
Input: A=[a1,a2,…,an] – un șir de n numere naturale.
Ouput: A′=[a1′,a2′,…,an′], astfel incat a1′≤a2′≤⋯≤an′

a) Booble sort
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False # Optimizare: verificăm dacă au fost schimbări
for j in range(0, n - i - 1): # Ultimele i elemente sunt deja sortate
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j] # Swap
swapped = True
if not swapped: # Dacă nu s-au făcut schimbări, lista este deja sortată
break
return arr

1. Definim invariantul buclei

Un invariant al buclei este o proprietate care rămâne adevărată la fiecare iterație a unui
algoritm.
După k parcurgeri complete ale vectorului, cele mai mari k elemente sunt plasate corect
la sfârșitul vectorului, iar restul elementelor (nesortate) se află în partea stângă.
 2. Demonstrarea corectitudinii prin inducție matematică
Vom folosi inducția pentru a demonstra că invariantul buclei este adevărat pentru orice k.
Cazul de bază (k = 1)

La prima parcurgere completă prin vector:

• Comparăm fiecare pereche de elemente adiacente și le interschimbăm dacă sunt în ordine
greșită.
• Astfel, cel mai mare element ajunge în ultima poziție (pentru că la fiecare swap, cel mai
mare element „urcă” spre dreapta).

Pasul de inducție
Presupunere de inducție: Să presupunem că după k parcurgeri, cele mai mari k elemente sunt
plasate corect în ultimele k poziții ale vectorului.
Dovedim pentru k + 1:
• La a (k+1)-a parcurgere, aplicăm aceeași strategie: comparăm și interschimbăm perechi
adiacente.
• Elementul cel mai mare dintre cele rămase se „ridică” spre dreapta și ajunge pe poziția
corectă (n - k - 1).
• Astfel, acum primele n - k - 1 elemente rămase sunt nesortate, iar ultimele k+1 elemente
sunt în poziția finală corectă.

3. Terminarea algoritmului
Trebuie să demonstrăm că algoritmul se oprește și că la final vectorul este complet sortat.
• În cel mai rău caz, avem nevoie de n-1 parcurgeri pentru ca toate elementele să fie în ordine
corectă.
• După n-1 parcurgeri, toate elementele sunt sortate, deci nu mai sunt necesare interschimbări
(swapped = False → bucla se oprește).
• Deoarece n-1 este un număr finit, algoritmul se termină întotdeauna.

4. Concluzie
1. Prin inducție, am demonstrat că după k parcurgeri, cele mai mari k elemente sunt plasate
corect.
2. După n-1 parcurgeri, toate elementele sunt ordonate în ordine crescătoare.
3. Algoritmul se termină într-un număr finit de pași, deci este corect.

Selection sort
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i # Considerăm inițial că elementul curent este cel mai mic
for j in range(i + 1, n):
if arr[j] < arr[min_idx]: # Căutăm cel mai mic element
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i] # Swap
return arr
 Algoritmul rezolva corect problmea?
1. Definim invariantul buclei
După k iterații ale buclei externe, primele k elemente din vector sunt sortate în ordine
crescătoare și conțin k dintre cele mai mici elemente ale vectorului inițial.

2. Demonstrăm corectitudinea prin inducție

Caz de bază (k = 1)
• La prima iterație (k = 1), algoritmul caută cel mai mic element din vector și îl plasează în
prima poziție.
• Aceasta înseamnă că primul element este corect plasat, iar restul vectorului conține încă n-1
elemente nesortate.

Pasul de inducție
Presupunem că invariantul este adevărat pentru k iterații, adică primele k elemente sunt
sortate și conțin cele mai mici k valori.
Dovedim că este adevărat și pentru k + 1:
1. În a k+1-a iterație, algoritmul caută cel mai mic element din secțiunea nesortată (de la
poziția k la n-1).
2. Îl mută în poziția k, asigurându-se că primele k+1 elemente sunt acum sortate și conțin cele
mai mici k+1 valori.
3. Restul elementelor rămân nesortate, dar toate sunt mai mari decât primele k+1 elemente.

3. Terminarea algoritmului
Trebuie să demonstrăm că algoritmul se termină întotdeauna.
• Bucle exterioară rulează de n-1 ori (0 până la n-2), deoarece ultimul element va fi deja în
poziția corectă.
• La fiecare pas, dimensiunea părții nesortate scade cu 1, deci algoritmul ajunge inevitabil la o
secțiune goală și se oprește.
• Deoarece n-1 este un număr finit, Selection Sort se termină întotdeauna.

Concluzie
1. Am demonstrat prin inducție că după k iterații, primele k elemente sunt sortate și sunt cele
mai mici din vector.
2. După n-1 iterații, întregul vector este sortat.
3. Algoritmul se termină întotdeauna.

6. un nr natural n, si n-1 nr naturale distincte intre 1 si n, nr lipsa?

Input: n∈N, a1,a2, …, an-1, oricare ai∈1..n si ai!=aj, oricare i,j∈1..n-1
Ouput: x∈1...n-1, x nu apartine a1,an, …, an-1

def missingNumber(n, A):

total_sum = n * (n + 1) // 2 # Suma numerelor de la 1 la n
actual_sum = sum(A) # Suma elementelor din șirul dat
return total_sum - actual_sum # Diferența este numărul lipsă
 Algoritmul rezolva corecta problema?
1. Definim invariantul buclei
Pentru orice nr natural n, diferenta dintre suma totala a elementelor si suma elementelor n-1
date este exact elementul lipsa. La inceput avem S=suma elementelor n, si calculam suma
elemntelor multimii A care contine n-1 elemente, iar diferenta S-A este exact nr lipsa.

2. Demonstrarea prin inducție matematică

Cazul de bază (n = 2)
Dacă n = 2, avem două posibile liste:
• A = [1] → lipsă 2
• A = [2] → lipsă 1
Folosind formula:S=2(2+1)/2=3,Sactual=∑A
Numărul lipsă este S - S_actual, ceea ce dă valoarea corectă în ambele cazuri.

Pasul de inducție
Presupunem că pentru n = k algoritmul funcționează corect. Adică:
Suma teoretica Sk=k(k+1)/2
iar numărul lipsă este dat corect de formula:
lipsa=Sk−Sactual
Pentru n = k+1, noua sumă este:
Sk+1=(k+1)(k+2)/2
iar A conține k elemente. Aplicând algoritmul pe A, diferența dintre S_{k+1} și S_actual va
da exact numărul lipsă. Prin ipoteza de inducție, rezultatul este corect și pentru k+1.

4. Concluzie
Demonstrarea prin invariant:
Am arătat că diferența dintre suma teoretică și suma elementelor din A rămâne constant
egală cu numărul lipsă pe tot parcursul execuției.
Demonstrarea prin inducție:
Am verificat cazul de bază și am arătat că, dacă algoritmul funcționează pentru n = k, atunci
funcționează și pentru n = k+1.
Prin urmare, algoritmul este corect și rezolvă problema numărului lipsă pentru orice n.

Seminar 3 – Algoritmi probabilisti. Algoritmi nedeterministi.

I. Algoritmi probabilisti
Un algoritm probabilistic este un algoritm care folosește aleatoriu (randomness) în
procesul său de execuție. Spre deosebire de algoritmii deterministici, care produc întotdeauna
același rezultat pentru aceeași intrare, algoritmii probabilistici pot returna rezultate diferite pe
execuții diferite.
Există două mari categorii de algoritmi probabilistici:
1. Algoritmi Las Vegas (100% corecți, dar timp de rulare variabil)
• Acești algoritmi oferă întotdeauna un răspuns corect, dar timpul lor de execuție
poate varia în funcție de alegerile aleatorii făcute.
• Dacă au o limită de timp rezonabilă, sunt foarte utili.
 2. Algoritmi Monte Carlo (timp fix, dar pot da răspuns greșit cu probabilitate mică)
• Acești algoritmi au un timp de execuție garantat, dar pot returna un rezultat
incorect cu o anumită probabilitate.
• Prin repetarea algoritmului, putem face probabilitatea de eroare foarte mică.

Cum calculăm probabilitatea ca un algoritm probabilist să se oprească după exact i

iterații?
Definim probabilitatea ca algoritmul să se oprească exact la iteratia i:
P(T=i)=P(x1=1)×P(x2=1)×⋯×P(xi−1=1)×P(xi=0)

Dacă un algoritm probabilist se bazează pe o probabilitate p pentru a continua și 1 - p pentru

a se opri, atunci numărul de iterații T urmează o distribuție geometrică cu probabilitatea de oprire:
P(T=i)=pi-1×(1−p)

Cum calculăm valoarea medie întoarsă de un algoritm probabilist?

Valoarea medie (speranța matematică) a unui algoritm probabilist este definită ca:
E[X]=∑P(X=i)⋅i
unde X este variabila aleatoare ce reprezintă rezultatul algoritmului, iar P(X = i) este probabilitatea
ca algoritmul să returneze valoarea i.

Exemplu 1: Algoritmul de aruncare a unei monede de n ori

import random

def coin_flip_sum(n):
sum_x = 0
for _ in range(n):
sum_x += [Link]([0, 1]) # Aruncăm moneda
return sum_x

1. Definirea variabilei aleatoare

Fie X_i variabila aleatoare care ia valori 0 sau 1 pentru fiecare aruncare de monedă.
• P(X_i = 1) = 0.5
• P(X_i = 0) = 0.5
Suma totală S_n a celor n aruncări este: Sn=X1+X2+⋯+Xn
2. Calculul valorii medii
Folosim proprietatea liniarității speranței matematice: E[Sn]=E[X1]+E[X2]+⋯+E[Xn]
Cum fiecare X_i are speranța matematică: E[Xi]=0⋅0.5+1⋅0.5=0.5
Rezultă că: E[Sn]=n⋅0.5=n/2
Concluzie: Algoritmul coin_flip_sum(n) returnează în medie n/2.

Cum calculam timpul mediu de asteptare al unui algoritm?

Timpul mediu de așteptare pentru un algoritm probabilist este echivalent cu numărul mediu
de pași până la oprire, adică speranța matematică a timpului până la oprire.
Dacă algoritmul probabilist se oprește la fiecare pas cu probabilitate q = 1 - p și continuă cu
probabilitate p, atunci timpul de așteptare urmează o distribuție geometrică.
Distributia geometrica: P(T=i)=pi-1 * q Timpul mediu de asteptare: E[T]=1/q=1/1-p
 Exemplu: Algoritmul care aruncă o monedă până obține "cap"
import random

def asteptare():
i=0
while [Link]([0, 1]) != 0: # Continuă până apare 0 (cap)
i += 1
return i + 1

Fie T = numărul de pași până la primul succes (x = 0).

• Probabilitatea de continuare: p = 0.5
• Probabilitatea de oprire: q = 1 - p = 0.5

Distribuția geometrică: P(T=i)=pi-1 * q

Timpul mediu de așteptare (speranța matematică): E[T] = 1/q = 1/(1-p)

Cum calculăm timpul mediu de execuție al unei instrucțiuni într-un algoritm

probabilist?
Timpul mediu de execuție al unei instrucțiuni într-un algoritm probabilist se calculează prin
speranța matematică a numărului de execuții ale acelei instrucțiuni.
Dacă X este variabila aleatoare care reprezintă numărul de execuții ale unei instrucțiuni,
atunci:
E[X]=∑i⋅P(X=i)
Pașii principali pentru calcul:
1️. Identificăm variabila aleatoare X
• X = numărul de execuții ale instrucțiunii dorite
2️. Determinăm distribuția de probabilitate
• Care este probabilitatea P(X = i) ca instrucțiunea să fie executată exact i ori?
3️. Aplicăm speranța matematică
• Folosim formula de mai sus pentru a calcula valoarea medie a lui X.

Exemplu: Fie urmatorul algoritm:

alg2(S) {
if (S == {}) failure;
uniform x from S;
S = S \ {x};
while (S != {}) {
uniform y from S;
if (y < x) x = y;
S = S \ {y};
}
return x;
}

Să se calculeze numărul mediu (as, teptat) de execut, ii ale atribuirii x = y;.

Pasul 1: Se alege uniform aleator un element x din mulțimea S.
Pasul 2: Pe parcursul fiecărei iterații, se alege aleator un element y din restul mulțimii S.
Pasul 3: Dacă y < x, actualizăm x = y.
Pasul 4: Repetăm procesul până când S devine mulțimea vidă.

Fie x₀, x₁, x₂, ..., xₙ₋₁ elementele mulțimii S, ordonate crescător.
Alegem x aleator la început. Dacă x = xᵢ, atunci vom compara x cu toate elementele care sunt mai
mici decât xᵢ, deci cu elementele x₀, x₁, ..., xᵢ₋₁.
Probabilitatea ca x să fie elementul xᵢ este: 1/n. Când x = xᵢ, numărul de atribuiri x = y este
exact i.
Numarul mediu de atribuiri este: E[nr atribuiri]=∑1/n*i=1/n∑i
Suma numerelor naturale: ∑i = n(n−1)/2
Rezultatul final: E[nr atribuiri]=1/n*n(n−1)/2=(n−1)/2

II. Algoritmi nedeterministi

Un algoritm nedeterminist este un algoritm care poate explora simultan mai multe căi de
execuție pentru a găsi o soluție.

Diferența față de un algoritm determinist:

Algoritm Determinist Algoritm Nedeterminist

Urmează un singur fir de execuție. Explorează toate căile posibile simultan.
La fiecare pas, face o alegere fixă. Poate face alegeri multiple, simultan.
Eficiența depinde de cât de inteligent alege. Își "ghicește" instant soluția corectă.
Folosește "for", "if", "while". Folosește "choose" sau "guess".

Cum funcționează un algoritm nedeterminist?

Pasul 1: Alege simultan toate posibilitățile.
Pasul 2: Verifică dacă o cale duce la soluție.
Pasul 3: Dacă o cale este corectă, algoritmul se oprește.

Exemplu clasic: Problema Subset Sum (SSD3)

Input: O mulțime S de numere întregi și un număr M.
Output: Există un subset a cărui sumă este exact M?

alg(S, M):
choose S' ⊆ S # Alege simultan toate subseturile
if sum(S') == M:
return "DA"
else:
return "NU"
Intuiție:
• În loc să verificăm fiecare subset pe rând, algoritmul nedeterminist "ghicește" direct
subsetul corect.
• Apoi, doar verifică dacă suma subsetului este M, ceea ce se face în timp polinomial.
1. ban maslui, cap = 5/9 si pajura 4/9

def arunca_ban_masluit():
std::uniform_int_distribution<> dist(0,8);
int x = dist(gen);
if x < 5:
return "cap"
else:
return "pajura"

2. un algoritm

ok = true;
i = 0;
while (ok) {
uniform x from {0, 1};//alege 0 sau 1 cu distribut, ie uniform ̆a
if (x == 0) {
ok = false;
}
++i;
}
print(i);

a) rulati de cateva ori algorimtul;

b) probabilitatea ca alg sa se opreasca dupa i iteratii;

Fie P(i) probabilitatea ca algoritmul să se oprească exact după i iterații.
• Pentru ca algoritmul să ruleze exact i pași, trebuie să obținem i-1 valori de 1, urmate de un 0.
• Deoarece fiecare alegere este independentă și uniformă, probabilitatea de a obține 1 este 1/2,
iar probabilitatea de a obține 0 este 1/2.
• Astfel, probabilitatea ca algoritmul să se oprească exact după i iterații este:
P(i)=(1/2)i-1×1/2=1/2i

3. un algoritm

def algoritm_probabilist(n):
sum = 0
for _ in range(n):
x = [Link]([0, 1])
sum += x
return sum

a) rulati de cateva ori algr;

b) care este media valorilor intoarse de alg pentru un n arbitrar?
Fie S_n suma valorilor x generate, unde fiecare x este o variabilă aleatoare independentă cu
distribuție Bernoulli(1/2), adică: P(x=1)=1/2, P(x=0)=1/2
Fiind suma a n astfel de variabile, valoarea așteptată a lui S_n este:
E[Sn]=E[∑xi]=∑E[xi]
Știm că valoarea așteptată pentru o variabilă Bernoulli(1/2) este:
E[xi]=0×1/2+1×1/2=1/2
Deci:
E[Sn]=∑n*1/2=n×1/2=n/2

4. Input: o functie rand2 care intoarce 0 cu probabilitatea ½ si 1 cu probabilitatea ½.

Output: o functie zar care intoarce un nr intre 0 si 5 fiecare cu aceeasi probabilitate.

def rand2():
# Funcția probabilistă de bază care returnează 0 sau 1 cu probabilitate 0.5
return (some_external_source() % 2) # Simulăm rand2 fără random

def zar():
while True:
# Generăm un număr pe 3 biți: x = b2b1b0
x = (rand2() << 2) | (rand2() << 1) | rand2()
if x < 6: # Acceptăm doar valorile 0-5
return x

Explicație
1. Generare pe 3 biți:
• rand2() << 2 → bitul cel mai semnificativ
• rand2() << 1 → bitul din mijloc
• rand2() → bitul cel mai puțin semnificativ
• Aceasta creează un număr între 0 și 7 (ex. 000 = 0, 111 = 7).
2. Refuzarea numerelor 6 și 7
• Dacă x este 6 sau 7, repetăm procesul pentru a menține probabilități egale.
• Acest lucru nu introduce bias, deoarece distribuția rămâne uniformă între 0 și 5.

5. Input: o functie rand2p care intoarce 0 cu probabilitate p si 1 cu probabilitatea 1-p

Ouput: o functie rand2corect care intoarce 0 sau 1 cu probabilitatea ½

def rand2p():
# Aceasta este funcția probabilistă dată, care returnează 0 cu probabilitate p și 1 cu 1 - p.
# Nu știm valoarea exactă a lui p.
pass # Trebuie înlocuită cu implementarea reală.

def rand2corect():
while True:
 a = rand2p()
b = rand2p()
if a == 0 and b == 1:
return 0
elif a == 1 and b == 0:
return 1
# Dacă (a, b) este (0,0) sau (1,1), repetăm procesul

# Testare
for _ in range(10):
print(rand2corect(), end=" ")

Explicație și Justificare
• Neuniformitatea lui rand2p() este eliminată, deoarece alegem doar cazurile (0,1) și (1,0),
care apar cu aceeași probabilitate.
• Procesul este garantat să se termine, deoarece șansa de a repeta scade exponențial (în
medie durează 1/(2p(1-p)) pași).
• Nu folosim nicio altă sursă de aleatoriu, respectând cerința problemei.

6. INPUT: a0, a1, …, an-1; ai∈1..n; ai!=aj; oricare i,j∈0..n-1; i!=j, k∈N
OUTPUT: i∈N, 0<=i<=n-1; ai. ai=k

alg nedet(a,k) {
//ghicire
int i = rand(0...n-1)
if(a[i] == k) return i;
failure;
}

7.
SSD1 - Cel mai mare sub-sumă posibilă ≤ M
Strategie:
• Alegem nedeterminist un subset S' ⊆ S.
• Verificăm dacă suma elementelor lui S' este ≤ M.
• Găsim cel mai mare astfel de M*.

def SSD1(S, M):

M_star = 0
S_prime = choose(subsets(S)) # Alegem nedeterminat un subset S'
sum_S = sum(S_prime)
if sum_S <= M:
M_star = max(M_star, sum_S) # Ținem minte cea mai mare sumă validă
return M_star
Complexitate: O(2^n*n), deoarece verificăm toate subseturile.
SSD2 - Există un subset cu sumă între K și M?
Strategie:
• Alegem nedeterminist un subset S' ⊆ S.
• Verificăm dacă suma elementelor lui S' este între [K, M].

def SSD2(S, M, K):

S_prime = choose(subsets(S)) # Alegem nedeterminat un subset S'
sum_S = sum(S_prime)
if K <= sum_S <= M:
return True
return False
Complexitate: O(2^n*n), deoarece verificăm toate subseturile.

SSD3 - Există un subset cu sumă exactă M?

Strategie:
• Alegem nedeterminist un subset S' ⊆ S.
• Verificăm dacă suma elementelor lui S' este exact M.

def SSD3(S, M):

S_prime = choose(subsets(S)) # Alegem nedeterminat un subset S'
if sum(S_prime) == M:
return True
return False
Complexitate: O(2^n*n)

Seminar 4 – Algoritmi probabilisti. Complexitate medie

1. Avem un algoritm probabilist care primește un vector v de dimensiune n și returnează numărul de

execuții ale instrucțiunii sum = sum + 1 dintr-o buclă interioară. În această problemă, vectorul v
conține numere întregi, iar fiecare element din vector este ales uniform aleator între 0 și n-1.

max = v[0]
sum = 0
for i = 0 to n-1:
if v[i] > max:
max = v[i]
for j = 0 to n-1:
sum = sum + 1 # Bucla interioară
return sum

Bucla interioară se va executa de n ori pentru fiecare actualizare a lui max.

Numărul de actualizări ale lui max este echivalent cu numărul de elemente care sunt mai
mari decât toate cele anterioare. Acestea sunt denumite "elemente dominante" sau "maximi
parțiali".
 Probabilitatea ca un element v[i] să fie un maxim parțial este 1 / (i + 1).
Așadar, numărul total de actualizări ale lui max în medie este:
E[actualizari de max]=∑1/(i+1)
Deoarece bucla interioară rulează de n ori pentru fiecare actualizare a lui max, numărul total
de execuții ale buclei interioare va fi: E[execuții ale buclei interioare]=n*∑1/(i+1) = n*Hn

2. Pentru acest algoritm probabilist, vrem să calculăm timpul mediu de execuție. Să analizăm pașii
algoritmului și cum putem determina numărul mediu de iterații pe care le va face bucla for, ținând
cont de faptul că vectorul v conține numere naturale, iar fiecare element are o probabilitate
uniformă de a fi par sau impar.

for (i = 0; i < n; ++i) {

if (v[i] % 2 == 0) { # Verifică dacă v[i] este par
break; # Dacă găsește un număr par, se oprește
}
}
return 0;

Probabilitatea ca bucla să se oprească la iterația i este aceea ca primele i elemente să fie

impare (fiecare cu probabilitatea 0.5), iar al i+1-lea element să fie par (cu probabilitatea 0.5). Deci,
probabilitatea ca bucla să se oprească în iterația i este:
P(oprește la iterația i)=(1/2)i×1/2=1/2i+1
Numărul mediu de iterații reprezintă așteptarea pentru numărul de iterații până când
algoritmul se oprește. Acesta poate fi calculat ca suma produselor dintre probabilitatea ca algoritmul
să se oprească în iterația i și numărul de iterații (i). Așadar, timpul mediu de execuție este dat de:
E[timpul de execuție]=∑i×P(oprește la iterația i) = ∑i×1/2i+1

3. a) Aratati ca algoritmul urmator nu este corect:

for (i = 0; i < n; ++i) {
p[i] = i; // Inițializarea permutării
}

for (i = 0; i < n; ++i) {

uniform j from [0..n-1]; // Alege aleator un index j între 0 și n-1
temp = p[i];
p[i] = p[j];
p[j] = temp;
}
ın sensul ın care nu genereaza fiecare permutare cu aceeasi probabilitate. Hint: considerat, i
toate rezultatele posibile pentru n = 3 si calculati probabilitatea fiecaruia. Se recomanda sa se
testeze fiecare dintre algoritmii prezentati.
Descrierea algoritmului:
1. Inițializarea permutării: În prima buclă, algoritmul setează fiecare element al vectorului p
la valoarea sa corespunzătoare (p[i] = i), adică vectorul p va arăta astfel: [0, 1, 2, ..., n-1].
 2. Generarea permutării: În a doua buclă, pentru fiecare element p[i], alegem aleator un alt
element p[j] din intervalul [0..n-1] și schimbăm valorile acestora. Deci, fiecare element din
vector poate fi schimbat cu orice alt element aleatoriu, inclusiv cu el însuși.
Problema algoritmului:
1. Probabilitatea pentru fiecare permutare:
Algoritmul, așa cum este, nu garantează că fiecare permutare va avea aceeași probabilitate,
iar acest lucru poate fi demonstrat pentru un caz simplu, cum ar fi n = 3.
Să presupunem că avem n = 3. Vectorul inițial va fi:
p=[0,1,2]
În prima iterație a celei de-a doua bucle (când i = 0), algoritmul alege un j aleatoriu din
intervalul [0, 1, 2]. Dacă j = 0, atunci p[0] și p[0] sunt schimbate, ceea ce nu schimbă vectorul. Dacă
j = 1 sau j = 2, se schimbă valorile dintre p[0] și p[1] sau p[0] și p[2].
La a doua iterație (când i = 1), se alege un alt index j între 0 și 2 pentru a schimba valorile
dintre p[1] și p[j]. Aici se întâmplă același lucru.
Rezultatul: Această metodă nu garantează ca toate permutările să fie generate cu aceeași
probabilitate, deoarece numărul de schimbări depinde de ordinea în care alegem valorile pentru i și
j, iar anumite permutări vor apărea mai frecvent decât altele.
2. Exemplu pentru n = 3:
Să vedem ce se întâmplă la n = 3. Există 6 permutări posibile ale vectorului [0, 1, 2]:
• Permutările posibile:
[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]
Acum, să analizăm probabilitatea de a obține fiecare permutare folosind algoritmul propus.
• Permutarea [0, 1, 2]:
• p[0] și p[0] sunt schimbate (probabilitate 1/3)
• p[1] și p[1] sunt schimbate (probabilitate 1/3)
• p[2] și p[2] sunt schimbate (probabilitate 1/3)
• Permutarea [0, 2, 1]:
• p[0] și p[0] sunt schimbate (probabilitate 1/3)
• p[1] și p[2] sunt schimbate (probabilitate 1/3)
• p[2] și p[1] sunt schimbate (probabilitate 1/3)
În acest exemplu, veți observa că unele permutări vor avea o probabilitate mai mare de a
apărea decât altele din cauza ordinii în care se fac schimbările.

Seminar 5 – NP Completitudine

Un algoritm determinist este un algoritm care, pentru un anumit input, urmează o

secvență fixă de pași și produce întotdeauna același output.
Un algoritm nedeterminist este un algoritm care, pentru un anumit input, are mai multe
fire de executie si poate produce rezultate diferite.
O problemă de optimizare este o problemă computațională în care obiectivul este găsirea
celei mai bune soluții conform unui criteriu specific.
O problemă de decizie este o problemă computațională în care răspunsul așteptat este
"DA" sau "NU".
 Clasa de probleme P
Clasa P (PTIME) = {X | X este o problemă de decizie si există un algoritm determinist
polinomial ı̂n cazul cel mai nefavorabil pentru X}

1. 2-COL
INPUT: un graf neorientat G=(V,E), V este mulțimea de noduri (vârfuri), cu ∣V∣=n, E⊆V×V
este mulțimea muchiilor, cu ∣E∣=m, O muchie (u,v)∈E înseamnă că există o
conexiune între nodurile u și v, fiecare nod vi∈V are un grad d(vi) dat de numărul de
noduri adiacente
OUTPUT: f(G)={1 daca G este 2-colorabil; 0 altfel}

DEMONSTRATIE:
Pentru a demonstra că 2-COL aparține clasei P, trebuie să arătăm că poate fi rezolvată în
timp polinomial.
Pasii algoritmului:
• Alegem un nod de start și îl colorăm cu culoarea 1.
• Parcurgem graful folosind BFS (sau DFS).
• Pentru fiecare nod vizitat:
• Dacă nu este colorat, îl colorăm cu culoarea opusă față de părinte.
• Dacă este deja colorat și are aceeași culoare ca părintele → graful NU este bipartit,
deci nu poate fi 2-colorabil.
• Repetăm procesul pentru toate componentele conexe.
• Dacă nu găsim conflicte, returnăm "Graful este 2-colorabil".
• Algoritmul BFS/DFS rulează în O(V + E) (timp polinomial).
• Deci, 2-COL ∈ P, deoarece se poate rezolva determinist în timp polinomial.

2. 2-SAT
INPUT: X={x1,x2,…,xn}, Φ=C1∧C2∧⋯∧Cm in CNF, Ci=(ℓi1∨ℓi2)
OUTPUT: Dacă există o soluție validă, returnăm "SATISFIABIL" și o afectare validă.
Dacă nu există nicio afectare validă, returnăm "NESATISFIABIL".

DEMONSTRATIE:
• Se construiește un graf de implicație G=(V,E), unde:
• Nodurile sunt literalii (xj și ¬xj).
• Muchiile reprezintă implicațiile logice.
Construim graful de implicație în timp O(n+m).
• Calculăm componentele tare conexe
• Dacă un literal și negarea lui apar în aceeași componentă tare conexă, formula nu este
satisfiabilă.
Complexitatea totală este O(n+m) (liniară).
Algoritmul este determinist și rulează în timp polinomial.
• Deoarece P conține toate problemele care pot fi rezolvate într-un timp polinomial, rezultă
că 2-SAT aparține clasei P
3. Sortarea unui vector
INPUT: V=(v1,v2,…,vn), vi∈ {1, …, n}
OUTPUT: V′=(v1′,v2′,…,vn′), vi′ ∈ {1, …, n}, v1′≤v2′≤⋯≤vn′

DEMONSTRATIE:
Pentru a demonstra că problema sortării unui vector aparține clasei P, trebuie să arătăm
că poate fi rezolvată de un algoritm determinist într-un timp polinomial față de dimensiunea
inputului. Există algoritmi deterministi cunoscuți care sortează un vector în timp polinomial:
• MergeSort – timp O(nlogn)
• QuickSort (în medie) – timp O(nlogn)
• HeapSort – timp O(nlogn)
• BubbleSort, InsertionSort, SelectionSort – timp O(n^2) (mai puțin eficienți, dar tot
polinomiali)
Sortarea este o problemă computațională care poate fi rezolvată eficient folosind algoritmi
deterministi în timp O(nlogn). Deoarece O(nlogn) este polinomial, rezultă că problema sortării
aparține clasei P.

4. Cautarea intr-o lista sortata

INPUT: V=(v1,v2,…,vn), v1≤v2≤⋯≤vn, (V,x)∈Sn×S.
OUTPUT: {1, daca exista i astfel incat vi=x; 0 daca x nu apartine V}

DEMONSTRATIE:
Pentru a demonstra că problema căutării într-o listă sortată aparține clasei P, trebuie să
arătăm că poate fi rezolvată de un algoritm determinist într-un timp polinomial față de
dimensiunea inputului.
Există două metode deterministe principale pentru căutare:
(a) Căutare Liniară
• Parcurge lista secvențial și compară fiecare element cu x.
• Are complexitate O(n).
(b) Căutare Binară (Binary Search)
• Alege elementul din mijloc și compară cu x.
• Dacă x este mai mic, caută în prima jumătate, altfel caută în a doua jumătate.
• Se repetă până când se găsește x sau se termină lista.
• Are complexitate O(logn).
Căutarea într-o listă sortată se poate rezolva eficient cu căutare binară în O(logn), care este
polinomială. Prin urmare, problema aparține clasei P.

5. Inmultirii a doua matrici

INPUT: Două matrici A∈Rm×p și B∈Rp×n, A=(aij)m×p, B=(bjk)p×n
OUTPUT: O matrice rezultat C∈Rm×n, unde: C=(cik)m×n,cik=∑ de la j=1 la p din aij * bjk

DEMONSTRATIE:
Algoritmul clasic pentru înmulțirea a două matrici presupune trei bucle for:
• for i=1 to m(randuri din A)
• for k=1 to n(coloane din B)
• for j=1 to p(elemente comune ın ınmulțire) cik=cik+aij*bjk
 Complexitatea acestui algoritm este: O(m*p*n) care este polinomială în dimensiunile
matricelor.
Deoarece există un algoritm determinist care rulează în timp polinomial, rezultă că
problema înmulțirii a două matrici aparține clasei P.

6. SHORTEST-PATH
INPUT: un graf G=(V,E,w) și două noduri s,t∈V, V este mulțimea de noduri, E⊆V×V este
mulțimea de muchii, w:E→R+ este o funcție de ponderi asociate muchiilor, s,t∈V sunt nodurile
sursă și destinație
OUTPUT: un drum de cost min P=(v0,v1,...,vk) cu v0=s și vk=t, cost(P)∑w(vi,vi+1)

DEMONSTRATIE
Problema SHORTEST-PATH poate fi rezolvată într-un timp polinomial de un algoritm
determinist. De exemplu:
Algoritmul lui Dijkstra este un algoritm determinist care, pentru un graf cu V noduri și E
muchii, rulează în timp polinomial în funcție de V și E, adică în O((V+E)logV)

7. EULER-TOUR
INPUT: un graf neorientat G=(V,E),
OUTPUT: Fiecare muchie e∈E leagă două noduri u și v (adică e=(u,v)).

DEMONSTRATIE
Algoritmul lui Hierholzer este cel mai cunoscut algoritm pentru rezolvarea problemei
EULER-TOUR. Acesta funcționează într-un timp liniar în funcție de numărul de muchii și noduri,
adică în O(E), unde E este numărul de muchii din graf.
Algoritmul lui Hierholzer:
1. Verificarea condițiilor pentru turul eulerian:
• Verificăm dacă toate nodurile au gradul par și dacă graful este conectat. Dacă oricare
dintre aceste condiții nu este îndeplinită, nu există un tur eulerian.
2. Construirea turului:
• Dacă graful satisface condițiile pentru a avea un tur eulerian, putem construi turul
folosind algoritmul lui Hierholzer. Acesta selectează un drum arbitrar care nu a fost
încă parcurs complet, parcurge o muchie care nu a fost traversată și repetă acest
proces până când toate muchiile au fost vizitate.
3. Complexitatea:
• Algoritmul parcurge fiecare muchie o singură dată. Într-un graf cu E muchii, acest
proces va dura O(E) pași.

Clasa de probleme NP
Clasa NP (NPTIME) = {X | X este o problemă de decizie si există un algoritm nedeterminist
polinomial ı̂n cazul cel mai nefavorabil pentru X}
O problemă X este NP-dificilă dacă orice problemă Y∈NP se poate reduce polinomial la X,
adică: Y≤pX,∀Y∈NP.
O problemă X este NP-completă dacă:
1. Este în NP: Există un algoritm de verificare care poate verifica o soluție în timp polinomial.
X∈NP
 2. Este NP-dificilă: Orice problemă Y∈NP se poate reduce polinomial la X, adică:
Y≤pX,∀Y∈NP

1. VERTEX-COVER
INPUT: un graf neorientat G = (V, E), k ∈ N
OUTPUT: există V’⊆ V a.ı̂. |V’| ≤ k si pentru orice muchie {u, v} ∈ E avem u ∈ V’ sau
v ∈ V’ ?

DEMONSTRATIE
Pentru a arăta că Vertex Cover este NP-completă, facem o reducere polinomială de la 3-
SAT (un problem NP-completă):
• Pasul 1: Transformarea formulei 3-SAT într-un graf
• Fiecare literă și negarea sa din formula 3-SAT devin noduri într-un graf.
• Fiecare clauză cu 3 literale devine un triunghi de 3 noduri conectate, fiecare nod
corespunzând unui literal sau complementul acestuia.
• Pasul 2: Aplicarea problemei Vertex Cover
• Dacă formula 3-SAT este satisfiabilă, există o alegere de literale adevărate care poate
fi reprezentată printr-un vertex cover de dimensiune m.
• Vertex cover-ul va acoperi muchiile între nodurile literale și clauze, acoperind astfel
întreaga formulă.
• Vertex Cover este în NP și poate fi redusă în mod polinomial din 3-SAT, ceea ce dovedește
că este NP-completă.

2. HAMILTONIAN-CIRCUIT
INPUT: un graf orientat G = (V, E);
OUTPUT: există un circuit hamiltonian ı̂n G? (o permutare v1 , v2 , . . . vn a nodurilor din V
astfel ı̂ncât vi , vi+1 ∈ E (pentru 1 ≤ i < n) si vn , v1 ∈ E))

DEMONSTRATIE
Pentru a demonstra că problema Hamiltonian Circuit este NP-completă, urmează acești
pași sintetizați:
1. Hamiltonian Circuit este în NP:
• Problema Hamiltonian Circuit se află în clasa NP deoarece, dat un circuit posibil, putem
verifica într-un timp polinomial dacă este un circuit valid (vizitează fiecare nod o singură
dată și se întoarce la nodul de început).

2. Reducerea din 3-SAT la Hamiltonian Circuit:

• Problema 3-SAT (NP-completă) este redată la Hamiltonian Circuit astfel:
• Fiecare variabilă și complementul său devin noduri într-un graf.
• Fiecare clauză (cu 3 literale) devine un triunghi de noduri conectate.
• Adăugăm muchii între noduri astfel încât un circuit Hamiltonian valid să reprezinte o
asignare de valori care satisface formula 3-SAT.
Hamiltonian Circuit este NP-completă deoarece este în NP și există o reducere
polinomială de la problema NP-completă 3-SAT.
3. HAMILTONIAN-TOUR
INPUT: un graf orientat G = (V, E);
OUTPUT: există un tur hamiltonian ı̂n G? (o permutare v1 , v2 , . . . vn a nodurilor din V
astfel ı̂ncât vi , vi+1 ∈ E (pentru 1 ≤ i < n))

DEMONSTRATIE
Pentru a demonstra că problema Hamiltonian Tour este NP-completă, urmează pașii
sintetizați:
1. Hamiltonian Tour este în NP:
• O soluție posibilă este un ciclu Hamiltonian (vizitează fiecare nod exact o dată și se întoarce
la nodul de început).
• Verificarea validității acestui ciclu se face într-un timp polinomial (O(n)), deci Hamiltonian
Tour este în NP.
2. Reducerea din 3-SAT la Hamiltonian Tour:
• Fiecare problemă 3-SAT (NP-completă) poate fi transformată într-un graf în care un ciclu
Hamiltonian va reprezenta o soluție pentru formula 3-SAT.
• Reducerea implică construirea unui graf unde nodurile și muchiile reflectă literalele și
clauzele formulei 3-SAT, iar un ciclu Hamiltonian valid reprezintă satisfacerea formulei.
Hamiltonian Tour este NP-completă deoarece este în NP și există o reducere polinomială
de la problema NP-completă 3-SAT.

4. MAXIMUM-INDEPENDENT-SET
INPUT: un graf neorientat G = (V, E), k ∈ N
OUTPUT: există V’ ⊆ V a.ı̂. |V’| ≥ k si pentru orice u, v ∈ V’ , avem {u, v} nu ∈ E?

DEMONSTRATIE
Pentru a demonstra că problema Maximum Independent Set este NP-completă, urmează
pașii sintetizați:
1. Problema Maximum Independent Set este în NP:
• O soluție posibilă este un subset de noduri care constituie un set independent.
• Verificarea dacă acest subset este independent și dacă dimensiunea acestuia este ≥k se face
într-un timp polinomial (O(∣E∣)).
• Prin urmare, problema este în NP.
2. Reducerea din Vertex Cover la Maximum Independent Set:
• Problema Vertex Cover (NP-completă) poate fi redusă la Maximum Independent Set.
• Un vertex cover de dimensiune k într-un graf are complementul său, un set
independent de dimensiune ∣V∣−k.
• Astfel, un vertex cover de dimensiune k echivalează cu un set independent de
dimensiune cel puțin ∣V∣−k.
• Reducerea este realizată într-un timp polinomial.
5. CLIQUE
INPUT: un graf neorientat G = (V, E), k ∈ N
OUTPUT: există V⊆ V a.ı̂. |V| ≥ k si pentru orice u ∈ V’, v ∈ V’, u != v avem muchia
{u, v} ∈ E?

DEMONSTRATIE
Pentru a demonstra că problema Clique este NP-completă, urmează pașii sintetizați:
1. Problema Clique este în NP:
• O soluție posibilă pentru problema Clique este un subset de k noduri.
• Verificarea dacă acest subset formează un clique (adică dacă toate perechile de noduri sunt
conectate prin muchii) se face într-un timp polinomial (O(k2)).
• Prin urmare, problema este în NP.
2. Reducerea din Vertex Cover la Clique:
• Problema Vertex Cover (NP-completă) poate fi transformată într-o instanță a problemei
Clique în graful complementar.
• Un vertex cover de dimensiune k într-un graf G echivalează cu un clique de
dimensiune ∣V∣−k în graful complementar G′.
• Reducerea se face într-un timp polinomial.
Clique este în NP și există o reducere polinomială de la Vertex Cover la aceasta.

6. PARTITION
INPUT: S={x1,x2,…,xn}
OUTPUT: Există două subseturi S1⊆S și S2⊆S astfel încât:
• S1∩S2=∅ (adică sunt disjuncte),
• S1∪S2=S (adică uniunea lor este S),
• ∑xi∈S1xi=∑xj∈S2xj.

DEMONSTRATIE
Pentru a demonstra că problema Partition este NP-completă, realizăm următoarele pași
sintetizați:
1. Partition este în NP:
• O soluție posibilă pentru problema Partition este un subset S1⊆S.
• Verificarea dacă suma elementelor din S1 este egală cu suma elementelor din S2
=S∖S1 se face într-un timp polinomial, deoarece presupune doar calcularea sumelor
celor două subseturi.
• Astfel, Partition este în NP.
2. Reducere din Subset-Sum la Partition:
• Subset-Sum este o problemă NP-completă.
• Dăm ca input pentru problema Partition un set S′={x1,x2,…,xn,T}, adăugând un
număr T la setul S.
• Dacă putem împărți setul S′ în două subseturi cu suma egală, atunci suma unui subset
va fi exact T, ceea ce echivalează cu problema Subset-Sum.
3. Concluzie:
• Deoarece Partition este în NP și există o reducere polinomială din Subset-Sum
(NP-completă) la Partition, rezultă că Partition este NP-completă.
7. SUBSET-SUM
INPUT: S ⊆ N, t ∈ N
OUTPUT: există S ⊆ S astfel ı̂ncât Σx∈S’ x = t?

DEMONSTRATIE
Pentru a demonstra că problema Subset Sum este NP-completă, urmează pașii sintetizați:
1. Problema Subset Sum este în NP:
• O soluție posibilă este un subset S′ din S.
• Verificarea dacă suma elementelor din subsetul S′ este egală cu T se face într-un timp
polinomial, O(n).
• Astfel, problema este în NP.
2. Reducerea din 3-SAT la Subset Sum:
• 3-SAT este NP-completă, iar reducerea se face într-un timp polinomial.
• Fiecare literă din formula 3-SAT este reprezentată de un număr.
• Clauzele sunt reprezentate de combinații de numere.
• Un subset de numere din 3-SAT poate fi ales astfel încât suma să fie T dacă și numai
dacă formula 3-SAT este satisfăcută.
Subset Sum este în NP și există o reducere polinomială de la 3-SAT la [Link] urmare,
Subset Sum este NP-completă.

8. 3-SAT
INPUT: Φ=C1∧C2∧⋯∧Cm, Φ în CNF, unde fiecare Ci este o clauză și are forma:
Ci=(li1∨li2∨li3)
OUTPUT: True (sau 1) dacă există o asignare de valori booleene pentru variabilele
x1, x2, …, xn astfel încât formula Φ să fie satisfăcută (adică fiecare clauză să fie adevărată).
False (sau 0) dacă nu există nicio asignare de valori booleene pentru variabile care să
satisfacă formula Φ.

DEMONSTRATIE
Demonstratia ca problema 3-SAT este NP-completă:
1. 3-SAT este în NP:
• O soluție pentru problema 3-SAT este o asignare de valori pentru variabilele
booleene.
• Verificarea dacă formula booleeană este satisfăcută pentru această asignare se face
într-un timp polinomial (evaluând fiecare clauză). Astfel, 3-SAT este o problemă în
NP.
2. Reducerea din SAT la 3-SAT:
• SAT este o problemă NP-completă.
• Orice formulă CNF (Conjunctivă Normal Form) din SAT poate fi transformată într-o
formulă 3-SAT.
• Dacă o clauză are mai mult de 3 literale, o descompunem într-o combinație de clauze
cu 3 literale folosind literale suplimentare.
• Dacă o clauză are mai puțin de 3 literale, o completăm cu literale suplimentare până
ajungem la 3.
 3. Concluzie:
• Deoarece 3-SAT este în NP și orice problemă NP-completă (SAT) poate fi redusă la
3-SAT într-un timp polinomial, 3-SAT este NP-completă.

9. 3-COL
INPUT: G = (V, E)
OUTPUT: este G 3-colorabil?

DEMONSTRATIE
Pentru a demonstra că problema 3-Coloring este NP-completă, pașii sintetizați sunt
următorii:
1. Problema 3-COL este în NP:
• O soluție posibilă este o colorare a nodurilor grafului cu cel mult 3 culori.
• Verificarea dacă această colorare este validă (adică nodurile adiacente nu au aceeași culoare)
se face într-un timp polinomial.
• Prin urmare, 3-COL este în NP.
2. Reducerea din 3-SAT la 3-Coloring:
• 3-SAT (o problemă NP-completă) poate fi transformată într-un graf.
• Fiecare literă și clauză din formula 3-SAT este reprezentată de noduri și muchii în graf.
• Construcția grafului este făcută astfel încât să existe o colorare validă cu 3 culori dacă și
numai dacă formula 3-SAT este satisfăcută.
• Reducerea se face într-un timp polinomial.
Concluzie:
• 3-Coloring este în NP și există o reducere polinomială de la 3-SAT la aceasta.
• Prin urmare, 3-Coloring este NP-completă.

10. CIRCUIT-SAT
INPUT: un circuit combinat, ional C
OUTPUT: există date de intrare astfel ı̂ncât circuitul să producă output-ul 1?

DEMONSTRATIE
Pentru a demonstra că problema Circuit-SAT este NP-completă, pașii sintetizați sunt
următorii:
1. Problema Circuit-SAT este în NP:
• O soluție posibilă este o asignare de valori booleene pentru intrările circuitului.
• Verificarea dacă această asignare satisface ieșirile dorite se face într-un timp polinomial,
deoarece evaluarea unui circuit logic este un proces polinomial.
• Prin urmare, Circuit-SAT este în NP.
2. Reducerea din 3-SAT la Circuit-SAT:
• 3-SAT este o problemă NP-completă.
• Fiecare instanță a 3-SAT este transformată într-un circuit logic, unde fiecare literă este
reprezentată de un bit și fiecare clauză de o combinație de porți logice.
• Un circuit va evalua formula 3-SAT și va fi satisfăcut dacă și numai dacă formula este
satisfăcută.
Concluzie:
• Circuit-SAT este în NP.
 • Există o reducere polinomială din 3-SAT (NP-completă) la Circuit-SAT.
• Prin urmare, Circuit-SAT este NP-completă.

11. LONGEST-PATH
INPUT: Graf G=(V,E), vârf de început s=v1
OUTPUT: lungimea celui mai lung drum: 3 (drumul fiind v1→v3→v4, sau v1→v2→v3
→v4).

DEMONSTRATIE:
Sintetizarea demonstrației că problema Longest-Path este NP-completă:
1. Longest-Path este în NP:
• Problema Longest-Path este o problemă de decizie, unde întrebarea este dacă există
un drum de lungime cel puțin k într-un graf. Se poate verifica într-un timp
polinomial, deoarece, având drumul, putem contoriza numărul de muchii pentru a
verifica lungimea.
2. Reducerea din Hamiltonian-Path la Longest-Path:
• Problema Hamiltonian-Path (care este NP-completă) este redusă la Longest-Path.
Dacă există un drum Hamiltonian într-un graf G, atunci există un drum de lungime
∣V∣−1 (unde ∣V∣ este numărul de vârfuri din graf). Astfel, întrebarea dacă există un
drum Hamiltonian este echivalentă cu întrebarea dacă există un drum de lungime
∣V∣−1 în problema Longest-Path.
3. Concluzie:
• Deoarece Longest-Path este în NP și Hamiltonian-Path poate fi redusă la Longest-
Path într-un timp polinomial, Longest-Path este NP-completă.

Seminar 6 – Algoritmi de cautare pe siruri

I. Algoritmul KMP
Ideea principală este de a refolosi informatia obtinută prin comparatiile de la un anumit
deplasament pentru a reduce din comparatiile necesare la deplasamentele ulterioare.
O frontieră a unui șir este cel mai lung prefix propriu (adică nu tot șirul) care este și sufix
al acelui șir.
După o nepotrivire în KMP, nu reluăm căutarea de la începutul pattern-ului. În schimb,
ne uităm la frontiera șirului potrivit până atunci și repoziționăm pattern-ul astfel încât această
frontieră să se alinieze cu sufixul din text.
Componentele principale
1. Construirea tabelului "lps" (longest prefix suffix):
• Pentru fiecare poziție din pattern, determină cea mai lungă secvență proprie care e și
prefix și sufix.
2. Parcurgerea textului cu ajutorul tabelului lps, evitând comparații repetate.

Exemplu practic:
Pentru pattern-ul: "ABABAC" parcurgem fiecare poziție și construim:
i pattern[i] lps[i] Explicație
0 A 0 Nu are frontieră
1 B 0 A≠B
2 A 1 A = A (prefix A)
3 B 2 AB = AB
4 A 3 ABA = ABA
5 C 0 nu se potrivește, niciun sufix/prefix

Rezultatul: lps = [0, 0, 1, 2, 3, 0]

Exemplu:
TEXT = HIABABXABABXABABY (lungime n = 17)
pattern = ABABXABABY (lungime m = 10)

PASUL 1: Construim LPS, sau calculam functia prefix, pentru pattern

Pattern: ABABXABABY
Index: 0123456789
Aplicăm algoritmul de construcție LPS:
• i = 0: A → lps[0] = 0
• i = 1: B ≠ A → lps[1] = 0
• i = 2: A = A → len = 1, lps[2] = 1
• i = 3: B = B → len = 2, lps[3] = 2
• i = 4: X ≠ A → backtrack: len = lps[1] = 0, lps[4] = 0
• i = 5: A = A → len = 1, lps[5] = 1
• i = 6: B = B → len = 2, lps[6] = 2
• i = 7: A = A → len = 3, lps[7] = 3
• i = 8: B = B → len = 4, lps[8] = 4
• i = 9: Y ≠ X → backtrack: len = lps[3] = 2, apoi Y ≠ A → len = lps[1] = 0, lps[9] = 0
LPS = [0, 0, 1, 2, 0, 1, 2, 3, 4, 0]

PASUL 2: Căutăm pattern-ul în TEXT cu KMP

Inițial:
• i = 0 (index în text)
• k = 0 (index în pattern)
🔸 i = 0, k = 0:
T[0] = H, P[0] = A → nu se potrivesc
➡️k = 0, deci i = i + 1 = 1
🔸 i = 1, k = 0:
T[1] = I, P[0] = A → nu se potrivesc
➡️i = 2
🔸 i = 2, k = 0:
T[2] = A, P[0] = A → se potrivesc
➡️k = 1
T[3] = B, P[1] = B → se potrivesc
➡️k = 2
T[4] = A, P[2] = A → se potrivesc
➡️k = 3
T[5] = B, P[3] = B → se potrivesc
➡️k = 4
T[6] = X, P[4] = X → se potrivesc
➡️k = 5
T[7] = A, P[5] = A → se potrivesc
➡️k = 6
T[8] = B, P[6] = B → se potrivesc
➡️k = 7
T[9] = A, P[7] = A → se potrivesc
➡️k = 8
T[10] = B, P[8] = B → se potrivesc
➡️k = 9
T[11] = X, P[9] = Y → ❌ NU se potrivesc

Nepotrivire la k = 9
Folosim LPS:
• lps[9] = 0
➡️k devine 0 (niciun sufix util), dar i rămâne 2
➡️pattern-ul sare direct la poziția i = i + k - lps[k] = 2 + 9 - 0 = 11
🔄 Reluăm de la i = 11, k = 0
T[11] = X, P[0] = A → ❌
➡️i = 12
T[12] = A, P[0] = A → ✔️
➡️k = 1
T[13] = B, P[1] = B → ✔️
➡️k = 2
T[14] = A, P[2] = A → ✔️
➡️k = 3
T[15] = B, P[3] = B → ✔️
➡️k = 4
T[16] = Y, P[4] = X → ❌
➡️backtrack folosind lps[4] = 0, deci k = 0
➡️i = 17 > n - m → terminat

Exercitiul 1: In timpul executiei algoritmului KMP, se verifica daca pattern-ul ababa apare ın
textul bbabaababa la pozitia i = 2. Primele k = 3 caractere se potrivesc, iar al 4-lea caracter nu se
potriveste. Care este urmatorea pozitie a pattern-ului, dupa procesarea nepotrivirii? Care este
numarul de caractere care se potrivesc sigur la noul deplasament?
Date:
• Pattern: ababa
• Text: bbabaababa
• Poziția curentă în text: i = 2
• Primele k = 3 caractere se potrivesc, dar al patrulea nu.
Pas 1: Calculăm prefix function (pi[]) pentru pattern-ul ababa
Prefix function π[i] = lungimea celui mai lung prefix propriu al P[0..i] care este și sufix.
P[i] = [‘a’, ‘b’, ‘a’, ‘b’, ‘a’] π[i] = [0 0 1 2 3]

Pas 2: Ce facem la nepotrivire după 3 potriviri (k = 3)

Avem o nepotrivire la k = 3 (adică pattern-ul a mers până la poziția P[3]), dar T[5] ≠ P[3].
Algoritmul KMP spune: când apare o nepotrivire la poziția k, ne uităm în π[k-1], adică π[2] = 1.
→ Așadar, deplasăm pattern-ul astfel încât poziția π[2] = 1 (deci prefixul a) să fie aliniat cu
poziția corespunzătoare în text.
Următoarea poziție a pattern-ului în text va fi i = 2 + (k - π[k-1]) = 2 + (3 - 1) = 4.
La noul i = 4, vor fi potrivite sigur π[k-1] = 1 caractere, adică a.

II. Alboritmul Boyer-Moore

Boyer-Moore parcurge patternul de la dreapta la stânga, și în caz de nepotrivire folosește
informații preprocesate pentru a decide cu cât poate deplasa patternul astfel încât să sară peste cât
mai multe caractere din text.

Important:
• cautarea se face de la dreapta la stanga;
• indentificam caracterul rau (BC) si sufixul bun (GS);
• BC → caracterul din text care nu s-a potrivit;
• GS → overlap-ul (potrivirea)

Componente cheie
1. Regula caracterului rău (Bad Character Rule)
• Dacă apare o nepotrivire, te uiți la caracterul din text care a provocat-o.
• Muti patternul astfel încât ultima apariție a acelui caracter în pattern să se alinieze cu
caracterul din text. Dacă nu apare în pattern, poți muta patternul complet după acel caracter.
2. Regula sufixului bun (Good Suffix Rule)
• Dacă ai o potrivire parțială la sfârșitul patternului, dar apare o nepotrivire, încerci să aliniezi
un altă apariție a acestui sufix în pattern sau un prefix potrivit.
• Astfel eviți să reîncepi căutarea de la zero.

Pașii algoritmului
1. Preprocesare:
• Construiești două tabele:
• Tabelul de caracter rău – O hartă cu ultima poziție a fiecărui caracter din
pattern.
• Tabelul de sufix bun – Spune cât de mult poți să muți patternul dacă un sufix
s-a potrivit.
2. Căutare:
• Aliniezi patternul cu textul.
• Compari caracterele de la dreapta la stânga.
• La nepotrivire, alegi între cele două reguli (cea care dă deplasarea mai mare).
• Repeți până când patternul nu mai încape în text.
Exemplu
Text: "ABAAABCD"
Pattern: "ABC"

1. Tabelul "Caracter Rău" (Bad Character Table)

Pentru fiecare caracter din pattern, memorăm ultima poziție la care apare:

Caracter Poziție în pattern

A 0
B 1
C 2

2. 🔹 Regula Sufixului Bun – Good Suffix Table

Pattern: "A B C"
Posibilități de sufixuri potrivite:
• C – nu apare în altă parte
• BC – nu apare
• ABC – nu apare
Nu există sufixuri interne care se regăsesc și ca prefix (în pattern).
Deci nu avem niciun sufix bun util → fallback-ul este deplasarea completă cu m = 3.

Căutarea
Pasul 1: Aliniere inițială
Aliniem patternul sub text:
T: A B A A A B C D
ABC
Comparam de la dreapta la stânga:
• C (pattern) vs A (text, poziția 2) → ❌ nepotrivire
• Caracterul rău este A
• În pattern, A este la poziția 0
• Nepotrivirea a fost la poziția 2 (index în pattern)
• Calculăm deplasarea: max(1, 2 - last(A)) = max(1, 2 - 0) = 2

Pasul 2: Mutăm patternul cu 2 poziții:

T: A B A A A B C D
ABC
Comparăm:
• C (pattern) vs A (text[4]) → ❌
• Caracter rău = A, ultima apariție = 0
• Nepotrivirea a fost la index 2
• Deplasare: 2

Pasul 3: Mutăm patternul cu încă 2 poziții:

T: A B A A A B C D
ABC
Comparăm:
• C (pattern) vs C (text[6]) → ✅
 • B (pattern[1]) vs B (text[5]) → ✅
• A (pattern[0]) vs A (text[4]) → ✅
Toate caracterele se potrivesc ✅
Important:
Text = A B A B C A A B A C
pattern = C A A B
• caracterul rau este primul B din Text, iar sufixul bun este primul sir ‘AB’ de dupa BC;
• BC rule = aliniez aparitia lui BC din Text cu alta aparitie din pattern;
• GS rule = aliniez aparitia GS din Text cu penultima aparitie a sa din pattern;
• BC[i] → pozitia ultimei aparitii a caracterului in P / -1 daca nu apare;
• GS[i] → pozitia penultimei aparitii a sufixului P[i...m-1] in P;

Exercitiul 1:
1. Pattern: oxoxoyoxo
• BC[i] = [‘x’: 6, ‘o’: 7, ‘y’: 4]
• GS[i] = [9, 9, 9, 9, 9, 6, 6, 3, 1]
2. Pattern: ABCWABCYABXAB
• BC[i] = [‘A’: 11, ‘B’: 12, ‘C’: 6, ‘W’: 3, ‘X’: 10, ‘Y’: 7]
• GS[i] = [13, 13, 13, 13, 13, 13, 13, 13, 10, 7, 4, 1, 1]
◦ h[i] = [2 1 0 0 2 1 0 0 2 1 0 0 0]
◦ f[i] = [0 0 0 0 1 2 3 0 1 2 0 1]
◦ R[i] = []
◦ g[i] = []

III. Algoritmul Rabin-Karp

Algoritmul Rabin-Karp este un algoritm eficient pentru căutarea unui șir (pattern) într-
un text, bazat pe utilizarea funcțiilor de hashing. În loc să compare caracterele unul câte unul, ca
KMP sau Boyer-Moore, Rabin-Karp transformă șirurile în valori numerice (hash) și compară
aceste valori.
Ideea principală
1. Se calculează o valoare hash pentru pattern și pentru fiecare subșir de lungime egală din
text.
2. Dacă valorile hash sunt egale, se face o comparare caracter cu caracter pentru confirmare
(pentru a evita coliziunile).
3. Dacă nu sunt egale, se continuă căutarea.

Important:
• asociaza un numar pattern-ului si subsirurilor de lungime m din text;
• E – alfabet; |E| = k => fiecare litera un are asociata un nr de la 0 la k-1;
• P = A B C D , A-0, B-1, C-2, p-prim; p=23;
◦ 0 1 23
• h(P) = ( 0*26^3 + 1*26^2 + 2*26^1 + 0*26^0 ) %p
• pot aparea subsiruri diferite cu valori hash egale => verificare;
Cum funcționează?
Presupunem că:
• P este pattern-ul, de lungime m
• T este textul, de lungime n
• H(x) este funcția hash pentru un șir x
Pași:
1. Calculăm hash-ul pattern-ului: H(P)
2. Calculăm hash-ul primului subșir de lungime m din text: H(T[0..m-1])
3. Pentru fiecare poziție i de la 0 la n - m:
• Dacă H(P) == H(T[i..i+m-1]), atunci comparăm direct șirurile caracter cu caracter
• Dacă se potrivesc, am găsit o apariție
• Dacă nu, continuăm
4. Pentru eficiență, folosim rolling hash: hash-ul pentru T[i+1..i+m] se calculează rapid din
T[i..i+m-1], fără recalcul complet.

Formula hash-ului (rolling hash)

Se folosește o bază b (ex: 256 pentru caractere ASCII) și un modul q (prim):
H(s) = (s[0]*b^(m-1) + s[1]*b^(m-2) + ... + s[m-1]*b^0) mod q

La fiecare pas:
H(T[i+1..i+m]) = (b * (H(T[i..i+m-1]) - T[i]*b^(m-1)) + T[i+m]) mod q

Exemplu
• Pattern: abc
• Text: ababcabcabc
• Baza hash-ului: b = 256 (pentru caractere ASCII)
• Modulul: q = 101 (un număr prim pentru a evita coliziunile)

Pasul 1: Calcularea hash-ului pentru pattern și primul subșir din text

1.1 Calculăm hash-ul pentru pattern-ul P = "abc"
Folosim formula pentru hash:
H(s) = (s[0]*b^(m-1) + s[1]*b^(m-2) + ... + s[m-1]*b^0) mod q
Pentru pattern-ul abc, având lungimea m = 3:
H("abc") = (a * b^(3-1) + b * b^(3-2) + c * b^(3-3)) mod 101
H("abc") = (97 * 256^2 + 98 * 256^1 + 99 * 256^0) mod 101
H("abc") = (97 * 65536 + 98 * 256 + 99 * 1) mod 101
H("abc") = (6360576 + 25088 + 99) mod 101
H("abc") = 6386763 mod 101
H("abc") = 54

1.2 Calculăm hash-ul pentru primul subșir din text T = "ababcabcabc", adică subșirul T[0..2] =
"aba"
Aplicăm aceeași formulă:
H("aba") = (97 * 256^2 + 98 * 256^1 + 97 * 256^0) mod 101
H("aba") = (97 * 65536 + 98 * 256 + 97 * 1) mod 101
H("aba") = (6360576 + 25088 + 97) mod 101
H("aba") = 6386761 mod 101
H("aba") = 53

Astfel, hash-ul pentru subșirul T[0..2] = "aba" este 53.

Pasul 2: Compararea hash-urilor

• Hash-ul pentru pattern: 54
• Hash-ul pentru primul subșir din text T[0..2] = "aba": 53
Se observă că hash-urile nu sunt egale, deci nu există o potrivire aici.
Pasul 3: Calcularea hash-ului pentru următoarele subșiruri folosind rolling hash
Acum, folosim rolling hash pentru a calcula rapid hash-ul pentru următoarele subșiruri de lungime
3.
Formula de rolling hash este: H(T[i+1..i+m]) = (b * (H(T[i..i+m-1]) - T[i] * b^(m-1)) + T[i+m])
mod q

3.1 Calculăm hash-ul pentru subșirul T[1..3] = "bab"

H("bab") = (256 * (H("aba") - 97 * 256^2) + 98) mod 101
H("bab") = (256 * (53 - 97 * 65536) + 98) mod 101
H("bab") = (256 * (53 - 6360576) + 98) mod 101
H("bab") = (256 * (-6360523) + 98) mod 101
H("bab") = (-1624979968 + 98) mod 101
H("bab") = (-1624979868) mod 101
H("bab") = 54 mod 101
H("bab") = 54

Hash-ul pentru subșirul T[1..3] = "bab" este 54, care este egal cu hash-ul pattern-ului. Așadar,
există o potrivire potențială la poziția 1.
3.2 Comparăm caracter cu caracter
Am obținut că hash-urile sunt egale, dar trebuie să facem și o comparație directă a caracterelor:
• Subșirul "bab" se potrivește cu pattern-ul "abc"?
• Comparăm fiecare caracter: T[1] = "b" vs P[0] = "a" → nu se potrivesc.
Deci, nu avem o potrivire la poziția 1.
Pasul 4: Continuăm căutarea pentru următoarele subșiruri
Acum, continuăm să calculăm hash-urile pentru următoarele subșiruri din text folosind același
rolling hash.

Exercitiul 1: Calculati hash-urile pattern-ului p, precum si a tuturor subsirurilor de lungime m ale lui
s pentru urmatoarele valori: p = aba, s = aabbababbabab, q = 3.
1. Formula de hash: hash(s)=(s0⋅d^m−1+s1⋅d^m−2+…+sm−1)modq
2. Hash-ul pattern-ului p = aba: hash(p) = (0⋅26^2+1⋅26^1+0⋅26^0)mod3 =(0+26+0)mod3 =
26mod3 = 2
3. Hash-urile subsirurilor de lungime m=3
Număr total de subșiruri: len(s) - m + 1 = 13 - 3 + 1 = 11
Vom calcula hash pentru fiecare subșir.
Poziție Subșir Valori (a=0, b=1) Hash formula Hash mod 3
0 aab 001 0×26² + 0×26 + 1 = 1 1
Poziție Subșir Valori (a=0, b=1) Hash formula Hash mod 3
1 abb 011 0×26² + 1×26 + 1 = 27 0
2 bba 110 1×26² + 1×26 + 0 = 702 + 26 = 728 728 % 3 = 1
3 bab 101 1×26² + 0×26 + 1 = 676 + 1 = 677 2
4 aba 010 0×26² + 1×26 + 0 = 26 2 ✅ (match)
5 bab 101 676 + 0 + 1 = 677 2
6 abb 011 26 + 1 = 27 0
7 bba 110 702 + 26 = 728 1
8 bab 101 676 + 1 = 677 2
9 aba 010 26 2 ✅ (match)
10 bab 101 676 + 1 = 677 2

Seminarul 7 – Backtracking

Backtracking este o tehnică de programare folosită pentru a rezolva probleme prin

încercarea tuturor posibilităților într-un mod sistematic. Este adesea folosită în cadrul paradigmei
de programare algoritmică și poate fi privită ca o abordare de tip recursiv care explorează un
„arbore al deciziilor”.
Pe scurt, backtracking presupune:
1. Alegerea unei opțiuni posibile;
2. Verificarea dacă această alegere conduce către o soluție validă;
3. Dacă da, continuarea explorării;
4. Dacă nu, revenirea (backtrack) la pasul anterior și alegerea unei alte opțiuni.

Exemplu: Problema celor N regine

Problema celor N regine este o problemă clasică de combinatorică și teorie a mulțimilor,
care constă în a plasa N regine pe o tablă de șah N × N, astfel încât nicio două regine să nu se
atace reciproc.
Regulile șahului dictează că o regină poate ataca:
• pe linia ei (orizontal);
• pe coloana ei (vertical);
• pe oricare dintre cele două diagonale.

Fie N∈N∗ (un număr natural nenul). Se cere:

Să se determine o permutare Q=[q1,q2,…,qN], unde fiecare qi∈{1,2,...,N}, astfel încât:
• qi !=qj pentru i!=j (nu sunt pe aceeași coloană);
• ∣qi−qj∣!=∣i−j∣ pentru i!=j (nu sunt pe aceeași diagonală).

Input: n ∈ N, n ≥ 4 table size = the number of lines/columns/queens.

Output: (x1, y1),(x2, y2). . .(xn, yn), with xi, yi ∈ 1, n and: ∀ (i, j) ∈ {1 . . . n}2 with i != j:
xi != xj and yi != yj and |xi − xj| != |yi − yj|
Soluția 1: [2, 4, 1, 3]
Aceasta înseamnă:
• linia 1 → coloana 2
• linia 2 → coloana 4
• linia 3 → coloana 1
• linia 4 → coloana 3

. R . . → linia 1, coloana 2
. . . R → linia 2, coloana 4
R . . . → linia 3, coloana 1
. . R . → linia 4, coloana 3
Validare matematică:
• Coloanele sunt diferite: 2, 4, 1, 3 → OK
• Diagonalele: nu există perechi i,j cu ∣qi−qj∣=∣i−j∣ → OK

Soluția 2: [3, 1, 4, 2]
Aceasta înseamnă:
• linia 1 → coloana 3
• linia 2 → coloana 1
• linia 3 → coloana 4
• linia 4 → coloana 2

. . R . → linia 1, coloana 3
R . . . → linia 2, coloana 1
. . . R → linia 3, coloana 4
. R . . → linia 4, coloana 2
Validare matematică:
• Coloanele: 3, 1, 4, 2 → OK
• Diagonalele: toate distanțele diagonale sunt unice → OK

Seminarul 8 – Programare dinamica

Ideea principala: impartim problema data in mai multe subprobleme care se pot suprapune,
si combinam rezultatul acestora pentru a obtine rezultatul final. Tehnica de baza este tehnica de
memoizare care presupune retinerea rezultatelor subproblemelor intr-un array.

Exercitiul 1
INPUT: n∈N, sigma={X, O, Y}
OUTPUT: m∈N, ai nr = |{ S∈sigma* ai. [Link]=n si nu exsita 2 caractere consecutive
egale si fiecare O este incadrat de un X si un Y }|
n = 1 => {X}, {Y}
n = 2 => {XY}, {YX}
n = 3 => {XYX}, {YXY}, {XOX}, {YOY}
n = 4 => {XYXY}, {YXYX}, {XOYX}, {YOXY}, {XYOX}, {YXOY}
nr[n] = { 2, n=1, n=2 } || nr[n] = { nr[n-1] + nr[n-2], n>2 }
Exercitiul 2
Caz de baza: n=1
fib(2) fib(1) = 1 1 => 1 1=1 1
fib(1) fib(0) = 1 0 => 1 1=1 0
=> fib(1) = 1, fib(0)=0, fib(2)=1
Presupunem ca P(k):
fib(k+1) fib(k) = 1 1 la k si este adevarat
fib(k) fib(k-1) = 1 0
Demonstram P(k+1)

Exercitiul 3
combinari de n luate cate k = combinari de n-1 luate cate k-1 + combinari de n-1 luate cate k
Fie matrice c cu: - c[n][k] = 1, n=1, k=1 sau n=1, k=0
- c[n][k] = c[n-1][k-1] + c[n-1][k] % p, n>=2, k>=1

Exerciitul 4
S = 100101
100--1
--0--1

Fie sub[i] → nr max de substitutii din S[1...i]

sub[i] = 0, daca i=0, i=1
sub[i] = sub[i-2] + 1, daca S[i] != S[i-1]
sub[i] = sub[i-1], daca S[i] = S[i-1]

Exercitiul 5
n=1: 0, 1, 2,
n=2: 01, 02, 00, 10, 12, 11, 20, 21, 21
n=3: 101, 102, 110, 111, 112, 120, 121, 122, 201, 202, 210, 211, 212, 220, 221, 222

nz[i] = cate nr in baza k de lungime i se termina cu cifra !=0

nz[i] = k-1, daca i=1
nz[i] = (k-1)(nz[i-1] + z[i]), daca i >1

z[i] = cate nr in baza k de lungime i se termina cu cifra = 0

z[i] = 1, daca i=1
z[i] = nz[i-1], daca i>1

Rezultatul: z[N] + nz[N]

Exercitiul 6
Un șir bitonic este o secvență care crește și apoi descrește sau descrește și apoi crește (cu
un singur punct de inflexiune). Dat un șir S=[s1,s2,…,sn], vrem să găsim cea mai lungă
subsecvență (nu neapărat continuă) care este bitonică.
 1. LIS↑(i): lungimea celei mai lungi subsecvențe crescătoare care se termină la i;
2. LIS↓(i): lungimea celei mai lungi subsecvențe descrescătoare care începe de la i;

Cazuri de bază:
Fiecare element singur e o secvență crescătoare sau descrescătoare: LIS↑(i)=1, LIS↓(i)=1
pentru orice i.

Relatii de recurenta
1. Relație pentru subsecvențe crescătoare: și LIS↑(i)=1+max{LIS↑(j)∣j<i și S[j]<S[i]}
Dacă nu există asemenea j, atunci LIS↑(i)=1
2. Relație pentru subsecvențe descrescătoare: și LIS↓(i)=1+max{LIS↓(j)∣j>i și S[j]<S[i]}
Dacă nu există asemenea j, atunci LIS↓(i)=1

Exercitiul 8
Ni se dă un triunghi de numere cu n niveluri. Trebuie să alegem o cale de la vârf la bază,
unde:
• la fiecare pas putem merge la stânga-jos sau dreapta-jos
• vrem să maximizăm suma numerelor alese

Vom nota:
DP(i,j)=suma maxima care se poate obține pana la poziția (i,j) unde:
• i este nivelul în triunghi (de sus în jos)
• j este poziția pe linia i (de la stânga la dreapta)

Caz de bază: DP(1,1)=T(1,1)(valoarea de sus)

Relația de recurență
Pentru orice poziție (i,j), putem ajunge acolo din:
• poziția (i−1,j−1) — de sus-stânga
• poziția (i−1,j) — de sus-dreapta
Dar: poziția j trebuie să fie validă în acele cazuri.
DP(i,j)=T(i,j)+max(DP(i−1,j−1),DP(i−1,j))
Cu grijă la margini:
• Dacă j=1, nu există DP(i−1,j−1) → luăm doar DP(i−1,j)
• Dacă j=i, nu există DP(i−1,j) → luăm doar DP(i−1,j−1)

Seminarul 8 – Programare dinamica

1. Problema subsecventei de suma minima de lungime k

Fie Si suma subsecvenței continue de lungime K care începe la poziția i:

Si=v[i]+v[i+1]+⋯+v[i+K−1],1≤i≤N−K+1
Avem N−K+1 astfel de subsecvențe.
 Cazul de baza
Pentru început, calculăm suma primei subsecvențe de lungime K:
S1= j=1∑K v[j] min_sum=S1,count=1

Relatia de recurenta
Putem calcula Si+1 din Si în timp constant, folosind diferență de margini:
Si+1=Si−v[i]+v[i+K]

2. Numarul de paranterizari corecte

Dat un număr N, să determinăm câte șiruri corect parantezate putem forma, având exact N
caractere.
Fie n=N/2, adică avem n paranteze deschise ( și n paranteze închise ).
Definim: C(n)=numarul de moduri ın care putem forma o parantezare corecta cu n perechi

Cazul de baza
C(0)=1 → Șirul vid (fără nicio paranteză) este considerat corect.

Relatia de recurenta
Pentru n≥1, putem construi un șir corect de forma:
(parantezare corecta cu k perechi) parantezare corecta cu n−1−k perechi
Pentru fiecare k∈[0,n−1], punem o paranteză deschisă, apoi o sub-parantezare cu k perechi,
închisă de ), urmată de o parantezare cu n−1−k perechi.
C(n)= k=0∑n−1 C(k)⋅C(n−1−k)

Exemplu:
Să calculăm primele valori:
• C(0)=1
• C(1)=C(0)⋅C(0)=1
• C(2)=C(0)⋅C(1)+C(1)⋅C(0)=1+1=2
• C(3)=C(0)C(2)+C(1)C(1)+C(2)C(0)=2+1+2=5
• C(4)=C(0)C(3)+C(1)C(2)+C(2)C(1)+C(3)C(0)=5+2+2+5=14
Deci, de exemplu: Pentru N=6 (adică 3 perechi): C(3) = 5 șiruri corect parantezate.
Șiruri valide pentru n=3:(
(()))
(()())
(())()
()(())
()()()

3. Cel mai lung drum de lungime impara carea leaga doua frunte intr-un arbore.
Fie T=(V,E) arbore, root = un nod arbitrar de pornire.
Definim pentru fiecare nod u:
• dpeven(u): lungimea maximă a unui drum par de la u până la o frunză din subarborele său
• dpodd(u): lungimea maximă a unui drum impar de la u până la o frunză din subarborele său
 Caz de baza
Dacă u este frunză, atunci:
• dpeven(u)=0 (drumul către sine însuși are 0 muchii – par)
• dpodd(u)=−∞ (nu există drum impar de la frunză către alt nod în jos)

Relatia de recurenta
Pentru orice nod intern u, parcurgem toți copiii săi c și actualizăm:
dpeven(u)=max(dpeven(u),1+dpodd(c))
dpodd(u)=max(dpodd(u),1+dpeven(c))