Principii de proiectare a algoritmilor (divide et impera – introducere)

Divide et Impera („dezbină și stăpânește”) este o tehnică fundamentală de proiectare a algoritmilor, folosită pentru a rezolva probleme complexe prin descompunerea lor în subprobleme mai mici, similare cu problema inițială, dar mai ușor de rezolvat. Principiul de bază constă în trei etape: 1. Divide (împarte): Problema se împarte în două sau mai multe subprobleme de același tip, de dimensiuni mai mici. 2. Impera (stăpânește): Fiecare subproblemă se rezolvă recursiv (sau direct, dacă este suficient de mică – caz de bază).

3. Combină (îmbină): Soluțiile subproblemelor se combină pentru a obține soluția problemei inițiale. Pentru a aplica corect această tehnică, trebuie identificate: cazul de bază (dimensiunea pentru care problema se poate rezolva direct) și modul de combinare a soluțiilor parțiale. Divide et Impera este eficient mai ales atunci când subproblemele sunt independente (nu se suprapun).

Exemple clasice includ: sortarea prin interclasare (Merge Sort), sortarea rapidă (Quick Sort), căutarea binară, turnurile din Hanoi, sau calculul puterii unui număr. În informatică, această paradigmă reduce complexitatea temporală a algoritmilor de la O(n²) la O(n log n) în cazul sortării, ceea ce o face extrem de utilă pentru volume mari de date. Elevii din clasele 5–8 trebuie să înțeleagă că nu este vorba doar de împărțire, ci și de modul în care reasamblăm rezultatele.

Un exemplu intuitiv este împărțirea unui șir de numere în jumătăți, sortarea fiecărei jumătăți, apoi interclasarea lor ordonată. Pe parcursul lecției, vom explora trei exemple concrete, de la simplu la mediu, pentru a fixa noțiunile.

Exemple

• Exemplul 1 – Căutarea binară (Binary Search): Avem un vector sortat crescător, de ex. [2, 5, 7, 10, 15, 20]. Căutăm valoarea 10. Divide: împărțim vectorul în două jumătăți (mijlocul = index 3, valoarea 10). Impera: verificăm dacă valoarea din mijloc este egală cu cea căutată – da, am găsit. Dacă nu, continuăm recursiv în jumătatea stângă sau dreaptă, după caz. Cazul de bază: când subvectorul rămâne gol (nu există elemente).
• Exemplul 2 – Turnurile din Hanoi: Avem 3 tije și n discuri de dimensiuni diferite pe prima tijă, în ordine descrescătoare (cel mai mare jos). Scopul: mutarea tuturor discurilor pe tija a treia, respectând regula că nu putem pune un disc mai mare peste unul mai mic. Divide: pentru a muta n discuri de pe tija A pe tija C, mutăm primele n-1 discuri de pe A pe B (folosind C ca ajutătoare), apoi mutăm discul cel mare de pe A pe C, apoi mutăm cele n-1 discuri de pe B pe C (folosind A ca ajutătoare). Impera: mutarea a n-1 discuri este aceeași problemă, dar cu un disc mai puțin. Cazul de bază: n=1 (mutăm direct discul).
• Exemplul 3 – Sortarea prin interclasare (Merge Sort) pe o listă mică: Avem [38, 27, 43, 3, 9, 82, 10]. 1. Împărțim în două: stânga [38,27,43,3] și dreapta [9,82,10]. 2. Continuăm împărțirea până când avem subliste de un singur element (caz de bază). 3. Apoi interclasăm perechi: [38] și [27] → [27,38]; [43] și [3] → [3,43]; apoi interclasăm [27,38] cu [3,43] → [3,27,38,43] (partea stângă). Similar, dreapta: [9] cu [82] → [9,82]; apoi cu [10] → [9,10,82]. 4. În final, interclasăm cele două jumătăți sortate: [3,27,38,43] și [9,10,82] → [3,9,10,27,38,43,82].

Concepte cheie: Divide et Impera: împărțirea problemei în subprobleme mai mici, Caz de bază: condiția de oprire a recursivității, Combinarea soluțiilor parțiale pentru a obține soluția finală, Independenta subproblemelor – cheia eficienței, Exemple practice: căutare binară, turnurile din Hanoi, Merge Sort