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".
Calea generală de rezolvare a unei probleme prin tehnica diviziunii este următoarea:
Fie problema P.
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:
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. |