cap 3 a si construirea algoritmilor

8/3/2019 Cap 3 a Si Construirea Algoritmilor

1/78

Reprezentareai construirea algoritmilor 3-1

Capitolul 3. Reprezentareai construireaalgoritmilor

3.1. Generalit i

3.1.1. AlgoritmiDup cum setie activitatea noastr zilnic poate fi algoritmizat n anumitesituaii. Algoritmizm de obicei o activitate n urmtoarele cazuri: volumul de calcul necesar este mare activitatea se repet foarte frecvent rezultatele sunt necesare n foarte scurt timpConstruirea de algoritmii utilizarea calculatoarelor pentru rezolvareaacestora, n alte situaii dect cele amintite, nu este justificat.n continuarea prezentrii, accentul este pus nu pe anumii algoritmi pentrurezolvarea diferitelor probleme, ci pe modulcum se reprezint i cum seconstrue te un algoritm pentru rezolvarea unor probleme reale i dificile .De asemenea, ne intereseaz dac exist algoritmi pentru rezolvarea uneiprobleme, iar dac da, care este cel mai bun algoritm, cu complexitate redus n timp sau cu spaiul de memorie redus.Ce este de fapt un algoritm? Un algoritm reprezint descrierea exact a unei activit i i planificarea namnunt, pe pai, a realizrii ei.

Prin algoritm se nelege deci un sistem de reguli care, aplicat la o anumit clas de probleme de acelasi tip, conduce de la o informaie iniial lasoluia final, cu ajutorul unor operaii succesiv ordonatei unicdeterminate.O informaie iniial pentru care un algoritm este definit se va numiinforma ie admisibil, iar totalitatea informaiilor de acest gen constituedomeniul algoritmului, D. De exemplu, pentru algoritmul lui Eucliddomeniul este dat de multimea ZxZ a perechilor de numere intregi, iarpentru regula lui Cramer este dat de mulimea matricelor sistemelornedegenerate de n ecuaii cu n necunoscute.


2/78

3-2 Reprezentareai construirea algoritmilor

Dac o informaie initial aparine domeniului D, atunci regulilealgoritmului f, dup un anumit numr de pai, determin ntotdeaunainformaia final corespunzatoare. Ca urmare, un algoritm f poate fi definitca o funcie f:DF, unde prin F s-a notat mulimea informaiilor finale.Sistemul de reguli ce constitue algoritmul f arat efectiv cum poate fi

calculataceast funcie.Caracteristicile algoritmilorUn algoritm trebuie s se caracterizeze prin urmtoarele :- generalitate- algoritmul este conceput astfel nct s se rezolve toate

problemele din clasa respectiv. De exemplu, nu se concepe unalgoritm pentru nmulirea matricelor A2,3 i B3,5 ci pentru nmulireaoricror doumatrice Am,n i Bn,k;

- finititudine- numrul de transformri intermediare aplicate informaieiadmisibile (iniiale) pentru a obine informaia final (soluia) este finit.Ca exemplu, s consiredrm algoritmul lui Euclid. Dac se consider dou numere intregi ai b i se noteaz r0=a, r1=b, iar qk este ctul,operaia de mpr ire cu rest pentru determinarea celui mai mare divizorcomun al celor dou numere a si b, se aplic pn cnd identitateark=qk*rk+1+rk+2, k=0,1,2,...conduce la rk+2=0;

- unicitatea- toate transformrile intermediare f cute asupra informaieiini iale sunt unic determinate de regulile algoritmului, acesta trebuinds precizezeordinea strict a transformrilor. De asemenea, regulileprecizeaz n ce caz se obine informaia final, dup care activitateaalgoritmului se ntrerupe.

- automatism-odat construit, algoritmul se aplic n mod automat f r a mai fi necesardemonstrarea corectitudinii sale.

SubalgoritmiOrice algoritm de rezolvare a unei probleme sau aplicaii poate fidescompus ntr-o combinaie de algoritmi cu structura mai simpl numiisubalgoritmi. Compunerea sau combinarea acestora se poate face n dou feluri :- compunerea prin suprapunere a algoritmilor f 1 si f 2 este algoritmul

f=f 1(f 2) in care f 2 face parte din etapa de calcul a algoritmului f 1.- compunerea prin sucesiunea algoritmilor f 1 si f 2 este algoritmul

f=f 1*f 2 n care informaia final a lui f 1 face parte din domeniulalgoritmului f 2.


3/78


Algoritmul compus f este numit algoritm principal in raport cu f 1 si f 2 carese vor numisubalgoritmisauproceduri.Evident c pot exista situaii n care f este rezultatul unei compuneri prinsuprapunerei succesiune sau o secvende suprapuneri / succesiuni.

3.1.2. Clase de algoritmi

Din punct de vedere al structuriii al formei de prezentare algoritmii pot ficlasificai, n: liniari, cu ramificaii i ciclici. Algoritmii cu ramificaiepresupun o anumit testare a ndeplinirii unor condiii n urma crora trebuiesse ia o anumitdecizie (da saunu, adevrat saufals).n cadrul unui algoritm ciclic (iterativ) se alege o aproximaie iniial asoluiei care este mbunt it prin iterare, astfel nctirul de soluii obinutes convearg ctre soluia problemei considerate.

Din punct de vedere al cantit ii de informaie prelucrat i al volumuluioperaiilor de calcul algoritmii pot fi mpr i i n dou categorii:

- algoritmi numerici- algoritmi de prelucrare

n ultima perioad, progresele din domeniul tehnologiei informaiei impunluarea n considerare, a unor tipuri specifice de algoritmi necesari pentruprelucri de imaginii prelucrarea sunetelor.

Algoritmi numericiAlgoritmii numerici reprezint o categorie importantde algoritmi pe care oregsim n rezolvarea problemelor tehnice,tiin ifice, de optimizare etc. cuvolum de date redusi cu volum mare de calcul. Din punct de vedere alrealizriii programrii lor, aceti algoritmi prezintunele caracteristici care i difereniaz fa de o alt categorie deosebit de important ce apare nrezolvarea problemelor economice: algoritmii de prelucrare. n general,algoritmii numerici au urmtoarele caracteristici mai importante:

- preponderena datelor numerice fade cele nenumerice;- structurarea datelor n masive: vectori, tablouri, matrici etc;- utilizarea cu preponderena memoriei interne;- preponderena operaiilor de calcul;- iterativitatea procesului de calcul;


4/78


- realizarea programelor n limbaje orientate spre procedur:FORTRAN, PL/1, PASCAL , C, C++, DELPHI etc.

O categorie aparte de algoritmi numerici este constituit de algoritmiirecursivi. Recursivitatea algoritmilor poate fi definitastfel:

Fie urmtoarea secven: u1,u2,u3,...un de numere reale / complexe sau, maiscurt ,{un}, n1. Dac pentru () kN n calculul tuturor numerelor {un},n 1 se folosete relaia:

un+k=a1un+k-1+a2un+k-2+...+akun, (1)atunci irul este numit secven recursiv de ordin k iar relaia estenumit rela ie recursiv de ordin k. O secven recursiv estecaracterizat prin fiecare dintre termenii si, prin valoarea de nceput (start)i prin relaia recursivcare folosete la determinarea unui termen oarecare.Pentru progresia geometric cu u1=a, u2=a*q, ... un=a*qn-1, relaia recursiv este un+1=q*un care esterela ie recursiv de ordinul nti.irul de numere 1,1,2,3,5,8,13,21,... reprezint valorile funciei Fibonaccif : NN, definitastfel:

+==

