Tehnici de programare

În cele ce urmează, se prezintă unele tehnici generale de elaborare a algoritmilor și programelor, care pot fi utile în abordarea unei probleme noi, pentru care nu există algoritmi deja cunoscuți.
 
Cuvântul "tehnică" este folosit aici în sensul de "modalitate practică de a îndeplini o anumită sarcină", spre deosebire de "metodă", care este o "cale sistematică de a îndeplini o anumită sarcină". Tehnica presupune o abordare mai puțin riguroasă a rezolvării problemei, în care este loc și pentru intuiție, inspirație și soluții empirice, în timp ce metoda presupune rigoare.

Cele mai răspândite tehnici de concepere a programelor sunt: "Divide et impera", "backtracking" , "greedy" , "branch and bound" si "programarea dinamica".
 

Tehnica diviziunii ("Divide et impera")

Este tehnica împărțirii problemei în subprobleme care se rezolvă separat, după care se cumulează rezultatele.

Calea generală de rezolvare a unei probleme prin tehnica diviziunii este următoarea:

Fie problema P.

Esențial pentru tehnica diviziunii este că, pentru rezolvarea problemei P, trebuie rezolvate toate subproblemele în care aceasta a fost descompusă. La rezolvarea fiecăreia din subprobleme, dacă este necesar, se poate aplica din nou tehnica diviziunii, pană se ajunge la subprobleme simple, care pot fi rezolvate direct.
 
Exemple de algoritmi, la elaborarea cărora a fost folosită tehnica "divide et impera", sunt cei de căutare binară, sortare prin interclasare, sortare rapidă (quick-sort) și alții. În aceste cazuri, tehnica diviziunii s-a aplicat asupra datelor: mulțimea datelor de intrare se împarte în doua submulțimi, care se prelucrează separat, după care se cuplează rezultatele. Deosebirea între sortarea prin interclasare și sortarea rapidă este următoarea:
  • la sortarea prin interclasare, împărțirea tabloului de date în două subtablouri se face direct, prin "secționare"; fiecare subtablou se sortează separat, după care rezultatele parțiale se combină prin interclasare. În consecința, prima etapa, a împărțirii în subprobleme, este simplă, în timp ce a treia etapă, a combinării rezultatelor, este mai complicată;
  • la sortarea rapidă (quick sort), tabloul se împarte în două subtablouri astfel, încât toate elementele din primul subtablou să fie mai mici decât cele din al doilea. Apoi fiecare subtablou se sortează separat, iar rezultatul final se obține prin simpla punere a celor două subtablouri cap la cap. În consecință, prima etapă, a împărțirii în subprobleme, este mai complicată, în timp ce ultima etapă este foarte simplă.
Particularitatea căutării binare este că, după împărțirea tabloului în subtablouri, căutarea continuă numai în unul din cele două subtablouri.

Remarcăm că, în toate aceste cazuri, tehnica diviziunii se aplică recursiv: fiecare subtablou poate fi iarăși împărțit în două subtablouri și așa mai departe, până se ajunge la tablouri cu lungimea de un singur element.

Într-un cadru mai larg, tehnica diviziunii stă la baza elaborării programelor prin rafinări succesive. În acest caz, tehnica diviziunii nu se mai aplică asupra datelor, ci asupra programului însusi, prin modularizarea acestuia: programul se împarte în mai multe module, fiecare modul reprezentând rezolvarea unei subprobleme autonome. Aceste module se combină conform principiilor programării structurate, folosind structuri secvențiale, alternative sau repetitive. La rândul lui, fiecare astfel de modul poate fi descompus pe baza aceleeași tehnici. Rafinarea continuă, până se ajunge la module pentru care se pot aplica algoritmi deja cunoscuți.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați