Cuvantul "tehnica" este folosit aici in sensul de "modalitate practica de a indeplini o anumita sarcina", spre deosebire de "metoda", care este o "cale sistematica de a indeplini o anumita sarcina". Tehnica presupune o abordare mai putin riguroasa a rezolvarii problemei, in care este loc si pentru intuitie, inspiratie si solutii empirice, in timp ce metoda presupune rigoare. |
Cele mai raspandite tehnici de concepere a programelor sunt: "Divide
et impera", "backtracking" , "greedy" , "branch and bound"
si "programarea dinamica".
Calea generala de rezolvare a unei probleme pe aceasta cale este urmatoarea:
Fie problema P.
Exemple de algoritmi la elaborarea carora a fost folosita tehnica "divide
et impera" sunt cei de cautare
binara, sortare
prin interclasare, sortare
rapida (quick-sort) si altii. In aceste cazuri, tehnica diviziunii
s-a aplicat asupra datelor: multimea datelor de intrare se imparte in doua
submultimi, care se prelucreaza separat, dupa care se cupleaza rezultatele.
Deosebirea intre sortarea prin interclasare si sortarea rapida este urmatoarea:
Remarcam ca, in toate aceste cazuri, tehnica diviziunii se aplica recursiv: fiecare subtablou poate fi iarasi impartit in doua subtablouri si asa mai departe, pana se ajunge la tablouri cu lungimea de un singur element. Intr-un cadru mai larg, tehnica diviziunii sta la baza elaborarii programelor prin rafinari succesive. In acest caz, tehnica diviziunii nu se mai aplica asupra datelor, ci asupra programului insusi, prin modularizarea acestuia: programul se imparte in mai multe module, fiecare modul reprezentand rezolvarea unei subprobleme autonome. Aceste module se combina conform principiilor programarii structurate, folosind structuri secventiale, alternative sau repetitive. La randul lui, fiecare astfel de modul poate fi descompus pe baza aceleeasi tehnici. Rafinarea continua, pana se ajunge la module pentru care se pot aplica algoritmi deja cunoscuti. |