Ce este un algoritm?

Definiția clasică: un algoritm e o secvență finită de pași bine definiți, care primește o intrare și produce o ieșire.

Termenul vine de la Al-Khwarizmi, matematician persan din secolul al IX-lea.

Proprietățile unui algoritm

1. Finit — se termină după un număr finit de pași
2. Bine definit — fiecare pas e clar și neambiguu
3. Intrare — zero sau mai multe valori de intrare
4. Ieșire — una sau mai multe valori de ieșire
5. Efectiv — fiecare pas poate fi executat în principiu de un om cu hârtie și creion

Algoritm vs Program

| Algoritm | Program | |---|---| | Concept abstract | Implementare concretă | | Descris în pseudocod | Rulează pe un calculator | | Corect prin demonstrație | Corect prin testare |

Paradigme fundamentale

Divide et Impera

T(n) = a·T(n/b) + f(n). QuickSort, MergeSort, căutare binară.

Greedy

Alegerea optimă locală → optim global. Dijkstra, Huffman, Prim.

Programare Dinamică

Subprobleme suprapuse + memorizare. Knapsack, LCS, Floyd-Warshall.

Backtracking

Explorează sistematic, taie ramurile moarte. Minimax, N-Regine.

Aleatorizare

QuickSort randomizat, Monte Carlo, Skip Lists.

Modul Expert

Secțiunile următoare sunt destinate cititorilor care vor să înțeleagă algoritmii la nivel de rigoare matematică.

1. Analiza amortizată

Analiza amortizată calculează costul mediu per operație într-un șir de operații, nu costul individual. E esențială pentru structuri de date unde operațiile rare sunt scumpe dar majoritatea sunt ieftine.

Metoda contabilă (Accounting method)

Atribui fiecărei operații un "cost amortizat" mai mare decât costul real. Diferența se "economisește" și se folosește la operațiile scumpe.

Exemplu — Dynamic Array (vector cu redimensionare):

• Inserarea normală: cost real = 1, cost amortizat = 3
• Redimensionarea (dublarea capacității): cost real = n, dar avem suficienți "bani" economisiți
• Cost amortizat total per inserare: O(1)

Metoda potențialului (Potential method)

Definim o funcție de potențial Φ(D_i) care măsoară "energia" stocată în structura de date. Costul amortizat = costul real + ΔΦ.

Pentru Dynamic Array, Φ = |2·size - capacity|.

Metoda agregării

Calculăm costul total al unui șir de n operații și împărțim la n.

2. Teorema Master — demonstrație și cazuri

Teorema master rezolvă recurențe de forma T(n) = a·T(n/b) + f(n).

Cele trei cazuri

Comparăm f(n) cu n^(log_b a):

| Caz | Condiție | Rezultat | |---|---|---| | 1 | f(n) = O(n^(log_b a - ε)) | T(n) = Θ(n^(log_b a)) | | 2 | f(n) = Θ(n^(log_b a) · log^k n) | T(n) = Θ(n^(log_b a) · log^(k+1) n) | | 3 | f(n) = Ω(n^(log_b a + ε)) și a·f(n/b) ≤ c·f(n) | T(n) = Θ(f(n)) |

Exemplu — căutare binară: T(n) = T(n/2) + O(1). a=1, b=2. n^(log_2 1) = n^0 = 1. f(n) = 1 = Θ(n^(log_b a)). Cazul 2, k=0. T(n) = Θ(log n). ✓

Exemplu — MergeSort: T(n) = 2·T(n/2) + O(n). a=2, b=2. n^(log_2 2) = n. f(n) = n = Θ(n). Cazul 2, k=0. T(n) = Θ(n log n). ✓

Exemplu — QuickSort (caz rău): T(n) = T(n-1) + O(n). a=1, b... n-1 ≠ n/b. Teorema master NU se aplică. Rezolvăm prin substituție: T(n) = T(0) + Σ(i=1..n) O(i) = O(n²).

Cazuri care nu se încadrează