=restin1),-f(n2)-f(n

1nsau0ndaca,1f(n) (2)

Relaia un+2=un+1+un cu u1=1, u2=1 este rela ia recursiv de ordinul doi pentru obinereairului Fibonacci.

Definiiile recursive se pot clasifica dup modul n care descriu procesulcalcului valorilor funciilor pe care le definesc. Cea mai simpla form esterecursivitatea liniar definitprin:

=endif

f(x))(f(h(x)),elseg(x)thenc(x)if

f(x) (3)

Un exemplu ilustrativ de recursie liniar l constitue funcia factorialf : N => N,


5/78


>==1ndaca1)f(n*n

0ndaca1f(x) (4)

Al doilea tip l constituierecursiile n cascad care sunt de forma:

=endif

f(i(x)))(f(h(x)),elseg(x)thenc(x)if

f(x) (5)

Ca exemplu al acestui tip de recursie este funcia Fibonacci din (2).

Al treilea tip de recursii este cel mpachetat,de forma

=endif

)...)...).f(...)...(f(...f(..elseg(x)thenc(x)if

f(x) : (6)

Funcia Manna-Pnueli definitprin:

+>

=endif

2))f(f(xelse1xthen10xif

f(x) (7)

constituie un exemplu de recursie neliniarde tip mpachetat.Toate formulele recursive menionate definesc o singur funcie. Exist ns definii pentru sisteme de funcii recursive.Un exemplu concret de recursivitate liniar de ordinul I este problemacalculului dobnzii compuse. Se consider un salariu net de 5.500.000 leicare este depus lunar n contul unei persoane ntr-o perioad de n luni.Presupunem c dobnda pe an este de 18% cu capitalizare lunar de 1,5%ic asupra contului nu se efectueaz nici o alt operaie. n acest caz funciarecursivpentru calculul dobnzii compusei al soldului contului este:


6/78


S0=5.500.000Sk=S0+(1+1.5)*Sk-1 , pentru k=1,nDk= Sk- S0 , pentru k=1,nunde S0 - suma depus lunar

Sk soldul contului n luna kDk dobnda n luna k

Algoritmii de prelucrare

Algoritmii de prelucrare reprezint o clas important de algoritmi legai deoperaiile executate asupra structurilor de date. Sunt caracterizai deprelucrarea unui volum mare de date asupra crora se efectuaz un volumrelativ redus de calcule. Aceti algoritmi se refer att la proiectareaprogramelor, cti la realizarea schemelor logice corespunztoarei prezint o serie de particularit i: n algoritmii de prelucrare intervin, de obicei, mai multe fiiere care

servesc pentru intrare, ieire sau intrare/ieire n programul respectiv. Specificul prelucrrii datelor implic specializarea programelor, decii

a algoritmilor. Distingem deci programe de creare fiiere, de actuali-zare, de validare, de sortare etc. Rezolvarea problemelor de prelucrare adatelor solicit, n general, un sistem de programei deci, rezult necesitatea proiectrii acestuia pentru a pune n evidenstructurarea peprograme, necesarul de date, informaiile de ieire, etc.

Datorit posibili ilor de structurare a datelor care implic o structurareadecvata operaiilor, algoritmii de prelucrare au ostructur modular (procedural) compus dintr-o procedur general numit monitor i celpu in una din procedurile: de nceput algoritm; de sfr

it algoritm; de

nceput fiier; de cheie eronat; de acces la fiier; de prelucrare etc. Ca opera ii de prelucrare fiiere se disting: crearea, exploatarea,

actualizarea, sortarea, fuzionarea, ventilarea, interclasarea,reorganizarea, inventarierea,tergere etc., pentru fiecare dintre acesteaexistnd programe de firm sau utilizatorul i poate concepe propriileprograme (decii algoritmi) de prelucrare.

Prelucrarea fiierelor se realizeaz la nivel de nregistrare ceea ceconduce la construirea dealgoritmi cu structuri repetitive pentrutratarea ntregului fiier sau a unor mulimi de nregistrri ale acestuia. ngeneral, n astfel de probleme intervine unfiier conducator (coordonator).


7/78


Datorit faptului c astfel de probleme implic un volum mare de date,se creaz module (programe) specializate nvalidarea datelor i/saucutarea datelor.

Realizarea structurat a algoritmilor cu fiier conductor pune n eviden existena a trei grupe de operaii: iniale, de prelucrarei finale. Operaiilein iale se refer la: deschiderea fiierelor, iniializarea unei variabileasociate sfritului de fiier conducator (SF), citirea primei nregistrri dinacest fiier, afiarea capului de tabel, iniializarea unor date de lucru etc.Operaiile de prelucrare asupra fiierului conductor se refer la prelucrarea nregistrrii anterior cititei citirea unei noi nregistrri.Operaiile finale corespund ncheierii unor tabele, afirii unor statistici, nchiderea fiierelor etc. Dezvoltare progresiv a modulelor referite demodulul monitor urmeaz ordinea propus mai nainte. Specificul diferitelortipuri de probleme se va manifesta prin dezvoltarea diferit a procedurii deprelucrare a nregistrrii anterior citite din fiierul conductor.

3.1.3. Analiza algoritmilor

Construirea algoritmilor nu se ncheie odat cu elaborarea i cudemonstrarea corectitudinii acestora, ci se continu cu analiza lor. Analizaunui algoritm presupune studiul eficienei sale, cel puin din punct devedere al timpului cerut pentru execuia sai al necesarului de memorie.Necesitatea analizei algoritmilor deriv din urmtoarele dou aspecte:

Necesitatea de a elabora algoritmi ct mai performani n condiiileabordrii cu ajutorul calculatorului a unor probleme din ce n ce

mai complexe; Necesitatea de a ne asigura c algoritmii construii nu vor fieliminai de practic datorit timpului marei/sau spaiului dememorie mare necesare execuiei.

Analiza algoritmilor const deci din: determinarea memoriei suplimentare necesare; determinarea timpului necesar execuiei algoritmilor; determinarea optimalit ii algoritmului.

n ceea ce privete memoria suplimentar necesar execuiei algoritmului,datorit progreselor din ultimul timp din domeniul IT, importana acesteia


8/78


9/78


Timpul de execuie este influenat de numrul de operaii aritmeticei detransfer condiionat, numr ce depinde de calitatean a datelor de intrare,sau altfel spus, de lungimea intrrii n algoritm.Fie T(n)-timpul cerut de un algoritm oarecarei fie f(n)-termenul dominant n expresia lui T(n), adic termenul care tinde cel mai rapid spre +.Atunci vom nota T(n)=O(f(n))i-l vom numi ordin de mrime alcomplexit ii care exprim faptul c

n general este greu, dac nu chiar imposibil, de determinat o expresiepentru T(n), deci este greu de determinat f(n). Pentru anumii algoritmiputem fi n una din urmtoarele dou situaii i deci vom defini ordinul decomplexitate n unul din urmtoarele moduri: Se pot determina o valoare minim i o valoare maxim pentru T(n),

valori n care termenul dominant f(n) difer doar printr-o constant multiplicativ.

Definiia 1: Spunem c T(n)=O(f(n)) este ordinul de complexitate al unuialgoritm dac exist dou numere c1i c2 precumi n0 astfel nct

c1f(n)T(n)c2f(n), ()n n0.

n situaii mai complexe, pentru unii algoritmi se poate determina doaro limit superioar a expresiei timpului necesar.

Definiia 2: Spunem c T(n)=O(f(n)) este ordinul de complexitate al unuialgoritm dac exist dou constante pozitive c,n0, astfel nct

T(n)cf(n), ()n n0.n mod evident, se caut cea mai mic funcie f i cea mai micvaloare c.Pentru a ilustra modul de determinare a ordinului de complexitate vomanaliza algoritmul de sortare a unui vector folosind arbori binari (metod prezentat n capitolul 2, paragraful 2.2.2). Considernd un vector A(a1, a2, ,an) cu n componente, sortarea prin comparare presupune la primatrecere (n-1) comparri, la a doua trecere (n-2) comparri, .a.m.d.Numrul total de operaii de comparare care va permite ordonareacresctoare /descresctoare a componentelor vectorului va fi deci de:

1)()(lim =

n f nT

n

22)1(

123.....)2()1(

2 nnnnnn

=

=+++++


10/78


Factorul dominant n acest caz este n2 /2 i deci ordinul de complexitate alalgoritmului este O(f(n))=O(n2 /2).Cunoscnd timpul necesar realizrii unei operaii de comparare, timpultotal de execuie va fi: T(n)=( n2-n)/2i, dup cum se observ, dac f(n)=n2 /2, atunci:

Algoritmul considerat se spune c are ordin de complexitate polinomial sau, mai scurt, algoritmul este polinomial, deoarece f(n) este o funciepolinomial n n-lungimea intrrii n algoritm.Posibilii termeni dominani i importana lor n calculul ordinului decomplexitate rezult i din Fig. 3.1.:

f(n) n log2n n log2n n2 n3 2n 1 0 0 1 1 22 1 2 4 8 44 2 8 16 64 168 3 24 64 512 25616 4 64 256 4096 6553632 5 160 1024 32768 4294967296

Figura 3.1. Valori ale unor funcii uzuale de evaluare a complexit iiVom putea da, ca urmare, urmtoarele dou definiii:Definiia 3: Un algoritm se numete polinomialdac are o complexitatetemporal O(f(n)), unde f(n) este o funcie polinomial n n, lungimeaintrrilor.Definiia 4: Dac un algoritm nu este de complexitate polinomial, atunciel se numete exponenial; tot exponeniali sunt considerai algoritmii decomplexitate nlog n, cu toate c ei nu sunt polinomiali, dar nici exponeniali n sens strict matematic.Menionm c: practica a impus ca acceptabili numai algoritmii cu comportare n

timp polinomial deoarece, chiar pentru valori nu prea mari ale lui n,algoritmii exponeniali devin inutilizabili;

1

2

2lim)()(lim 2

2

=

= n

nn

n f nT

nn


11/78


n acelai timp, pentru valori mici ale lui n, un algoritm exponenialpoate fi mai bun dect unul polinomial;

n calculul timpului de execuie necesar algoritmului, putem considerac toate operaiile elementare ce intervin n algoritm necesit acelaitimp.

Pentru a justifica aceste afirmaii vom considera c o operaie necesit 10-6 secunde pentru a se executa. n acest caz Figura 3.2. furnizeaz timpul de calcul pentru algoritmii polinomiali cu f(n) egal cu n, n2, n3, n5i exponeniali cu f(n) egal cu 2n,3n, pentru diferite valori ale lungimii n aintrrilor.

N 10 20 30 40 50N 0,0001" 0.0002" 0.0003" 0.0004" 0.0005"N2 0.0001" 0.0004" 0.0009" 0.0016" 0.0025"N3 0.001" 0.008" 0.027" 0.064" 0.125"N5 0.1" 3.2" 24.3" 1.7' 5.2'2n 0.001" 1" 17.9" 12.7 zile 38.7 ani3n 0.059" 38' 6.5ani 38.5 secol 2*108 secol

Figura 3.2 Timpi de calcul pentru algoritmi polinomialiDin tabel se observ c:- comparnd viteza de cretere n funcie de n a timpului de execuie

pentru funciile f(n) considerate, constatm c pentru valori ale lui n nuprea mari, timpul de execuie este inacceptabil n cazul algoritmilorexponeniali care devin astfel inutilizabili;

- pentru valori mici ale lui n, un algoritm exponenial poate fi mai bundect unul polinomial; astfel, funcia f(n)=2n ne conduce la o valoare atimpului de execuie mai mic dect n cazul f(n)=n5 pentru n20.

- exist algorimi exponeniali care se comport acceptabil pentrurezolvarea majorit ii problemelor particulare, cum este metodasimplex pentru rezolvarea problemelor de programare liniar (metodaeste de complexitate exponenial, dar este eficient n rezolvareaproblemelor concrete). Astfel de exemple sunt rarei nu exist ometod care s prevad c un algoritm de complexitate exponenial este practic acceptabil.

Observa ia 1: pentru a justifica faptul c am considerat toate operaiilecare intervin ntr-un algoritm cu acelai timp de execuie, vom luaurmtorul exemplu:


12/78


Presupunem c un algoritm prelucreaz un vector A=(a1, a2, ,an) i c nalgoritm intervin dou tipuri de operaii notate prin (*)i (+). Considerm,de asemenea, c timpul de execuie al operaiei (*) este de 10.000 mai mareca al operaiei (+),i c n timp de operaia (*) se execut de n ori, operaia(+) se executde n3 ori.

N (+) (*)Nr operaii n*10000 N3 N=1 10.000 1N=10 10.000 1.000N=100 1.000.000 1.000.000N=200 2.000.000 8.000.000N=500 5.000.000 125.000.000

Figura 3.3 Timpi de prelucrare pentru operaiiDin tabelul 3.3. se observ c pentru n100 avem n*10.000n3, dar pentrun>100 obinem n*10.000


13/78


continuare n acest capitol - conduce la algoritmi exponeniali n cazul ncare sunt enumerate toate cile de identificare a soluiei unei probleme).Din acest motiv se spune c o problem este uor rezolvabil sau uoar numai dac s-a elaborat un algoritm polinomial pentru rezolvarea ei. Oproblempentru care nu existun algoritm polinomial se numetedificil.Calitatea algoritmului depinde de polinomialitatea sai de gradul ct maimic al polinomului.n ceea ce privete problemele dificile, dificultatea poate avea dousemnificaii:- Timpul necesar pentru gsirea unei soluii este exponenial- Spaiul necesar obinerii soluiei este att de mare nct nu poate fi

exprimat printr-o expresie, mrginit de valoarea unui polinom nlungimea intrrii.

Problemele pentru care s-a demonstrat c nu exist algoritmi pentrurezolvarea lor se numescprobleme dificile n sens tare.Problemele dificile se pot mpr i n doumari categorii:- probleme dificile pentru care exist algoritmi nedeterminiti polinomiali

(clasa problemelor NP)- probleme dificile pentru care se poate demonstra c nu pot fi rezolvate

cu algoritmi nedeterminiti de complexitate polinomial i care suntincluse, mpreun cu categoria problemelor pentru care nu exist algoritmi, n clasa problemelor dificile (n sens tare).

Noiunea de algoritm nedeterminist este preluat prin analogie cu noiuneade main de calcul paralel care este capabil s efectueze un numr orictde mare de calcule independente n mod simultan.Problemele dificile pentru care exist algoritmi nedeterminiti de

complexitate polinomial sunt incluse n clasa NP a problemelor dificilenedeterminist polinomiale.

Problemei algoritmi nedeterminist polinomiali(NP)

Algoritmii utilizai n general pentru rezolvarea problemelor suntdeterminiti, n sensul c structura lor nu prevede posibilitatea alegerii ntremai multe ci posibile pentru a ajunge la rezultat. De exemplu, un algoritmbacktracking efectueaz calcule pn n momentul cnd se ajunge nsituaia de a alege ntre mai multe alternative.


14/78


Un algoritm nedeterminist este acela n care e permis trecereanecondiionat dintr-o stare n mai multe stri urmtoare i care poateefectua simultan mai multe calcule independente. Mai exact, un algoritmnedeterminist realizeaz, ori de cte ori ajunge n situaia de a alege ntremai multe alternative, orict de multe copii ale sale astfel nct s fie

posibil parcurgerea independent a tuturor alternativelor. Dac o copiecorespunde unei alegeri ce nu furnizeaz un rezultat, atunci execuia ei se ntrerupe, dac o copie depisteaz o soluie a problemei, rezultatele suntmemoratei se ntrerupe parcurgerea tuturor copiilor. Dac s-a ajuns lasituaia n care nici o copie generatanterior nu furnizeazun rezultati nicinu mai pot fi generate alte copii, atunci algoritmul semnalizeaz c problema studiatnu are soluie.Observa ia 3: Nici un sistem de calcul nu se poate comporta nedeterministun timp nelimitat, ca urmare algoritmii nedeterminiti constituie o noiuneabstract care permite s se ignore anumite detalii ale cutrii cu ntoarcere(backtracking), una din consecine fiind aceea c ei nu conin ntoarceri(reluri).Definiia 5: Un algoritm se numete nedeterminist polinomial(NP) atuncicnd complexitatea calculelor efectuate de orice copie a sa (deci pe oricedrum al arborelui ce descrie ramificrile procesului de cutare a soluiei)este polinomial. n mod analog se definete algoritmuldeterministpolinomial(P) .Definiia 6: O problem esteNP-dificil dac orice problem din clasa NPse reduce la ea.; o problem esteNP-complet dac ea este NP-dificil i nacelai timp aparine clasei NP.O tratare amnunit a acestor tipuri de problemei algoritmi este realizat n [GAJ79].

3.2. Reprezentarea algoritmilor

Dup ce un algoritm este elaborat principial el trebuie prezentat ntr-oform accesibil i n mod detaliat. Aceast operaie este numit reprezentarea algoritmului. Descrierea se poate face n mai multe modurii anume prin:- limbaj logico-matematic,- limbaje de tip pseudocod,


15/78


- limbaj grafic- scheme logice verticale- scheme logice orizontale (Chapin),- diagrame arborescente (Tabourier sau Mills),- tabele de decizie

Aceste modalitai de reprezentare a algoritmilor pot fi utilizate n oricecombinaie, fiecare form avnd avantajelei dezavantajele sale.n continuare vor fi descrise cteva din modalit ile de reprezentare aalgoritmilor atat grafice cati textuale.

3.2.1. Limbajul pseudocod

Limbajul pseudocod este folosit n faza de proiectare a programelor pentrudescrierea algoritmilor; el este o alternativ la schemele logice. Limbajulpseudocod nu este un limbaj de programare. Pseudocodul are

numeroase variante, practic ele deosebindu-se de la proiectant laproiectant. Chiar la acelai proiectant se pot ntlni variaii ale formei,existnd n anumite limite impuse de claritatea descrierii algoritmului,libertatea alegerii variantei celei mai adecvate. Toate variantele au ns ca trsturi comune utilizarea enunurilor nestandard, precumi aoperaiilor prescrise de programarea structurat.Construcia de baza a limbajului este propoziia, un algoritm fiindconstituit ca o succesiune de propoziii. Propoziiile sunt de tipul: propozitii simple, prin care se exprim operaii ce se vor codifica

apoi direct ntr-un limbaj de programare (de exemplu: deschidefisier, citeste inregistrare din fisier etc.);

propoziii complexe, prin care se exprim operaii ce urmeaza a fidetaliate ulterior. Simbolul # este utilizat pentru a marca astfel depropoziii care se vor detalia ulterior.

Fiecare propoziie ncepe cu un verb care exprima ct mai fidel operaiadescris. Astfel se definesc urmtoarele construcii de baz:citete sau citete scrie sau scrie atribuie sau


16/78


atribuie,...

sfritexecut (;)

stopunde:var este numele unei variabile,exp este o expresie algebric saulogic ce poate folosi variabile din memorie,nume-proceste numele uneiproceduri, l-exp este lista expresiilor de intrare iarl-var este listavariabilelor de ieire.Limbajul pseudocod reprezint structurile de control ale programriistructurate: secvena, selecia, iteraia. Pentru mai mult similitudine culimbajele de programare TURBO PASCAL sau DELPHI, C++, JAVA,etc. se adopt i varianta n limba englez a cuvintelor cheie ce marcheaz structurile de control.

structura secven ial, un bloc format din prelucrrile s1,s2, notat cu (s1,s2) este: nceput begin

s1 s1 s2 s2

sfrit end structura alternativ (c,s1,s2):

dac c if catunci s1 then s1 altfel s2 else s2

sfrit end structura repetitiv condi ionata anterior (c,s):

ct timp c while cexecut s do s

sfrit endwhile structura pseudoalternativ '(c,s):

dac c if catunci s then s

sfrit endif structura repetitiv condi ionat posterior (c,s):


17/78


execut s do spn cnd c until c

structura alternativ generalizat: ''(i,s1,s2,...,sn)selecteaz i dintre: case i of

1: s1 c1: s1;2: s2 c2: s2;......... ..........n: sn cn: sn;

sfrit end caseDac n procesul de definire a structurii programului se detaliaz istructura datelor atunci se pot folosi propoziii standard i pentrudescrierea acestora. De exemplu: pentru variabile simple:

var v1,v2,...,vn: {Integer/real/boolean/character[m]}unde v1,v2,...,vn sunt nume de variabile iar integer, real, boolean,

character[m] indic tipul acestora; pentru variabilele de tip tablou k-dimensional:var v: array [1..n1;1..n2;... ;1..nk] of {integer/real/boolean/character[m]}

unde v este numele tabloului iar n1, n2,...,nk numrul maxim deelemente de pe prima, a doua, ... , a k dimensiune .

pentru variabile de tip nregistrare:var v: record of

v1:t1;v2:t2;.......vn:tn

endunde v este numele nregistrrii, vi, i=1,n este numele unui cmp iarti, i=1,n este tipul acestuia (integer, real, logic,ir de caractere, list de valori).

pentru declarare fiiere:sequential

var f: direct file of v1,v2,...,vn indexed

unde f este numele fiierului, vi, i=1,n este numele nregistrrii iarsequential, direct, indexed indic modul de organizare;

pentru citire/scriere din/n fiiere:


18/78


citete (nume fiier, nume nregistrare)scrie (nume fiier, nume nregistrare).

Caracteristica principal a limbajuluii n acelai timp un mare avantajeste libertatea pe care o ofer utilizatorului n descrierea algoritmului. Lafiecare nivel de detaliere, textul are o claritate maxim datorit sintaxeifoarte simple cti a limbajului natural curent.Modul de abordare a unei probleme n pseudocod este de tip "top-down"(de sus n jos). Se pornete de la nivel de maxim generalitate (o prim versiune a programului)i urmeaz o dezvoltare arborescent pe unnumr de n nivele (versiuni), variabil n functie de complexitateaproblemei ce trebuie rezolvat. Primele (n-1) versiuni ale programuluicuprind propoziii nestandard iar versiunea final Vn este alctuit dinpropoziii standard ce vor fi codificate n limbajul de programare ales.S considerm de exemplu problema numrrii elementelor pozitive,negativei zero dintr-un vector A(I), I=1,N. O prima versiune de descriere

a programului NUMARARE este:#nceput NUMARARE#NUMARARE-elemente#Sfrit NUMARARE

Identificand operaiile elementare corespunzatoare fiecareia din cele treipropoziii complexe se obine forma finala compusa numai din propozitiisimple

program NUMARAREvar I: integervar N: integervar NP: integervar NN: integervar NZ: integervar A: array[1..N] of {integer} nceput

citete n ;execut i=1 ;execut NP=0 ;execut NN=0 ;execut NZ=0 ;ct timp iN execut

nceputcitete A(i)dac A(i) > 0

atunci


19/78


executa NP=NP+1;altfel

dacA(i)< 0atunci

execut NN=NN+1altfel

execut NZ=NZ+1sfrit

sfritsfrit

sfritexecut scrie NPexecut scrie NNexecut scrie NN

sfrit

3.2.2. Scheme logice Schema logic este o reprezentare grafic a algoritmului prin care fiecrei

etape din structura sa i se ataeaz un simbol numit bloc iar modul de nln uire a acestor blocuri este dat prin segmente orientate.Se poate arta corice schemlogicse compune din trei tipuri de blocuri (Fig.3.4.):

Bloc de tip funcional : Y=f(X)X Y

Bloc de tip predicativ (decizional) YZ = c(X)

Conectori

Figura 3.4 Elemente constitutive ale unei scheme logice

f

X C

Y

Z


20/78


Mai riguros, o schema logica este un graf orientat in care: exista o unica instructiune START si o unic instruciune STOP; orice nod este etichetat cu una din urmtoarele informaii: START

sau STOP; o citire sau o scriere; o atribuire; un predicat,etc. pentru orice nod exist cel puin un drum care ncepe cu START, se

termin cu STOPi cuprinde nodul considerat.n general, structura uni program nseamn ordinea de execuie ainstruciunilor sale, numit i structurde control a programului.n schemelestructurate se regsesc urmtoarele structuri fundamentale de control:a) structura liniar notat (s1,s2,...,sn) n care si,i=1,n sunt secvene de

instruciuni (fig.3.5).

Figura 3.5 Structura liniar Aceasta se poate scrie: (s1,s2,...sn)= ( (s1, s2,...sn-1), sn) i, nparticular (s1) = s1b)structura alternativ notat (c,s1,s2), n care c este condiia(predicatul) de testat (fig.3.6)

