Carte Algoritmi Partea1!20!12 04

7/27/2019 Carte Algoritmi Partea1!20!12 04

1/165

Structuri de date i algoritmi_______________________________________________________________________________

CUPRINS

BAZELE ALGORITMILORIntroducereDescrierea Algoritmilor

-algoritm, program, programare-scheme logice-limbajul Pseudocod-calculul efectuat de un algoritm-rafinare in pasi succesivi-probleme propuse-test

Subalgoritmi-conceptul de subalgoritm-apelul unui subalgoritm-elaborarea algoritmului-proiectarea ascendenta si descendenta-proiectarea modulara-apel recursiv-programare structurata-probleme propuse-test de verificare

Limbajul Pascal-mediul de programare Turbo Pascal-programe pascal simple-subprograme-tipuri de date-probleme propuse-test de verificare

STRUCTURI DE DATEIntroducere

Lista simplu inlantuitaTeorie generala-definitia componentelor listei-metoda statica-metoda dinamica-operatii specifice listei

Test de verificareLista dublu inlantuita

Teorie generala-definitia componentelor listei

________________________________________________________________________________

1


2/165


-metoda statica-metoda dinamica-operatii specifice listei

Test de verificareStivaTeorie generala

-definitia componentelor stivei-metoda statica-metoda dinamica-operatii specifice stivei

Simularea stiveiProbleme propuseTest de verificareProbleme rezolvate

CoadaTeorie generala

-referitor la coada-alocarea secventialaalocarea dinamica

Simularea functionarii coziiProbleme propuseProbleme rezolvate

Arborele BinarTeorie generala

-generalitati-definitia elementelor arborelui-implementarea in pascal-operatii specifice

Simularea operatiiTest de verifProbleme rezolvata

GrafulTeorie generalaExemple

COMPLEXITATEA ALGORITMILOR-etapele rezolvarii unei probleme-notiune de algoritm si de program-modelul abstract al masinii Turing-teza Turing-Church-analiza , proiectarea si implementarea algoritmilor-operatia de baza cheia studiului complexitatii-clase de algoritmi-eficienata algoritmi

________________________________________________________________________________

2


3/165


-functii de complexitate-apartenenta la o clasa de complexitate-limita mimimala sau efort minimal

-algoritm optimal-dificultatea problemelor-complexitatea de timp-probleme rezonabile si probleme nerezonabile\-probleme de decizie si de optimizare-clasa problemelor NP-reductia polinamiala a problemelor-echivalarea problemelor prin reductie polinopmiala-teorema lui Cook-clasa probleme NP-marea intrebare a complexitatii algoritmilor

-algoritmi aproxiamtivi-probleme insolvabile algoritmic-complexiatea algoritmilor , calculatorul si viitorul-test de verificare

TEHNICI DE CAUTARECautare secventiala

Teorie generala-descrierea generala a metodei

-descrierea algoritmului in pseudocod-implementarea algoritmului in Pascal-implementarea algoritmului in C-performanta metodei de cautare

Probleme rezolvateProbleme propuseSimularea metodei de cautare

Cautare binaraTeorie generala

-descrierea generala a metodei

-descrierea algoritmului de cautare in Pseudocod-implementarea algoritmului in Pascal-implementarea algoritmului in C-performanata metodei de cautare binara

Probleme rezolvateProbleme propuseSimularea metodei de cautare binaraTest de verificare

Arbori

________________________________________________________________________________

3


4/165


Arbore binar balansat in inaltime-introducere-descriere generala

-descrierea algoritmului in Pseudocod-implementarea algoritmului in Pascal-implementarea algoritmului in C-performanata arbore binar balansat in inaltime-simularea cautarii in arborele balansat in inaltime-test de verificare

Arbore 2-3-descriere generala-descrierea algoritmului de cautare in Pseudocod-implementarea alg in Pascal-performanata arborelui 2-3

-simularea arborelui 2-3 in algoritmul de cautaretest de verificare

Arbore balansat in greutate-descrierea generala a arborelui-descrierea algoritmului de cautare in Pseudocod-implementarera algoritmului in Pascal-performanta arborelui balansat in greutate-simularea arborelui balansat in greutate in algoritmul cautarii-test de verificare

Probleme rezolvateProbleme propuse

Tablele HasingIntroducereFunctia Hash

-generalitati a functiilor hash-metoda Impartirii-metoda Patrat Mediu-metoda Indoirii-metoda Digit Analysis

-metoda dependenta de lungimea cheii-metoda codarii algebrice-metoda Hashing Multiplicativ

Performanta functiei hashSimularea metodei ImpartiriiTest de verificare

Tehnici de rezolvare a coleziunilorIntroducereProbarea liniara

-descrierea generala a metodei

________________________________________________________________________________

4


5/165


-descrierea lagorotmului de cautare inserare in Pseudocod-implementarea algoritmului in Pascal-implementarea algoritmului in C

-performanta metodeiProbarea aleatoare-descrierea generala a metodei-descrierea algoritmului de cautare inserare in Pseuducod-implementarea algoritmului in Pascal

Hashing multiplicativ-descrierea generala a metodei-descrierea algoritmului de cautare inserare in Pseuducod-implementarea algoritmului in Pascal-implementarea algoritmului in C-performanta metodei

Inlantuire separata (Separate Chaining)-descrierea generala a metodei-descrierea algoritmului de cautare inserare in Pseuducod-implementarea algoritmului in C-performanta metodei

Buckets-descrierea generala a metodei-descrierea algoritmului de cautare inserare in Pseuducod-implementarea algoritmului in C

Probleme propuseSimularea tehnicii Probarii aleatoareTest de verificare

TEHNICI DE SORTARE Istoric

Prezentare generala

BubleSort-descrierea generala metodei-implementarea algoritmului in Pascal si C

-complexitatea algoritmului-probleme rezolvate-probleme propuse-simulare-test de verificare

SelectionSort-descrierea generala metodei-implementarea algoritmului in Pascal si C-complexitatea algoritmului

________________________________________________________________________________

5


6/165


-probleme rezolvate-probleme propuse-simulare

-test de verificare

InsertSort-descrierea generala metodei-implementarea algoritmului in Pascal si C-complexitatea algoritmului-probleme rezolvate-probleme propuse-simulare-test de verificare

ShellSort-descrierea generala metodei-implementarea algoritmului in Pascal si C-complexitatea algoritmului-probleme rezolvate-probleme propuse-simulare-test de verificare

QuickSort-descrierea generala metodei-imbunatatiri-probleme rezolvate-probleme propuse-simulare-test de verificare

MergeSort-descrierea generala metodei-imbunatatiri-probleme rezolvate

-probleme propuse-simulare-test de verificare

HeapSort-descrierea generala metodei-probleme rezolvate-probleme propuse-simulare-test de verificare

________________________________________________________________________________

6


7/165


RadixSort-descrierea generala metodei-probleme rezolvate

-probleme propuse-simulare-test de verificare

TEHNICI DE PROGRAMAREBacktrackingGreedyProgramarea dinamicaBranch&BoundTest de verificare

Exemple

Introducere

________________________________________________________________________________

7


8/165


Progresele tehnologice n domeniul informaticii au condus la creterea puterii de calcul i amemoriei calculatoarelor electronice, la ieftinirea acestor calculatoare, permind abordarea unor

probleme extrem de complexe, din toate sferele activitii umane. Calculatorul a devenit un

instrument indispensabil pentru viaa omului modern. Penetrarea Internetului i a accesului laresursele informatice mondiale, lrgirea considerabil a spectrului de aplicaii a contribuit icontribuie la impunerea calculatorului ca instrument de lucru vital n activitatea omului. nconsecin, cerina de noi programe n toate domeniile activitii umane a crescut mereu.

De aceea, se impune tot mai pregnant creterea importanei metodologilor de realizare aproduselor program, necesitatea unei instruiri corespunztoare a noilor generaii de specialiti i deutilizatori ai calculatoarelor. n formarea specialitilor n informatic este important dobndireaunor cunotine i deprinderi de a realiza produse program de o complexitate variat, care ssatisfac cerinele beneficiarului. Pentru aceasta este necesar respectarea unei discipline de lucru icunoaterea unei metodologii adecvate de proiectare i realizare a acestor produse software. ntrecutul nu prea ndeprtat, n activitatea de instruire a specialitilor n informatic s-a pus un maimare accent pe nvarea unor limbaje de programare i pe programarea propriu-zis, acordndu-seo pondere mai mic analizei i proiectrii programelor. Specializarea n informatic nu nseamndoar cunoaterea limbajelor de programare, ci n primul rnd nsuirea metodelor moderne deanaliz i proiectare a aplicaiilor soft.

Scopul acestei cri este de a contribui la nvarea programrii ca o disciplin unitar avndo fundaie tiinific solid, necesar programatorilor. Pentru aceasta este nevoie s ncercm sdefinim mai clar noiunea de programare.

Conform cu Sedgewitz [1990], programarea poate fi privit ca o activitate general de aextinde sau a de a modifica funcionalitile unui sistem. Este o activitate general deoarece ea

poate fi efectuat att de specialiti (programatori) ct i de nespecialiti (setarea unui telefoncelular sau a unei alarme de acces ntr-o ncpere). Din acest punct de vedere activitatea de

programare const din dou elemente fundamentale: o component tehnologic i o componenttiinific. Partea tiinific include elemente printre care se regsesc structurile de date i algoritmiinecesari descrierii operaiilor de manipulare a acestor structuri de date. Aceast abordare ne permiteo independena a acestor structuri de date fa de limbajele de programare i fa de tehnologiile de

proiectare utilizate in activitatea de programare.

Programele sunt fcute pentru a rezolva probleme din viaa de zi cu zi. Informaia prelucratde un program este stocat cu ajutorul structurilor de date. Aceste structuri de date grupeaz ntr-oform eficient datele. O structur de date corect definit poate simplifica operaia care prelucreazacele date sau o poate complica. De aceea structurile de date au o importan major n activitatea

de proiectare si programare.Programele prelucreaz informaii. Informaiile sunt organizate sub form de structuri de

calcul. Modul n care reprezentm structurile de date afecteaz claritatea, conciziunea, viteza derulare i capacitatea de stocare a programului. Dezvoltarea unui program complex este dificil dac

programatorul nu posed cunotine n domeniul structurilor de date, algoritmicii i a tehnicilor deprogramare.

Dac nu se cunoate o soluie pentru rezolvarea unei probleme nu exist o soluie magic dea scrie un program care s rezolve acea problema. Un proverb afirm c dac nu tii cum s ajungintr-un anumit loc atunci nu are importan cum ajungi n acel loc. Mai mult chiar Murphi afirm c

________________________________________________________________________________

8


9/165

Structuri de date i algoritmi_______________________________________________________________________________orice problem complex are o soluie simpl eronat. De aceea, nainte de a implementa un

