O anumita problema poate fi rezolvata cu ajutorul calculatorului numai daca se gaseste un algoritm pentru rezolvarea ei, care este dat calculatorului sub forma unui program.
Intrucat toate problemele practice pe care le intalnim se pot rezolva cu ajutorul calculatorului, s-ar putea crede ca orice problema este rezolvabila. Aceasta afirmatie este insa falsa. Se stie ca nu exista un program care sa rezolve problema terminarii programelor: Scrieti un program care sa decida daca un algoritm oarecare, dat, intra sau nu intr-un ciclu infinit.
Chiar si problemele pentru care exista algoritmi corespunzatori nu sunt neaparat rezolvabile cu calculatorul. Este posibil ca timpul necesar executiei acestor algoritmi, sau cantitatea de memorie necesara, sa nu permita folosirea lor in practica.
Evident, daca spatiul de memorie necesar programului este mai mare decat cantitatea de memorie disponibila, programul nu poate fi executat. De asemenea, daca numarul calculelor ce trebuie efectuat este foarte mare, programul poate fi inutil. Iar asta se poate intampla destul de usor in cazul problemelor ce trebuiesc rezolvate in timp real (adica solutia trebuie obtinuta inaintea unui timp critic). Iata cateva motive pentru care este necesar sa analizam algoritmii pe care-i concepem pentru rezolvarea unei probleme.
4) Alte calitati pe care le are.
4. 1 Corectitudinea programelor Un program este corect daca el satisface specificatiile problemei.
Nu ne intereseaza cata memorie foloseste acest program, din cate instructiuni este compus, sau cat timp de executie necesita. Cu alte cuvinte, un program este corect daca pentru acele date de intrare care satisfac specificatiile problemei rezultatele obtinute in urma executiei sunt corecte.
Pentru orice program P deosebim trei tipuri de variabile, pe care le vom grupa in trei vectori X, Y si Z. Componentele vectorului X desemneaza variabilele de intrare, deci datele presupuse cunoscute in problema rezolvata prin programul P.
Componentele vectorului Z sunt variabilele care reprezinta rezultatele cerute de problema. In sfarsit, componentele vectorului Y sunt variabilele de lucru, care noteaza diferitele rezultate intermediare necesare in program.
O problema nu are sens pentru orice date de intrare.
Vom folosi predicatul R (X) pentru a preciza datele pentru care problema are sens. R (X) se numeste predicat de intrare sau preconditie. Pentru acele valori ale lui X pentru care predicatul este adevarat problema are sens, pentru celelalte nu are sens sa executam programul P.
Intre rezultatele Z ale problemei si datele initiale X (cunoscute in problema) exista anumite relatii. Vom reda aceste relatii prin predicatul de iesire R (X, Z), numit si postconditie. Acesta este corect pentru acele valori a si b ale vectorilor X si Z pentru care rezultatele problemei sunt b in cazul cand datele initiale sunt a si este fals in caz contrar. Deci, daca executand programul cu datele initiale a obtinem rezultatele b si ...
Pentru a descărca acest document,
trebuie să te autentifici in contul tău.