nu da

Figura 3.6 Structura alternativ

c) structura repetitiv condi ionat anterior notat (c,s)(fig.3.7).

da

Figura 3.7. Structura repetitiv condi ionat anterior

s1 s2 s3 s4

C s

C

s1 s2


21/78


Aceste trei structuri sau diagrame sunt numite structuri de baz.Totui, pentru a putea reprezenta uor diferite situaii s-au introdusiurmtoarele tipuri de structuri derivate:d) structura repetitiv condi ionat posterior notat '(c,s)(fig.3.8)

Figura 3.8 Structura repetitiv condi ionat posterior

e) structura pseudoalternativ notat '(c,s)(fig.3.9)

nu da

Figura 3.9 Structura pseudoalternativ

f) structura alternativ generalizat notat ' '(c,s1,s2,...sn) care realizeaz selecia parcurgerii unui arc n funcie de valorile naturale ale variabilei i(fig.3.10)

Figura 3.10 Structura alternativ generalizat

g) structura /\ (blocul vid) care este echivalent cu funcia identic, nuexecut nici o operaie.

C

s2

C

s

s1 s2 sn


22/78


Ca notaie se folosesci urmtoarele corespondene pentru a descriearborele de structur al programului.(s1,s2) = (BLOCK,s1,s2); (c,s1,s2) = (IF-THEN-ELSE, c,s1,s2);

(c,s) = (DO-WHILE,c,s)

' (c,s) = (DO-UNTIL,c,s)'(c,s) = (IF-THEN,c,s)' '(i,s1,s2,...sn) = (CASE-OF,i,s1,s2,...,sn).

Propriet ile structurilor fundamentale.1) Structuraeste n general necomutativ:

(s1,s2)=,/ (s2,s1).Daca s1 i s2 sunt independente, atunci ele pot fi programate ca dou procese concurente.

2) Structuraeste asociativ:(s1, (s2,s3)= ((s1,s2),s3).

3) Blocul vid /\ constituie elementul neutru pentru structura secvenial:(s,/\)=(/\,s).

4) Structuraeste distributiv la dreapta n raport cu structura alternativ:( (c,s1,s2),s3)= (c,(s1,s3), (s2,s3)).

5) Structuraeste distributiva la stnga in raport cu structura alternativ :(s1, (c,s2,s3))= (c,(s1,s2), (s1,s3)).