program ntr-un anumit limbaj de programare, este necesar nelegerea problemei, descrierea pascu pas a soluiei, cu alte cuvinte este necesar a descrie problema prin intermediul unui algoritm.

Din pcate nu exist un algoritm care s aleag algoritmul care rezolv orice problem. Ceeace exist sunt o serie de tehnici de dezvoltare a algoritmilor, numite n general tehnici de

programare.

Scopul principal al lucrrii de fa este familiarizarea celor care doresc s o nvee, cuactivitatea de programare. Vom vedea n ce const aceast activitate i vom remarca accentul pus pegndirea omului, pe proiectarea algoritmilor i corectitudinea lor, calculatorul fiind doar unealtacare execut ceea ce "dicteaz" programatorul. Pentru a putea dicta calculatorului avem nevoie deun limbaj neles de ambele pri; limbajul ales n acest scop este limbajul Pascal. De asemenea,vom prezenta metodele de programare cunoscute n prezent i discutate n literatura de specialitate.Vom nva s analizm algoritmii, dar vom fi mai puin preocupai de msurarea complexitii unui

program, accentul fiind pus pe modul n care el poate fi obinut. Noiunile i conceptele prezentatesunt nsoite de exemple simple, n care s-au folosit: limbajul Pseudocod n descrierea algoritmilor,un limbaj de specificare informal n descrierea tipurilor abstracte de date i limbajul Pascal pentrucodificare.

I. BAZELE ALGORITMILOR

I.1.DESCRIEREA ALGORITMILOR

I.1.1. Algoritm, program, programare

Ce este un algoritm? O definiie matematic, riguroas, este greu de dat, chiar imposibil fra introduce i alte noiuni (Giumale [2004]). Vom ncerca n continuare o descriere a ceea ce senelege prin algoritm.

Vom constata c un algoritm este un text finit, o secven finit de propoziii ale unui limbaj.Din cauz c este inventat special n acest scop, un astfel de limbaj este numit limbaj de descriere aalgoritmilor. Fiecare propoziie a limbajului precizeaz o anumit regul de calcul, aa cum se vaobserva atunci cnd vom prezenta limbajul Pseudocod.

Algoritmii au urmtoarele caracteristici: generalitate, finitudine i unicitate (Livovschi [1980])

n descrierea algoritmilor se folosesc mai multe limbaje de descriere, dintre care cele mai desfolosite sunt:- limbajul schemelor logice;

________________________________________________________________________________

9


10/165


11/165

Structuri de date i algoritmi_______________________________________________________________________________propoziii nestandard. Aa cum se va arta mai trziu, propoziiile nestandard sunt texte care descriupri ale algoritmului nc incomplet elaborate, nefinisate, asupra crora urmeaz s se revin. Elese recunosc prin faptul c ncep ntotdeauna cu semnul '@' i se termin cu punctul obinuit

(caracterul '.').Pe lng aceste propoziii standard i nestandard, n textul algoritmului vom mai introduce

propoziii explicative, numite comentarii. Pentru a le distinge de celelalte propoziii, comentariilevor fi nchise ntre acolade. Rolul lor va fi explicat puin mai trziu.

Prin execuia unui algoritm descris n Pseudocod se nelege efectuarea operaiilor precizatede propoziiile algoritmului, n ordinea citirii lor (de sus n jos i de la stnga spre dreapta).

Propoziiile standard ale limbajului Pseudocod folosite n aceast lucrare, corespundstructurilor de calcul prezentate n Figura 1.1 i vor fi prezentate n continuare.

n Figura I.1, prin A, B s-au notat subscheme logice, adic secvene de oricte structuri

construite conform celor trei reguli menionate n continuare.Structura secvenial (Figura I.1.a) este redat prin concatenarea propoziiilor, simple saucompuse, ale limbajului Pseudocod, care vor fi executate n ordinea ntlnirii lor n text.

Propoziiile simple din limbajul Pseudocod sunt CITETE, TIPARETE, FIE i apelul desubprogram. Propoziiile compuse corespund structurilor alternative i repetitive.

Structura alternativ din Figura I.1.b este redat n Pseudocod prin propoziia DAC,prezentat n seciunea 2.3.2, iar structura repetitiv din Figura I.1.c este redat n Pseudocod prinpropoziia CTTIMP, prezentat n seciunea 2.3.3.

Bhm i Jacopini [1966] au demonstrat c orice algoritm poate fi descris folosind numaiaceste trei structuri de calcul.

Propoziiile DATE i REZULTATE sunt folosite n faza de specificare a problemelor, adicenunarea riguroas a acestora.

Figura 1.1.Structuri elementare de calcul.

________________________________________________________________________________

11


12/165


Fiecare propoziie standard ncepe cu un cuvnt cheie, aa cum se va vedea n cele ceurmeaz. Pentru a deosebi aceste cuvinte de celelalte denumiri, construite de programator, n acest

capitol vom scrie cuvintele cheie cu litere mari. Menionm c propoziiile simple se termin cucaracterul ';' n timp ce propoziiile compuse, deci cele n interiorul crora se afl alte propoziii, auun marcaj de sfrit propriu. De asemenea, menionm c propoziiile limbajului Pseudocod vor filuate n seam n ordinea ntlnirii lor n text, asemenea oricrui text al limbii romne.

Propoziia DATE se folosete pentru precizarea datelor iniiale, deci a datelor consideratecunoscute n problem (numite i date de intrare) i are sintaxa:

DATE list ;

unde list conine toate numele variabilelor a cror valoare iniial este cunoscut.n general, prin list se nelege o succesiune de elemente de acelai fel desprite prin

virgul. Deci n propoziia DATE, n dreapta acestui cuvnt se vor scrie acele variabile caremarcheaz mrimile cunoscute n problem.

Pentru precizarea rezultatelor dorite se folosete propoziia standard:

REZULTATE list;

n construcia "list" ce urmeaz dup cuvntul REZULTATE fiind trecute numele variabilelorcare marcheaz (conin) rezultatele cerute n problem.

Acum putem preciza mai exact ce nelegem prin cunoaterea complet a problemei derezolvat. Evident, o problem este cunoscut atunci cnd se tie care sunt datele de intrare cedefinesc problema dat i rezultatele ce trebuiesc obinute.

Deci pentru cunoaterea unei probleme este necesar precizarea variabilelor care marcheazdatele considerate cunoscute n problem, care va fi reflectat printr-o propoziie DATE icunoaterea exact a rezultatelor problemei, care se va reflecta prin propoziia REZULTATE.

Variabilele prezente n aceste propoziii au anumite semnificaii, presupuse cunoscute.Cunoaterea acestora, scrierea lor explicit, formeaz ceea ce vom numi n continuare specificarea

problemei. Specificarea unei probleme este o activitate foarte important dar nu i simpl.De exemplu, pentru rezolvarea ecuaiei de gradul al doilea, specificarea problemei, poate

fi:

DATE a,b,c; { Coeficienii ecuaiei }

REZULTATE x1,x2; { Rdcinile ecuaiei }

Aceast specificaie este ns incomplet. Nu ntotdeauna ecuaia are rdcini reale. n cazul

________________________________________________________________________________

12


13/165

Structuri de date i algoritmi_______________________________________________________________________________n care rdcinile sunt complexe putem nota prin x1, x2 partea real, respectiv partea imaginar ardcinilor. Sau pur i simplu, nu ne intereseaz valoarea rdcinilor n acest caz, ci doar faptul cecuaia nu are rdcini reale.

Cu alte cuvinte avem nevoie de un mesaj care s ne indice aceast situaie, sau de unindicator, fie el numit ind. Acest indicator va lua valoarea 1 dac rdcinile sunt reale i valoarea 0n caz contrar. Deci specificaia mai complet a problemei este:

DATE a,b,c; { Coeficienii ecuaiei }

REZULTATE ind, {ind = 1 pt. rdcini reale, 0 pt complexe}

x1,x2; {Rdcinile ecuaiei, n cazul ind = 1, respectiv}

{partea real i cea imaginar n cazul ind = 0}

Evident c specificarea problemei este o etap important pentru gsirea unei metode derezolvare i apoi n proiectarea algoritmului corespunztor. Nu se poate rezolva o problem dacaceasta nu este bine cunoscut, adic nu avem scris specificarea problemei.

Cunoate complet problema este prima regul ce trebuie respectat pentru a obine ct mairepede un algoritm corect pentru rezolvarea ei.

I.1.3.1. Algoritmi liniari

Propoziiile CITETE i TIPRETE sunt folosite pentru iniializarea variabilelor deintrare cu datele cunoscute n problem, respectiv pentru tiprirea (aflarea) rezultatelor obinute. netapa de programare propriu-zis acestor propoziii le corespund ntr-un limbaj de programareinstruciuni de intrare-ieire.

Propoziia CITETE se folosete pentru precizarea datelor iniiale, deci a datelorconsiderate cunoscute n problem (numite i date de intrare) i are sintaxa:

CITETE list ;

unde list conine toate numele variabilelor a cror valoare iniial este cunoscut.Deci n propoziia CITETE, n dreapta acestui cuvnt se vor scrie acele variabile care apar

n propoziia DATE n specificarea problemei. Se subnelege c aceste variabile sunt iniializate cuvalorile cunoscute corespunztoare.

Pentru aflarea rezultatelor dorite, pe care calculatorul o va face prin tiprirea lor pe hrtiesau afiarea pe ecran, se folosete propoziia standard:

TIPRETE list ;

________________________________________________________________________________

13


14/165


n construcia list ce urmeaz dup cuvntul TIPRETE fiind trecute numele variabilelor a crorvalori dorim s le aflm. Ele sunt de obicei rezultatele cerute n problem, specificate i n

propoziia REZULTATE.Blocului de atribuire dintr-o schem logic i corespunde n Pseudocod propoziia standard:

[FIE] var := expresie ;

Aceast propoziie este folosit pentru a indica un calcul algebric, al expresiei care urmeazdup simbolul de atribuire ":=" i de atribuire a rezultatului obinut variabilei var. Expresia dindreapta semnului de atribuire poate fi orice expresie algebric simpl, cunoscut din manualele dematematic din liceu i construit cu cele patru operaii: adunare, scdere, nmulire i mprire(notate prin caracterele +, -, *, respectiv /).

Prin scrierea cuvntului FIE ntre paranteze drepte se indic posibilitatea omiterii acestuicuvnt din propoziie. El s-a folosit cu gndul ca fiecare propoziie s nceap cu un cuvnt al limbiiromne care s reprezinte numele propoziiei. De cele mai multe ori vom omite acest cuvnt. Atuncicnd vom scrie succesiv mai multe propoziii de atribuire vom folosi cuvntul FIE numai n prima

propoziie, omindu-l n celelalte.

