Tehnici de programare

In cele ce urmeaza se prezinta unele tehnici generale de elaborare a algoritmilor si programelor, care pot fi utile in abordarea unei probleme noi, pentru care nu exista algoritmi deja cunoscuti.
 
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".
 

Tehnica diviziunii ("Divide et impera")

Este tehnica impartirii problemei in subprobleme care se rezolva separat, dupa care se cumuleaza rezultatele.

Calea generala de rezolvare a unei probleme pe aceasta cale este urmatoarea:

Fie problema P.

Esential pentru tehnica diviziunii este ca, pentru rezolvarea problemei P, trebuie rezolvate toate subproblemele in care aceasta a fost descompusa. La rezolvarea fiecareia din subprobleme, daca este necesar, se poate aplica din nou tehnica diviziunii, pana se ajunge la subprobleme simple, care pot fi rezolvate direct.
 
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:
  • la sortarea prin interclasare, impartirea tabloului de date in doua subtablouri se face direct, prin "sectionare"; fiecare subtablou se sorteaza separat, dupa care rezultatele partiale se combina prin interclasare. In consecinta, prima etapa, a impartirii in subprobleme, este simpla, in timp ce a treia etapa, a combinarii rezultatelor, este mai complicata;
  • la sortarea rapida (quick sort), tabloul se imparte in doua subtablouri astfel, incat toate elementele din primul subtablou sa fie mai mici decat cele din al doilea. Apoi fiecare subtablou se sorteaza separat, iar rezultatul final se obtine prin simpla punere a celor doua subtablouri cap la cap. In consecinta, prima etapa, a impartirii in subprobleme, este mai complicata, in timp ce ultima etapa este foarte simpla.
Particularitatea cautarii binare este ca, dupa impartirea tabloului in subtablouri, cautarea continua numai in unul din cele doua.

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.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati