Download - 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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
2/165
Structuri de date i algoritmi_______________________________________________________________________________
-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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
3/165
Structuri de date i algoritmi_______________________________________________________________________________
-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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
4/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
5/165
Structuri de date i algoritmi_______________________________________________________________________________
-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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
6/165
Structuri de date i algoritmi_______________________________________________________________________________
-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/27/2019 Carte Algoritmi Partea1!20!12 04
7/165
Structuri de date i algoritmi_______________________________________________________________________________
RadixSort-descrierea generala metodei-probleme rezolvate
-probleme propuse-simulare-test de verificare
TEHNICI DE PROGRAMAREBacktrackingGreedyProgramarea dinamicaBranch&BoundTest de verificare
Exemple
Introducere
________________________________________________________________________________
7
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
8/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
10/165
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
12/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
14/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
15/165
Structuri de date i algoritmi_______________________________________________________________________________
{ 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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
16/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
17/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
18/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
19/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
20/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
21/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
22/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
23/165
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
24/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
25/165
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
26/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
27/165
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
28/165
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
29/165
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
30/165
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
31/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
32/165
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
33/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
34/165
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
36/165
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
37/165
Structuri de date i algoritmi_______________________________________________________________________________
{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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
38/165
Structuri de date i algoritmi_______________________________________________________________________________
{ 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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
40/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
42/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
43/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
44/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
45/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
46/165
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
47/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
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)
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
49/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
51/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
52/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
53/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
54/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
55/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
56/165
Structuri de date i algoritmi_______________________________________________________________________________
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
-
7/27/2019 Carte Algoritmi Partea1!20!12 04
57/165
Structuri de date i algoritmi_______________________________________________________________________________
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]:
______________________________