Tehnici de programare

Prezentarea principalelor paradigme și tehnici algoritmice avansate.

Divide et Impera: împarte, rezolvă, combină

Divide et Impera rezolvă o problemă în trei pași care se repetă recursiv:

• Divide: problema se împarte în subprobleme de același tip, dar de dimensiune mai mică (de regulă două jumătăți);
• Impera: subproblemele suficient de mici se rezolvă direct (cazul de bază al recursivității);
• Combină: soluțiile subproblemelor se asamblează în soluția problemei inițiale.

Condiția esențială, care se uită la examen: subproblemele trebuie să fie independente — rezolvarea uneia nu depinde de rezultatul alteia. Când subproblemele se suprapun (aceleași calcule apar de mai multe ori), Divide et Impera devine ineficientă și locul ei îl ia programarea dinamică.

Exemple canonice: căutarea binară (împarte intervalul în două, păstrează o singură jumătate), MergeSort (sortează recursiv cele două jumătăți, apoi le interclasează), QuickSort (partiționează în jurul pivotului, apoi sortează recursiv cele două zone), turnurile din Hanoi.

Capcana clasică de grilă: nu orice funcție recursivă înseamnă Divide et Impera. O recursivitate care reduce problema cu 1 (de la n la n-1, ca la suma elementelor) nu împarte problema în subprobleme comparabile — metoda cere împărțirea în bucăți semnificative, tipic înjumătățire, ceea ce duce la complexități cu log n.

Greedy: alegerea local optimă, fără revenire

Metoda Greedy construiește soluția pas cu pas: la fiecare pas alege elementul care pare cel mai bun în acel moment (optimul local), iar alegerea făcută nu se mai revizuiește niciodată. De aici vin și puterea, și slăbiciunea metodei:

• puterea: algoritmii Greedy sunt rapizi — de regulă o sortare inițială plus o singură parcurgere, deci O(n log n);
• slăbiciunea: optimul local nu garantează optimul global; Greedy dă soluția corectă doar pentru problemele la care se poate demonstra că strategia locală conduce la optim global.

Exemple la care Greedy funcționează demonstrabil: problema spectacolelor (selectarea numărului maxim de activități care nu se suprapun — se alege mereu activitatea care se termină cel mai devreme), interclasarea optimă, algoritmii Kruskal și Prim pentru arbore parțial de cost minim, Dijkstra pentru drumuri minime.

Contraexemplul care se cere la examen: problema restului cu monede arbitrare. Pentru monedele 1, 3, 4 și suma 6, Greedy alege 4 + 1 + 1 (trei monede), dar optimul este 3 + 3 (două monede). Concluzia de reținut: Greedy nu explorează alternative și nu revine asupra deciziilor — dacă problema cere garantat optimul și strategia locală nu e demonstrată, se folosește altă metodă (programare dinamică sau backtracking).

Backtracking: explorare sistematică cu revenire

Backtracking generează toate soluțiile posibile construindu-le element cu element, într-un vector soluție x[1..n]. La fiecare pas k se încearcă pe rând valorile candidate pentru x[k]:

• dacă valoarea satisface condițiile de continuare, se avansează la pasul k+1;
• dacă nicio valoare nu mai e validă, se revine (backtrack) la pasul k-1 și se încearcă acolo următoarea valoare.

Ideea care face metoda utilizabilă: condițiile de continuare taie din start ramurile care nu pot duce la soluție — nu se generează toate combinațiile și abia apoi se verifică, ci se abandonează prefixele invalide cât mai devreme. Fără această tăiere, backtracking degenerează în forță brută pură.

Probleme standard, de recunoscut instantaneu în enunț:

• permutări (n dame pe tabla de șah, aranjarea a n persoane pe n scaune);
• submulțimi și combinări (alegerea unui grup din n obiecte);
• produs cartezian (generarea tuturor șirurilor de lungime dată peste un alfabet);
• colorarea hărților, partiții, parcurgeri de labirint.

Complexitatea este exponențială (sau factorială la permutări) — de aceea backtracking se aplică doar la dimensiuni mici. Grilă frecventă: la generarea permutărilor lui n, numărul soluțiilor este n!; la submulțimi este 2^n. Cine le inversează pierde punctul fără drept de apel.

Programarea dinamică: subprobleme care se suprapun

Programarea dinamică se aplică problemelor de optimizare care au două proprietăți:

• substructura optimă: soluția optimă a problemei se construiește din soluțiile optime ale subproblemelor (principiul optimalității al lui Bellman);
• subprobleme suprapuse: aceleași subprobleme apar de mai multe ori în procesul de rezolvare.

Strategia: fiecare subproblemă se rezolvă o singură dată, iar rezultatul se memorează într-un tablou (de regulă numit d sau dp), de unde e refolosit ori de câte ori e nevoie. Se lucrează fie bottom-up (se completează tabloul de la cazurile mici spre problema mare), fie top-down cu memoizare (recursivitate care își notează rezultatele).

Exemplul didactic standard: șirul lui Fibonacci. Calculat recursiv naiv, F(n) cere timp exponențial pentru că F(n-2) se recalculează de nenumărate ori; cu memorare, timpul devine liniar. Probleme clasice de examen: subșirul crescător de lungime maximă, problema rucsacului (varianta discretă), numărul de drumuri într-o matrice, suma maximă pe un traseu în triunghi de numere.

Delimitarea față de celelalte metode — întrebare de teorie garantată: față de Divide et Impera, programarea dinamică tratează subprobleme care se suprapun (D&I cere subprobleme independente); față de Greedy, programarea dinamică examinează toate alternativele la fiecare pas și garantează optimul, în timp ce Greedy face o singură alegere locală.

Branch and Bound și alegerea metodei potrivite

Branch and Bound explorează, la fel ca backtracking, un arbore de soluții candidate, dar cu două diferențe:

• pentru fiecare ramură se calculează o margine (bound) — o estimare optimistă a celui mai bun rezultat care s-ar mai putea obține continuând pe acea ramură;
• dacă marginea este mai slabă decât cea mai bună soluție găsită deja, întreaga ramură se taie fără a mai fi explorată.

În plus, ordinea de explorare nu e neapărat în adâncime: se poate alege mereu nodul cel mai promițător (best-first). Metoda se folosește la probleme de optimizare grele (problema comis-voiajorului, rucsacul), unde backtracking simplu ar explora inutil ramuri evident proaste.

Cum alegi metoda la examen — schema de decizie care rezolvă majoritatea grilelor de teorie:

• se cer toate soluțiile sau o configurație care respectă restricții → backtracking;
• problema se sparge în subprobleme independente de același tip → Divide et Impera;
• optimizare cu subprobleme suprapuse → programare dinamică;
• optimizare unde alegerea locală duce demonstrat la optim global → Greedy;
• optimizare cu spațiu uriaș de căutare, unde se pot estima margini → Branch and Bound.

Confuzia frecventă: Branch and Bound nu e „backtracking mai rapid” în general — tăierea depinde de calitatea estimării; cu o margine proastă, explorează la fel de mult.

Test — 6 întrebări ca la examen