6) Structura este reductibil la structuri alternative incluse:(c,s)=(c,(s,(c,s)),/\)= (c, (s, (c,(s,(c,s) )),/\)),/\)=...

7) Structurile

',

", ' sunt reductibile la structurile

,

, :'(c,s)=(s, (c,s));,

'(c,s)= (c,s,/\); '(c,s)= (c,s, (c,s)); '(c,s1,s2,...sn)= (c1,s1, (c2,s2,...)),unde c1,c2,...cn sunt derivate din ci sunt condiiile care determin selecia alternativelor.Toate strucurile prezentate se bucur de proprietatea c au o singur intrarei o singur ieire. Aceste blocuri pot fi din nou interpretate caoperaii unice mai complexe ntr-un process de calcul secvenial.caurmare, orice program poate fi construit numai din asfel de structuri


23/78


(blocuri)i poate fi succesiv transformat ntr-un singur bloc cu o intrareio ieire. Acest proces de transformare poate fi folosit pentru a nelegeprogramuli pentru a-i dovedi corectitudinea.Dac se consider aceste transformri n sens invers, se obine o calesistematic prin care se poate deduce structura de control a programelor.Astfel, iniial programul este considerat ca un bloc complex cu o intrareio ieire. Printr-o examinare atent, acest bloc se poate descompune n treimoduri,i anume:a) ca o secven de dou sau mai multe blocuri cu o intrarei o ieireb) ca o selecie ntre dou sau mai multe alternativec) ca o repetare de mai multe ori a unei secvene de operaiiAcest proces de descompunere, repetat pentru fiecare bloc, poate ficontinuat pn cnd acestea corespund unor operaii executabile pe uncalculator real sau virtual luat ca referin.Procesul de transformare descris se numete descompunere top-downsaudescompunere n pai succesivi,i constituie principalul mijloc de definirea structurii de calcul a programelor.Definiie: Se numete program structurat orice program a cruistructur de control este realizat folosind doar blocuri cu structur secvenial, alternativ cu dou ramurii repetitiv condiionat anterior.De exemplu, schema din figura 3.11 se poate scrie:

Figura 3.11 Exemplu schem structurat

(c1,c2,c3,s1,s2,s3)= (c1, (c2, (s2,s3), (c3,s1))), adic schema admite odescompunere n termeni de, , .

S2

S3 S1

C1

C2

C3


24/78


Sunt situaii n care acest lucru nu este posibil directi, pentru a obine oschem logic echivalent, dar structurat, se pot folosi variabile booleene,variabile de stare sau duplicarea de cod. Varianta folosirii variabilelorbooleene pentru transformarea schemelor logice nestructurate n schemelogice structurate este justificat prin teorema luiBoehmi Jacopini.

Teorema de structur Boehmi JacopiniProgramarea structurat se bazeaz pe o serie de teoreme de structur idescompunere pe care le vom prezenta n continuare.Vom introduce acum trei noi blocuri functionale T,F,Ki un nou blocpredicativ W. Efectul blocurilor Ti K este s transforme un obiect x n perechea ordonat (v,x) unde v poate avea numai valorile t(adevrat)i f (fals):

T F Tx--->(t,x) ; x--->(f,x) ; x--->(t,(t,x)).

Blocul K separ dintr-o pereche ordonat cea de-a doua component a sa:K K

(v,x)--->x ; (t,(f,(t,x)))--->(f,(t,x)).Predicatul W este definit ca W[(v,x)]=t v=t adic predicatul W esteverificat sau nu, dupa cum prima component a sa este t sau f.Programarea structurat se bazeaz pe o serie de teoreme de structur idescompunere pe care le vom prezenta n continuare.Teorema de structur (Bohmi Jacopini)Dac o aplicaie x-->x' estereprezentabil printr-o schem logic ce conine aciunile s1,s2,... ipredicatele c1,c2,... ea este de asemenea reprezentabil printr-o schem

logic ce se descompune n, i i care conine aceleai blocuri cai schema iniial, plus blocuri de tip T, F, Ki W.Teorema poate fi enunat mai simplu astfel: dac o schema cuprinde omul ime S de aciunii o mulime C de predicate, pot fi adugate lui SiC noi funcii, respectiv noi predicate astfel nct organigrama s fiestructurat i s fie echivalent ca rezultat al prelucrrii cu cea iniial.Aceast teorem de existen ilustreaz faptul c orice program poate fipus sub form de structur, adic s conina numai structuri , i i/sau variante ale acestora prin utilizarea unor variabile booleene asociateunor funcii suplimentare.


25/78


Demonstraia teoremei se face prin inducie dup n- numrul blocurilor,i, n principiu,const din urmtorii pai: Se verific faptul c teorema este adevarat pentru n=1 caz n care se

ob ine structura(s), pentru n=2 se obine structura (c,s) sau(s1,s2)) iar pentru n=3 se obine structura(c,s1,s2) i variante ale

structurilor i Se demonstreaz c, presupunnd c afirmaia este adevrat pentrun=k blocuri, atunci este adevrat i pentru n=k+1 blocuri. Blocul k+1poate fi de tip funcional sau predicativ.Se deosebesc urmtoarele cazuri:- Dac blocul k+1 este de tip funcionali este n faa, ntre, sau n

urma celor k blocuri, atunci avem o nou structur de tip.- Dac blocul k+1 este de tip predicativi este n faa celor k

blocuri, atunci avem o nou structur de tip sau.- Dac blocul k+1 este de tip predicativi este n urma celor k

blocuri, atunci avem o nou structur de tip - Dac blocul k+1 este de tip predicativi n interiorul celor k blocurianterioare atunci se folosesc operatorii T, F, Ki W pentru

reprezentarea schemei logice cu k+1 blocuri n termeni de tip, , .Pentru a ilustra utilizarea variabilelor boolene n structurarea schemelorlogice se condider schema logic nestructurat din figura 3.12.

Figura 3.12(C1,C2,C3,S1,S2,S3,S4,S5)

Aceast schem se poate reprezenta n termeni de, i introducnd ovariabil boolean v ce va lua valorilet i f prin operatoriiT i F (figura3.13).

DA

DA

DA

C1

C2

C3

S2

S1

S3

S4

S5


26/78


Figura 3.13 Reprezentare alternativ

Astfel schema logic ini ial (C1,C2,C3,S1,S2,S3,S4,S5) == (v=t, (v=t,(C1, (C2, (S1,S5,v=f), S2)), (C3, (S3,S5,v=f), S4)))) unde v=ti v=f din structurile corespund blocurilor Ti F, iar v=t din structura corespunde blocului W.Corolarul "top-down" ("de sus in jos").Un program structurat este echivalent cu un program pus sub una din formele:

P =(s1,s2), P = (c,s1,s2)P = (c,s), P = '(c,s)

unde c este predicat, iar s,s1,s2 sunt proceduri structurate sau funcii aleprogramului.n fig. 3.14 este reprezentat structura unui program P care poate fi scris sub forma:

P =( (c1, (s3,s4), (c2, (c3,s1),s2)),s5).

Figura 3.14 Schema logic a programului P

t f

DA

C1

DA

C2

S2

S1 S5 v=f

DA

C3

S

S3 S5 v=f v=t v=t

STOP

S1

S2

S5

S3 S4

C1

C2

C3


27/78


BLOCK

S1 S2

IFTHENELSE

S1 S2

S1

S1

WHILEDO

IFTHEN

S1 S2 Sn S1

CASEOF DOUNTIL

c

c

c

c c

Dac programul din fig. 3.14 nu cuprindea procedura s5, se putea scrie:P = (c1, (s3,s4, , (c2, (c3,s1),s2)).

3.2.3 Diagrame arborescente

Diagramele arborescente constituie, alturi de schemele logice, una dintehnicile grafice de reprezentare cele mai rspndite. Exist mai multevariante:a) Varianta Tabourier utilizeaz reprezentrile din figura 3.14 pentru

urmatoarele structuri:- secvenial (s1,s2)=(BLOCK, s1,s2)- alternativ (c,s1,s2) (IFTHENELSE,c,s1,s2)- repetitiv condiionat anterior notat (WHILEDO,c,s)- pseudoalternativ notat (IFTHEN, c,s)- alternativ multipl notat (CASEOF, c,s1,s2,...,sn)

-

repetitiv condiionat posterior notat (DOUNTIL,s,c),reprezentrile din figura 3.15.

Figura 3.15 Diagrame arborescente-structuri fundamentaleModul de parcurgere al acestor diagrame este de sus n josi de lastnga la dreapta. n cazul unor programe mai mari este foarte uor deizolat o subarborescen, creia i corespunde un program propriui careexecut o anumit funcie.


28/78


Pentru exemplul algoritmului de numrare a elementelor pozitive,negative i zero dintr-un vector cu N elemente (paragraful 3.2.1.),diagrama arborescent este dat n figura 3.16.

Figura 3.16 Exemplu de diagram arborescent

b) Varianta Mills ('arbore program') este foarte apropiat de variantaTabourier, deosebirea constnd n faptul c numele structurilor,condiiile i secvenele de realizat nu mai sunt incluse n figurigeometrice (dreptunghi, romb). De exemplu, programul definit prin(WHILEDO, c1,(IFTHENELSE,c2,s1,(BLOCK,s2,s3))) corespundeunui arbore-program de forma dat n figura 3.17.

Figura 3.17 Exemplu de diagram arborescent, varianta Mills

Amintim c exist, ca i n cazul schemelor logice, o mare varietate deconvenii grafice de tip diagram arborescent. Astfel, o a treia variant de diagram arborescent a fost propus de R.W. Jensen sub numele dearbore logic al prelucrrii sau PLT (processing logic tree). Un PLTconstituie o metod clar de reprezentare grafic a structurii de control aprogramelor, dari un sistem de notare adecvat procesului de detaliere

I N

BLOCK

I=1 WHILE-DO

BLOCK

CITIRE A(I)

NP=NP+1

NN=0 NZ=0NP=0

IF-THEN-ELSE

A I >0 IF-THEN-ELSE

A I


29/78


n pai. Exist i o a patra varianta de diagram arborescent numit arbore programatic sau AP ("Arbore Programmatique") propus de M.T.Bertinii Y. Tallineau n cadrul unui model de programare structurat nlimbajul COBOL ca o alternativ nou la schema logica.

3.2.4. Tabele de decizieTabelele de decizie constituie o alt tehnic de reprezentare a algoritmilor.Structura unei astfel de tabele este dat n figura 3.18.a. n care primele rlinii sunt de tip condiie iar urmtoarele p linii sunt de tip aciune.

SITUATIITABEL DE DECIZIES1 S2 . . . . . Sm

C1 C2 . . . .

CONDI II

Cr

A1A2. . . .

AC IUNI

ApFigura 3.18.a. Forma general a unei tabele de decizie

Elementele primelor r linii pot fi definite astfel: de tip NU, DA (respectiv0,1) dac este vorba de condiii cu dou valori; de tip (respectiv0,1,2) dac este vorba de condiii cu trei valori; de tip 0,1,2,... daca estevorba de condiii cu mai mult de trei valori. Numrul m al situaiilor(regulilor) este funcie de numrul de condiii care exist i de ce valoriiau acestea i anume: m=n1*n2*....*nr unde ni este numrul de valori

pentru condiia ci. De exemplu, pentru dou condiii c1 cu valori n {0,1}i c2 cu valori n {0,1,2} numrul situaiilor este m=2*3=6, cu semnificaiadin figura 3.18.b:

c1

0

1

c2

0

1 2