Din cele de mai sus rezult c o variabil poate fi iniializat att prin atribuire (deci daceste variabila din stnga semnului de atribuire :=) ct i prin citire (cnd face parte din lista

propoziiei CITETE). O greeal frecvent pe care o fac nceptorii este folosirea variabilelorneiniializate. Evident c o expresie n care apar variabile care nu au valori nu poate fi calculat, ea

nu este definit. Deci nu folosii variabile neiniializate.Pentru a marca nceputul descrierii unui algoritm vom folosi propoziia:

ALGORITMUL nume ESTE:

De asemenea, prin propoziia:

SFALGORITM

vom marca sfritul unui algoritm.

Algoritmii care pot fi descrii folosind numai propoziiile prezentate mai sus se numescalgoritmi liniari.

Ca exemplu de algoritm liniar prezentm un algoritm ce determin viteza v cu care a mersun autovehicul ce a parcurs distanaD n timpul T.

Exemplul I.1.

ALGORITMUL VITEZA ESTE: { Algoritmul 1: Calculeaz viteza }

________________________________________________________________________________

14


15/165


{ D = Distana (spaiul) }

{ T = Timpul; V = Viteza }

CITETE D,T; { v:= spaiu/timp }FIE V:=D/T;

TIPRETE V

SFALGORITM

I.1.3.2. Algoritmi cu ramificaii

Foarte muli algoritmi execut anumite calcule n funcie de satisfacerea unor condiii.Aceste calcule sunt redate de structura alternativ prezentat n Figura I.1.b, creia i corespunde

propoziia Pseudocod:

DAC cond

ATUNCI A

ALTFEL B

SFDAC

sau varianta redus a ei:

DAC cond

ATUNCI A

SFDAC

folosit n cazul n care grupul de propoziii B este vid.

Aceste propoziii redau n Pseudocod structura alternativ de calcul. n primul rnd estenecesar verificarea condiiei scrise dup cuvntul DAC. n cazul c aceast condiie esteadevrat se va executa grupul de propoziii A. n cazul n care aceast condiie este fals se vaexecuta grupul de propoziii B, dac este prezent ramura ALTFEL. Indiferent care dintresecvenele A sau B a fost executat, se va continua cu propoziia urmtoare propoziiei DAC, ce

urmeaz dup marcatorul de sfrit SFDAC.O generalizare a structurii alternative realizat de propoziia DAC este structura selectiv:

SELECTEAZ i DINTRE

v1: A1;

v2: A2;

. . .

________________________________________________________________________________

15


16/165


vn: An

SFSELECTEAZ

structur echivalent cu urmtorul text Pseudocod:

DAC i = v1

ATUNCI A1

ALTFEL

DAC i = v2

ATUNCI A2

ALTFEL. . .

DAC i = vn

ATUNCI An

SFDAC

...

SFDAC

SFDAC

Cu propoziiile prezentate pn acum putem descrie un numr nsemnat de algoritmi.Acetia se numesc algoritmi cu ramificaii.

De exemplu, vom descrie un algoritm pentru rezolvarea ecuaiei de gradul al doilea. Amprezentat n I.1.3 aceast problem i am precizat semnificaia variabilelor respective. Pe lngaceste variabile, pentru rezolvarea problemei mai avem nevoie de dou variabile auxiliare:

delta - pentru discriminantul ecuaiei;

r - pentru valoarea radicalului folosit n calculul rdcinilor.

Exemplul I.2.

ALGORITMUL ECGRDOI ESTE: { Algoritmul 2: Rezolvarea }

{ ecuaiei de gradul doi }

CITETE a,b,c; { a,b,c = coeficienii ecuaiei }

FIE delta:= b*b-4*a*c;

DAC delta < 0

________________________________________________________________________________

16


17/165


ATUNCI ind:= 0; {Cazul rdcini complexe }

@r:=radical din (-delta);

x1:=-b/(a+a);x2:= r/(a+a);

ALTFEL ind:=1; {cazul rdcini reale }

@r:=radical din delta;

x1:=(-b-r)/(a+a);

x2:=(-b+r)/(a+a);

SFDAC

TIPRETE ind, x1,x2;

SFALGORITM

I.1.3.3 Algoritmi ciclici

n rezolvarea multor probleme trebuie s efectum aceleai calcule de mai multe ori, sau srepetm calcule asemntoare. De exemplu, pentru a calcula suma a dou matrice va trebui sadunm un element al primei matrice cu elementul de pe aceeai poziie din a doua matrice, aceastadunare repetndu-se pentru fiecare poziie n parte. Alte calcule trebuiesc repetate n funcie de

satisfacerea unor condiii.n acest scop n limbajul Pseudocod exist trei propoziii standard: CTTIMP, REPET i

PENTRU. Propoziia CTTIMP are sintaxa:

CTTIMP cond EXECUT A SFCT

i cere execuia repetat a grupului de propoziii A, n funcie de condiia "cond". Mai exact, seevalueaz condiia "cond"; dac aceasta este adevrat se execut grupul A i se revine la evaluareacondiiei. Dac ea este fals execuia propoziiei se termin i se continu cu propoziia care

urmeaz dup SFCT.Dac de prima dat condiia este fals grupul A nu se va executa niciodat, altfel se va

repeta execuia grupului de propoziii A pn cnd condiia va deveni fals. Din cauz c nainte deexecuia grupului A are loc verificarea condiiei, aceast structur se mai numete structurrepetitiv condiionat anterior. Ea reprezint structura repetitiv prezentat n Figura I.1.c.

Ca exemplu de algoritm n care se folosete aceast structur ciclic s rezolvm algoritmullui Euclid pentru calculul celui mai mare divizor comun a dou numere.

________________________________________________________________________________

17


18/165


Exemplul I.3.

ALGORITMUL Euclid ESTE: {Algoritmul 3: Cel mai mare divizor comun}

CITETE n1,n2; {Cele dou numere a cror divizor se cere}

FIE d:=n1; i:=n2;

CTTIMP i 0 EXECUT

r:=d modulo i; d:=i; i:=r

SFCT

TIPRETE d; { d= cel mai mare divizor comun}

SFALGORITM {al numerelor n1 i n2 }

n descrierea multor algoritmi se ntlnete structura repetitiv condiionat posterior:

REPET A PNCND cond SFREP

structur echivalent cu:

A

CTTIMP not (cond) EXECUT A SFCT

Deci ea cere execuia necondiionat a lui A i apoi verificarea condiiei "cond". Va avealoc repetarea execuiei lui A pn cnd condiia devine adevrat. Deoarece condiia se verificdup prima execuie a grupului A aceast structur este numit structura repetitiv condiionat

posterior, prima execuie a blocului A fiind necondiionat.

Ca exemplu de algoritm n care se folosete aceast propoziie vom scrie un algoritm pentruaproximarea numrului e cu o precizie dat de numrul eps pozitiv, folosindu-ne de dezvoltarea nserie:

e = 1 + 1/1! + 1/2! + 1/3! + ... + 1/n! + ...Specificaia problemei n Pseudocod este:

DATE eps ; { eps>0 }

REZULTATE ve; { aproximarea seriei cu o eroare < eps }

{ deci r=e-ve


19/165


e = 1 + 1/1! + 1/2! + 1/3! + ... + 1/n! + ...

= sn + rn

este mai mic dect ultimul termen adunat la sn, deci rn 0 }

FIE ve:=2.5; t:=0.5; n:=2;

REPET

n:=n+1

t:=t/n;

ve:=ve+t;

PNCND t < eps SFREP

TIPRETE ve;

SFALGORITM

O alt propoziie care cere execuia repetat a unei secvene A este propoziia

PENTRU c:=li; lf [;p] EXECUT A SFPENTRU

Ea definete o structura repetitiv predefinit, cu un numr determinat de execuii alegrupului de propoziii A i este echivalent cu secvena:

c:=li ; final:=lf ;

REPET

A

c:=c+p

