Tehnici de programare

Se introduc tehnici fundamentale de proiectare a algoritmilor pentru probleme mai complexe.

De la algoritm simplu la tehnică de programare

Până acum ai rezolvat probleme în care drumul spre rezultat era direct: citești, calculezi, afișezi. Dar există probleme la care trebuie să explorezi mai multe variante: în câte moduri pot așeza 4 elevi în bancă? Care combinație de monede plătește exact o sumă? Pentru asemenea probleme informatica a dezvoltat tehnici de programare — rețete generale de construire a algoritmilor, nu soluții pentru o singură problemă.

Cea mai simplă tehnică este forța brută (căutarea exhaustivă): generezi TOATE variantele posibile și le verifici pe rând. E garantat corectă — nu ratează nicio soluție — dar poate fi îngrozitor de lentă: numărul de variante crește exploziv. Pentru 4 elevi în bancă există 24 de aranjări, pentru 10 elevi — peste 3,6 milioane!

De aici nevoia de tehnici mai deștepte:

• backtracking — explorează variantele pas cu pas, dar abandonează din timp drumurile care sigur nu duc la soluție;
• divide et impera — sparge problema în bucăți mai mici de același fel, le rezolvă separat și combină rezultatele.

Cuvântul-cheie al capitolului este spațiul soluțiilor: mulțimea tuturor variantelor care ar putea fi soluții. Forța brută îl parcurge integral; backtracking-ul îl parcurge inteligent, tăind ramurile moarte. Deosebirea dintre cele două este exact ceea ce trebuie să poți explica.

Metoda backtracking – ideea

Backtracking înseamnă, cuvânt cu cuvânt, „întoarcere pe pași” — exact ca atunci când cauți ieșirea dintr-un labirint: mergi înainte cât poți, iar când dai de fundătură te întorci la ultima intersecție și încerci alt drum.

Cum se traduce asta în construirea soluțiilor: soluția se construiește element cu element, ca un vector x[1], x[2], ..., x[n]. La fiecare pas:

• alegi o valoare candidat pentru poziția curentă;
• verifici condițiile de continuare — poate valoarea asta să facă parte dintr-o soluție? (de exemplu: să nu se repete, să fie în ordine crescătoare, să nu se atace două regine pe tabla de șah);
• dacă DA, avansezi la poziția următoare;
• dacă NU, încerci următoarea valoare candidat pe aceeași poziție;
• când ai epuizat toți candidații unei poziții, te întorci (backtrack) la poziția anterioară și schimbi valoarea de acolo.

Când toate cele n poziții sunt completate corect, ai găsit o soluție — o afișezi și continui căutarea celorlalte.

Puterea metodei stă în verificarea condițiilor DIN TIMP: dacă primele două elemente deja încalcă regula, nu mai are rost să construiești restul — tai dintr-o singură mișcare mii de variante imposibile. Asta o deosebește de forța brută, care ar genera varianta completă și abia la final ar constata că e invalidă.

Probleme celebre rezolvate cu backtracking: permutările, problema reginelor pe tabla de șah, colorarea hărților, ieșirea din labirint.

Generarea permutărilor și a combinărilor

Cele două aplicații-standard ale backtracking-ului sunt generările de aranjamente de obiecte.

Permutările răspund la întrebarea: în câte moduri pot ORDONA n obiecte distincte? Pentru n = 3 și mulțimea {1, 2, 3}, permutările sunt: 123, 132, 213, 231, 312, 321 — șase în total. Numărul lor este n factorial: n! = 1 · 2 · ... · n. La permutări ordinea contează și fiecare element apare exact o dată — condiția de continuare la generare este ca valoarea candidat să nu fi fost deja folosită.

Combinările răspund la altă întrebare: în câte moduri pot ALEGE k obiecte din n, fără să conteze ordinea? Din {1, 2, 3, 4} luate câte 2: 12, 13, 14, 23, 24, 34 — șase combinări. Pentru că ordinea NU contează (12 și 21 sunt aceeași alegere), convenim să generăm elementele în ordine strict crescătoare — condiția de continuare este x[i] > x[i−1]. Așa fiecare alegere apare o singură dată.