c2

0

1 2

s1

s2

00

01 02 00

01

02

s3s4s5

s6Figura 3.18.b. Identificarea situaiilor


30/78


n zona liniilor de aciune elementele tabelei se vor defini astfel:

n funcie de valorile pe care le pot lua condiiile, tabelele de decizie suntde trei tipurii anume:a) cu intrri limitate (toate condiiile iau valori n mulimea L2={0,1});b) cu intrri extinse (adic condiiile au valori ntr-o mulime Ln, n>2);c) cu intrri mixte (unele condiii iau valori n L2 iar altele n Ln, n>2.

Rezolvare problemelor cu ajutorul tabelelor de decizie presupuneparcurgerea mai multor etape care se succed dup cum urmeaz:

stabilirea condiiilor tabelei de decizie stabilirea regulilor stabilirea aciunilor ce se pot ntreprinde elaborarea tabelei de decizie eliminarea contradiciilori redundanelor simplificarea tabelei rezultate

Exemplu: Fie P1, P2, P3, trei produse aflate ntr-o magazie n cantit ileCP1, CP2 respectiv CP3. Se presupune c se solicit unul dintre produse, ntr-o anumit cantitate notat respectiv CANT1, CANT2, CANT3 .Dac se solicit produsul P2 se procedeaz astfel:- cnd CANT2< CP2 se satisface integral cererea;- cnd CANT2 = CP2 se satisface parial cererea n cantitatea CANT2 /2;- cnd CANT2 > CP2 se refuz cererea.Pentru produsul P3 se procedeaz n mod analog, iar pentru produsul P1 seaplic acelai regim cu o singur excepie, i anume dac CANT1 = CP1 sesatisface cererea n ntregime (i nu jumtate ca pentru P2 i P3).Rezolvarea problemei propuse presupune percurgerea urmtoarelor etape: stabilirea cerinelor

c1- pune n evidentipul produsului solicitati ia valori L3 i anume:0, dac se solicit P1

c1= 1, dac se solicit P2 2, dac se solicit P3

tij= * daca n situaia Sj a condiiilor se ntreprinde aciunea Aispa iu dac nu se ntreprinde aciunea Ai n situaia Sj


31/78


c2 pune n evidenrela ia dintre stocul de produsei cantitateasolicitat, astfel:

0, cnd cererea depete stoculc2= 1, cnd cererea este egal cu stocul

2, cnd cererea este mai mic dect stocul

stabilirea regulilorTabela de decizie va fi cu intrri extinse. Cele dou condiii c1 i c2 iauvalori n L3={0,1,2}, deci numrul situaiilor va fi de nou.

0 00 S1 0 c2 1 01 S2

2 02 S30 10 S4

c1 1 c2 1 11 S52 12 S6

0 20 S72 c2 1 21 S8 2 22S9

Figura 3.19 Stabilirea regulilor tabelei de decizie stabilirea aciunilor

Vor exista trei tipuri de aciuni,i anume:A1 satisfacerea total a cereriiA2 satisfacerea parial a cereriiA3 refuzul cererii

elaborarea tabelei de decizie

S1 S2 S3 S4 S5 S6 S7 S8 S9C1 0 0 0 1 1 1 2 2 2C2 0 1 2 0 1 2 0 1 2A1 * * * *A2 * *A3 * * *

Figura 3.20 Tabela de decizie iniial eliminarea contradiciilori redundanelor simplificarea tabelei rezultateDup ntocmirea unei tabele se pune problema simplificrii ei, nsensul reducerii numrului de situaii. Acest lucru este posibil atunci


32/78


cnd, indiferent de valoarea unei condiii, pentru mai multe situaii se ntreprinde o aceeai ac iune sau aceleai ac iuni.De exemplu, tabela din figura 3.20 permite simplificarea deoarece:1. cnd cererea depete stocul (C2=0), indiferent de produs (C1=) se

refuz cererea (se realizeaz ac iunea A3).2. cnd cererea e mai mic dect stocul (C2=2), indiferent de produs(C1=) se satisface cererea (se realizeaz ac iunea A1).n aceste condiii, n loc de S1,S2,...,S9 se pot considera situaiileS'1,S'2,S'3,S'4,S'5 definite astfel: n loc de S1,S4,S7 se consider S'1 caracterizat de faptul c C2=0 i C1

este indiferent (acest lucru se marcheaz prin C1=); S'2 rezult din S3,S6,S9 caracterizat de faptul c C2=2 si C1 este

indiferenta (C1=). S'3,S'4,S'5 provin din S2,S5,S8 prin preluare;n concluzie, tabela capt forma mai simpl din figura 3.21.

S'1 S'2 S'3 S'4 S'5C1 0 1 2C2 0 2 1 1 1A1 * *A2 * *A3 *

Figura 3.21 Tabela de decizie simplificat

Aceast tabel se poate transcrie ca o secvende schemlogic (fig. 3.22).

C2=0

C2=1

C1=0

A3

A1

A1

DANU

DANU

NU DA

A2

Figura 3.22. Schema logic a tabelei simplificate


33/78


Aceeai tabel se poate descriei prin diagram arborescent (fig.3.23).

Figura 3.23. Diagrama arborescent a tabelei simplificatePn aici s-au expus tabele de decizie complete. Exist ns i tabele lacare numrul de situaii ar fi prea mare (tabele cu multe condiii). Deaceea se utilizeaz regula ELSE care const n explicitarea situaiilorcare intereseaz, iar celelalte sunt considerate n alternativa (regula) ELSE [].Reprezentarea prelucrrilor prin tabele de decizie contribuie la asigurareacorectitudinii (completitudinii)i a uurintei ntreinerii produsului-program.

3.3. Metode de construire a algoritmilor

3.3.1. Introducere

Rezolvarea problemelor reale necesit n multe situaii construirea dealgoritmi noii/sau combinarea de algoritmi cunoscui. n acelai timp, nuto i algoritmii sunt indicai pentru rezolvarea cu ajutorul calculatorului adiferitelor probleme, reale deoarece: problemele reale nu sunt numai de un anumit tip, ele sunt combinaii de

dou sau trei probleme de tipuri diferite dimensiunea problemelor reale este mare sau foarte mare problemele sunt multicriteriale n cadrul lor apar aspecte vagi de formularea restriciilor necesitun timp de calcul foarte mare

IFTHENELSEE

C2=0

C1=0

C2=1

IFTHENELSE

IFTHENELSE A1

A1A2

A3


34/78


Din aceste motive, n continuare se vor trata tehnicii metode de construire aalgoritmilor pentru problemele reale, grupate n urmtoarele categorii: metode clasice optimale metode clasice suboptimale metode de simulare local

Reducerea complexit ii problemelori algoritmilor poate fi realizatprinparalelizarea procesului de calcul, fapt ce implic i aspecte de natur tehnic la nivelul hardware-ului utilizat.

3.3.2. Metode clasice optimaleAceste categorii de metodei algoritmi sunt tratate n cadrul disciplinelor deingineria programrii i conduc la soluii optimale ale problemelor. Dinpcate ele se preteaz la rezolvarea problemelor reale numai n combinaiecu ali algoritmi. Din aceast grup de metode fac parte metodaBactracking, metoda Branch and boundi metoda programriidinamice.3.3.2.1. Metoda Backtracking (Metoda cutrii cu revenire)n multe aplicaii, gsirea soluiei este rezultatul unui proces de cutaresistematic, cu ncercri repetatei reveniri n caz de nereuit.Metoda se aplic problemelor n care soluia se poate prezenta sub formaunui vector s = (s1, s2, , sn), sD, D = D1 x D2 x . x Dn unde D1 , D2 , . , Dn sunt mulimi finite avnd | Di | = di elemente.Pentru fiecare problem concret sunt date anumite relaii ntrecomponentele s1, s2, , sn , numite condi ii interne .Mulimea finit

D = D

1x D

2x . x D

nse nume

te spa

iul solu

iilor

posibile. Soluiile posibile care satisfac condiiile interne se numesc solu ii finale (solutii rezultat) .Metoda Backtracking urmrete s evite generarea tuturor soluiilorposibile. n acest scop elementele vectorului s primesc pe rnd valori, nsensul c lui sk i se atribuie o valoare numai dac au fost atribuite dejavalori lui s1, s2,,sk-1. Mai mult, deoarece a fost stabilit o valoare pentrusk, nu se trece direct la atribuirea unei valori lui sk+1 ci se verific condiiide continuare referitoare la s1, s2,,sk . Aceste condiii stabilesc situaiile n care are sens s se treac la calculul lui sk+1, nendeplinirea lor


35/78


semnificnd faptul c oricum s-ar alege sk+1, ,sn nu se va putea ajunge lao soluie mai bun sau la soluia final.Evident c n cazul nendeplinirii condiiilor de continuare va trebui s sefac o alt alegere pentru valorile lui skDk , sau dac Dk a fost epuizat, semicoreaz k cu o unitate, ncercnd s se fac o nou alegere pentru sk-1

etc. Aceast micorare a lui k justific denumirea metodei cutare curevenire.Presupunnd stabilite condiiile de continuare, se poate scrie proceduraBacktracking, n care se va nota cu f k (s1, , sk) condiiile de continuarepentru s1, s2, , sk n continuare se prezint, n pseudocod,o procedur general pentru problemele de tip BacktrackingProcedura Backtracking(n,s)

n, max, k: integeri: boolean : reals: array [1,n]Dk : array [1,max]

Begink=1while k>0 do

i = 0while [mai exist o valoare din Dk netestat] do

sk = if f k (s1, s2, ..,sk)

i = 1;exit

endif endwhileif i = 0

then k = k 1else

if k = nthen write s1, .., sn else k = k 1

endif endif

endwhileend

Aplica ie economic Un ntreprinztor, care dispune de un capital c, pe care dorete s linvesteasc n vederea obinerii unui profit, va proceda n felul urmtor: va


36/78


alege din n oferte la care trebuie avansate fondurile f i i care aducbeneficiile bi, pe acelea pe care le poate onora cu capitalul de care dispunei care i aduc beneficiul total maxim.O soluie a problemei poate fi reprezentat printr-o selecie de oferte (s1,s2,,sn) n care si = 1 dac oferta a fost luat n considerare de investitorsau si = 0 n caz contrar.Condiia si {0,1}, cunoscut sub numele derestric ie explicit defineteun spa iu al solu iilor posibile.Condiia ca suma investit s nu depeasc capitalul c definete o func iede limit ri sau orestric ie implicit care restrnge numrul soluiilor.De exemplu se consider cazul concret n care numrul de oferte este n=3,capitalul de care dispune investitorul este c=5000$, iar sumele necesareinvestiiilori beneficiile corespunztoare sunt prezentate n figura 3.24:

Oferta 1 Oferta 2 Oferta 3

Investiia f i 2000$ 2200$ 2500$Beneficiul bi 300$ 400$ 500$

Figura 3.24 Datele problemei

Modelul folosit va fi: cs f ii

i =

*3

1cu max i

ii sb *

3

1

=

Spaiul strilor posibile ale soluiilor problemei se poate reprezenta printr-un arbore, numit arborele spa iului st rilor (ASS). Fiecare nod din arboreva defini o stare a soluiilor problemei; nodurile intermediare sunt solu ii

par iale iar nodurile frunz solu ii finale . Nodul rdcin va reprezenta solu ia ini ial .

n problema investitorului, fiecare soluie corespunde unei decizii deacceptare sau de respingere a unei oferte, iar soluia iniial este aceea ncare nu a fost luat n considerare nici o ofert.Primul nod va avea doi succesori, corespunznd acceptrii sau respingeriiprimei oferte, subarborii fiecrui nod de pe nivelul p corespunzndacceptrii sau respingerii ofertei p. nl imea arborelui spaiului striloreste deci de n+1 (n cazul concret 3+1=4).Acceptarea ofertei 1 (s1=1) este posibil deoarece investiia total ar finumai de 2000$ iar beneficiul ar fi de 300$. Dac se accept i oferta 2(s2=1), investiia devine 2000$+2200$=4200$ iar beneficiul 300$+400$ =


37/78


700$. Acceptarea ofertei 3 nu mai este posibil deoarece investiia total 4200$+2500$=6700$ este mai mare dect capitalul disponibil care este de5000$, deci oferta 3 va fi respins (s3=0). Pentru soluia (s1=1, s2=1, s3=0)investiia total este de 4200$ iar beneficiul de 700$. Aceast soluie va fideocamdat re inut ca cea mai bun soluie (*).

Dac nu se accept oferta 2 (s2=0) se poate accepta oferta 3 (s3=1)deoarece se face o investiie total de 4500$i se obine un beneficiu de800$. Soluia (s1=1, s2=0, s3=1) este mai bun ca cea mai bun soluiecurent, fiind reinut ca soluie optim (**).Soluia (s1 = 1, s2 = 0, s3 = 0) obinut prin ignorarea ofertei 3 presupuneinvestiia total de 2000$i aduce beneficiul de 300$, mai mic ca lasoluia optim aleas anterior, motiv pentru care nu este reinut.Dac se ignor oferta 1i se accept ofertele 2i 3 se obine o investiie de4700$i un beneficiu de 900$. Deci soluia (s1=0, s2=1, s3=1) este cea maibun i se reine ca soluie optim.

Figura 3.25 Arborele spaiului soluilorMetoda cutrii cu revenire const n generarea sistematic de noduri destri ale soluiei problemei, pornind de la nodul rdcin i selectnddintre acestea nodurile soluii.

i = 0profit = 0

i = 2000profit =

300

s1 = 1

i = 0profit = 0

s1 = 0

i = 4200profit =

700

s2 = 1

i = 2000profit =300

s2 = 0

i = 2200profit =

00

s2 = 1

i = 0profit = 0

s2 = 0

i = 6700profit = 1200

i = 4200profit =

700

i = 4500profit =

800

i = 2000profit =

300

i = 4700profit =

900

i = 2200profit =

00 i = 2500profit =

500

i = 0profit = 0

s3 = 1 s3 = 0 s3 = 1 s3 = 0

s3 = 1s3 = 0 s3= 1 s3 = 0

* * * * * *


38/78


n parcurgerea arborelui spaiului strilor se va lua n considerare o list de noduri active (noduri la care nu s-au generat nc to i succesorii direci).Funciile de limitare reduc numrul nodurilor active f r a le genera toiurmaii; se minimizeaz astfel procesul de cutare prin detectareai evitareacilor care nu conduc la soluii. n exemplul de mai sus, funcia de limitareincluderea ofertei p este posibil, impune satisfacerea condiiei:

investiia = cs f ii

i =

*3

1.

Pentru a minimiza procesul de cutare, se va evita generarea soluiilor cubeneficiu mic, provenite din excluderea de oferte. Pentru fiecare ofert sepoate estima un beneficiu potenial. Acesta are la nceput valoarea

beneficiu potenial = in

p p sb *

1

=i scade la excluderea fiecrei oferte p cu

valoarea beneficiului adus de oferta nlturat. Dac prin excluderea uneioferte beneficiul potenial scade sub valoarea beneficiului celei mai bunesoluii curente, atunci excluderea ofertei nu este posibil.Funcia de limitare excluderea ofertei p este posibil se exprim deciprin condiia: beneficiu potenial bp beneficiu cel mai bun curent.Aplicarea acestei funcii de limitare, n problema enunat, reduce la treinumrul soluiilor generate.n prealabil se face sortarea ofertelor n ordinea descresctoare abeneficiilor, aa cum se poate vedea n figura 3.26:

Oferta 1 Oferta 2 Oferta 3

Investiia f i 2500 2200 2000Beneficiul bi 500 400 300

Figura 3.26 Oferte sortate

n figura 3.27 se poate observa modul de obinere a soluiilor.


39/78


Figura 3.27 Soluia ob inut

Cea mai bun soluie este (s1 = 1, s2 = 1, s3 = 0) adic se accept ofertele2 i 3i se ignor oferta 1 obinndu-se beneficiul total de 900$.

i = 0profit = 0

S1 = 0

Profit potenial = 700$ = 500$+400$+300$-500$

S1 = 1Profit potenial = 1200$

i = 2500$profit = 500$

S2 = 0

Profit potenial = 800$ = 500$+400$+300$-400$

S2 = 1Profit potenial = 1200$

i = 2500$profit = 500$

S3 = 0

Profit potenial = 900$ = 500$+400$+300$-300$

S3 = 1

Profit potenial = 1200$

i = 6700$ profit = 1200$


40/78


3.3.2.2. Metoda Branch and Bound (ramific i mrginete)

Aceast metod este nrudit cu metoda Backtracking. Diferenele constau n ordinea de parcurgere a arborelui spaiului soluiilor (strilor) i nmodul n care se elimin subarborii care nu pot conduce la rezultat.Metoda folosete o list n care vor fi nscrise vrfuri ale arboreluispa iului soluiilor pentru a fi prelucrate ulterior, numitevrfuri active .Dintrevrfurile active se va alege cte un vrf care va fi prelucrat, numitvrf curent . n momentul n care un vrf activ devine vrf curent se vorgenera/determina toi descendenii si, acetia devenind vrfuri active (sevor aduga listei vrfurilor active) dup care unul din elementele acesteiliste devine vrf curent.Lista poate funciona ca o coad sau ca o stiv. Parcurgerea (vizitarea)arborelui spaiului soluiilor, n cazul metodei Branch and Bound difer de metoda Backtracking prin aceea c n momentul n care un vrf activ

devine vrf curent sunt generai (determinai) toi descendenii si, acetiadevenind vrfuri active (fiind deci adugai listei vrfurilor active), dupcareunul dintre elementele acestei liste devine vrf curent.Presupunnd c vrfurile active vor fi memorate ntr-o list L i c pentruvrful i vom memora tatl n TATA(i), o procedur Branch and Boundpoate fi:procedureBranchBound (arbore, rd)i rd, L do

for [to i j vecini ai lui i]if [j vrf rezultat]

then write[drumul de la rdcin

la j],return

endif L jTATA(j) i

repeatif L =

then write Nu ,return

elsei Lendif

enddoreturn


41/78


Observaie: deoarece pentru vrfurile active i vom memora n TATA(i)tatl lor, aceasta permite ca odat ajuni ntr-un vrf rezultat, s putemreface cu uurin drumul de la rdcin la vrful rezultat respective.Exemplu: Fie urmtoarea problem de ordonanare: se dau dou repere R1 i R2 prelucrate pe dou maini m1 i m2. Procesul de prelucrare estereprezentat prin graficul reea din figura 3.28,

Figura 3.28 Prelucrarea reperelorunde n noduri sunt reprezentate fazele sau operaiile de efectuat pentrufiecare reperi pe ce main de execut iar arcele reprezint duratele. Secere minimizarea duratei totale de efectuare a operaiilor.Metoda presupune ramificareai mrginirea, pornindu-se de la ideea c peambele maini nu s-a programat nici o operaie:

Figura 3.29 Obinerea soluiei

m1 m2 m1 1 2 3

4 5 6

0 7

03 7

01 4

5

7

R1 - reper

R2 - reper

m2 m1 m2

A

B C

E

F G

H I

m1={}m2={}

Z0=0

m1={5}m2={}

Z2=20m1={1}m2={}Z1=15

m1={1,5,3}m2={2}Z6=20

m1={1,5,3}m2={}

Z5=15

m1={1,5,3}m2={4}

Z7=15

m1={1,5,3}m2={4,6,2}

Z9=22

m1={1,3,5}m2={2}Z4=22

m1={1,5,3}m2={4,2,6}Z8=15

Soluie optim

D


42/78


Nod B

Nod C

Soluia optim

Fig 3.30 Reprezentarea soluiilor

3.3.2.3. Metoda programrii dinamiceProgramarea dinamic este o metod care rezolv problemele combinndsoluiile subproblemelor. Pentru aplicarea ei este necesar satisfacereaprincipiului optimalit ii.Pentru aplicarea metodei este necesar satisfacerea principiuluioptimalitaii: dac exist un ir optim de decizii (d1,,dn) care transform o stare iniial s0 ntr-o stare final sn, trecnd printr-o serie de striintermediare (s1,,sn-1), atunciirul de decizii este optim pentru s1 ca stareini ial i sn ca stare final. Cu alte cuvinte o soluie optim la o problem

m1 R1

5

1 2 3

4 5 6

0 7

03 7

01 4

5

7

Z=3+7+5=15

R1

m2

m1

R1

R1

R2 R2

R2 3 10 15

1 2 3

4 5 6

0 7

03 7

01 4

5

7

Z=1+4+3+7+5=20

R2

m2

R2

R1

R2 R1

8 15

1 2 3

4 5 6

0 7

03 7

01 4

5

7

Z=1+4+3+7+5=20

20


43/78


conine soluii optime la subproblemele care compun problema ce trebuierezolvat.Dup ce principiul optimalitaii a fost verificat, problema const n a scrierelaiile de recurencorespunztoarei a le rezolva. Aceste relaii sunt dedou tipuri :- fiecare decizie di depinde de deciziile di+1,,dn, aici aplicndu-semetoda nainte, iar deciziile se iau n ordinea dn,dn-1,,d1;- fiecare decizie di depinde de deciziile d1,,di-1. n acest caz spunem c

se aplic metoda napoi. Deciziile vor fi luate n ordinea d1,d2,,dn.n programarea dinamic se rezolv problema combinnd soluiilesubproblemelor (la fel ca n cazul metodei divide et impera). Exist trei

principii : evitarea recalculrii de mai multe ori a unor subcazuri comune, prin

memorarea rezultatelor intermediare; metoda opereaz de jos n sus : se pornete cu cele mai mici subcazuri,

se combin rezultatele lori se obin soluii pentru subcazuri din ce nce mai mari pn cnd se ajunge la soluia cazului iniial;

trebuie sa fie satisf cut principiul optimalit ii.Un algoritm de programare dinamic poate fi descris prin urmtoareasecven de pai :1) se caracterizeaz structura unei soluii optime;2) se obine recursiv valoarea unei soluii optime;3) se calculeaz de jos n sus valoarea unei soluii optime;4) din informaiile calculate, se construiete de sus n jos o soluie optim.Observaie :Pasul 4) se aplic atunci cnd se dorete soluia propriu-zis i se rezolv printr-un algoritm recursiv, care efectueaz o parcurgere n sens invers asecvenei optime de decizii calculate anterior.Un exemplu de problem concret pentrucare se poate utiliza metodaprogramrii dinamice este problema reaprovizionrii la un depozit. Fie s0 stocul iniial existent ntr-un depozit la momentul t0. n general, si este stareastocului dup o perioad de producie iar di cantitatea de reaprovizionat lamomentul ti (vezi figura 3.31).