PNCND (c>final i p>0) sau (c


20/165


Semnificaia propoziiei PENTRU este clar. Ea cere repetarea grupului de propoziii Apentru toate valorile contorului c cuprinse ntre valorile expresiilor li i lf (calculate o singur datnainte de nceperea ciclului), cu pasul p. Se subnelege c nu trebuie s modificm valorile

contorului n nici o propoziie din grupul A. De multe ori aceste expresii sunt variabile simple, iarunii programatori modific n A valorile acestor variabile, nclcnd semnificaia propoziieiPENTRU. Deci,

Obs: Nu recalcula limitele i nu modifica variabila de ciclare (contorul) n interiorul unei structurirepetitive PENTRU.

S observm, de asemenea, c prima execuie a grupului A este obligatorie, abia dupmodificarea contorului verificndu-se condiia de continuare a execuiei lui A.

Ca exemplu, s descriem un algoritm care gsete minimul i maximul componentelor unuivector de numere reale.

Vom nota prin X acest vector, deci X = (x1, x2, ... , xn).

Specificaia problemei este urmtoarea:

DATE n,(x[i] ,i=1,n);

REZULTATE valmin,valmax;

iar semnificaia acestor variabile se nelege din cele scrise mai sus. Pentru rezolvarea problemeivom examina pe rnd cele n componente. Pentru a parcurge cele n componente avem nevoie de uncontor care s precizeze poziia la care am ajuns. Fie i acest contor. Uor se ajunge la urmtorulalgoritm:

Exemplul I.5.

ALGORITMUL MINMAX ESTE: { Algoritmul 5: Calculul }

{ valorii minime i maxime }

CITETE n,( x[i],i=1,n);

FIE valmin:=x[1]; valmax:=x[1];

PENTRU i:=2;n EXECUTDAC x[i]valmax

ATUNCI valmax:=x[i];

SFDAC

________________________________________________________________________________

20


21/165


SFPENTRU

TIPRETE valmin,valmax;

SFALGORITM

Un rol important n claritatea textului unui algoritm l au denumirile alese pentru variabile.Ele trebuie s reflecte semnificaia variabilelor respective. Deci alege denumiri sugestive pentruvariabile, care s reflecte semnificaia lor. Putem formula astfel regula de mai jos:

Obs:. Alege denumiri sugestive pentru variabile! n exemplul de mai sus denumirile valmin ivalmax spun cititorului ce s-a notat prin aceste variabile.

I.1.4 Calculul efectuat de un algoritm

Fie X1, X2, ..., Xn, variabilele ce apar n algoritmul A. n orice moment al execuieialgoritmului, fiecare variabil are o anumit valoare, sau este nc neiniializat.

Vom numi stare a algoritmului A cu variabilele menionate vectorul s = ( s1,s2,...,sn ) formatdin valorile curente ale celorn variabile ale algoritmului.

Este posibil ca variabila Xj s fie nc neiniializat, deci s nu aib valoare curent, caz ncare valoarea sj este nedefinit, lucru notat n continuare prin semnul ntrebrii '?'.

Prin executarea unei anumite instruciuni unele variabile i schimb valoarea, decialgoritmul i schimb starea.

Se numete calcul efectuat de algoritmul A o secven de stri s 0, s1, s2, ..., sm unde s0 estestarea iniial cu toate variabilele neiniializate, iar sm este starea n care se ajunge dup execuiaultimei propoziii din algoritm.

Exemplul I.6

Algoritmul Nrdivizori calculeaz numrul de divizori proprii ai unui numr dat X1.

P1 CITESTE X1;

P2 FIE X2:=1;

P3 FIE X3:=0;

P4 CTTIMP X1 X2 EXECUT

P5 X2:=X2+1;

P6 DAC X1 modulo X2 = 0

ATUNCI X3:=X3+1

________________________________________________________________________________

21


22/165


SFDAC

SFCT

P7 TIPRETE X1,X3

Presupunnd c X1 = 6, atunci strile prin care trece acest algoritm, deci calculul efectuatde el, este redat mai jos.

s0 = ( ?, ?, ?)

P1(s0) = s1 = ( 6, ?, ?)

P2(s1) = s2 = ( 6, 1, ?)

P3(s2) = s3 = ( 6, 1, 0)

P5(s3) = s4 = ( 6, 2, 0)

P6(s4) = s5 = ( 6, 2, 1)

P5(s5) = s6 = ( 6, 3, 1)

P6(s6) = s7 = ( 6, 3, 2)

P5(s7) = s8 = ( 6, 4, 2)

P6(s8) = s9 = ( 6, 4, 2)

P5(s9) = s10= ( 6, 5, 2)

P6(s10)= s11= ( 6, 5, 2)

P6(s11)= s12= ( 6, 5, 2)P5(s12)= s13= ( 6, 6, 2)

P7(s13)= s14= ( 6, 6, 2)

Execuia (calculul) se va ncheia cu tiprirea valorilor 6 i 2 a celor dou variabile dinpropoziia P7. Se poate observa c cele dou valori tiprite reprezint, prima (X1), numrul citit, iara doua (X3), rezultatul obinut. Rezultatul X3 reprezint numrul divizorilor proprii ai lui X1.

I.1.5 Rafinare n pai succesivi

Adeseori, algoritmul de rezolvare a unei probleme este rezultatul unui proces complex, ncare se iau mai multe decizii. Observaia este adevrat mai ales n cazul problemelor complicate,dar i pentru probleme mai simple din procesul de nvmnt. Este vorba de un proces de detaliere

pas cu pas a specificaiei problemei, proces denumit iproiectare descendent, sau rafinare n paisuccesivi. Algoritmul apare n mai multe versiuni succesive, fiecare versiune fiind o detaliere aversiunii precedente.

n versiunile iniiale apar propoziii nestandard, clare pentru cititor, dar neprecizate prinpropoziii standard. Urmeaz ca n versiunile urmtoare s se revin asupra lor. Algoritmul apare

________________________________________________________________________________

22


23/165


24/165


Decizia ce trebuie luat este cum s verificm apartenena unui elementul x i la mulimea Yformat din k elemente. Pentru aceasta calculm indicatorul r, egal cu 0 dac rspunsul este negativ

i egal cu 1 n caz contrar. Aceasta se poate face cu secvena de propoziii:

FIE r:=0; j:=1;

CTTIMP (r=0) i (j


25/165


26/165


Aceast propoziie este urmat de textul efectiv al subalgoritmului, text care precizeazcalculele necesare rezolvrii subproblemei corespunztoare. Descrierea se va ncheia cu cuvntulSFSUBALGORITM sau SF-nume.

Exemplul I.11

S considerm ca exemplu un subalgoritm cu numele MAXIM, care determin maximuldintre componentele vectorului X = (x1, x2, ..., xn).

Datele cunoscute pentru acest subalgoritm sunt vectorul X i numrul n al componentelorvectorului X. Ca rezultat vom obine maximul cerut, pe care-l vom nota cu max. n concluziespecificarea subproblemei este:

DATE n, X

REZULTATE max

Deci lista parametrilor formali conine trei variabile, n, X i max. Pentru a gsi maximulparcurgem toate componentele vectorului X, reinnd n variabila max valoarea cea mai marentlnit. Evident, trebuie s ncepem cu max = x1. Subalgoritmul este prezentat n continuare.

SUBALGORITMUL maxim(n,X,max) ESTE: {Calculeaz valoarea maxim}{dintre cele n componente ale lui X}FIE max:=x[1];PENTRU i:=2;n EXECUT

DAC x[i]>maxATUNCI max:=x[i];

SFDACSFPENTRUSF-maxim

Una dintre greelile frecvente ale nceptorilor const n introducerea n corpul

subalgoritmului a unor instruciuni de citire a datelor presupuse cunoscute, sau de tiprire arezultatelor obinute. Acest lucru denot o nenelegere a conceptului de subalgoritm i a roluluisubalgoritmilor n programare. Subalgoritmul rezolv o subproblem - care e o parte dintr-o

problema complex de rezolvat.De obicei, datele presupuse cunoscute pentru subproblem, nu sunt datele iniiale cunoscute

n problema iniial; ele sunt rezultatul unor calcule efectuate nainte de apelul subalgoritmului. ngeneral, ele nu sunt cunoscute de programator, fiind rezultatul unor calcule fcute de algoritm.Analog, rezultatele obinute de subalgoritm sunt adesea doar valori intermediare, necesare ncontinuare, fr a fi ns obligatoriu i rezultate ale problemei iniiale. De aceea nu este necesar sle tiprim; este sarcina algoritmului apelant s trateze rezultatele obinute de subalgoritm cum credede cuviin.

Obs. Evit s citeti i s tipreti ntr-un subalgoritm.

Excepie de la aceast regul o fac subalgoritmii dedicai citirilor unor date, sau tipririlorunor rezultate. n acest caz, citirea, respectiv tiprirea unor date este cerut expres n enunul

________________________________________________________________________________

26


27/165


28/165


29/165


30/165


31/165


pozitiv r astfel nct x = r.

Vom folosi un algoritm de aproximare a lui r. Deci specificarea fcut nu este complet,neputnd gsi un algoritm care s rezolve direct problema n forma enunat. Vom modifica aceastspecificare, cernd s se calculeze raproximativ, cu o eroare ce nu depete un numr real pozitiveps prestabilit. Ajungem astfel la urmtoarea specificare:

DATE eps,x; { eps, Rx , eps>0 i x 0 }REZULTATE r; { xr < eps }

b. Urmeaz s precizm metoda de rezolvare a problemei. Se tie c exist mai multe metode decalcul al radicalului. Menionm urmtoarele dou posibiliti:- ca limit a unui ir convergent la r(definit printr-o relaie de recuren);

- prin aproximarea soluiei ecuaiei x = r.

Alegem pentru exemplificare metoda a doua, deci l vom calcula pe rrezolvnd ecuaia x = r.

Pentru rezolvarea ecuaiei generale f (x) = 0 exist mai multe metode. Alegem pentrurezolvare metoda coardei i a tangentei.

Aceast metod const n micorarea repetat a intervalului [a,b] care conine rdcina rcutat, la intervalul [a',b'], aa cum se poate vedea n Figura 1.2. Variabilele folosite n descriereaalgoritmului sunt:

a i b, reprezentnd capetele intervalului n care se afl rdcina;rmijlocul intervalului (a,b) n momentul n care b-a < eps, deci valoarea cutat.

Figura 1.2.:Grafic pentru metoda coardei i a tangentei.

Algoritmul propriu-zis (secvena de propoziii care obine rezultatele dorite pornind de la

________________________________________________________________________________

31


32/165


33/165


REPETa := E1; {abscisa punctului de intersecie a axei OX cu}{coarda ce unete punctele (a,f(a)) i (b,f(b))}

b := E2; {abscisa punctului de intersecie a axei OX cu tangenta}{ n punctul (b,f(b)) dus la graficul funciei f(t) = t2-x }PNCND b-a


34/165


35/165

Structuri de date i algoritmi_______________________________________________________________________________sistemului identificm dou subprobleme independente:

- reducerea sistemului, prin metoda lui Gauss, la un sistem triunghiular echivalent;

- rezolvarea sistemului triunghiular obinut.Mai mult, subproblema reducerii sistemului conine ca subprobleme determinarea ecuaiei

n care rmne xi i care este folosit la reducerea acestei necunoscute din celelalte ecuaii,schimbarea a dou ecuaii ntre ele, deci interschimbarea a dou linii din matricea extins ieliminarea propriu-zis. Subalgoritmul PIVOT, corespunztor primei subprobleme, determin caredintre ecuaiile de rang i, i+1, ..., n are coeficientul lui xi maxim n valoare absolut, caz n careerorile introduse din cauza aproximrilor n calcule cu numere reale sunt minime. SubalgoritmiiINTERSCHIMB i ELIMIN corespund celorlalte dou subprobleme. Arborele de programarecorespunztor se d n Figura.1.5.

Exemplul I.17

Algoritmul REZSISTEM este:

Cheam CITSISTEM(n, A, B)

Cheam SISTEM(n, A, B, kod)

Dac kod = 1 atunci Cheam TIPSOL(n, B)

altfel Tiprete "Sistemul nu este compatibil determinat."

sfdac

sf-RezSistem

Figura 1.5.Arborele de programare pentru rezolvarea sistemului

Subalgoritmul SISTEM pentru rezolvarea unui sistem liniar de n ecuaii cu n necunoscuteeste prezentat n continuare.

________________________________________________________________________________

35


36/165


37/165


{numai zerouri. ind=1 pt.sistem determinat}

{in care caz solutia se pune in vectorul B}

{si ind=0 dac e nedeterminat sau incompatibil}Fie r1:=b[n]; ind:=1;

Dac a[n,n]=0

atunci ind:=0

altfel b[n]:=r1/a[n,n]

sfdac

Fie i:=n-1;

Cttimp (ind=1) i (i>=1) execut

Dac a[i,i]=0atunci ind:=0

altfel

r1:=b[i];

Pentru k:=i+1,n execut

r:=a[i,k]*b[k]; r1:=r1-r;

sfpentru

b[i]:= r1/a[i,i]

sfdacFie i:=I-1

sfct

sf-REZOLV

Subalgoritmul PIVOT(n,A,i,j) este: {j primete o valoare >=i pentru care}

Fie j:=i; { a[j,i] e maxim n valoare absolut}

Pentru l:=i+1, n execut

Dac a[l,i] > a[j,i]atunci j:=l

sfdac

sfpentru

sf-PIVOT

Subalgoritmul INTERSCHIMB(i,j,n,A,B) este: {Schimb ntre ele liniile i i j din matriceaA}

________________________________________________________________________________

37


38/165


{ de ordinul n i termenii liberi corespunztori}

Pentru l:=1; n execut

r:=a[i,l]; a[i,l]:=a[j,l]; a[j,l]:=rsfpentru

Fie r:=b[i]; b[i]:=b[j]; b[j]:=r

sf-INTERSCHIMB;

Subalgoritmul ELIMIN(n,A,B,i) este: {Elimin necunoscuta x[i] din ecuaiile i+1,...,n}

Fie r:=a[i,i]; { x[i] din ecuaiile n ipoteza a[i,i] 0}

Pentru k:=i,n execut {Imparte ecuaia nr i cu r}

Fie a[i,k]:=a[i,k]/rsfpentru

Fie b[i] := b[i]/r

Pentru j:=i+1,n execut {Elimin necunoscuta}

Fie r:=a[j,i]; {x[i] din ecuaia nr.j}

Pentru k:=1,n execut

a[j,k]:=a[j,k]-r*a[i,k];

sfpentru

Fie b[j]:=b[j]-r*b[i]sfpentru

sf-ELIMIN

n multe cri metoda top-down este ntlnit i sub denumirea stepwise-refinement, adicrafinare n pai succesivi. Este vorba de un proces de detaliere pas cu pas a specificaiei, denumit

proiectare descendent. Algoritmul apare n diferite versiuni succesive, fiecare fiind o detaliere aversiunii precedente. n aceste versiuni succesive apar multe enunuri nestandard ce urmeaz a fi

precizate treptat prin propoziii standard. Se recomand ca ele s rmn comentarii n versiunea

final. Algoritmul apare n versiuni succesive, tot mai complet de la o versiune la alta. n versiuneafinal n algoritm apar numai propoziii standard. Un exemplu de rafinare succesiv a fost dat nseciunea 1.5.

Diferena ntre metoda top-down i metoda rafinrii succesive este neesenial, scopulurmrit fiind acelai: concentrarea ateniei asupra prilor importante ale momentului i amnareadetaliilor pentru mai trziu. Dac ar fi necesar s le deosebim am spune c metoda top-down serefer la nivelul macro iar metoda rafinrii succesive la nivel micro. La nivel macro se doretedescompunerea unei probleme complexe n subprobleme. La nivel micro se dorete obinerea unuimodul n versiune final. ntr-o versiune intermediar pot fi prezente numai prile importante aleacestuia, urmnd s se revin asupra detaliilor n versiunile urmtoare, dup ce aspectele importante

________________________________________________________________________________

38


39/165

Structuri de date i algoritmi_______________________________________________________________________________au fost rezolvate.

Avantajele proiectrii top-down (cunoscut i sub denumirea "Divide et impera") suntmultiple. Avantajul principal const n faptul c ea permite programatorului s reduc

complexitatea problemei, subproblemele n care a fost descompus fiind mai simple, i s amnedetaliile pentru mai trziu. n momentul n care descompunem problema n subprobleme nu negndim cum se vor rezolva subproblemele ci care sunt ele i conexiunile dintre ele.

Proiectarea descendent permite lucrul n echipe mari. Prin descompunerea problemei nmai multe subprobleme, fiecare subproblem poate fi dat spre rezolvare unei subechipe. Fiecaresubechip nu cunoate dect subproblema pe care trebuie s o rezolve.

Metoda "Divide et Impera" poate fi folosit nu numai la mprirea problemei nsubprobleme ci i la mprirea datelor n grupe mai mici de date. n acest caz ea este cunoscut subnumele de metoda divizrii metod prezentat n seciunea 8.1. Un astfel de procedeu este folosit desubalgoritmul Quicksort, care va fi prezentat n seciunea 7.2.

Metoda ascendent (bottom-up) pornete de la propoziiile limbajului i de la subalgoritmiexisteni, pe care i asambleaz n ali subalgoritmi pentru a ajunge n final la algoritmul dorit. Cualte cuvinte, n cazul metodei ascendente va fi scris mai nti subalgoritmul apelat i apoi cel careapeleaz. Ca rezultat al proiectrii ascendente se ajunge la o mulime de subalgoritmi care seapeleaz ntre ei. Este important s se cunoasc care subalgoritm apeleaz pe care, lucru redat

printr-o diagram de structur, ca i n cazul programrii descendente.

Aceast metod are marele dezavantaj c erorile de integrare vor fi detectate trziu, abia nfaza de integrare. Se poate ajunge abia acum la concluzia c unii subalgoritmi, dei coreci, nu sunt

utili. De cele mai multe ori nu se practic o proiectare ascendent sau descendent pur ci ocombinare a lor, o proiectare mixt.

I.2.5. Proiectarea modular

Prin proiectare (programare) modular nelegem metoda de proiectare (programare) a unuialgoritm pentru rezolvarea unei probleme prin folosirea modulelor.

Dar ce este un modul? Modulul este considerat (Frentiu M. et al. [1986]) o unitatestructural de sine stttoare, fie program, fie subprogram, fie o unitate de program. Un modulpoate conine sau poate fi coninut ntr-alt modul. Un modul poate fi format din mai multesubmodule. Astfel, n Pseudocod fiecare subalgoritm i algoritmul principal sunt consideratemodule. n limbajele de programare cu structur de bloc, de exemplu n Turbo Pascal UNIT-urile

pot fi considerate module. La compilarea separat un grup de subprograme compilate deodatconstituie un modul, dar acest modul poate fi considerat ca o mulime de submodule din care estecompus.

Este ns important ca fiecare modul s-i aib rolul su bine precizat, s realizeze o funcien cadrul ntregului program. El apare n mod natural n descompunerea top-down.

________________________________________________________________________________

39


40/165


Indiferent c privim modulul ca un singur subalgoritm, un grup de subalgoritmi, sau unalgoritm de sine stttor ce apeleaz ali subalgoritmi, considerm modulele relativ independente,dar cu posibiliti de comunicare ntre ele. Astfel, un modul nu trebuie s fie influenat de maniera

n care se lucreaz n interiorul altui modul. Orice modificare ulterioar n structura unui program,dac funcia pe care o realizeaz un modul M nc este necesar, acest modul trebuie s fie util ifolosit n continuare fr modificri.

Rezult c programarea modular se bazeaz pe descompunerea problemei n subproblemei proiectarea i programarea separat a subalgoritmilor corespunztori. De altfel, considerm cntr-o programare serioas nu se poate ajunge la implementare fr a avea n prealabil algoritmiidescrii ntr-un limbaj de descriere (la noi Pseudocod). Deci programarea modular se refer n

primul rnd la proiectarea modular a algoritmilor i apoi la traducerea lor n limbajul deprogramare ales, innd seama de specificul acestui limbaj. Programarea modular este strns legatde programarea ascendent i de programarea descendent, ambele presupunnd folosireasubalgoritmilor pentru toate subproblemele ntlnite.

Avantajele programrii modulare sunt multiple. Menionm n cele ce urmeaz ctevadintre ele:

Descompunerea unei probleme complexe n subprobleme este un mijloc convenabili eficient de a reduce complexitatea (Principiul Divide et impera acioneaz i n

programare). Este evident c probabilitatea apariiei erorilor n conceperea unuiprogram crete cu mrimea programului, lucru confirmat i de experiena practic.De asemenea, rezolvnd o problem mai simpl, testarea unui modul se poate facemult mai uor dect testarea ntregului algoritm.

Apoi, faptul c trebuiesc proiectate mai multe subprograme pentru subproblemele

ntlnite, permite munca mai multor programatori. S-a ajuns astfel la munca nechip, modalitate prin care se ajunge la scurtarea termenului de realizare a

produsului program.

Modulele se pot refolosi ori de cte ori avem nevoie de ele. Astfel, s-a ajuns lacompilarea separat a subprogramelor i la pstrarea subprogramelor obinute n

biblioteci de subprograme, de unde ele se pot refolosi la nevoie. Sunt cunoscuteastzi multe astfel de biblioteci de subprograme. Reutilizabilitatea acestorsubprograme este o proprietate foarte important n activitatea de programare. Eaduce la mrirea productivitii n programare, dar i la creterea siguranei nrealizarea unui produs corect.

Uneori, n timpul proiectrii algoritmului sau a implementrii lui, se ajunge laconcluzia c proiectarea a fost incomplet sau c unele module sunt ineficiente. i naceast situaie programarea modular este avantajoas, ea permind nlocuireamodulului n cauz cu altul mai performant.

Una din activitile importante n realizarea unui program este verificarea corectitudiniiacestuia. Experiena a artat c modulele se pot verifica cu att mai uor cu ct sunt mai mici.Abilitatea omului de a nelege i analiza corectitudinea unui subalgoritm este mult mai mare pentrutexte scurte. n unele cri chiar se recomand a nu se folosi subalgoritmi mai mari dect 50 de

________________________________________________________________________________

40


41/165

Structuri de date i algoritmi_______________________________________________________________________________propoziii. Sigur c o astfel de limit nu exist, dar se recomand descompunerea unui subalgoritmn ali subalgoritmi oricnd acest lucru este posibil n mod natural, deci aceti noi subalgoritmirezolv subprobleme de sine stttoare, sau realizeaz funcii bine definite.

Ca exemplu de proiectare modular ne propunem s dm un algoritm pentru rezolvareaurmtoarei probleme:

Exemplul I.18

S se verifice dac mulimea finit K, pe care s-au definit dou operaii, este corp n raportcu aceste operaii.

n vederea proiectrii unui algoritm pentru rezolvarea ei avem nevoie de specificareaproblemei. S observm mai nti c nu a fost precizat exact natura elementelor mulimii K = { k1,k2, ..., kn }.

Trebuie s specificm modul de definire al unei operaii O peste mulimea K. Evident,pentru a definii o operaie pe mulimea finit K, trebuie ca pentru oricare dou elemente ki, kj Ks cunoatem O(k[i], k[j]) = k[s] K.

Deci O ar fi o matrice ptratic de ordinul n cu elemente din K. Cum natura acestorelemente nu este precizat, convenim s reinem doar indicii acestor elemente, cu alte cuvinte slucrm cu mulimea K' = { 1, 2, ... , n }.

Ea este precizat prin numrul n. n acest caz definirea operaiei O va fi simpl,exprimndu-se printr-o matrice ptrat de ordinul n cu elemente din K'. Deci specificarea problemei

este:

DATE n, O1, O2; {O1, O2 = operaii peste K'}

REZULTATE kod {kod = 0 pentru corp, altfel kod > 0}

{Prin valoarea lui kod se poate reine care}

{proprietate din definiia corpului nu a fost ndeplinit}

Trecnd la proiectarea algoritmului, s observm c la citirea datelor se ntlnesc douoperaii, deci se repet aceleai operaii de dou ori. Tiprirea rezultatului este mult mai simpl: setiprete valoarea lui kod. Decidem s folosim un subalgoritm CITOP(n,O) pentru citirea uneioperaii, subalgoritm care va fi apelat n modulul principal de dou ori: prima dat pentru citirea luiO1, apoi pentru citirea lui O2.

naintea acestor apeluri n modulul principal se va citi valoarea lui n. Apoi se va apelasubalgoritmul CORP(n,O1,O2,kod) pentru verificarea propriu zis. Ea const din trei verificri:

a - este mulimea grup n raport cu operaia O1 ?

b - scznd elementul neutru pentru O1, este noua mulime grup n raport cu O2;

c - este O2 distributiv fa de O1?

________________________________________________________________________________

41


42/165


Putem realiza verificrile a i b cu acelai subalgoritm GRUP(p,n,O,e,kod) care verificaxiomele grupului, reinnd rezultatul n kod, iar n e elementul neutru. Aceasta este posibil dacelementul neutru pentru O1 este 1, cele dou apeluri fcndu-se prima cu p=1, a doua cu p=2 (deci

elementul neutru pentru O1 este eliminat la a doua verificare). n cazul n care elementul neutrupentru operaia O1 este e1 vom inter-schimba numerotarea celor dou elemente, deci 1 va devenielement neutru !

Pentru verificarea axiomelor grupului se folosesc patru module: COMUTATIV, NEUTRU,INVERS i ASOCIATIV. Ele corespund subalgoritmilor:

COMUTATIV(n,O,kod) verific dac operaia O e comutativ;

NEUTRU(n,O,e) gsete elementul neutru e pentru O (sau e=-1);

INVERS(n,O,e,kod) verific existena inverselor;

ASOCIATIV(n,O,kod) verific dac O este asociativ.

Se ajunge la arborele de programare din Figura.1.6.

Figura 1.6.Arborele de programare pentru verificarea axiomelor corpului.

Ca un al doilea exemplu de definire i folosire a subalgoritmilor, s considerm urmtoareaproblem:

Se dau trei mulimi de numere:

A = { a1, a2, ... , am }

B = { b1, b2, ... , bn }

C = { c1, c2, ... , cp }

Se cere s se tipreasc n ordine cresctoare elementele fiecrei mulimi, precum i amulimilor A B, B C, C A.

n rezolvarea acestei probleme se ntlnesc urmtoarele subprobleme:

________________________________________________________________________________

42


43/165


S1: S se citeasc elementele unei mulimi;

S2: S se efectueze reuniunea a dou mulimi;

S3: S se tipreasc elementele unei mulimi;S4: S se ordoneze cresctor elementele unei mulimi.

Presupunnd c pentru rezolvarea acestor subprobleme am conceput subalgoritmii:

CITMUL(m,A);

REUNIUNE(m,A,n,B,k,R);

TIPMUL(m,A);

ORDON(m,A);

care sunt specificai mai jos (la locul definirii lor) prin comentarii, algoritmul de rezolvare aproblemei de mai sus este dat n continuare. ntruct operaiile respective se folosesc de mai multeori (de 3 ori), am definit un subalgoritm TIPORDON(m,A) care ordoneaz mai nti elementelemulimii A i apoi le tiprete.

ALGORITMUL OPER-MULTIMI ESTE: { Algoritmul 3.6: Subalgoritmi }

CHEAM CITMUL(m,A);

CHEAM CITMUL(n,B);

CHEAM CITMUL(p,C);

CHEAM TIPORDON(m,A);CHEAM TIPORDON(n,B);

CHEAM TIPORDON(p,C);

CHEAM REUNIUNE(m,A,n,B,k,R);

CHEAM TIPORDON(k,R);

CHEAM REUNIUNE(n,B,p,C,k,R);

CHEAM TIPORDON(k,R);

CHEAM REUNIUNE(p,C,m,A,k,R);

CHEAM TIPORDON(k,R);SFALGORITM

Subalgoritmii apelai mai sus sunt definii n continuare.

SUBALGORITMUL CITMUL(n,M) ESTE: {Citete n i M}

CITETE n; {n=nr. elementelor mulimii}

________________________________________________________________________________

43


44/165


CITETE (m[i],i=1,n); {M=mulimea cu elementele m1,m2,...,mn}

SF-CITMUL

SUBALGORITMUL ORDON(n,M) ESTE: {Ordoneaz cresctor cele n}

REPET {elemente ale mulimii M}

FIE ind:=0; {Cazul M este ordonat}

PENTRU i:=1;n-1 EXECUT

DAC m[i]>m[i]+1 ATUNCI {schimb ordinea celor}

FIE t := m[i]; {dou elemente}

m[i]:= m[i]+1; m[i]+1:=t;

ind:=1; {Cazul M nu era ordonat}SFDAC

SFPENTRU

PNCND ind=0 SFREP

SF-ORDON

SUBALGORITMUL REUNIUNE(m,A,n,B,k,R) ESTE: { R := A U B }

{ k = numrul elementelor mulimii R }

FIE k:=m; R := A;PENTRU j:=1,n EXECUT

FIE ind:=0; {Ipoteza bj nu e in A}

PENTRU i:=1;m EXECUT

DAC b[j]=a[i] ATUNCI

ind:=1 {bj este in A}

SFDAC

SFPENTRU

DAC ind=0 ATUNCIk:=k+1; r[k]:=b[j];

SFDAC

SFPENTRU

SF-REUNIUNE

SUBALGORITMUL TIPMUL(n,M) ESTE: { Tiprete cele n elemente }

PENTRU i:=1;n EXECUT { ale mulimii M }

________________________________________________________________________________

44


45/165


TIPRETE mi

SFPENTRU

SF-TIPMUL

SUBALGORITMUL TIPORDON(n,M) ESTE: { Ordoneaz i tiprete }

CHEAM ORDON(n,M); { elementele mulimii M }

CHEAM TIPMUL(n,M);

SF-TIPORDON

Tot ca exemplu de folosire a subalgoritmilor, vom scrie un algoritm pentru rezolvareaurmtoarei probleme:

Exemplul I.19

Dirigintele unei clase de elevi dorete s obin un clasament al elevilor n funcie de mediageneral. n plus, pentru fiecare disciplin n parte dorete lista primilor ase elevi.

n rezolvarea acestei probleme este necesar gsirea ordinii n care trebuiesc tiprii elevii nfuncie de un anumit rezultat: nota la disciplina "j", sau media general. Am identificat prin urmaredou subprobleme independente, referitoare la:

(1) aflarea ordinii n care trebuie tiprite n numere pentru a le obine ordonate;(2) tiprirea elevilor clasei ntr-o anumit ordine.

Prima subproblem se poate specifica astfel:

Dndu-se numerele x1, x2, ... , xn, gsii ordinea o1, o2, ..., on, n care aceste numere devinordonate descresctor, adic

x[o1] x[o2] ... x[on] .

Pentru rezolvarea ei vom da un subalgoritm ORDINE n care intervin trei parametriformali:

- n, numrul valorilor existente;

- X, vectorul acestor valori;

- O, vectorul indicilor care dau ordinea dorit.

Primii doi parametri marcheaz datele presupuse cunoscute, iar al treilea, rezultatelecalculate de subalgoritm.

SUBALGORITMUL ORDINE(n,X,O) ESTE: {n, numrul valorilor existente; X, vectorulacestor }

________________________________________________________________________________

45


46/165


47/165


Algoritmul este:

ALGORITMUL CLASAMENT ESTE: { Algoritmul 3.7: Ordonare }

CITETE m, {numrul disciplinelor i}

n, {al elevilor}

NUME[i], i=1,n, {numele elevilor}

NOTE[i,j], j=1,m, i=1,n; {notele elevilor}

PENTRU i:=1;n EXECUT { calculeaz media general}

FIE S:=0; {a elevului i}

PENTRU j:=1;m EXECUTS:=S+NOTE[i,j];

SFPENTRU

FIE MEDII[i]:=S/m

SFPENTRU

CHEAM ORDINE(n,MEDII,O);

CHEAM TIPAR(n,NUME,O)

PENTRU j:=1;m EXECUT

CHEAM ORDINE(n,NOTE.j,O);CHEAM TIPAR(n,NUME,O);

SFPENTRU

SF-ALGORITM

ntr-un algoritm, parametrii formali i actuali pot fi funcii sau proceduri. n continuare esteprezentat un astfel de exemplu, n care se calculeaz radicalii de ordinul doi i trei din constanta mmrezolvnd ecuaiile:

x2 - mm = 0, notat g(x) = 0,

respectiv

x3 - mm = 0, notat h(x) = 0.

Pentru rezolvarea unei ecuaii se pot folosi mai multe metode. n program am ales dou:metoda njumtirii i metoda coardei. Metoda coardei este descris amnunit n seciuneaurmtoare. Metoda njumtirii const n njumtirea intervalului [a,b] care conine rdcina ireinerea aceluia n care se afl rdcina, subinterval care va fi noua valoare a lui [a,b]. Calculul sencheie n momentul n care lungimea intervalului [a,b] este mai mic dect , care ne d eroarea cu

________________________________________________________________________________

47


48/165

Structuri de date i algoritmi_______________________________________________________________________________care dorim s aflm rdcina.

ntruct metoda coardei folosete i prima derivat, am notat prin f1, respectiv g1 derivatelefunciilor f i g. Prin c i t s-au notat cele dou extremiti ale intervalului care conine rdcina, t

fiind extremitatea n care se duce tangenta.SUBALGORITMUL coarda(c,t,r,f,f1) ESTE: {Se rezolv ecuaia f(x)=0 prin metoda

coardei}

{c,t sunt extremitile intervalului care conine}

{rdcina, iar f1este derivata lui f }

{r este rdcina care se calculeaz}

REPET

c:=c-f(c)*(t-c)/(f(t)-f(c));

t:=t-f(t)/f1(t);PNCND ct < 0.00001;

FIE r:=(c+t)/2

SF-coarda

SUBALGORITMUL juma(a,b, r, f,f1) ESTE: {Se rezolv prin metoda njumtirii}

{ecuaia f(x)=0, care are o rdcin n [a,b]}

{r= rdcina obinut, iar f1 este derivata lui f}

REPETr:=(a+b)/2;

DAC f(a)*f(r)


49/165


TIPRETE 'njumtire Coarda ' ;

CHEAM Rezec(1,2,rj,g,g1,juma);

CHEAM Rezec(1,2,rc,g,g1,coarda);TIPRETE rj,rc ;

CHEAM Rezec(1,2,rj,h,h1,juma);

CHEAM Rezec(1,2,rc,h,h1,coarda);

TIPRETE rj,rc ;

SFALGORITM

Prin proiectare (programare) modular nelegem metoda de proiectare (programare) aunui algoritm pentru rezolvarea unei probleme prin folosirea modulelor.

Dar ce este un modul? Modulul este considerat [Schach90, Freniu94] o unitate structuralde sine stttoare, fie program, fie subprogram, fie o unitate de program. Un modul poate coninesau poate fi coninut ntr-alt modul. Un modul poate fi format din mai multe submodule. Astfel, nPseudocod fiecare subalgoritm i algoritmul principal sunt considerate module. n limbajele de

programare cu structur de bloc (de exemplu n Turbo Pascal, prezentat n capitolul trei) UNIT-urilepot fi considerate module. La compilarea separat un grup de subprograme compilate deodatconstituie un modul, dar acest modul poate fi considerat ca o mulime de submodule din care estecompus.

Este ns important ca fiecare modul s-i aib rolul su bine precizat, s realizeze o funcien cadrul ntregului program. El apare n mod natural n descompunerea top-down.

Indiferent c privim modulul ca un singur subalgoritm, un grup de subalgoritmi, sau unalgoritm de sine stttor ce apeleaz ali subalgoritmi, considerm modulele relativ independente,dar cu posibiliti de comunicare ntre ele. Astfel, un modul nu trebuie s fie influenat de manieran care se lucreaz n interiorul altui modul. Orice modificare ulterioar n structura unui program,dac funcia pe care o realizeaz un modul M nc este necesar, acest modul trebuie s fie util ifolosit n continuare fr modificri.

Rezult c programarea modular se bazeaz pe descompunerea problemei n subproblemei proiectarea i programarea separat a subalgoritmilor corespunztori. De altfel, considerm cntr-o programare serioas nu se poate ajunge la implementare fr a avea n prealabil algoritmiidescrii ntr-un limbaj de descriere (la noi Pseudocod). Deci programarea modular se refer n

primul rnd la proiectarea modular a algoritmilor i apoi la traducerea lor n limbajul deprogramare ales, innd seama de specificul acestui limbaj. Programarea modular este strns legatde programarea ascendent i de programarea descendent, ambele presupunnd folosireasubalgoritmilor pentru toate subproblemele ntlnite.

I.2.5. Apel recursiv

n exemplele anterioare se observ c apelul unui subprogram se face dup ce el a fostdefinit. Este ns posibil ca un subalgoritm s se apeleze pe el nsui. ntr-un astfel de caz spunem

________________________________________________________________________________

49


50/165

Structuri de date i algoritmi_______________________________________________________________________________c apelul este recursiv, iar subalgoritmul respectiv este definit recursiv.

Ca exemplu, definim n continuare o funcie care calculeaz recursiv valoarea n!. Se vafolosi formula:

( )

=

>=

0,1

0,!1!

n

nnnn

Recursivitatea const n faptul c n definiia funciei Factorial n argumentul n se foloseteaceeai funcie Factorial dar de argument n-1. Deci funcia Factorial se apeleaz pe ea nsi. Esteimportant ca numrul apelurilor s fie finit, deci ca procedeul de calcul descris s se termine.

FUNCTIA Factorial(n) ESTE:DAC n=0 ATUNCI

Factorial:=1ALTFEL

Factorial:= n*Factorial(n-1)SFDACSF-Factorial;

I.2.6. Programarea structurat

Programarea structurat este un stil de programare aprut n urma experienei primilor ani deactivitate. Ea cere respectarea unei discipline de programare i folosirea riguroas a ctorva structuride calcul. Ca rezultat se va ajunge la un algoritm uor de urmrit, clar i corect.

Termenul programare, folosit n titlul acestei seciuni i consacrat n literatura despecialitate, este folosit aici n sens larg i nu este identic cu cel de programare propriu-zis. Estevorba de ntreaga activitate depus pentru obinerea unui program, deci att proiectarea algoritmuluict i traducerea acestuia n limbajul de programare ales.

Bhm i Jacopini [1966] au demonstrat c orice algoritm poate fi compus din numai treistructuri de calcul:- structura secvenial;- structura alternativ;- structura repetitiv.

I.3. Probleme propuse

I. Descriei n Pseudocod subalgoritmi care calculeaz urmtoarele funcii:

1. Pentru nN funcia Prim(n) calculeaz al n-lea numr prim.

2. Pentru z,l,aN dai, 1z31, 1l12, 1900


51/165


4. Pentru polinomul P de gradul n cu coeficieni reali dat i xR funcia VALPOL(x,n,P) dvaloarea polinomului P n punctul x.

5. Pentru k,nN, 0kn, funcia C(n,k) calculeaz numrul combinrilor de n obiecte luate cte k.

6. Pentru vectorii X i Y cu n componente, funcia E(n,X,Y) d valoarea 0 dac X=Y, respectiv idac i este cel mai mic indice pentru care xi < yi.

7. Cunoscnd mulimile A i B funcia INCLUS(A,B) verific dac mulimea A este inclus nmulimea B;

8. Fie f o funcie de forma f : {1, 2, ..., m} {1, 2, ..., n}.

Definim T(f) egal cu 1 dac f este o funcie injectiv, egal cu 2 dac f este surjectiv, egal cu 3 dacf este bijectiv, i 0 n caz contrar. Se d funcia f prin perechile de elemente (x,f(x)) care definescgraficul su. S se calculeze T(f).

9. Se d o relaie binar R prin graficul su. S se calculeze E(R) prin definiie egal cu 0 dac Reste o relaie de recuren i egal cu 1 n caz contrar.

10. irul Fibonacci este definit astfel: f0=f1=1 i fn=fn-1+fn-2, pentru n >1. Pentru nN dat calculaiF(n)=fn.

11. Pentru nN dat calculai j(n), unde j este funcia lui Euler, deci j(n) este numrul numerelor

mai mici dect n i relativ prime cu n.

12. Pentru nN dat calculai P(n), unde P(n) este 0 dac numrul n este perfect i 1 n caz contrar(un numr n este perfect dac este egal cu suma divizorilor si mai mici dect el nsui. Exemplu:6=1+2+3)

II. Scriei subalgoritmi pentru rezolvarea urmtoarelor probleme:

1. Cunoscnd mulimile A i B calculai C = A B;

2. Cunoscnd mulimile A i B calculai C = A B;

3. Dndu-se vectorul X cu n componente, tergei toate componentele care se repet;

4. Dndu-se vectorul X cu n componente numere ntregi ordonate cresctor i aZ inserai pe a nX astfel nct X s rmn ordonat cresctor;

5. Dndu-se dou polinoame calculai suma lor;

6. Dndu-se dou polinoame calculai produsul lor;

________________________________________________________________________________

51


52/165


7. Dndu-se dou matrice calculai suma lor;

8. Dndu-se dou matrice ptrate de ordinul n calculai produsul lor;

9. Dndu-se dou numere A i B prin reprezentrile lor n baza p gsii suma lor A+B prinreprezentarea ei n baza p;

10. Dndu-se numerele reale x1, x2,... ,xn, determinai secvena de termeni consecutivi care aresuma maxim.

11. Se dau p,qN i numrul A prin reprezentarea sa n baza p. Determinai reprezentarea sa nbaza q.

12. Se d nN, n2. S se formeze matricea ptrat A de ordinul n ale crei coloane scrise unadup alta constituie primii n2 termeni ai irului1,2,3,4,5,6,7,8,9,1,0,1,1,1,2,1,3,1,4,1,5,1,6,1,7,1,8,1,9,2,0, ... obinut din scrierea cifrelor

semnificative ale numerelor naturale.

III. Proiectai prin metoda top-down algoritmi pentru rezolvarea urmtoarelor probleme:

1. Se d un ir de numere naturale x1, x2, ..., xn. Spunem c dou numere naturale sunt prietene dacscrierea unui numr (n baza 10) este obinut prin scrierea cifrelor celuilalt n ordine invers (deexemplu 3678 i 8763). S se gseasc toate perechile de numere consecutive prietene din irul dati frecvenele cifrelor n scrierea numerelor date.

2. Se d un ir de numere naturale x1, x2, ..., xn. S se gseasc toate subirurile de elementeconsecutive de lungime maxima formate din numere prime i toate numerele prime distinctentlnite.

3. Se d o matrice ptrat A de ordinul n i numrul natural m>0. Se cere s se tipreasc matriceleA, A2, ..., Am i suma lor.

4. Se d polinomul P cu coeficieni ntregi, fie prin monoamele sale, fie prin grad i coeficieni. Sse scrie un algoritm care determin rdcinile raionale ale polinomului P.

5. Se dau numerele naturale n1 i n2. Determinai mulimea numerelor prime aflate ntre n1 i n2 imulimea perechilor de gemeni (numerele prime p i q se numesc gemeni dac q-p=2).

6. Fiind date mai multe polinoame cu coeficieni reali s se determine suma lor i polinomul degrad maxim. Un polinom se d fie prin monoamele sale, fie prin grad i coeficieni.

7. Se citesc mai multe iruri de numere naturale. Pentru fiecare ir citit, tiprii cea mai lung scar(secvena de termeni consecutivi strict cresctori) i depunei aceast scar ntr-un ir (rezultat) R.La sfrit tiprii cea mai lung scar din R. Citirea unui ir se termin la ntlnirea unui numrnegativ, iar citirea se oprete la ir de lungime 0 (deci fr nici un termen).

________________________________________________________________________________

52


53/165


8. Se dau mai multe mulimi de numere ntregi pozitive. S se determine reuniunea i interseciaacestor mulimi.

9. Se dau mai multe mulimi de numere naturale. Fie I(M) numrul mulimilor diferite de M si careconin pe M. S se determine mulimea pentru care I(M) este maxim.

10. O matrice rar A este o matrice n care majoritatea termenilor sunt nuli. O astfel de matrice sepoate reprezenta prin tripletele (linie, coloan, valoare) corespunztoare valorilor nenule alematricei; deci A[linie,coloan] = valoare. Dndu-se mai multe matrice rare determinai suma lor.

11. Se dau mai multe numere naturale prin reprezentrile lor n baza p. Gsii suma lor i maximulacestor numere (reprezentate n baza p i toate operaiile se fac n baza p).

12. Se dau mai multe matrice cu coeficieni ntregi. Se cere suma matricelor care au determinantul

nenul, matricele care au determinantul nul i matricea care are determinantul maxim.

Complexitatea algoritmilor

Etapele rezolvrii unei probleme

Este cunoscut faptul c rezolvarea unei probleme presupune n principal trei etape:

I. Analiza problemeiII. Proiectarea soluiei

III. Implementarea i testarea soluiei n practic.

n funcie de gradul de generalitate a analizei efectuate, n a doua etap se ntlnesc dousituaii: proiectarea uneisoluii particulare, valabil doar pentru acea problem, i proiectarea unei

soluii generale, valabil pentru orice instaniere a acelei probleme, soluia generalizat.n timp ce soluia particular este valabil doar pentru o instan a problemei, soluia

general este independent de parametrii problemei i ofer o metod general de rezolvare aproblemei.

Astfel, soluionarea imediat a ecuaiei x3+1=0 este particular fa de soluionarea ecuaieigeneralizate ax3+bx2+c=0.Noiunea de algoritm i cea de program

Atunci cnd metoda general de rezolvare a unei probleme este prezentat precis, pe pai ce seefectueaz ntr-o ordine bine precizat i care conduc n timp finit la soluia oricrei instanieri a

problemei, vorbim de algoritmul de rezolvare a problemei.De exemplu, algoritmul de determinare a unei soluii reale a ecuaiei polinomiale P(x) = 0,

cu o aproximare dat,prin metoda tangentei.

________________________________________________________________________________

53


54/165


Avantajul major al proiectrii unui algoritm de soluionare a problemei este dat de faptul cefortul de rezolvare poate fi transferat unei maini automate (calculator) sub forma programuluiexecutabil ce implementeaz algoritmul general de soluionare.

Implementarea algoritmului general de soluionare a problemei ntr-un program pecalculator permite o important economie prin faptul c efortul major de analiz i proiectare asoluiei a fost efectuat o singur dat iar rezolvarea problemei se reduce la efortul foarte redus deexecutare (rulare) a programului cu ajutorul calculatorului pentru fiecare instan diferit a

problemei.Modelul abstract al Mainii Turing

Primul model teoretic riguros de main automat de calcul este Modelul mainii abstracteTuring(1936). Acest model teoretic a stat la baza apariiei efective a primei maini electronice decalcul, denumit mai trziu computer (calculator) dup denumirea operatorului uman(tehnicianului) care era angajat s fac toate calculele inginereti sau contabile ale unui proiect sauale unei firme.

Teza Turing-ChurchRezult c, n ultim instan, puterea de rezolvare a unui calculator se reduce la puterea de

calcul a mainii Turing. Iar puterea de calcul a acestei maini abstracte riguroase este exprimat subforma Tezei Turing-Church: O main Turing poate face tot ceea ce poate face un computer umannzestrat cu creion, oricte foi de hrtie i reguli precise ( mecanice sau automate ) de calcul.

Exist, pe lng aceast formulare iniial a lui Turing, o serie de alte formulri echivalenteale acestei teze unanim acceptate de teoreticienii ce au pus bazele teoriei informatice i a tiineicalculatoarelor (computer science). S observm c aceast tez (propoziie acceptat frdemonstraie ca avnd valoarea logic de adevrat) stabilete o echivalen perfect ntre puterea decalcul a unui computer uman i puterea de calcul a unui computer main.

Echivalarea subneles (tacit) a noiunii teoretice vagi de algoritm cu noiunea matematicriguroas de Main Turing a nsemnat acceptarea unanim a Tezei Turing-Church de ctreiniiatorii informaticii. n consecin, studiul eficienei unui algoritm n soluionarea unei problemerevine n studiul eficienei n funcionare a mainii Turing i implicit a eficienei n funcionare a

programului ce implementeaz acel algoritm de rezolvare.Aceasta este consecina faptului c, n accepiunea original, algoritmul de soluionare a unei

probleme este destinat unui computer uman, dar puterea de calcul a acestuia este aceeai cu putereade calcul a unei maini Turing = computer main care este pus n micare printr-un programexecutabil.

Analiza, Proiectarea i Implementarea algoritmilor i Complexitatea algoritmilor

Relund ideea iniial, n rezolvarea automat a unei probleme (adic rezolvarea cu ajutorulcalculatorului a oricrei instane diferite problemei) se trece prin cele trei etape:Analiza teoretic a

problemei, Proiectarea algoritmului de soluionare iImplementarea algoritmului ntr-un programexecutabil pe calculator.

n timp ce n prima etap analiza problemei - rezultatul cheie, pe care se concentreazpreponderent efortul de analiz, este demonstrarea corectitudinii soluiei, n a doua etap proiectarea algoritmului de soluionare - cuvntul cheie este eficiena de rezolvare. Studiul cu unpronunat caracter teoretic coninut n aceast a doua etap i propune s prevad eficiena nfuncionare (necesarul de timp i spaiu calculator) a programului executabil ce va implementaalgoritmul, eventual prin compararea teoretic a algoritmilor de soluionare diferii.

________________________________________________________________________________

54


55/165


De exemplu, n cazul problemei sortrii unui ir de n chei prin comparaii se poate estimateoretic comparativ c algoritmul de sortare QuickSort este printre cele mai eficiente soluii.

Disciplina informaticii care se ocup cu studiul teoretic al eficienei algoritmilor este numit

Complexitatea algoritmilor.

Operaia de baz, cheia studiului complexitii

La baza studierii complexitii unui algoritm st detectarea n descrierea algoritmului aoperaiei sau a operaiilor de baz, acea operaie (acele operaii) aflat (aflate) n cel mai interiorcorp de ciclu repetitiv i a crei (a cror) contorizare permite estimarea n avans, nainte de lansarean execuie, a timpului de execuie a programului executabil corespunztor.

n majoritatea cazurilor exist o legtur foarte strns ntre operaia de baz (cea mairepetat operaie) i operaia care este dedus n etapa de analiz a problemei ca fiind operaiainevitabil pentru rezolvarea problemei.

De exemplu, n cazul problemei sortrii unui ir de n chei prin comparaii este limpede coperaia de comparare a mrimii cheilor este operaia inevitabil i de asemenea ea va fi ioperaia de baz a crei contorizare va permite estimarea, nainte de execuie, a duratei defuncionare a programului ce implementeaz algoritmul de sortare respectiv.

Clase de algoritmin aceast situaie, toi algoritmii diferii care soluioneaz aceeai problem i care se

bazeaz pe aceeai operaie de baz (inevitabil) formeaz clasa algoritmilor de soluionare aproblemei. De obicei numele clasei va fi dat chiar de numele acelei operaii de baz ce esteconinut de fiecare algoritm al clasei n mod inevitabil.

De exemplu, n cazul problemei sortrii unui ir de n cheiprin comparaii, algoritmii diferiice soluioneaz problema sunt grupai n clasa algoritmilor de sortare prin comparaii, spredeosebire de clasa algoritmilor de sortare prin distribuire ce soluioneaz aceeai problem

bazndu-se ns pe alt operaie de baz: distribuirea cheilor de sortat.Operaia de baz a algoritmilor dintr-o clas de algoritmi poate fi comparat cu o vergea

vertical pe care sunt nirai toi algoritmii clasei. Ea este cea care permite studiul comparativ aeficienei algoritmilor din acea clas (ea fiind o veritabil coloan vertebral a clasei respective).Eficiena algoritmilor

Compararea eficienei a doi algoritmi diferii ce soluioneaz aceeai problem se face prindeterminarea teoretic a numrului de repetiii a operaiei de baz n fiecare algoritm i

compararea celor dou valori. n final rezultatul comparrii va permite estimarea comparativ aduratei de funcionare a programelor i alegerea celui mai bun.Compararea eficienei a doi algoritmi, din punct de vedere practic, se face prin compararea

timpilor medii de execuie a celor dou programe ce i implementeaz. Aceast metod pragmaticare dezavantajul c necesit rularea programelor care, n anumite situaii, poate dura un timpsurprinztor de mare.

Funciile de complexitateNumrul de repetiii al operaiei de baz se exprim matematic printr-o funcie de

complexitate individual asociat algoritmului, funcie ce depinde n mod inevitabil de dimensiunea(mrimea) vectorului datelor de intrare.

________________________________________________________________________________

55


56/165


De exemplu, n cazul algoritmului de determinare a maximului dintr-un ir de n elementeprin comparaii, este evident c numrul de comparaii efectuat de orice algoritm de maxim va fi ofuncie de n. Iat descrierea n Pseudocod a algoritmului:

Citeten, a1, a2,, an; Dup cum se observ vectorul de intrare (irul a) are dimensiunea n.Max := a1;Pentru i := 2 pn la n execut Este evident c operaia de baz comparaia


57/165


Fie f : N N o funcie care indic relaia dintre numrul de valori (date de intrare)prelucrate de un algoritm, i numrul de operaii elementare efectuate de acesta pentru obinerearezultatelor. Funcia f poate avea o expresie analitic destul de complicat, de aceea considerm

nc o funcie g :NN cu o expresie analitic simplificat.Definiia 1.2. Funcia f are ordinul de mrime cel mult g(n), notaie: f O(g(n)), dac i numaidac exist valori c> 0 i n0N astfel nct pentru orice n> n0 s avem f(n) c g(n).

O(g) = { h : N N | c> 0, n0N a. . n> n0, h(n) c g(n) }.(1.1)

Definiia 1.3. Funcia f are ordinul de mrime cel puin g(n), notaie: f(g(n)), dac i numaidac exist valori c> 0 i n0N astfel nct pentru orice n> n0 s avem f(n) c g(n).

(g) = { h : N N | c> 0, n0N a. . n> n0, h(n) c g(n) }.(1.2)

Definiia 1.4. Funcia f are ordinul de mrime g(n), notaie: f(g(n)), dac i numai dac existvalori c1, c2> 0 i n0N astfel nct pentru orice n> n0 s avem c1 g(n) f(n) c2 g(n).

(g) = { h : N N | c1, c2> 0, n0N a. . n> n0, c1 g(n) h(n) c2 g(n) }. (1.3)Prezentm dou rezultate remarcabile care vor fi folosite foarte frecvent pe parcursul lucrrii

Knuth [1976]:(1) Se d un ir de n valori dintr-un domeniu pe care este definit o relaie de ordine total.

Cel mai eficient algoritm de ordonare a irului dat, care se bazeaz pe comparaii, are complexitatede ordin (n log n).

(2) Se d un ir de n valori ordonate. Cutarea unei valori (localizarea poziiei acesteia sauobinerea unui rspuns negativ) n irul dat necesit un timp de ordin O(log n).

O categorie special de probleme, numite NP-complete, se caracterizeaz prin urmtoarele:

nu se cunosc algoritmi eficieni (de complexitate polinomial), se cunosc n schimbalgoritmi de complexitate exponenial pentru rezolvarea acestora;

problem NP-complet este polinomial transformabil ntr-o alt problem tot NP-complet: dac se rezolv o problem A, soluia unei alte probleme B se poate obine

printr-o transformare n timp polinomial din soluia problemei A.

Cea mai general problem NP-complet este problema satisfiabilitii: fiind dat o expresielogic n forma normal conjunctiv cu n variabile, s se determine dac pot fi atribuite valori

logice variabilelor astfel nct expresia s fie adevrat Cook [1970].

Complexitatea medie. Considerm un algoritm care proceseaz n valori date la intrare.Pentru o anumit configuraie a valorilor, probabilitatea configuraiei fiind pi, sunt necesare fi(n)

operaii. Complexitatea medie a algoritmului este o sum ponderat: ( )i

ii nfp .

Exemplul 1.1. Algoritmul Quick-sort necesit un timp de ordin O(n log n) n majoritatea cazurilorpentru a ordona un ir de n valori. Exist ns cteva configuraii (foarte puine) care au nevoie deun timp de ordin O(n2) pentru a fi procesate. Complexitatea medie a acestui algoritm este de ordinO(n log n) Knuth [1976]:

______________________________

Date post:	14-Apr-2018
Category:	Documents
Upload:	anna-lupu
View:	346 times
Download:	6 times

Carte Algoritmi Partea1!20!12 04

Documents