Deosebirea dintre cele două, întrebare de teorie garantată:

• permutare: folosește TOATE elementele, ordinea contează;
• combinare: alege DOAR k elemente, ordinea nu contează.

Există și aranjamentele: alegi k din n și ordinea contează — hibridul celor două.

Verificare rapidă a înțelegerii: podiumul (locurile 1, 2, 3) dintr-o cursă cu 8 alergători este un aranjament (contează cine e pe ce loc); echipa de 3 elevi trimisă la concurs este o combinare (nu contează ordinea în echipă).

Divide et impera – împarte și stăpânește

Divide et impera („împarte și stăpânește”) rezolvă o problemă mare prin trei mișcări repetate:

• Împarte problema în subprobleme mai mici, DE ACELAȘI FEL cu problema inițială;
• Stăpânește: rezolvă subproblemele — dacă sunt încă mari, le împarți la rândul lor; dacă au devenit banale (o singură valoare), le rezolvi direct;
• Combină rezultatele subproblemelor în rezultatul problemei mari.

Pentru că subproblemele sunt de același fel cu întregul, implementarea naturală este recursivă — funcția se apelează pe jumătăți din ce în ce mai mici, până la cazul de bază.

Exemplul pe care îl cunoști deja fără să știi: căutarea binară! Problema „caută x în vector” se împarte în „caută x într-o JUMĂTATE de vector”, iar cazul de bază este intervalul gol sau elementul găsit. Aici pasul de combinare e trivial — răspunsul jumătății alese e chiar răspunsul final.

Alt exemplu clasic: maximul unui vector prin înjumătățire — maximul întregului este cel mai mare dintre maximul jumătății stângi și maximul jumătății drepte; cazul de bază: un singur element își este propriul maxim.

Când ajută cu adevărat tehnica? Când împărțirea reduce masiv munca — la fiecare nivel tai problema la jumătate, deci adâncimea împărțirilor e mică (pentru n = 1000, doar vreo 10 niveluri). Sortările rapide studiate la liceu (MergeSort, QuickSort) sunt tot divide et impera.

Nu orice problemă se pretează: dacă subproblemele NU sunt de același fel cu întregul sau nu se pot combina simplu, tehnica nu se aplică.

Cum alegi tehnica potrivită

La probleme concrete, prima decizie e alegerea tehnicii — iar alegerea greșită duce fie la program corect dar inutil de lent, fie la complicații fără rost.

Întrebările de pus, în ordine:

• Cere problema TOATE variantele posibile (toate așezările, toate submulțimile, toate drumurile)? → backtracking. Semnale în enunț: „generați toate...”, „afișați toate modurile...”, „în câte feluri...”.
• Se poate sparge problema în jumătăți de același fel, cu rezultate ușor de combinat? → divide et impera. Semnale: vector mare, operație asociativă (maxim, sumă, căutare), structură care se înjumătățește natural.
• E spațiul de căutare mic (câteva sute sau mii de variante)? → forța brută e perfect acceptabilă: simplă de scris, imposibil de greșit. Nu disprețui forța brută la probleme mici!

Două avertismente pentru practică:

• La backtracking, uitarea condițiilor de continuare transformă programul în forță brută mascată — generează tot și „explodează” la n mare. Condițiile de continuare sunt esența metodei, nu un detaliu.
• La divide et impera, cazul de bază lipsă sau greșit produce recursivitate infinită — aceeași boală ca la orice funcție recursivă.

Merită reținută și imaginea de ansamblu: aceste tehnici nu concurează, ci se completează. Un program real poate căuta binar (divide et impera) într-un catalog sortat și, separat, poate genera cu backtracking orarul claselor. Tehnica este unealta; problema dictează unealta potrivită.

Test — 6 întrebări ca la examen