44/78


Figura 3.31 Evoluia stocului

Un alt exemplu este acela n care considerndu-se un graf neorientat G(X, )ale crui muchii au ataate o lungimi strict pozitive, se dorete determinriicelui mai scurt drum ntre douvrfuri ii j.Metoda programrii dinamice se poate aplica n mai multe moduri: Fie i, i1, i2, .... , in, j un drum de lungime minim de la i la j. Atunci este

evident c i1, i2, .... , in, j este un drum de lungime minim de la i1 la j,ceea ce arat c este satisf cut principiul optimalit ii. Dac notmpentru kX prin L(k,j) lungimea drumului minim de la k la ji dac dik este lungimea muchei (i,k) obinem:

)},({min),(),(

jk Ld ji L ik ji+=

Dac i, i1, i2, .... , im, j este un drum de lungime minim de la i la j atuncise observ c drumul i, i1, i2, .... , im este un drum de lungime minim dela i la jm. Corespunztor acestei forme sub care este satisf cut principiuloptimalit ii vom nota L (i,j) lungimea drumului cel mai scurt de la i lak,kx. Obinem:

}),('{min),('),( kj jk

d k i L ji L +=

Fie i, i1, i2, .... , im, j un drum de lungime minim de la i la ji fie k = is =max {i1, ..., im}. Atunci se observ c i, i1, ..., is este cel mai scurt drum

ntre ii is, iar drumul is, i j+1, ..., im este cel mai scurt drum de la is la j; nplus vrfurile intermediare prin care trec aceste drumuri au valori maimici dect k. Corespunztor acestei noi forme sub care este satisf cutprincipiul optimalit ii, pentru dou vrfuri u, vX notm cu Lp(u,v)lungimea drumului minim de la u la v care nu trece prin vrfuri cunumere de ordine mai mari sau egale cu p. Atunci este valabil relaia:

L(i,j) = Lk(i,j) = Lk-1(i,is) + Lk-1(is, j)Observaie: fie (i, i1, i2, ..., is, ..., j) un drum care trece prin vrful is. Dac drumurile care trec prin (i, i1, ..., is) i (is, ..., i j) sunt de lungime minim

sn

d1

s0 s1 . . . . . . . .

d

Stare iniial Stare final


45/78


pentru capetele (i, is) respectiv (is, j) nu nseamn c drumul iniial arelungimea minimpentru capetele ii j.

3.3.3. Metode clasice suboptimale

Aceste categorii de metodei algoritmi atasai sunt tratate deasemenea ncadrul disciplinelor de ingineria programrii i au proprietatea ca nu conduc, n general, la soluii optimale a problemelor sau nu se cunoate acest fapt. Elese preteaz la rezolvarea probelmelor reale combinnd cu ali algoritmidoarece se blocheaz ntr-o soluie suboptimal pe care nu reuete s o mai nbunt easc. Din aceast grup de metode fac parte metoda Divide etimpera, Metoda optimului local ( Greedy )i metodele euristice.

3.3.3.1. Metoda Greedy (Metoda optimului local)

Metoda se aplic problemelor n care exist o mulime A de n date deintrarei se dorete determinarea unei submulimi B a lui A (BA) cares satisfac anumite condiii pentru a fi acceptat.Totalitatea submulimilor de acest tip formeaz solu iile posibile (SP)aleproblemei. Dintre soluiile posibile, pe baza unui criteriu suplimentar dealegere, se selecteaz o singur soluie, numit solu ie optim (SO).

Metoda nu caut s determine toate solu iile posibile i s aleag unaoptim , conform criteriului de optimizare dat, (ceea ce necesit timp decalculi spaiu de memorie mari) ci const n alegerea pe rnd a cte unuielement, urmnd s-l introduc (s-l nghit), eventual, n soluia optm

(de aicii numele metodei: greedy = lacom).Un exemplu de aplicare a acestei metode este problema rucsacului: unexcursionist se pregtete pentru a face o excursie; pregtete tot ce arenevoie i constat c lucrurile nu ncap toate n rucsac (ca volum saucantitate). Ce s fac? Cum obiectele nu sunt toate de aceeai necesitate,ievident de volum diferit, alege, pe rnd, cte un obiect de necesitatemaxim i de volum minimi l pune n rucsac. Procedeul se va relua pn la umplerea rucsacului.Fie deci SP mulimea soluiilor posibile ale problemei, soluii ce aupropropietatea de monotonie. Dac BSP i CB atunci CSP. Deci


46/78


orice submulime C a unei soluii posibile este de asemenea soluieposibil.Vom presupune c mulimea vid este ntotdeauna soluie posibil SP.Metoda Greedy trateaz acest tip de probleme n dou moduri, care nesen

sunt asem

ntoare, diferena constnd n ordinea operaiilor:

Metoda Greedy 1Se pleac de la soluia vid. Se alege, pe rnd, ntr-un anumit fel, un elementdin A, neales la paii precedeni. Dac adugarea lui la soluia parial,construit anterior, conduce la o soluie posibil se construiete aceast soluie prin adugarea elementului.

Unde procedura ALEGE furnizeaz elementul x = a j , a j a1,a2, ., an iefectueaz interschimbarea ai a j. Procedura POSIBIL furnizeaz nvariabila v valoarea 1 dacB x este soluie posibil sau 0 n caz contrar.Procedura ADAUG nlocuiete pe B prin B x .Se observ c dac procedura POSIBIL efectueaz verificrile date prinenunul problemei, n procedura ALEGE, persoana care realizeaz algoritmul, va trebui s stabileasc un criteriu conform cruia alegerea s conduc n final la soluia optim.

Procedura GREEDY1(A,n,B)B For i = 1,n

Call ALEGE(A,i,x)Call POSIBIL(B,x,v)If v = 1

ThenCall Adaug(B,x)

Endif RepeatReturn

End


47/78


Metoda Greedy 2Se procedeaz ca n cazul metodei Greedy 1, cu excepia faptului c sestabilete de la nceput (i nu dinamic) ordinea n care trebuie considerateelementele.

Procedura PREL efectueaz o permutare a elementelor mulimii A pe bazacriteriului stabilit.Un exemplu tipic de problem la care se pate aplica metoda Greedy lconstitui problemele de optimizare, cum ar fi determinarea maximului uneifuncii de cost. Ideia general a metodei este de a alege la fiecare pas acelelement care face screascct mai mult valoarea funciei obiectiv.Metoda prezint anumite dezavantaje. Pe de o parte, exist dificult i n

alegerea elementului, iar pe de alt parte, se pune ntrebarea dac prinmaximizri succesive se ajunge ntr-adevr la maximul global (lucru care ngeneral nu este adevrat). De aceea metoda Greedy trebuie privit doar ca osurs a unei ideei, urmnd s se determine apoi dac soluia obinut esteoptim.Exemplul 1:Se consider o mulime X x1,x2, ., xn de elemente reale. Se puneproblema determinrii unei submulimi Y a lui X astfel ca

Y y

y s fie

maxim. Se observ c dac dac o mulime Y conine un element yo0atunci suma elementelor lui Y-{yo} este mai mare sau egal cu suma

Procedura GREEDY2(A,n,B)

Begin Call PREL(A)B i = 1v 0While in

Call POSIBIL(B,x,v)If v = 1

ThenCall ADAUG(B,xi)

Endif i = i + 1

EndwhileEnd

Return


48/78


elementelor lui Y:

}{ 0 yY y Y y

y y . Din acest motiv se va accepta faptul

co submulime YX cu toate elementele pozitive, este o soluie posibil.Se va utiliza procedura Greedy1 n care: Procedura ALEGE furnizeazx = ai Procedura POSIBIL atribuie lui v valoarea i dacai>0i 0 n caz contrar k reprezintnumrul final de elemente din Y

Procedure SUBP(x,y,n,k)Array x(n), y(n);k = 0i=1while in

if xi > 0then

k = k + 1yk = xi

endif i = i + 1endwhile

end

Aplica ie economic O persoan dispune de o anumit sum de bani pe care o poate investi nmai multe obiective.Se consider urmtoarele notaii:

S suma total posibil de investitn numrul de obiective

s j suma necesar pentru obiectivul j, cu Ssn

j j >=1

e j eficenta investiiei jx j variabil decizional cu valoare 0 sau 1

Se dorete s se selecteze obiectivele n care se poate investii n limitasumei disponibilei care s conduc la o eficien maxim. Modelul va fiurmtorul:

=

n

j j j xe

1max


49/78


S xsn

j j j

=1cu { }1,0 j x

Presupunem obiectivele ordonate dup criteriuln

n

s

e

s

e

s

e ...2

2

1

1

Procedura va fi:Procedure Greedy(e,s,S,x)B=0SUM=0EF=0While jn

BeginIf SUM+s j < S

ThenB = Bs j EF=EF+e j

x j = 1Elsex j = 0

Endif j=j+1

EndEndwhile

End

3.3.3.2. Metoda Divide et impera

Este o metod general de elaborare a algoritmilor care const n mpr irea repetat a unei probleme de dimensiune mai mare n dou saumai multe subprobleme de acelai tip, urmat de combinarea soluiilorsubproblemelor rezolvate pentru a obine soluia problemei iniiale.Se presupune un vector A = (a1,,an) asupra elementelor cruia trebuieefectuat o prelucrare oarecare. Mai mult, se presupune c pentru orice p,q naturali cu 1 p


50/78


Deoarece subproblemele rezultate prin separare sunt de acela tip cu ceaini ial, problema se exprim n mod uzual prin urmtoarea procedur :

procedure divimp(p, q,)if q p then call prel(p, q,)

else call div(p, q, m);call div(p, m,)call divimp(m+1, q, )call comb(, , )

endif return

end Procedura descris trebuie apelat prin call divimp(1,N,), n ob inndu-se rezultatul finali unde:

este lungimea maxim a unei secvene {ap,,aq} notat prescurtatprin (p, q), pentru care prelucrarea se poate face direct, f r a maifi necesar mpr irea n subprobleme;

procedura prel relizeaz prelucrarea secvenelor de acest tip,furniznd rezultatul n. procedura comb realizeaz combinarea rezultatelor, ale

prelucrrii a dou secvene vecine, obinndu-se rezultatul. Valoarea m este obinut aplicnd proceduradiv.

Exemplu - sortarea prin interclasare: trebuie sortat cresctor un irA=(a1,,an). Proceduradiv va furniza valoarea m=[(p+p)/2]. Vom lua = 1deoarece e uor de scris o procedur prel care s ordoneze un subir de tipul{ai, ai+1}. Proceduracomb va interclasa subirurile deja sortate {ap, ... , am} i{am+1, ..., aq} furniznd rezultatul sortrii subirului {ap, ... , aq}.

3.3.3.3. Metode euristiceAlgoritmiii metodele prezentate anterior sunt neeficieni pentru problemegrele, combinatorialei de dimensiuni mari. Aceasta deoarece timpul derezolvarei /sau memoria intern necesar este exponenial n raport cudimensiunile problemei.n aceste situaii, pentru astfel de probleme, se accept utilizarea unoralgoritmi despre care nutie sau nu s-a demonstrat deocamdat c suntoptimali, dar care furnizeaz rezultate acceptabile ntr-un timp mai scurt


51/78


i cu un consum mai redus de memorie. Datorit importanei mari acriteriului timp n raport cu spaiul de memorie necesar, se va avea nvedere criteriul timp.Un algoritm se numete euristic dac are urmtoarele propiet i:

furnizeaz, de obicei, soluii bune dar nu neaprat optime poate fi implementat mai uor i permite obinerea rezultatelor ntimp rezonabil, n orice caz mai scurt dect cel cerut de orice

algoritm exact cunoscut.O idee frecvent utilizat n elaborarea algoritmilor euristici, const ndescompunerea procesului de cutare a soluiei n mai multe subprocese(etape) successivei cutarea soluiei optime a fiecreia n parte(presupunnd c fiecare subproces este suboptimal). Aceast strategie nuconduce ns ntotdeauna la o soluie optimal, deoarece optimizarealocal nu mplic, n general, optimizarea total (sau optimul parial nucoincide cu optimul general). Deoarece un algoritm elaborat pe bazametodei Greedy care furnizeaz

o soluie care nu este optim

(sau nu I se

poate demonstra optimalitatea) este un algoritm euristic.Pentru elaborarea unui algoritm euristic se pun n evidentoate condiiilepe care le satisface o soluie exact i se impart condiiile n dou sau maimulte clase conform unor criterii. Aceste criterii pot fi facilitateasatisfacerii condiiilor i necesitatea satisfacerii lor. Din aceste puncte devedere condiiile pot fi:

condiii uor de ndeplinit condiii dificil de ndeplinit (se poate accepta ndeplinirii primelor)

o condiii necesare (nendeplinirea lor mpiedic ob inereaunei soluii posibile)

o condiii pentru care se poate accepta un compromis, nsensul c ele pot fi nlocuite cu alte condiii care permitapropierea de o soluie optimal (eventual optim)

n aceast situaie satisfacerea condiiilor necesare e obligatory arcalitatea soluiei depinde n mare msur de compromisul adoptat pentrucondiiile din a doua categorie.Menionm c:

algoritmii euristici sunt utili pentru utilizri sporadice, unice,deoarece efortul determinrii soluiei optime este prea mare fadectigul obinut


52/78


algoritmii euristice furnizeaz soluii aproximative dari algoritmiianalizei numerice au soluii aproximative, f r a lua n considerarepropagarea erorilor de rotunjire, greu controlabile, care pottransforma un process convergent ntr-unul divergent.

De exemplu, n problema ordonanrii operaiilor pe o main, n graful dinfigura 3.32 nodurile reprezint reperele de ordonanat, iar arcele sunt tranziiiposibile ntre acestea. O secvenposibl de prelucrare este dat de un drumcare parcurge fiecare nod o singurdat. Matricea T conine timpii de trecerede la o operaie i la alta j.

1 2

5 4 Figura 3.32 Reprezentarea problemei de odonanare

Pornim de la produsul 1 (nodul 1) elementul minim pe linia 1 este t16 =1(coloana 6), marcm arcul 1-6.

1 2

5 4

Figura 3.33 Determinarea soluiein linia 6 elementul minim este t51 dar avem voie s facem ciclu numaicnd au fost parcurse toate produsele. Deci alegem minimul urmtor t63=3 (se putea alege t65=3) marcm arcul 6 3.

6 T =3

36

0 2 5 6 3 11 0 4 3 7 53 3 0 5 2 44 3 2 0 1 57 2 5 2 0 42 4 3 4 3 0


53/78


n lina 3 avem elementul minim t35=2, din linia 5 avem elementul minimt52sau t54=2.Marcm arcurile 3-5 si 5 2. La sfrit, n linia 2, minimul este atins de t21=1 dar nu am vizitat nc nodul 4, aa c alegem elementul t24=4.Avem ordonaarea produselor 1-6-3-5-2-4 iar timpul de pregtire total

este = 1+ 3+ 2 + 2 + 3 = 11.Se poate observa c plecnd dintr-un alt nod putem obine alte soluii maibune sau mai proaste.Execuia lucrrilor de ctre mai multe procesoare:Fie n procesoare P1, P2, ..., Pn i m lucrri L1, L2, ..., Lm, independente caretrebuie efectuate cu ajutorul acestor procesoare n urmtoarele condiii:

- procesoarele pot funciona simultan- orice lucrare poate fi efectuat de ctre orice procesor- o lucrare iniiat de un procesor este continuat de acesta pn

la terminare

Fie t1, t2, tn duratele executrii celor m lucrri. Se cere o programare alucrrilor pe procesoare astfel ca ele s se termine, n ansamblul lor, ctmai repede.O programare bine definit este un vectorL = {Li1, Li2, ..., Lim} cu {i1, i2,..., im}={1, 2, ..., m} dac sunt satisf cute condiiile:

- primul procesor devenit liber preia prima lucrare neprogramat dinL - dac dou sau mai multe procesoare devin libere simultan, cel carepreia o lucrare este cel de indice minim- procesoarele intr n lucru f r vreo ntrziere

Fie exemplul a trei procesoarei ase lucrri avnd n ordine duratele t1=2,t2=5, t3=8, t4=1, t5=5, t6=1.ProgramareaL 1 = (L2, L5, L1, L4, L6, L3) necesit un timp total T1 = 12,dar procesoarele P1 i P2 stau mult timp neocupate, deci nu poate fi oprogramare optim.


54/78


12105

L1 L4 L6 L3

L5

L2P1

P2

P3

Figura 3.34 ProgramareaL LL L 1

ProgramareaL 2 = (L3, L2, L5, L1, L4, L6) are T2 = 8, deci este mai bun ieste chiar optim, deoarece durata lui L3 este egal cu 8, deci durataoricrei programri este de cel puin opt unit i de timp.

L2

L5

1085

L1

L3 P1

P2

P3 L4 L6

Figura 3.35 ProgramareaL LL L 2

O procedur euristic simpl de rezolvare a problemei const nprogramarea lucrrilor n ordinea descresctoare a duratelor, care n cazulexemplului conduce chiar laL 2.n general aceast procedur nu conduce la programarea optim; deexemplu fie dou procesoare cu cinci lucrri cu t1=3, t2=3, t3=2, t4=2, t5=2.Conform ordinii descresctoare a duratelor avem (L1, L2, L3, L4, L5), iarprogramarea optimal este (L1, L3, L4, L2, L5).Se observ c s-a nlocuit condiia de durat minim greu de satsf cut cucondiia efecturii prioritare a lucrrilor cu durat maxim. Dar oschimbare a datelor poate produce ndeprtarea de soluia optimal.Deci algoritmii euristici sunt sensibili la schimbri ale datelor iniiale aleproblemei, mai exact schimbri mici n datele iniiale produc apropiereasau ndeprtarea simitoare de soluia optim.


55/78


3.3.4. Metode de simulare local Aceste metode sunt caracteriazte prin faptul ca ele caut ieirile dintr-unoptim locali sunt foarte bine paralelizabile pe oricte procesoare paralele.Din aceast grup fac parte metodele de simulare pur, simulare dirijat,simulare de tip clire, tabu, retele neuronale, algoritmi geneticii evolutivi.3.3.4.1. Simulare pur, simulare dirijat Cutare n spa iul soluiilor.Analiznd algoritmii deterministici (din analiz numeric sau cercetrioperaionale) i algoritmi stochastici se constat c majoritatea auelemente comune: poresc de la o soluie iniial i cauts nbun easc soluia curent unii algoritmi conduc la optimi acest lucru se poatei verifica, alii

conduc la optim dar verificarea acestui fapt devine practic inposibil,al ii nu pot sconduc la o soluie optimglobal.

Pornind de la aceste constatri, n literatura de specialitate s-au conturat oserie de cercetri n direcia nbunt irii algoritmilor clasici sau elaborareaalgoritmilor noi. Unele dintre aceste metode vor fi prezentate n continuare.n cele ce urmeaz vom descrie un algoritm cu caracter general pentruprocesul de cutare n spaiul soluiilor.Fie problema

max {cx | xS }unde S este spaiul soluiilor, x este un element din acest spaiu iar prin cxfiecarui element din S i se asociaz o valoare real care msoar calitateaelementului ntr-un anumit sens.Fie x un punct din S. Vom defini vecintatea punctului prin:

V(x) = { x | dist ( x - x)


56/78


Deoarece problema gsirii unui punct iniial de pornire poate fi complicat,iar muli algoritmi pleaccu un punct iniial, nu se preocupde determinareaefectiv a soluiei inialei nici de existena ei, cutarea determinist acelormai bune soluii este prohibitiv.Cutarea n spaiul soluiilor revine la determinarea punctului x* dinvecinetatea punctului x care satisface egalitatea:

c x* = { max c xx S V(x) }dup care se stabilete x = x* i se continu cu determinarea unui nou punctx*.Cutrile locale dirijate n spaiul soluiilor se pot ilustra ca n figura 3.36.

Fig. 3.36. Cutri locale dirijate n spaiul soluiilor

Unde dreptunghiurilei cercurile sunt vecintti, iar sge ile indic direcia n care se efectueazcutrea, respectiv simularea.Problemele de optimizare ntr-o vecinetate pot fi de asemenea dificile, motivpentru care se practic o simulare dirijat local n vecinetatea punctului xsau se simuleaz puncte din vecintate care s conduc numai la valori maibune (figura 3.37.).

Fig. 3.37. Simulare dirijat local Aceste procedee reduc numrul punctelor analizate ca soluii dar cutarea sepoate bloca ntr-un suboptim local. Din acest motiv s-au ncercat altemodalit i de simulare, unele din ele fiind prezentate n continuare.

1

2

3

4


57/78


3.3.4.2. Simulare de tip clire (SA)Simularea de tip clire (simulated annealing) este o metod de cutare nspa iul soluiilor prin simulare dirijat dup curba de rcire a metalelor ntimpul clirii (de undei denumirea metodei).

Clirea simulat este o tehnic de tip Monte-Carlo care poate fi folosit pentru a gsi soluii n problemele de optimizare. Metoda simuleaz procesul de rcire al metalelor. La temperaturi nalte atomii metalelor suntliberi s se deplasezei tind s o fac aleator. Cnd temperatura estesczut nu mai este posibil nici o micare, structura fiind ngheat. Dac rcirea metalului se face treptat, atomii tind s se aeze n punctele deminim energie ( astfel nct energiile dintre atomi s fie minime ). Dac rcirea se face brusc,ansele s se obin o asemenea poziionare aatomilor sunt minime. La orice temperatur dat, este acceptat o nou configuraie a atomilor dac energia sistemului este sczut. Probabilitateaca la o temperatur dat s se obin o scdere a energiei este

KT E e E P / )( = , unde K este constanta lui Boltzmann.Multe probleme de optimizare pot fi considerate ca un numr de obiectecare trebuie planificate astfel nct o funcie obiectiv s fie minimizat.Atomii sunt nlocuii cu obiecte, iar valoarea funciei obiectiv nlocuieteenergia sistemului. Sunt create o planificare iniial, aleatoare, aobiectelor, un cost iniial (c0) i o temperatur (T0). Permutrile serealizeaz astfel : se aleg aleator obiecte, sunt rearanjatei se calculeaz schimbarea n cost. Dac 0c , atunci schimbarea este acceptat. Dac

0>c se calculeaz probabilitatea schimbrii la temperatura T :T c

ecP /

)(

= Dac probabilitatea este mai mare dect o valoare aleas aleator nintervalul (0, 1), atunci schimbarea este acceptat. Dup un numr depermutri cu succes temperatura este sczut cu o rat de rcire.Legat de algoritmul de tip clire se pun dou intrebri:

dacprocedura converge? cum se implemanteaz algoritmul adic cine sunt (x,Tk) i cum

arat irul de temperaturi Tk.Pentru a rspunde la cele dou ntrebri se pot cita urmtoarele rezultate dinliteratur. Metropolis a aratt c dac avem ast , ats i (,T) = exp ( /T),


58/78

3-58 Reprezentareai co

cap 3 a si construirea algoritmilor

Documents