• T(n) = T(n/2) + T(n/2) + O(n) → e același cu MergeSort
• T(n) = 2·T(n/2) + O(n/log n) → între cazul 2 și 3
• T(n) = T(√n) + O(1) → substituție m = log n

3. Limite inferioare (Lower Bounds)

Pentru unele probleme, putem demonstra că orice algoritm are o anumită complexitate minimă.

Sortarea prin comparații

Teoremă: Orice algoritm de sortare bazat pe comparații are nevoie de Ω(n log n) comparații în cazul cel mai rău.

Demonstrație: Arborele de decizie are n! frunze (toate permutările). Înălțimea minimă a unui arbore binar cu n! frunze este log₂(n!) = Θ(n log n). Orice algoritm de sortare prin comparații corespunde unui drum în acest arbore.

Consecință: QuickSort, MergeSort, HeapSort sunt optimi asimptotic — nu poate exista un algoritm de sortare prin comparații mai rapid decât O(n log n).

Excepție: Sortarea prin numărare (Counting Sort), Radix Sort — nu folosesc comparații, deci pot fi O(n + k).

Găsirea minimului

Teoremă: Găsirea minimului într-un array nesortat necesită Ω(n) comparații.

Demonstrație: Orice element care nu a fost comparat ar putea fi minimul. Trebuie să compare fiecare element cel puțin o dată.

4. Reduceri și NP-completitudine

O reducere transformă o problemă A în problema B astfel încât o soluție pentru B dă o soluție pentru A. Notația: A ≤_p B (A se reduce polinomial la B).

Proprietăți

• Dacă A ≤_p B și B e rezolvabilă în timp polinomial, atunci și A e rezolvabilă în timp polinomial
• Dacă A ≤_p B și A e NP-completă, atunci B e NP-dificilă

Exemple clasice de reduceri

| Problemă | Redusă la | Metoda | |---|---|---| | 3-SAT | Clique | Construim un graf unde clicurile corespund asignărilor | | 3-SAT | Vertex Cover | Complementul clicii | | Vertex Cover | Hamiltonian Cycle | Construcție cu gadget-uri | | Hamiltonian Cycle | Traveling Salesman | Distanțe = 1 pentru muchii, ∞ pentru non-muchii |

Ce înseamnă practic

Dacă ai o problemă nouă și o poți reduce la o problemă NP-completă cunoscută, știi că nu merită să cauți un algoritm polinomial exact — cel mai bun e un algoritm de aproximare sau euristic.

5. Analiza probabilistică și algoritmi randomizați

QuickSort randomizat

Alegând pivotul aleator, cazul cel mai rău (O(n²)) are probabilitate exponențial mică. Timpul așteptat e O(n log n) pentru orice intrare.

Demonstrație: Variabila aleatoare X = numărul de comparații. E[X] = O(n log n). Folosim linearitatea speranței și probabilitatea ca două elemente să fie comparate = 2/(j-i+1).

Verificarea primalității (Miller-Rabin)

Test probabilistic: dacă un număr compus e declarat "prim" cu probabilitate < 4^(-k). Pentru k=20, probabilitatea de eroare < 10^(-12).

Skip Lists

Alternativă randomizată la arborii echilibrați. Fiecare element urcă la nivelul următor cu probabilitatea 1/2. Timpul așteptat: O(log n). Mai simplu de implementat decât AVL sau Red-Black.

6. Analiza de caz amortizat — exemplu complet

Problemă: Implementează o coadă cu două stive.

Soluție: Stiva S1 pentru intrări (push), stiva S2 pentru ieșiri (pop). Când S2 e goală, mutăm toate elementele din S1 în S2 (inversând ordinea).

Analiză: Fiecare element e împins în S1 o dată, scos din S1 și împins în S2 o dată, scos din S2 o dată. Total: 4 operații per element. Cost amortizat per operație: O(1).

Fără analiză amortizată, ai spune că operația de mutare e O(n). Cu analiză amortizată, vezi că e O(1) per operație, pentru că mutările sunt rare.

Vezi și

• Big O
• P vs NP
• Algoritmi de sortare avansați
• Mașina Turing
• Algoritmul Minimax