BNF

IIII

ANFXA 1 -Codi i l ASCII ...A^JA 2 " Sin'axa limbJ"lii PascalANhXA 3 - Diagrame sintacliceAM^JA 4 " F"nc!ii ?i l>rociuri s tandard . .A1NLXA 5 - Mic dictionar de lermeni inforniatici

Bibliografie

CAPITOLUL1

343349359

389

II

ALGORITMI

Notiunea de algoritm, utilizata din cele mai vechi timpuri, este unadin notiunile fundamentale ale matematicii.

Termenul de algoritm se pare ca a derivat din numelematematicianului persan Abu Abd-Allah ibn Musa al'Khwarizmi sau AbuJa'far Muhamad Ibn Musa alTChwarizmi (790-840), care a scris o carte dematematica cunoscuta in traducerea latina ca "Algorithmi de numeroindorum", apoi ca "Liber algorithmi".

Matematicienii din Evul Mediu, intelegeau prin algoritm o regula pebaza careia se efectuau calcule aritmetice. Astfel, in timpul lui Adam Riese(sec. XVI), algoritmii erau utilizati pentru dublari, injumatatiri, inmultiri denumere. In lucrarile lui Stifer ("Arithmetica integra", Niirnberg, 1544) siCardano ("Ars magna sive de reguli algebraicis", Niirnberg, 1545), apare deasemenea termenul de algoritm. Mai tarziu, Leibniz foloseste termenul"algoritm de inmultire".

Kronecker (1886) si Dedekind (1888) semneaza actul de nastere alteoriei functiilor recursive. Conceptul de recursivitate devine indisolubillegat de eel de algoritm. Dar abia in deceniile al treilea si al patrulea alesecolului XX, teoria recursivitatii si a algoritmilor incepe sa se constituie caatare, prin lucrarile lui Skolem. Ackermann. Sudan, Godel, Church, Kleene,Turing si altii.

Prin aparitia calculatorului, notiunea de algoritm capata noi valentesi se contureaza rolul central pe care il acesta joaca in rezolvareaproblemelor, de o mare diversitate, cu ineditul instrument de lucru. Se puneproblema definirii riguroase a notiunii de algoritm, se poate vorbi deabordarea algoritmica a unei probleme, si chiar a unei clase de probleme.

Prin algoritm astazi se intelege o metoda generala de rezolvare aunui anumit tip de problema, metoda care se poate implementa pecalculator, programul fund exprimarea unui algoritm intr-un limbaj deprogramare. Cei mai simpli algoritmi cunoscuti sunt reguli pe baza carora seefectueaza una sau alta din cele patru operatii aritmetice in sistemul zecimal,

14 RA7.KLE INFORMA TIC 11

numiti si algoritnii numeric!. Exista, de asemenea, algoritmi algebrici.algoritmi logici.

Vom prezenta cateva exemple de algoritmi, pcntru a pune inevidenta proprietatile lor generale.

Exemplul I. Operatia de adunare a doua numere cu mai multe cifrese descompune intr-un lant de operatii elementare de doua tipuri:

a) calculul cifrei corespunzatoare sumei a doua cifre;b) retinerea acesteia atunci cand se trece la pozitia imediat la stanga

celei precedente; ordinea indicata prin aceasta regula, de efectuare aoperatiilor, este de la dreapta la stanga.

Aceste operatii elementare au un caracter formal, deoarece ele pot fiefectuate in mod automat, cu ajutorul unui label de adunare a cifrelor dat dela inceput, facand complet abstractie de semnificatia lor.

Observatie. La fel se intampla si in cazul celorlalte trei operatiiaritmetice, pentru extragerea radacinii patrate etc.

Exemplul 2. Algoritmul lui Euclid permite aflarea celui mai maredivizor comun a doua numere naturale date a si b. Exista atatea problemedistincte de acest tip, cate perechi diferite de numere (a,b) exista. Oricaredintre aceste probleme se poate rezolva prin constructia unui sir descrescatorde numere, primul fund eel mai mare dintre numerele date, al doilea eel maimic dintre ele, al treilea restul impartirii primului la al doilea, al patrulearestul impartirii celui de al doilea la al treilea etc., pana cand se ajunge la oimpartire al carei rest este nul. In acest ultim caz, impartitorul va firezultatul cautat.

Putem prezenta algoritmul in mai multe variante; prin a si b vomintelege doua marimi variabile ale caror valori initiale sunt cele douanumere date:I) PI. Citeste a si b\

P2. Calculeaza r, restul impartirii lui a prin b (r - a- [a//>]-/?)P3. Daca restul este nul, scrie b si opreste procesul de calcul; altfel, aia valoarea lui b. b ia valoarea lui r ( a - b: b - r) si treci la pasul P2.Observatie. In aceasta prezentare a algoritmului nu este neaparata

nevoie ca a si b sa fie in ordine descrescatoare.Cum operatia de impartire se reduce la un sir de scaderi, algoritmul se poateprezenta si astfel:II) PI. Citeste a si b;

P2. Compara a cu b. Daca sunt egale, oricare dintre ele furnizeazarezultatul cautat, se scrie valoarea comuna si se opreste procesul de

calcul; altfel, daca primul dintre ele este mai mic, se permuta iele (c = o;a = b;b = c ) si se trece la pasul urmator.P3. Se scade b din a, se considera a scazatorul, iar h restul obi(r a - b; a = b ; h - r) si se trece la pasul P2.

Ill) PI. Citeste a si ft;P2. Compara a cu h. Daca sunt egale, atunci scrie a (sau b)opreste procesul de calcul; altfel, daca a este mai mare, a1a - a - b, in caz contrar b = b - a si se revine la pasul P2 cuvalori pentru a si b.In matematica, nu intotdeauna algoritmii sunt formula}! detaliat.

se prefera acest gen de fonnulare pentru algoritmii cunoscuti. Opeielementare necesare procesului de rezolvare al problemei de mai sivarianta III, de exemplu, sunt cele de scadere a doua numere, de comp;de citire i respectiv, de scriere. Dar descompunerca poate conscaderea se poate reduce, la randul ei, la un sir de operatii mai s(Exemplul 1), etc.

Algoritmii numeric!, cei care corespund problemelor arezolvare se reduce la cele patru operatii aritmetice, joaca un rol impin domeniile cele mai diverse ale matematicii, atat elementare * ] , prin formula a

k - 0,1,2 Procesul de calcul se opreste cand \xkn xk\ < K , unde E ested;il, u l t imul element calculat al sirului (^)tr=N furnizeaza rezultatul cautat sireprezinta radacina patrata a lui a cuprecizia .

Prin metode analoage analiza numerica reduce operatii maicomplexe cum ar fi integrarea si derivarea la operatii aritmetice. Spunem cao clasa de probleme de un anumit tip dat este rezolubila daca este pus inevidenta un algoritm pentru rezolvarea sa.

Daca nu dispunem de un algoritm prin care sa se rezolve toateproblemele de acest tip, atunci trebuie sa se descopere cate un procedeuspecial pentru fiecare caz in parte, care poate nu este convenabil de aplicatmajoritatii celorlalte cazuri.

De exemplu, sa consideram toate ecuatiile diofantice imaginabile,adica ecuatiile de tipul P = 0, unde P este un polinom cu coeficienti intregi.Ecuatia poate avea sau nu o solutie intreaga.

Printre cele 20 de probleme pe care marele matematician germanDavid HUbert (1862-1943) le-a prezentat in 1901 la Congresul Internationalde Matematica figura si problema urmatoare, cunoscuta sub numele de azecea problema a lui Hilbert: Gasirea unui algoritm care sa determine dacao eciiatie diofantica are sau nu o solutie intreaga

Daca ecuatia cu coeficienti intregi,anx" + aa_}x"~

] +...+ atx + a0 =0, (1)

admite o radacina intreaga, atunci radacina este un divizor al termenuluiliber. Se poate descrie algoritmul astfel:

PI. Citeste n. au,a},..,an.P2. Afla divizorii Iuio0 (verificand succesiv daca aa se divide cu

2,3v.,k/2]).P3. Calculeaza valoarea numerica a expresiei din primul membru alecuatiei (1) pentru fiecare divizor gasit.P4. Daca valoarea calculata este 0, atunci divizorul respectiv este oradacina a ecuatiei. Scrie acest divizor. Daca primul membru alecuatiei (1 ) nu se anuleaza pentru nici un divizor, atunci ecuatia nuare radacini intregi.Nu se cunoaste un algoritm pentru cazul general, in care ecuatia are

mai multe nedeterminate.

( \ ipilit lul I - Algoritmi 17

In general, un algoritm poate fi conceput ca un sir finit de etape cepennit obtinerea unui rezultat prin efectuarea unui numar finit de operatiiintr-o ordine determinate asupra unor valori initiate date.

Din exemplele examinate se evidentiaza deja caracteristicilealgoritmilor numerici, care sunt proprii oricarui algoritm si anumedeterminarea, universal!tatea si eficienta.

1) Fiecare operatic este bine determinata. Calculele efectuateconform instructiunilor precizate de algoritm nu depind de calculator sireprezinta un proces determinat care poate fi reluat oricand de altcineva, cuaceasi finalitate.

2) Un algoritm conduce la un program unic ce determina un anumitproces de calcul in care datele initiale pot fi diferite, dar in toate acestecazuri obtinandu-se rezultate corespunzatoare. Cu alte cuvinte, un algoritmrezolva nu doar o problema, ci o clasa de probleme de acelasi tip.

3) Un algoritm permite ca dupa efectuarea unui numar finit deoperatii asupra unor date initiale, sa se obtina efectiv anumite rezultate.

Fiecare proces ale carui etape izolate sunt realizate succesiv prinintermediul unui calculator poate fi descris printr-un algoritm. Pe de altaparte, orice algoritm cunoscut astazi sau care poate fi prevazut in stadiulactual al stiintei, poate fi, in principiu, realizabil prin intermediul unuicalculator. Un algoritm poate contine un ir finit, dar destul de lung deoperatii si din acest motiv poate deveni practic irealizabil de catre uncalculator, daca volumul de memorie necesara este mai mare decat eel decare dispune masina, sau timpul necesar efectuarii operatiilor algoritmului,desi finit, este prea mare. In astfel de cazuri, procesul de prelucrare a unuialgoritm poate fi considerat un proces potential realizabil, ce conduce larezultatul cautat dupa un numar finit, chiar foarte mare, de etape.

Cand vorbim despre posibilitatea realizarii unui algoritm intr-omasina, avem in vedere posibilitatea de a dispune de o memorie infinita.

Definitia matematica riguroasa a notiunii de algoritm. ca si notiuneade masina automata de calcul, nu s-a pus la punct decat dupa anul 1930.Pana atunci, in matematica, termenul de algoritm se intalnea cand se puneaproblema construirii lui efective; afirmatia existentei unui algoritm pentrurezolvarea problemelor de un tip anume era, de regula. probata de descriereasa. Nu se punea problema de a defini in mod riguros notiunea de algoritm. lavremea respectiva fiind satisfacatoare o reprezentare relativ vaga a sa.

Aceasta stare de lucruri a fost depasita prin insasi evolutiamatematicii care acumulase noi fapte. Dorinta naturala a matematicienilorde a crea algoritmi din ce in ce mai puternici, capabili sa rezolve clase din cein ce mai largi de probleme, a schimbat complet situatia.

I - Al_xritmi_

I X BA^ELEJNFVRMATJCfl

Pomind de la un algoritrn dat se poate formula intotdeauna unalgoritm rnai general. Astfel, de exemplu, plecand de la algoritmul deextragere a radacinii patrate se poate formula problema construirii unuialgoritm general de extragere a radacinii de un ordin oarecare dintr-unnumar dat. Mai mult, a extrage radacina de ordinul n dintr-un numar a datrevine la a rezolva ecuatia x" - a = 0. Putem formula, mai general,problema construiri* unui algoritm care sa gaseasca pentru o ecualic detipul anx" + an^x" ' + ...+ a}x + a0 - 0, ( / ? e N ) tuate radacinile sale (a gasipentru orice intreg k aproximarile zecimale ale radacinilor cu eroarea de1/10*, prin lipsa sau prin adaos).

Algebra polinoamelor isi propune construirea si justificarea unuiastfel de algoritm. Problema rezolvarii unei ecuatii de tipul mentionat nueste ultima posibilitate de generalizare.

O formulare foarte generala ar fi urmatoarea:Sa se construiasca un algoritm prin care sa se rezolve orice

problema matematica.O astfel de formulare, desigur, nu este suficient de clara, dar ea

exercita o atractie deosebita pentru matematicieni. Marele matematician sifilozof german Leibniz (1646-1716) isi propusese deja sa gaseasca o metodauniversala prin care sa rezolve orice problema matematica. Un astfel dealgoritm universal nu s-a creat, dar aceasta problema a fost reformulata maitarziu ca problema fundamentala a logicii matematice, numita problemadiscernerii deductibilitatii.

Metoda axiomatica in matematica consta in aceea ca orice teorema aunei teorii date se obtine prin deductie formala logica, poniind de la unanumit numar de afinnatii (axiome) admise fara demonstratie.

In cadrul logicii matematice este descris un limbaj special deformule ce permite descrierea oricarei propozitii (enunt) at unei teoriimatematice sub forma unei formule bine determinate. Problema discerneriideductibili(a{ii poate atunci fi tbrmulata astfel:

Pentru orice doua formule R si S ale calculului logic exista. sau nu,un font dcductiv de la R la S?

Constructia unui astfel de algoritm ar fi o metoda universala pentrurezolvarea automata a problemelor oricarei teorii matematice axiomatizate.Dar. in ciuda eforturilor perseverente ale specialistilor, o astfel deconstructie nu s-a realizat. In rezolvarea unor probleme matematiceparticulare s-au intampinat dificultati considerabile, ceea ce a condus laconcluzia potrivit careia nu poate fi construit un algoritm de rezolvarepentru orice clasa de probleme.

O astfel de afirmatie ar trebui insa justificata printr-o demonstimatematica, demonstratie care ar necesita o definitie riguroasa a notiunalgoritm pentru a proba non-existenta acestuiaT.

Exista probleme care nu pot fi rezolvate prin anumite metodeexemplu problema trisectiunii unghiului cu rigla fi compasul si c belse scrie ' a < b' ,

prcci/.ati ce opcratii descriu fiecare din ele si daca programul in pseuesle corect.

7. Repre/entati in pseudocod algoritmul de rezolvare a urm;probleme: fiind dat un numar reprezentat in baza 2, sa se afiseze ncxprimat in baza 10.

8. Sa se scrie un algoritm pentru calculul sumei a doua imari (care nu pot fi memorate), cunoscandu-se numarul de cifre al 1numar, cifrele si baza in care sunt reprezentate. Reprezentati acest ain pseudocod (vezi algoritmul schitat in Excmplul 1 din introducere).

II

32 ( \i/>iiuliil I - Algoritmi 33

9. Utilizandu-se o procedura de adunare (vezi Exercitiul 1), scrietiun algoritm (in pseudocod) pentru inmultirea a doua numere mari prinadunari repetate.

10. Descrieti detaliat algoritmul de adunare a doua numere cu maimulte cifre. Descrieti un algoritm de ridicare la o putere intreaga m a unuinumar real n dat (tinand seama de paritatea nuinarului n) astfel incatnumarul de operatii sa fie cat mai mic.

11. Se citesc a, b, c, trei numere reale. Daca valorile citite potconstitui coeficientii unei ecuatii de gradul 2, reprezentati in pseudocodalgoritmul de rezolvare, prin care se listeaza solutiile reale sau complexe aleecuatiei.

12. Scrieti un algoritm prin care, citindu-se n numere intregi(inregistrate eventual sub forma unui tablou), se testeaza daca primul numarcoincide cu unui dintre celelalte si se afiseaza un text corespunzator.Algoritmul va preciza, in caz afirmativ, numarul numerelor din sir care suntegale cu primul $i, pentru fiecare dintre acestea, pozitia lor in secventa data.

13. Scrieti un algoritm prin care sa gaseasca, intr-o secventa de nnumere date, primele m numere (cele mai mici) si ultimele m (cele maimari), fara a ordona intreaga secventa. Toate operatiile se efectueaza inaceeasi secventa (sunt date m, n si numerele apartinand listei).

14. Descrieti in pseudocod un algoritm pentru a rezolva urmatoareaproblema: fiind date doua siruri (finite) de elemente, sa se testeze daca unuidintre ele este subir al celuilalt.

15. Scrieti in pseudocod un algoritm care sa gaseasca eel mai lungmime dintr-o lista data. Este posibil ca in lista sa fie mai multe nume cuproprietatea ca sunt cele mai lungi. In acest caz sa se listeze toate.

5. Dezvoltarea unui algoritmPentru a rezolva o problema cu calculatorul, descoperirea

algoritmului ce descrie o metoda de rezolvare a problemei constituie oprima etapa, a doua constand in reprezentarea algoritmului sub forma deprogram. In general, nu poate fi dat un algoritm care sa descrie procesul insine de rezolvare a unei probleme oarecare, existand probleme care nu admitsolutii algoritmice.

Matematicianul George Polya (1887-1985) a evidential principaleleetape care se parcurg in procesul de rezolvare a unei probleme, si anume:intelegerea problemei, conceperea unui plan de rezolvare, punerea acestuiain practica si evaluarea solutiei atat din punct de vedere al corectitudinii cat

i ca instrument potential in rezolvarea alter probleme. Metoda de rezolvarea unei probleme ca procedura algoritmica conduce la formulareaalgoritmului si la reprezentarea acestuia ca program, evaluat apoi din punctde vedere al corectitudinii $i utilizat in dezvoltarea altor programe.

In practica insa, ordinea etapelor nu este neaparat aceasta sj deasemenea pot interveni factor! subiectivi, cu rol important in rezolvarea unorprobleme, ce tin de momentul de inspiratie sau de talentul cu care esteinzestrata o anumita persoana in a ,,vedea" o solutie, fara a urma cairecomandate de experientele matematice anterioare.

In general, se pot pune in evidenta cateva metode generale deabordare a problemelor. O astfel de metoda este sa procedam invers: dacadorim sa punem in evidenta o metoda de obtine un anumit rezultat pornindde la anumite date, putem porni de la reziiltatul dorit, parcurgand procesul insens invers pana ajungem la datele corespunzatoare de intrare.

O alta metoda este aceea de a cauta o problema inrudita cu aceeacare trebuie rezolvata, mai ximpla, sau pentru care se cunoaste deja osolutie; se va incerca apoi rezolvarea problemei initiate in functie de aceasta,exploatandu-se analogiile.

O alta metoda este aceea a rafmarii pas cu pas; ea consta inimpartirea problemei in subprobleme, rezolvarea fiecareia fiind o etapa inrezolvarea problemei initiale. Subproblemele se descompun la randul lor insubprobleme mai simple de reprezentat, sj asa mai departe, pana ce seajunge la etapele ce constau din subprobleme simplu de rezolvat.

Aceasta metodologie descendenta (top-down), de la general laparticular, se deosebeste de cea ascendenta (bottom-up), de la particular lageneral; in practica ele sunt ambele folosite de eel ce rezolva o problemaoarecare.

Un avantaj al metodei rafinarii pas cu pas este structura modulara asolutiilor, simplificand gestionarea procesului de dezvoltare a programuluii fiind adecvate activitatii in etapa. Reprezinta rnodul de lucru eel maiutilizat in dezvoltarea unui produs software, aceasta metoda devenind unadin cele mai importante metode deprocesare in prelucrarea datelor.

In tu i t i a si inspiratia, talentul celui care cauta o solutie pentru oproblema data au un rol important in alegerea unei metode de rezolvarepentru acea problema. utili/.and in mod creativ metodele evidentiate indezvoltarea algoritmilor.

L

34 BA7.l-.LK INI-ORMA T1CI1 ('opilohil 1 - Algoritmi

6. Complexitatea problemelor i a algoritmilorUn algoritm este o procedura de calcul bine definita care primete o

anumitS valoare sau o multime de valori ca date de intrare i produce oanumita valoare sau multime de valori ca date de iesire sau, altfel spus, unsir de pasi care transforms datele de intrare in date de iesire. Un algoritmpoate fi privit ca un instrument de rezolvare a problemelor prin descriereaetapelor ce fac trecerea intre intrare i ie?ire. In practicS, .existenta unuialgoritm reprezintS doar punctul de plecare, deoarece o anumita problemapoate necesita un timp de rulare foarte mare pe cele mai performantecalculatoare cunoscute. Se pune astfel problema scrierii unui algoritmeficient pentru rezolvarea unei probleme si deci de a analiza un algoritm dinacest punct de vedere.

Pentru compararea algoritmilor de rezolvare a unei probleme date sepot folosi criterii axate tie pe caracteristicile structural ale algoritmilor fiepe resursele consumate in timpul executiei. In primul caz ne bazam peinformatii cu caracter static, independente de datele de intrare (lungimeaalgoritmului, numarul maxim de secvente repetitive sau de apelarirecursive). In al doilea caz, analiza complexitatii are un caracter dinamic,deoarece exprima costul executiei algoritmilor in functie de dimensiuneadatelor prelucrate.

Analiza unui algoritm inseamnS prevederea resurselor pe carealgoritmul le solicits, intelegand prin resurse memoria, latimea benzii decomunicatie. portile logice, timpul de executie necesar algoritmului fund deregula cea mai importanta dintre ele. Inainte de a analiza un algoritm,trebuie sa dispunem de un model al tehnologiei de impleinentare careurmeaza sa fie folosita, al resurselor acesteia si sa putem estima costurilecorespunzatoare. Analiza, chiar si a unui singur algoritm. poate 11 oincercare dificila. fiind necesare cuno$tinte de combinatorica, teoriaprobabilitatilor. experienta in calculul algebric si abilitate in a identifica ceimai important! termeni dintr-o expresie.

Putem presupune ca tehnologia de impleinentare este un model desistem de calcul generic cu un-procesor, cu memorie cu acces aleator (RAM)si ca algoritmii vor fi implementati ca programe pentru calculator. In acestmodel, instructiunile sunt executate una dupa alta, fara operatii concurente.

Comportarea unui algoritm poate depinde de datele de intrare, iar inprocesul de analiza a unui algoritm trebuie sa putem exprima aceastacomportare in formule simple, usor de inteles, simplu de scris si de utilizat,care sa puna in evidenta principalele resurse necesare unui algoritm si sasuprime detaliile superflue.

Importanta studiului eficientei algoritmilor a fost pusa in evidprin lucrarile lui A. Cobhain si J. Edwards (1964).

In general, timpul de executie necesar unui algoritm create o datdimensiunea datelor de intrare. De aceea trebuie sa definim cu mai ITprecizie notiunile de timp de executie si de dimcnshine a datelor de intrar

Pentru multe probleme, cea mai naturals masura este numaruobiecte de compun datele de intrare, pentru altc probleme, ca de exerinmultirea a doi Tntregi, masura poate fi numarul de bid necesari pereprezentarea datelor de intrare in notatie binara. Pentru fiecare probstudiata, trebuie precizeaza masura utilizata pentru dimensionarea datekintrare.

Timpul de executie al unui algoritm pentru un anumit set de datintrare este determinat de numarul de operatii elementare sau deexecutati. Este util sa definim notiunea de pas astfel incat acesta sa depcat mai putin de calculator.

Pentru executia unei linii de pseudocod este necesara o diconstants de timp. Vom presupune ca fiecare executie a liniei / con:timpul d. unde c\ este o constants (punct de vedere in conformitatmodelul RAM).

Exemplul 1. Algoritmul de sortare prin insertie Vom da un exede analiza a acestui algoritm reprezentat in pseudocod. Pentru fifinstructiune se considers costul de timp si un numar care reprezintS deori aceasta este efectiv executata. Pentru fiecare / = 2, 3,..., n, undelungime[S], vom nota cu / / numarul de executii ale testului atdt timppentru valoarea fixatS /.

Sortare-prin-insertie (S): timp1: pentru/ < - 2, lungime[.Sr] executa n2: cheie S(j] n-\3: {Insereaza S\j] in sirul sortat S[ 1. . / -1 ]] n-14 :/0 si S[/]>cheie executa

7 : / < - / - I

z; ,',

Timpul de executie al algoritmului este suma tuturor timpikexecutie corespunzatori fiecarei instructiuni executate. O instructiuneconsuma timpul c, pentru executie, daca este executata de n ori va concu c, n la timpul total de executie. Nu acelasi lucru se intampla atunci

!6 HA/.l-.l.l: IN1-ORMATK'II

instructiunea se refera la alte resurse (daca se refera, de exemplu la meuvinte din memorie si este executata de n ori, nu consuma in general mncuvinte de memorie).

Calculam Tn . timpul de executie pentru sortare-prin-insertie, astfel:

- - ]Timpul de executie necesar procedurii Sortatre-prin-insertie depinde

de datele de intrare, atat de marimea datelor cat si de ordinea in care suntdate. Cazul eel mai favorabil este atunci cand vectorul de intrare este dejasortat. Sa presupunem ca procedura ordoneaza datele in ordine crescatoare.Pentru fiecare j = 2,3,..., n gasim S\i]

38 RAZE1.E1NFORMAT1CU

Definitii.1. Pentru o functie data g(n), si no.astfel meat 0< ctg(n) < f(n) < c2g(n) pent \?n > n0}.

2. Spunem ca o functie f(n) apartine multimii Q(g(n)), daca existaconstantele pozitive c, si c? astfel Tncat, pentru n suficient de mare, sa fieindeplinita conditia din definitia lui (g(n)).

Desi (g(n)) este o multime, putem nota prin ,f(n) = @(g(n))" faptulcaf(n) apartine acesteia.

A

n,,fig. 15

Figura 15 ofera o imagine intuitiva a functiilor f(n) si g(n), in cazulin care f(n) = @(g(n)). Pentru toate valorile lui n aflate la dreapta lui n0,valoarea \uif(n) este mai mare sau egala cu csg(n) si mai mica sau egala cuC2g(n). Spunem cag(n) este o margine asimptotic tare pentru f(n).

Spunem ca un algoritm ruleaza in limp poiinomial daca exista doiintregi fixati a si k. astfel incat atunci cand datelc de intrare au lungimea n,calculul sa fie efectuat in eel mult an* pasi. pentru orice valoare a lui n. Cualte cuvinte, ordinul de creslere pentru un astfel de algoritm este de tipul(-)( ). Aceste probleme sunt in general privite ca accesihile. Putem lua inconsiderare urmatoarele fapte ce sprijina aceasta afirmatie:

1) O problema cu ordinul de complcxitatc Q(nk), pentru k foartemare, poate fi considerata ca fund inaccesihila. desi in practica rareori aparprobleme cu algoritmi ce depind de o functie polinomiala de un grad atat demare.

2) Daca o problema poate fi rezolvata in timp poiinomial utilizandun anumit model de calcul, dc regula, aceasta va putea fi rezolvata in timppoiinomial folosind orice alt model de calcul (de exemplu, clasaproblemelor rezolvabile in timp poiinomial cu ajutorul masinilor seriale cu

Capitol ul 1 -Algoritmi

acces direct coincide cu clasa problemelor rezolvabile in timp polinomiajutorul masinilor virtuale Turing).

Clasa problemelor rezolvabile in timp poiinomial are cproprietati de inchidere interesante, deoarece polinoamele sunt inpentru operatiile de adunare, inmultire si compunere (daca iesireaalgoritm poiinomial este considerata intrare pentru un alt algpoiinomial, algoritmul rezultat va fi unul poiinomial). De asemenea, daalgoritm poiinomial apeleaza de un numar constant de ori sub,polinomiale, atunci, algoritmul rezultat este poiinomial.

Spunem ca un algoritm ruleaza in timp exponential daca ace;ruleaza in timp poiinomial. Pot fi necesari 2", 3", n", sau n! pasi peprelucra date de intrare de lungime n. Pot aparea functii ca n "K ", c;sunt in mod obisnuit privite ca functii exponentiate; algoritmii exporau ordinul de crestere de tipul (2"), G(3"), &(n") &(n!) etc.

Algoritmii care ruleaza in timp poiinomial sunt mai eficientiordinul de crestere mai mic decat cei care ruleaza in timp exponent!;ilustrat prin tabelul din figura 16.

1 inul i . i decomplcxitatc

e

10

In ca/,ul problemelor in t imp polinomial, cresterea dimensiunilorproblemei nu diminueaza drastic posibilitatea rezolvarii intr-un timpacceptabil, ca in cazul problemelor rezolvabiJe in timp exponential.

Nu toate problemele pot fi rezolvatc in timp polinomial. Existaprobleme care nu pot fi re/.olvate de nici un calculator, indifcrent de timpulacordat pentru gasirea unci solutii

Numim o problema accesibila, daca ea este rezolvabila in timppolinomial si inaccesibila daca ordinul sau de complexitate depinde de ofunctie care nu este polinomiala. Problemele de acest tip formeaza o clasainteresanta de probleme, asa-numitele probleme NP-complcte. Pana inprezent, nu s-a descoperit un algoritm polinomial pentru rezolvarea uneiastfel de probleme, dar nu s-a demonstrat ca exista o limita inferioara pentrutimpul (necesar rezolvarii acesteia) ce nu poate fi exprimat polinomial.Problema P ^ N P reprezinta, inca de la formularea in 1971, unul dintre celemai interesante subiecte deschise in algoritmica teoretica.Se afirma ca problemele NP-complete sunt inaccesibilc. Daca s-ar gasi orezolvare polinomiala pentru o problema NP-completa, atunci poate fi gasitun algoritm polinomial pentru rezolvarea oricarei alte probleme din aceastaclasa. Pentru a demonstra ca o problema este NP-completa, trebuie doveditainaccesibilitatea sa. Un mare numar de probleme interesante, care la primavedere nu par mai dificile decat o sortare, sunt de fapt NP-complete.Ca o ilustrare a modului in care notiunile de mai sus sunt folosite inclasificarea problemelor si algoritmilor reali, vom analiza o problemaimportanta din domeniul comercial si economic.

Exemplul 2. Problema comis-voiajorului. Sa presupunem ca uncomis-voiajor trebuie sa viziteze mai multe adrcse diferite. Cum trebuie saprocedeze astfel incut sa ajunga la toate adresele, parcurgdnd un drum catmai scurt?

Fiind cunoscute distantele dintre orice doua adrese care trebuievizitate, si implicit costurile distantelor respective, care este drumuJeconomic pentru vizitarea tu turor adreselor?

O abordare simpla a acestei probleme consta in determinarea tuturordrumurilor posibile, calcularea distantei totale pentru fiecare si alegereadrumului core.spunx.ator celui mai mic cost. Se obtine cu siguranta solutia,ceea ce arata ca problema poate fi rezolvata printr-un algoritm, deoareceprocedura indicata poate fi, in principiu. usor programata pe un calculator.Insa chiar pentru un numar redus de adrese, numarul drumurilor posibiledevine prea mare. Pentru n adrese, exista n! itinerarii posibile. Cum functian! creste mai repede dccat 2"sau3", pentru a detennina toate drumurile

Algorilmi 1 1

posibile este necesar un algoritm in t imp exponential. Pentru dear 10 adreseexista 10! 3 628 800 drumuri posibile.

Ce altceva am putcm incerca? Putcm imagina diferite strategii, carepot functiona bine in anumitc situatii particulare, dar care nu ofera o solutiegenerala a algoritmului. Mai mult de 300 de lucrari publicate de la enuntareaei, in 1930, de catre matematicianul vienez Karl Menger, problema comis-voiajorului a rezistat tuturor incercarilor de a se gasi o solutie generala.Faptele matematice de pana acum sugereaza mai degraba inexistenta unuialgoritm eficient pentru a o rezolva.

In practica, problemele care implica drumuri intre orage, pot firezolvate, in timp ce situatiile artificiale imaginate pot fi de o maredificultate. Fara sa intram in detain, putem preciza ca pentru anumite cazuriparticulare s-au construit solutii ale problemei comis-voiajorului, utilizandin implementare o serie de strategii pentru cresterea perfbrmanteialgoritmului (micsorarea a timpului de executie), si rezultate matematicecare simplifies algoritmul. Utilizand metode de programare clasice (metodabacktraking i metoda greedy) se construiesc algoritmi de rezolvare (decomplexitate &(n!)), comparabili intre ei. Principiul de rezolvare ramane inmare acela^i, pentru cazul eel mai defavorabil, si in cazul unui numar foartemare de adrese, ele functioneaza asemanator, complexitatea fiind aceeai.Utilizand metoda progrumarii dinamice se obtine o complexitate &(2"), deasemenea exponentiala. numai ca, pentru un numar mai mare de date deintrare, acest algoritm furnizeaza rezultatele incomparabil mai rapid dccatalgoritmii precedent!, cresterea complexitatii fiind mai lenta.

Se poate intampla ca in teorie un algoritm sa ruleze in timpexponential si sa fie considerat inelicient, dar in practica, aplicat unor datereale, sa fie chiar performant. 1 impul exponential apare in cazul acestanumai pentru anumite t ipur i de date cu care, de regula, nu ne intalnim.Problema comis-voiajorului se incadreaza in aceasta categoric, metodeleexistente de rezolvare comportandu-se bine pentru datele reale.

Pentru a analiza eficienta unui algoritm relativ la costul de executienu existi niste formule generale, intui t ia si experienta jucand un rol la fel deimportant ca si rationamentul. De exemplu. in algoritmul de calcul al valoriinumerice unui polinom intr-un punct se obtin timpi diferiti pentru douapolinoame de acelasi grad, daca primul are aproape toti coeficientii egali cu0 iar al doilea polinom nu are nici un coeficient nul. Aceasta abordare aproblemei poate fi utila in evidentierea complexitatii intrinsece a uneiprobleme. In alte cazuri este util sa studiem comportamentul algoritmului incazul mediu. Acest lucru poate fi realizat calculand costul algoritmuluipentru diferite configuratii ale valorilor de intrare, si determinand succesiv

42 KA7.El.T-. 1N1-ORMA1!('//

costul executiei diferitelor instructiuni ale programului, corespunzatorconfiguratiilor de intrare.

in analiza unui algoritm este important studiul comportamentulfunctiei care descrie costul de executie al algoritmului respectiv, odata cucresterea dimensiunii intrarilor.Este evident ca in cazuri particulare este posibila o analiza mai fina in caresa apara si constantele care determina cu precizie dimensiunea maxima aproblemei astfel incat aceasta sa fie acceptabila pe o masina data, fiindlimitata de memoria acestei masjni 5! de timp.

Pentru a descrie comportamentul asimptotic al functiilor, vom definii alte notiuni importante in studiul analizei unui algoritm.

iDefinitii

1. f(n)-O(g(n')) daca exista doua constante pozitive c si no, astfel incat|/()( < c|g(n)| pcntru Vn > 0 (/creste eel mult atat cat creste g );2. /() - Q(g(tt)) daca exista doua constante pozitive c si no astfel incat|/(/i)| ^ cjg()| pcntru Vn > ng (/'creste eel putin atat cat creste g);3. /() = o(g(n)) daca lim 1-^ = 0 (/'creste mai incet decat g);

n M g(W)

4. /() g(n) daca lim 1 (/'si g sunt egale, mai putin termenii de" * g(n)

ordin inferior).

Notatiile O(g(n}\ Q(g()), 0(g()) desemneaza clase de functii.Observatie. In aceste notatii, /()= 0(g()) daca exista trei

constante pozitivc c/, o. o, astfel incatg(n)\ 5 n) pentru Vn > nn (/'si g cresc la fel ).) 5 /(") -

I44 BAZELE1WORMA '11C 11 ( ' ti/iilolii! I - Algorilmi I S

3) Problema de ordonare a unui vector arecomplexitatea Q(n log n).

5. Demonstrati ca f(n) = 0fe ()) O

6. Fie dat un polinom J'(x) de gradul n. Demonstrati ca P(x) = &(x").7. Aratati ca problema de ordonare a unui vector are complexitatca

Q(n log n).8. Pentru un polinom P(x) de gradul n aratati ca P(x) = o(xntl) si

P(x)*anx".9. Estimati complexitatea algoritmului de inmultire a doua matrici

de dimensiune n x n .10. Demonstrati ca relatia "eO" este Iranzitiva: daca/e 6>(g) si g

e (/;). Deduced de aici ca daca g e. O(h), atunci0(g) c 0(/0.

11. Fie/, g : N - R* . Demonstrati ca:a. /) 0(/) = 0(g) 0/6 000 si g e 0(/)

/O 0(/) c 7. Structuri iterative. Structuri recursiveIn aceasta sectiune vom ilustra atat .slruclurile iterative cat si

structurilf recursive prin cateva exemple de algoritmi pentru a pune inevidenta in fiecare caz cateva caracteristici ale acestor Structuri.

Strvcturile iterative sunt Structuri in care anumite secvente deinstructiuni se repeta ciclic. Toti algoritmii prezentati pana acum in acestcapitol sunt exemple de algoritmi iterativi.

Exciiiphil 1. Algoritmul ile cautare secvenfiala. Fste un algoritmprin care se delermina daca o valoare data apartine sau nu unei lisle dateinitial. Presupunem ca elementele unei lisle numerice sunt ordonatecrescator. Elementele pot fi secvente dc caractere ordonate lexicografic,nume ordonate alfabetic sau valori numerice ordonate cu relatia de ordinenaturala. Daca ,,valoarea'' data initial va ti gasita in lista, cautarea este cusucces, altfel conduce la esec. Algoritmul poate ti reprczentat astfel:

I) Pasul l :ci teste, / [1J , . . / | / / ] ;Pasul 2: / := /;Pasul 3: element := /[/'] ;Pasul 4: cat timp [(valoare > element) fi (i < n )]

executa [/ := ; + /; mergi la Pasul 3 ];Pasul 5: daca [valoare = element] atunci [scrie ('succes'' )]

altfel [scrie ('eyef')] ;unde s-a pornit de la premisa ca exista eel putin un element in lista, iar listaeste structurata ca vector. Algoritmul prezentat in continuare, in pseudocod,prevede si situatia cand lista este vida, iar elementele sunt consideratearticole ale unei liste, algoritmul fund mai general.

II) procedure cautare_s (lista, valoare)if [lista e vida] then [scrie(' esec')]

else [selecteaza un articol din lista si anumeelement]

while [ valoare Oelement si mai sunt articole in lista neluate inconsiderare]do [selecteaza urmatorul articol al listei, si anume element, ceurmeaza a fi testat]if [valoare = element] then [scrie'succes']

else [ scrie 'esec' ]Util izarea unei St ructur i ciclice while- do sau repeat - until otera un

grad mai mare de flexibilitate. Corpul ciclului (secventa de instructiuni) ceurmeaza a li executat cat limp o conditie este satisfacuta, respectiv pdnacand o conditie va fi indeplinita, este introdus in program o singura data.Testarea conditiei este necesara pentru a incheia structure ciclica. Datele ceintervin in corpul ciclului an anumite valori, date inaintea instructiunii deciclare; acestea se modifica in corpul ciclului si astfel, la un moment dat, inurma verificarii conditiei, proccsul de ciclare ia sfarit.

Structurile recursive realizeaza procesele repetitive fara utilizareaciclurilor, ca in ca/.iil structurilor iterative. Pentm multe probleme solutiarccursiva este mai naturala decat alternativa ei iterativa. Chiar si pentru ceinefamiliarizati cu recursivitatea, unele exemple pot parea mai usor de inteles

ISA//:/,/. INI''ORMATJCJJ46

si se remarca legatura dintre ele. Sc pot pune in evidenta o serie de avantajeale utilizarii recursivitatii.

Procedurile recursive sunt relativ usor de analizat si pentru a ledetermina performanta. Analiza acestora conduce la relatii de recurenta,dintre care multe pot fi usor re/.olvate, demonstratia prin inductie fund desutilizata. Procedurile recursive sunt ilexibile, in sensul ca este relativ usor sase transforme o procedura generala intr-una specifica. Aceasta este de multeori o tehnica de proiectare utila: tnai intai se scrie un program pentru oproblema care reprezinta o generalizare a problemei reale date si apoi seadapteaza acestei probleme concrete.

Exista totusi si unele dezavantaje ale recursivitatii. Procedurilerecursive pot sa ruleze mai incet decat echivalentele lor nerecursive. Uncompilalor poate implennenta deficitar apelarile recursive (aproape toatecompilatoarele Pascal gestioneaza recursivitatea bine iar costul este ingeneral mic, eel mult 5% - 10%). Procedurile recursive necesita mai multspatiu decat echivalentele nerecursive. (Fiecare apelare recursiva implicacrearea unei inregistrari de activare iar, daca adancimea recursiei este mare,acest spatiu poate sa se mareasca considerabil. La procedurile maicomplexe, insa adancimea este mai mica). Neajunsurile legate de timp sispatiu pot fi eliminate uneori destul de simplu de catre un compilatorperformant.

Recursivitatea poate fi liniara, cand procedura contine o singuraapelare recursiva, recursie binara, cand se fac doua apeluri recursive, sirecursie n-ara. cand in procedura exista un numar nedefinit de apelurirecursive .

Exemplul 2. Algoritmul de caviare binara. Acest algoritm recursivconsta in fixarea unei pozitii curcnte, a primului articol din cea de a douajumatate a listei (punandu-se in evidenta asttel doua parti ale listei), si in adetermina daca articolul specificat este in prima pane sau in cea de a doua alistei, apoi a continua cautarea, in acelasi mod, in xnhlisia elementelor ailateinainte de (sau dupa) elemcntul situat la mijlocul sublistei in care se atlaarticolul.Aplicand asupra unei zone din ce in ce mai restranse de cautareaceeasi tehnica, in cele din urma procesul se sfarseste tie gasind articolul inlista, cautarea fiind incheiata cu succes. fie negasindu-1, cautarea tiindsoldata in acest caz cu csec. Impartirea listei de tiecare data in doua lisle maimici este motivul pentru care acest algoritm se numeste de cautare binara.

Algoritmul, in pseudocod se poate scrie astfel:procedure caulare h | lista, valoare]if [lista c vicla | (lu-n |scrie 'e^ec']

I - Algorilini

else (Sclecteaza mijlocul listei si atribuie acarticol lui element ];

if [valoare < elem] then[apeleaza procedura cautare b];if [cautarea are succes] then [scrie" succes']

else [scrie'esec']else if [valoare > elem] then[apeleaza procedura cautare b in a doua juma

a listei];if [cautarea are succes] then [scrie'succes']

else [scrie 'eecv]Spre deosebire de algoritmul de cautare secventiala, in algoritmi

cautare binara, fiecare pas al repetarii reprezinta o activitate subordcpasului anterior. Aceasta tehnica, recursivitatea, da si dcnuialgoritmului ce o utilizeaza. Este ca i cum in executia unui astfalgoritm ar exista mai multe copii ale algoritmului, ce se mai num!, 'pe',/>2);[apeleaza procedura h(k-\,pi,p2,pi)]',[apeleaza procedura h(n, 1, 2, 3)];

Am notat cu pi, p2 si respectiv p3 atat discurile cat si tijele (Deexemplu, ,,muta pi pe p2" inseamna ,,muta discul pi pe tija/^2").

Analiza algoritmului de rezolvare a acestei probleme din punct devedere al complexitatii sc poate face astfel:

Fie Tk este numarul operatiilor necesare pentru rezolvarea uneiprobleme de marime k. Cazul definit in mod explicit apare atunci cand

\b + 2Tk , k + \k-l . Astfel are loc relatia: 1\ - \ unde a reprezinta un test[a k -- 1

(k-l) si operatiile implicate in scriere, iar b reprezinta un test ( & = 1),operatiile implicate in scriere si doua proceduri de apelare. fiecare din eleimplicand, la fel ca apelarea in sine, o scadere (k-l) si alocarea a patruparametri.

Rezolvam relatia de recurenta prin substitute:Tn = b -i 27;, , - b + 2(b \ Tr .2) ^ b + 2h -i 22 Tn 7 --- b f 2b + 2! (b + Tn_,)= (l i 2 f 2 2 ) > - i 23 f Tn v... = (l + 2 t - 2 2 +. . . I 2" 2)-> + 2" ' 7 j^ ( l + 2 i - 2 2 - i . . .+ 2" ']b ^ 2" }a -2" '(a-\-h}-b

Vom folosi aceasta formula pentru a numara operatiile elementare.Pentru a avem 1 f M operatii, unde M este numarul de operatii implicate inscriere; pentru b avem o operatic (pentru test) + M (pentru scriere) + 10(pentru doua apelari) -f 2 (pentru doua scaderi) + 8 (pentru parametri),rezultand un total de 21 + M operatii. Astfel:

50 HA7J-:U' INl-'ORMATK 7J ('apitohil I - Algorilmi

/; :- - 2 " ' ( l

Sunt exact 2"-/ mutari astfel Incat costurilc suplimentare aleprocedurii de inai sus sunt de aproximativ 1 1 operatii elementare permiscare.

b) varianta recursivd a rezolvarii problemei:procedure hanoi2 (n : natural);

[p\ , p2, p3 pot lua valorile 1 , 2 sau 3]procedure h (k : natural; p\ , p2, p3 );

if k = 0 then {nimic}else [apeleaza procedura h(k-],pl,p3,p2)]',

[scrie ('muta ',/>!, 'pe',^2);[apeleaza procedura h(k-\,p3,p2,p\J\',[apeleaza procedura h(n, 1, 2, 3)];

Utilizand notatii analoage (T^,a',b')ce\or introduse in analizaalgoritrnului procedure hanoll, se obtine urmatoarea relatia de recurenta:

\b' + 2T! . k*Q\[a k = 0

comparatie cu cea originate: 7"n -2'"l(a + b)-b.In termenii operatiilor elementare, a' este pur si simplu 1 iar A' este la fel

ca b, adica 21 + M Facand substitutia obtinem: T'n = 2"(22 + A/)- 21 - Min comparatie cu: Tn = 2"(l 1 + A/)-21 -M. Pe masura ce costul lui Mtinde catre 0, raportul T'n/Tn tinde catre 2 si pe masura ce M tinde spre oo,raportul tinde catre 1 .

Observam ca alegerea punctului in care se opreste recursia poateafecta semnificativ performanta, sprc deosebire de recursia liniara, undediferentele sunt in general neglijabile.

T'k= carei solutie este: T' ^2"(a' + b')-b' in

Exercitii

1. Cate comparatii, in medic, sunt necesare pentru cautareasccventiala si respectiv, pentru cautarea binara a unui element intr-o lista delO.OOOdearticole?

2. Scrieti o versiune recursiva a algoritrnului lui Euclid.3. Scrieti in pseudocod un algoritm recursiv care sa ordoneze o

lista de n numere folosind un algoritm de ordonare a unei liste de n-\numere.

4. Desenati schemele logice pentru urmatoarele secventc depseudocod :

if a = 3 then if ft < 2 then c : = 7;s: = 0 ; n : = 10;while .v < n do s : = K i- 2;x : = a; y : = b\repeat x : = x + 1; y : = y - 1 until x > y.

5. Ce diferente sunt intre rezultatele obtinute in urma apelariiurmatoarelor doua proceduri, pentru / = 1:

a) procedure alfa (/)if i 5 then scrie (/) ;alfa ( / + ! ) ;

b) procedure beta (i)lfi5 then beta (i + 1);scrie (/).

6. Scrieti procedurile corespunzatoare schemelor din figura 15(arespectiv 15(b), utilizand structurile repetitive while - do si repeat - until.

(b)

(a)

7. Urmatoarea procedura descrie un algoritm recursiv. Specific;ce realizeaza aceasta procedura.

procedure l\(n, i, j)i f / ; > 0 then [apeleaza procedura \\(n~\, i, 6 - / ' / ) ] :

[scrie (/ "->"; );[apeleaza procedura H(-1, 6-1-7,7)];

52 .I-; INFORM A IK'//

8. Eficienta i corectitudinea algoritmilorExigenta definirii algoritmilor pentru calculul functiilor sau, in

genera), pentru rezolvarea problemelor din domenii matematice ce s-audezvoltat in timp, a pus in evidenta proprietatile structurilor geomctrice,algcbrice, topologice, proprietati ce formuleazn cu precizie problemele datesi pot conduce spre solutionarea acestora,

A trecut mult timp fara sa poata fi definit exact conceptul deconstructie a solutiei unei probleme. Incepand cu secolul XX, prin operaunor matematicieni ca David Hilbert, Kurt Godel, Kleene, Alan Turing etc.,algoritmii sj regulile formale pentru definirea acestora au inceput sa fieprivite ca obiecte importante de studiu prin utilizarea teoriei logice si asistemclor formale. Asa s-a ajuns la definirea conceptului de recursivitate inanii '30, la caracterizarea claselor de runctii calculable si la evidentiereaunor probleme care nu sunt rezolvabile in mod algoritmic. Aparitiacalculatoarelor electronice a contribuit la relansarea teoriei calculabilitatii,furnizand noi motivatii si modele de calcul legate de calculatoare reale si delimbajele de programare, detenninand pe de alta parte o serie de cercetariasupra timpului i spatiului necesare unei masini pentru a efectua un anumitcalcul.

Dupa 1960, conceptul de complexitate a calculului a inceput sa fieinteles mai pro fund. Pe de-o parte, teoria complexitati relative a furnizat odcfinitie ceva mai precisa a conceptelor: pasi de calcul, resurse necesarepentru executia unui program, clase dc functii calculabile intre anumitelimite ale resurselor. Multe dintre rezultatele anterioare se refereau lamodele particulare de masini si de limbaje de programare. Teoriacomplexitatii concrete s-a bazat pe caracterizarea complexitatii problemelorparticulare, de interes practic, probleme de structuri algebrice, de multimiordonate, de grafuri etc., si a dat nastere unor tehnici algoritmice pentrugasirea unor solup'i mai eficiente pentru problemele respective.

In cadrnl acestor studii a aparut necesitatea de a identifica in modclar clasele de probleme rezolvabile eficient prin intermediul calculatoarelor(adica probleme cu un cost ce creste in mod ,,rezonabil" odata cu cretereadimensiuniJor problemei respective). Aceste probleme au tost definite caprobleme acceptabile, iar conceptul de acccplabilitate a inceput sareprezinte un al doilea nivel al construirii solutiei unei probleme. Din punctde vedere practic, daca o problema este algoritmic rezolvabila, are mareimportanta ca solutia sa poate fi obtinuta in mod eficient.

1 - Algoritmi 53

Se poate constata, din analiza comparativa a doua metode derezolvare a unei probleme. ca numurul dc operatii necesare rezolvariiproblemei difera. De exemplu, considcrand algoritmii de cautare secventialai de cautare binara prezentati anterior, al doilea este mai avantajos, iarmodul de organizare al datelor avand de asemenea un rol important. Incadrul teoriei complexitatii sunt studiate tehnici de masurare a cficienteiprogramelor.

Verificarea programelor si cautarea unor tehnici eficiente deverificare constituie un domeniu important de cercetare, utilizarea metodelorlogicii formale pentru demonstrarea corectitudinii programelor fiind unadintre directiile de abordare a acestei probleme.

Pentru demonstrarea corectitudinii unui program, prcsupunem ca lainceputul executiei sunt indeplinite un anumit numar de preconditii. Seevalueaza apoi efectul propagarii in program a consecintelor acestorpreconditii in urma executiei unor instructiuni. Astfel, in anumite puncte aleprogramului se identifica unele asertiuni obtinute pornind de la preconditiileprogramului si in urmand secvente de instructiuni pana in punctul respectiv.Daca asertiunea rezultata in acest fel in punctul final al programuluicorespunde cu rezultatul de iesire din spccificutie, spunem ca programul estecorect.

Tehnicile formale de verificare a programelor nu pot fi aplicateasupra sistemelor generale de prelucrare a datelor. Verificarea programelornumai pe anumite date de testare demonstreaza doar faptul ca programulfunctioneaza corect pentru aceste date si erorile programului pot sa nu fiedescoperite.

CAPITOLUL 2

BAZELE ALGEBRICE ALEINFORMATION

1. Morfismel.l.; Definitie. Fie b: X x X >X o operatic binara pe

b': X'xX' >X' o operatie binara pe X\ wide X i X' sunt doua noarecare. Consideram structurile (X,b} si (X',ti\ Numim morfisrr,(X,b) la (X',b'), o f\mctie/:(A',5) >(X',h') cu urm;proprietate: f(xby) = f(x}b'f(y), Vx, v c X . Am notat prin xfty coelementelor x i y din A' prin operatia binara /). Alttel spus,/este un rdaca i numai daca diagrama urmatoare este comutativa:

A"xA"b'

ceea ce inseamna ca f ob = 6'o( f x /): A' x A' -ilej

undc (/x /)(.r,y) - (/(x), /(v))e A"'x.Y' pentru orice x,ye X .Pentru orice operatie binara b pe o multime A', aplicatia

1 x definita pe X este un morfism in sensul de

\x:(X,b)--+(Xtb).

56 HA '/.ELI: INI- RMA y icnr'u'c (A',/V) si :(A",/V) ------- >(X",b") sunt douamorfisme, atunci compunerea g of este de asemenea un morfisrn.

1.2. Excmple de morfisme.Logaritmul : (R ' , j ------- >(.R,+ ) , pentru o baza oarecare.Fie M o multime finita si A o familie de submultimi ale lu i M.

disjuncte doua cate doua. Functia cardinal (#), care atribuie fiecareisubmultimi X a lui A numarul elementelor submultimii X, satisfaceproprietatile care probeaza ca este morfism fata de trei perechi diferite deoperatii binare corespunzatoare: reuniunea a doua submultimi din A siaciunarea numerelor reale, produsul cartezian a doua submultimi din A sivnmultirea numerelor naturale, si respectiv fata de operatia de exponentierepentru multimi: Xr = { f \ f : Y ---- >X\.

(Y); H(XxY)=#(x)-#(Y);

Cand ambele operatii sunt de aciunare (inmultire), morfismul senumeste aditiv (multiplicativ).

1.3. Definitie. Fie X si X' doua multimi pe care sunt definiteoperatiile unare u, respectiv ;/'. Morfismul f:(X,u) >(X',n') deoperatii unare este o functie / : X ---- > X' cu proprietatea ca faceurmatoarca diagrama comutativa

ceea ce inseamna ca (/ o; /XT) ' ("'./X-x) pen^ni orice x & X .Daca i:X" ~ X ~ x . X x . X - > X este o operatic tcrnura pe X si

1': X'} - > A" este o operatic ternara pe X\ un moriism de operatii ternareeste o functie f:X- ->A'' ce satisface (fot^(xty,z)=^of^\x,y,z)V.T, y, z e X sau / ot ~-1 'of' : X' > X .

A.

Putem deiini analog un morfism de operatii /v-aref : ( X , u ) ~>(A' ' .M') ca liind o functie f : X - > A" cu proprietalea ca

diagrama urmatoare este comutativa:

A"'Fig. 3

sau altfel, (/ov)(x1,...,xn)= (\!'of"\x,,...,xn), pentru orice (*,,.,.,*) X".Prin definitie, un morfism f : ( X , z ) >(X',z'} de operatii zero-

are, unde z:\ >X, z':l >A" este o flmctie f: X- >A", cuproprietatea / oz = z' sau altfel spus, /(z(l)) = z'(l),

1.4. Definitie. Un morfisrn /:(A',a) >(A",a') este numitmonomorfism daca el ca functie este injectie; este epimorfism daca el cafunctie este surjectie; este izomorfism daca el ca functie este bijectie. Unmoriism / :(X,a) - >(A',a) se numeste endomorjism; daca functia/estebijectie, atunci morfismul f:(X,a) >(A',a) se numeste autornorfistn.Un morfism se mai numeste si homomorftsn.

1.5. Propozitie, Inversnl unui izomorfism este un izomorfism.&~ Demonstrate. Vom face demonstratia considerand ca morfismul

este de operatii binare. Daca bijectia / : X -> A" este un morfism. atuncivom demonstra ca si / :X' - >X este un morfism. Pentru aceasta. \atrebui sa aratam ca

/ ' ( .vet ' /)--/ '(.vh/' ' (?) pentru orice s j f A", unde a,a' sum operatiibinare pe A', respectiv pe A". Aplicandu-1 pe /' egalitatii de mai sus (/ fundbijectie), este suficient sa araiain ca sa't = f\f '(.v)a/ '(')j.

Cum /'este inortism, rnembrul drept din \iltima relatie este egal cu

./(./ '(^/-'(/^ (/o/

-~"

58 HA'/.El.E INI'ORMAIK"//

1.6. Definitie. Doua multimi X si A" pe care sunt date operatiilebinare a, respectiv a1 sunt numite izomorjc, daca exista un izomorfism/ : ( X , a ) -> (A",a'). In acest caz, notam X - X'.

Functia identica 1^ este intotdeauna un astfel de izomorfism.Nu este intotdeauna suficient sa stim ca doua obiecte sunt izomorfe,

ci trebuie specificat si care este izomorfismul.

Exercitii1. Enumerati endomorfismele aditive ale lui /.(, .2. Enumerati izomorfismele (Z.4,+) >(Q,o), unde Q este

multimea rotatiilor patratului, iar o este operatia de compunere.3. Fie f : ( X , a . ) >(A",a') si g:(A",a') >(A"',a") doua

morfisme. Aratati ca:i) daca g si / sunt monomorfisme, atunci g of este

monomorfism;ii)iii)iv)v)

daca g si/sunt epimorfisme, atunci g of este epimorfism;daca ^si g sunt izomorfisme, atunci g o / este izomorfism;daca go/ este monomorfism, atunci/este monomorfism;daca g of este epimorfism, atunci g este epimorfism.

4. Aratati ca relatia de izomorfism defmita Tntre doua multimioarecare X si X\ inzestrate cu operatiile binare a respectiv a', este o relatiede echivalenta.

2. Relatii de ordine partialaPornind de la multimi si relatii de incluziune intre acestea. se pot

defini relatia de ordine />cirtiala si notiunea de iat/ce in care intervin operatiianaloage intersectiei si reuniunii. Vom descrie aceste concepte si vomobserva ca notiunea de morfism apare in mod natural si pentru ele.

2.1. Definitie. O relatie binara pe o multime X, pe care o vom nota,,

60

2.5. Definitii.i) O multime partial ordonata X se numeste lanl sau multime siniplu

sau total ordonata, daca oricc doua cleincnte x s.i y ale sale suntcomparabile.

ii) Doua elemente x si y din X sunt numite comparabile, daca x < ysau >' < x .

2.6. Definitie. O multime partial ordonata cu un numar mic doelemente se poate reprezenta cu ajutorul diagramelor de incluziune, in careclementele comparabile sunt unite printr-o succesiune de segmente dedreapta ce leaga pe rand cate doua elemente dintre care eel mai mare Jl,,acopera" pe eel mai mic, de fiecare data eel mai mare dintre ele fund plasatdeasupra, Pentru a descrie o multime partial ordonata cu ajutoruldiagramelor de incluziune, se utilizeaza astfcl o relutie dc acoperirc sau deimediat superior, in sensul relatiei de ordine, definita in continuare:

Spunem ca a acopera pe b, Tntr-o multime partial ordonata finita P,daca b < a si mi exista z e P cu proprietatea ca b < z < a.

Putem reprezenta elementele din P prin puncte sau cerculete sipiasarn deasupra unui element x e P un element yi. /', unindu-lc printr-unsegment dc dreapta, atunci cand y il acopcrii pe x. "_v acopera pe ,v" se mainoteaza prin "y $ x".

Astfel orice doua elemente comparabile vor fi legate printr-o liniefranta.

Orice multime partial ordonata f in i ta /' este definita, in afara unuiizomorfism, printr-o astfel de diagrama corespunzatoare lui P.

Diagrama dualei unei multimi partial ordonate finite P se obtine.evident, prin rastumarea diagramei lui P.

]02.7. Kxemple. .^1) In figura 4 este data diagrama

mult imi i partial ordonate {2,5,8,10,25) prin ') 5\:b.c\ relatia de divizibilitate. l''K-4

2) In figura 5 este data diagrama mult imii

63

2 13. Dcfinitic. Fie (X,nk ,, altielare un element maximal.

2.17. Propozilie. Pentru un lant L dinlr-o multime partial ordonataX , notiunile de element minimal $i eel mai mic coineid. Analog pentruelemenlul maximal .>/ eel mai mare element.

^ Demonstrate. Vom utiliza definitiile notiunilor de prim element,respectiv clement minimal si lant, intr-o multime partial ordonata. Fie m anelement minimal in /,. Daca nu exista nici un element x e L eu proprictateaca x < m. atunci, prin definitia lantului, rezulta ca m

ff>4 HA7.E1J-: 1NFORMA TK '11 (\ipitolul 2 - /iazclc ricc ale informaticii

Exercitii1. Sa se reprezinte diagrama urmatoarelor multimi partial ordonate:

a) multimea divi/.orilor numarului 40. cu relatia de ordineindusa de relatia de divizibilitate de pe N.b) multimea partilor unei multimi cu 3 elemente.

2. Pe multimea N x N definim relatia a astfel: (m,n)a(m',n') dacasi numai daca m< m' si n < n' in N.

a) Sa se arate ca relatia a este o relatie de ordine partiala peN x N .

b) Sa se arate ca in multimea partial ordonata ( N x N , a) oricesubmultime nevida are un element minimal.

3. Sa se demonstreze unnatoarea proprietate extinsa de antisimetrie:daca < xg , atunci x} = ... = x

4. Sa se enumere toate relatiile de ordine definite pe o multime cu 5elemente.

5. Fie A o multime nevida, iar /' multimea tuturor relatiilor de ordinepartiala de pe A. Pentru p,a e P definim p < a daca pentru a,b e A ,apb => aab . Sa se arate ca (/*,)#b'.

3. Latici. Proprietati.Intr-o multime partial ordonata X putcin defini operatiile de

jnlersectie si de ruuniunc alunci cand sunt indeplinite anumite conditii.

3.1. Definitie. Fie X o multime partial ordonata. Numim supremumsau reuniting a doua elemente x i y e X un element a c X cu proprietatile:

1) x < a i y < a ;2) V6 G X cu proprietatea ,,x

66 HA/J-JJ: INI-'ORMA ncnCapilolul 2 - Razi.de til^hr/cc ulc infonnalicii

3.6. Observatie. Daca L este o latice. operatiile binarev. A : L x L - >L sunt definite pentru orice x s i y e L iji ele suntreuniunea si intersectia laticiale.

3.7. Exemple.1) in N i Z, cu relatiile de ordine partiala data de ordinea naturala,

reuniunea a doua elemente este eel mai mare dintre ele, iar intersectia adoua elemente este eel mai mic dintre ele.

2) In x A y - x o .v v y - y ( proprietate de consistenta).

^Demonstrate. Proprietatile Al) si A2) rezulta din defmitiilereuniunii si intcrscctiei. Prima egalitate a proprietatii A3) rezulta din faptulca atat primul membru cat si membrul al doilea al acesteia sunt fiecare egalicu eel mai mare ininorani al lui x, y si z, in conditiile ipotezei. Analog pentrua doua egalitate.

Pentru a demonstra proprietatea A4), de absorbtie. sa observam c;din x < x si x < x v y rezulta X < A A ( A V > - ) . Cum in mod evidenx" A(X v y)< x , rezulta prin antisimetrie x A (x v y) = x . Analog se arata cx v (x A y) = x .

Pentru a demonstra proprietatea C), sa presupunem ca x < y . Cutx < x, prin definitia intersectiei rezulta x < x A y . Pe de alta parx f \ y < x . Prin antisimetrie rez.ulta x A y = x .

Presupunem acum ca x A y = x . Din definitia intersectiei rezulx < y . Am demonstrat astfel ca x < y ci> x A y = x . Analog rezulta

X < y O x v y y .

t,' 3.10. Propozitie. Intr-o multime partial ordonata P ce arc un prelement 0 e P, au loe proprietatile:

AS) O A X = O si O v x = - x , Vxe P.Dual, daca P are un ultim element 1 e P, atunci au loc proprietatile:

x A 1 = x si x v 1 = 1, Vx e P .I ty-Demonstratia este imediata utilizand consistenta.

3.11. Propozitie. In orice latice L, operatiile de reuniune s,iintersectie sunt izotone:

[x A y < x A z,r/aca y < z , atunci < . oricare ar ft x e L [x v y < x v z

^Demonstratie. Daca y < z , utilizand proprietatile Al) - A4consistenta C), obtinemx A y = (x A ,x) A (y A z) - (x A y) A (x A z) , deci x A y < x A z . ErezAilta si a doua relatie.

3.12. Propozitie. In orice latice L sunt satis/acute inegaliti distributive:\ a) x A (y v z ) > (x A y) v (x A z) ;b) x v (y A z) < (x v y) A (x v z

i ^Demonstrate-. Deoarece x A \; < x si x A y < y < y v z . rex A y < A- A (y v z) prin definilia intersectiei laticiale. Ax A z < x A ( V v z) . Apoi, conform definitiei reuniunii re

(x A y) v (.x A z) < x A (y v z ) .Prin dualitate rezulta si a doua inegalitate.

3.13. Propozitie. intr-o latice L are loc inegalitatea modulara:Vx,y, z e L , x < z => x v (y A z) < (A- v y) A z .

68 KA7.E1J-. 1N1-'OKMA TK'll ("apilolul 2 - /itizele alghrice tile informal icii 69

} f Demonstraliei x < x v y si x < z implicaasemenea

y/\z x A z < y A t si x v z < y v / ; x, y, z, / e L

70tf/f///./: INFORMAT1C1I

4. Sublatici. Produse de latici4.1. Definitie, O latice S se numeste suhlatice a unei latici L daca S

este o submultime a lui L 51 incluziunea S >L este un inorfism delatici.

4.2. Exemple.-1 . Multimea vida este sublatice.2. Submultimea formata dintr-un element oarecare x&L

este sublatice.

4.3. Propozitie. Submultimea S, posibil vida, a unei latici L estesublatice daca si numai daca S este latice fata de restrictive la S aleoperatiilor laticiale pe L.

Imaginea printr-un morfism de latici / : L -- > M a unei sublaticiS a lui L este o sublatice a lui M. De asemenea, imaginea inversa a oricareisublatici T a lui M este o sublatice in L. Este posibil ca ea sa fie vida, chiardaca sublaticea Jnu este vida.4.4. Observatie. O submultime a unei latici L poate fi latice, fara caea sa fie sublatice. In laticea L a submultimilor unui grup finit G,Submultimea S a tuturor subgrupurilor lui G este latice fara a fi sublatice alui L: reuniunea de multimi a doua subgrupuri nu este, in general, unsubgrup.

4.5. Definitie. Pentru doua elemente a,beL multimea\x e L a < x < bj se numeste interval cu capetele a si b si se noteaza prinM].

Un interval \a,b] este o sublatice in L, pentru orice a,b c L .

4.6. Dcfinitiv. Numim ideal al unei latici L o submultime nevida / alui L cu proprietatile:

i) a .

Imaginea inversa a lui 0 printr-un morfism de latici este un ideal.Un ideal dua l se numeste filtru.

Ciifiilolul 2 - Kaxle al$brice ale infonnalicn /

/ 4.7. Defmitii.i 1) Numim ideal principal generat de un element a e; L. multiml(a) = a A L = (x e L\ x < a]

2) Un ideal propriu se numete \ prim dax A _ H e / --^ xe / sau y e / , Vx, v G L . Dual se defineste notiunea

" filtru prim.v 3) Un ideal propriu se numete .maximal flaca nu exista un idpropriu care sa-1 includa strict. Dual se defineste notiunea de fimaximal (ultrafiltru).

4.8. Dcfinitie., Numim i/a^'ce completa o latice in care pentru osubmultime X exista un eel mai mare minorant, notat prin inf X i unmai mic majorant notat prin sup X . Pentru X = L, se observa ca clatice completa nevida are atat prim cat si ultim element.

4.9. Observatii.1) Duala oricarei latici complete este o latice completa.2) Orice latice finita, ca si orice latice de lungime finita,

completa.3) Laticea tuturor subgrupurilor unui grup, chiar infinit, este ocompleta.

4.10. Definitie. O proprietate p a submultimilor unei multimi,

,' o proprietate de inchidere, daca:i) Multimea X are proprietatea p;ii) Orice intersectie de submultimi ale lui X

proprietatea p. arc ea insasj proprietatea p.

Ii 4.12. Exemple.\1. Proprietatea de a fi submultime a unei multimi.1. Proprietatea de a fi subgrup a unui grup este o proprh

inchidere.* 4.13. Teorema Fie L o latice completa si S o submultime a

proprietatile:(i) 1 6 S , unde 1 este ultimul element al lui L.(ii) 0 * T c S r:> inf T G S .A tune i S este o latice completa.

(}>fDemonstratie* Pentru orice submultime nevida T a lui S, infeste eel mai mare minorant al lui T in S. Fie acum U submultir

72 KA7.ELE INI'ORMATK '// ('apilolul 2 - liazi'lc albrice ale information 73

format a din majorantii tuturor elementelor din T; ea este nevida. prin ( i ) .Atunci inf U e S prin (ii) i este un majorant al lui 7", dar $i eel mai mic cuaceasta proprietate, pentru ca inf U < u , Vw e L/ . Deci 5 este o laticecompleta, conform definitiei .

4.14. Corolar. Multimea T a suhmultimilor unci multimi X care an proprietate data de inchidcre formeaza o latice completa, In careintersectia laticiala a lui (F este intersectia de multimi, iar reuniuncalaticiala este inlersectia tuturor submultimilor ce contin submultimilc date'.

Daca 'Y este o submultime a lui fF , atunci: inf 'Y --- \ S i

- \T, In particular, daca = {8,8'}, atunci:

4.15. Definitie. Produsul P *Q = {(.v,y)| x e P,y e Q] a douamultimi partial ordonate P si Q, este o multime partial ordonata prin relatiade ordine partiala definita prin

def(x],yl ) < (x2 ,y2 ) Ci> ( x} < x2 in P si y, < >-, in Q )(am notat la fel relatiile de ordine partiala in P. respectiv Q, neexistandpericol de confuzie).

4.15. Propozitie. Fie L si M doua lot id. Atund L x M este o latice.^-Demon.stratie. Vom nota la fel operative laticialc in L, M, respectiv

in L x A/ , neexistand pericol de confuzie.Vom proba ca elementele a - (x} v x^.y} v _ v n ) !?i

h - (A, A A%. y, A v2 ) sunt reuniunea $i respectiv interseclia elementelor(-v, . v, ) si (x-, , v2 ) din Lx. M .

Elementul ae LxM majoreaza pe (.*,.>',) si pe (x^.y-,) deoarcccx} v .v, > A-, si -v, v A% > ,v2 si analog ,v, v >-, > v, , y, v v2 > _y3 . Daca unelement c = ( s , f ) e Z , x M majoreaza pe (x, , v,) ?i pe ( x , . y 2 J , aceastainseamna ca s > A, ^i .v > A% i / > v, ;?' ' - >;2 Rezulta ca ,v > A, v A2 ;ji/ > _y, v v2 i deci c > a . Aceasta demonstreaza ca a este reuniuneaelementelor (jf ,,>',) ?i (A-.,,>'J). Dual, A este intersectia elementelor (x,,^,)si (x-,,y2) din Lx M .

Exercitii1. Fie L o latice. Atunci /, este un lant c> orice submultime S a lui

L este o sublatice.2. Aratati ca sublaticile unei latici /. formeaza o latice completa

fata de incluziunea multimilor.. 3.! Aratati ca daca L i M sunt latici complete, atunci produsul

L x M este latice completa.4. Aratati ca multimea idealelor unei latici L formeaza o latice

completa L fata de incluziunea multimilor. Aratati ca daca laticea L estefinita, atunci L i L sunt izomorfe.

5. In orice latice L, aratati ca functia a a a A L este un morfismde ordine care duce intersectiile laticiale (respectiv reuniunile) in intersectiide multimi (respectiv reuniuni).

6. ((aA*)Al) = (aAZ,)o(&Al),((a v h) A L) = (a A L)^j(b A L) .

7. Aratati ca laticea submultimilor multimii [a,b,c] nu contine osublatice cu 7 elemente.

8. Aratati ca orice latice L este izomorfa cu o sublatice a unei laticicomplete.

5. Latici Modulare5.1. Definitie. O latice se numeste modulara daca pentru orice

x,y,z e L cu proprietatca x < z , are loc urmatoarea identitate modulara:A6) x v (y A z) = (x v y] A :.

5.2. Propoxitic. Subgrupurile normals ale iinui grup G formeaza olatice modulara.

^Demonstralie^ Subgrupurile nomiale ale unui grup G fonneaza olatice in care intersectia laticiala a doua subgrupuri normale ale lui G esteintersectia de multimi, iar reuniunea laticiala este multimea tuturorproduselor dc doua elemente din primul. respectiv eel de-al doilea subgrup.Deci, daca M i N sunt doua subgrupuri normale ale lui G, atunci:M A A' -- M r\ N , M v N = {xy\x e M,y e A'}, unde A,V sunt operatiilelaticiale in multimea subgrupurilor normale ale grupului G. Pentru ademonstra ca aceasta latice este modulara, este suficient, conformpropozitiei 3.13, sa probam ca: Lc.N ^> (L v M) A N a L v (M A TV).

74 BA'/J-'.U-: INl-'ORMATKV/Capilolul 2 - Razclc a/ghricc tilt' iirfonnuticii

Fie A- e L c N . Atunci x e L v M si x = yz , unde y c- /, si z c M .

Dar din x = yz rezulta z = y lx, cu y l&LcN s.i x e N . Deci z e A-'.Dar, prin alegerea sa, z e M , astfel ca z 6 M o A/ . Prin urmarc x = yz, cu_>> e L ?i z e M o A/' , c.c.t.d.

5.3. Teorema. Orice latice nemodulara L confine olatice izomorfa cu laticea din diagrama reprezenlatcl infigura 10.

xlsa\ Demonstrate. Prin defmitie si inegalitatea modulara, \

laticea L contine elementele a, y s.i c, cu a y = \ i x A y = z A j y = 0 ?i genereaza laticeadin figura 10.Avem x v y = (a v (y A c)) v _y = a v ((y A c) v y) = a v y . Vom arata caz v _y - ((a v y) A c) v y = av ^ .

Cum x < z , x v _y < 2 v y. Trebuie aratat ca x v y > z v y. Dara v y > y i deciy v (c A (a v j')) < (_)> v c) A (a v y) = a v _ypcntru ca a < t1 din ipoteza i deci a v y < c v y . Aadar are loc iz v _y < .vv y . Deci x v y = z v y .

Vom arata ca x A _y = z A y. Pentru aceasta explicitam pe fiecare din

ele.y A z = _y A ((o v y) A c) = {y A (a v v)) A c = y A c .A- A y (o v ( y A c)) A v > ( v A c) v (a A v) = c A y .Cum x < 2 , rezulta x A y < z A v . Deci x A y = Z A _ y = C A _ y .Astfel elementele x.v. z, avy, cr\y formeaza o sublatice

not not

izomorfa cu cea din figura de mai sus, unde 0 = c A y i 1 = a v y .

5.4. Teorema. I'aitru oricc inel R. R-submodulelc oricarui R-modulA formeaza o lalicc modulara.

Exercitii/. Aratati ca orice latice de lungime 2 este modulara.2. Aratati ca orice sublatice a unei latici modulare este modulai3. Aratati ca produsul a doua latici modulare este o

modulara.4. Intr-o latice modulara, fie M A / ) - 0 , a\fb-\ ^i fie 0 a v (h AC) - ( v b) A c)ii) a A ((a A b) v c) = (a A 6) v (a A c) , Va, /), c' e Liii) Daca a > 6 i c e L , atunci u v c: -= /

a /\c b /\c => a b.8. Daca intr-o latice modulara L cu prim i ultim element,

0, respectiv 1, x i _y an proprietatile: a) x A v - 0 i x v y = 1, b)51 x v z = 1 c) x, y e [a, b], atunci x = y .

9. Aratati ca o latice este modulara daca i numai daidealelor sale este modulara.

6. Latici Distributive. Proprietati6.1. Defmitie. O latice se numete

*~~'

76 M/J-:i.E INl-ORMATK 'II 2 - Hazelc alf>briN7' care atribuie fiecarui intregpozitiv m o functie e : Z' - >N definita ca mai sus.

Astfel, daca w ,eZ^ si h(m) = e, / ; ( )=/ , atuncih((m,n)) = e A/ , iar h([m,n]) = e v f , unde cu (m,n) am notat eel maimare divizor comun al numerelor m si n, iar cu [w,w] am notat eel mai micmul t ip lu comun al lor.

In acest fel, multimea Z 4 , partial ordonata prin divizibilitate, poatefi privita ca o sublatice a lui N7' , partial ordonata prin relatia ' A Z . Atunci:A" = X A (z V A') = A" A (z V v) = (A' A r) V (x A )') = (z A )') V (A" A y) =(z v _ V ) A y- yuti l izand proprietatea de absorbtie si de distributivitate.

Exercitii.1. Aratati ca orice produs de lanturi este o latice distributiva.2. Aratati cfi orice produs de latici distributive este o latice

distributiva.3. Aratati ca daca adaugam la o latice distributiva doua elemente 0 si

1 ce satisfac 0 < x < 1, V.r e L, atunci rezulta o noua latice distributiva.

HA7.E1.E 1NFORMATH '11

4. Aratati ca daca n = p*1 -p j 2 -p'kk , (p, x' defmita pe iin L inverseaza deci ordinea si d\ice intersectiile in reuniuni si in-ca are loc proprietatea A10).

7.8. Definitie. O algebra booleana A este o multime intrei operatii dintre care doua binare. ,,v", ,,A" si una unara ,.' "',

80 RA7.ELK INFORMATICll

proprietatile Al) - A10). Daca A si 6 sunt algebre booleene. o functie/ : A > B este un morfism de algehre booleene daca el este morfism fatade operatiile v ",,, A " si . ' ".

Algebra booleana se mai nume$te s.i algebra Boole, ca un omagiuadus matematicianului englez George Boole (1815-1864) creatorul acesteidiscipline.

7.9. Observatie. Teorema anterioara spune ca orice latice booleanacu operatia unara ,,' ", care duce un element x in imaginea sa prin operatia ,,'" poate fi privita ca o algebra booleana.

7.10. Exemple.1) Multimea (P(M), a partilor unei multimi M, este o algebra

booleana.2) Orice corp de multimi (un inel de multimi / ce confine odata cu

submultimea S s, i submultimea S', uncle prin S' am notat complementara luiS in raport cu /) este o algebra booleana.

7.11. Observatie. Conform proprietatii A8), orice morfism / dealgebre booleene are proprietatile / ( ( ) )=() $.i / '(!)-! si deci el este unmorfism fata de operative zero-are ,,selectarea lui 0" s.i ,,selcctarea lui 1".Kxista o inversa partiala a acestei aiirmatii.

7.12. Propozitie. Daca A fi B sunt algebre booleene, atunci oricefunctie f : A >B cu f(0)-Q si /"(l) = 1 $i care este morfism fafa deopesatiile v, A este un morfism de algebre booleene.

. ^Demonstrate. Pentru orice x e A, aplicand functia / proprietatiiA8), si utilizand ipotezele, rezulta / (x) A J'(x') = 0, / (A) v f ( x ' ) = 1.

In algebra booleana B, aceasta inseamna ca f ( x ' ) este uniculcomplement (f(x)) al lui /(,v) sau altfel ca /(*') = (/(*)) i in consecinta/este un morfism de algebre booleene.

7.13. Definitie.' O algebra booleana S este subalgebra booleana aunei algebre booleene A, daca S este o submultime a lui A i incluziunea

-^~ A este un morfism de algebre booleene.Aceasta implica faptul ca, in S, operatiile ,,v" i .,A" si ' '" sunt

restrictii la S ale operatiilor corespunzatoare din A.Orice subalgebra a unei algebre booleene este o algebra booleana.

.

( 'npilohil 2 - liazelc alghricv ale informaticii

7.14. Observatii.1 ) Un interval [a,b], intr-o algebra booleana A. este o sublatice

booleana, dar nu i subalgebra booleana.2) Intersectia unei familii de subalgebre booleene dintr-o algebra

booleana A este o subalgebra booleana a lui A. In particular, intersectiatuturor subalgebrelor booleene ale lui A continand n elemente date, a] . a2...., an, constituie o subalgebra booleana a lui /I, numita subalgebra generatdde element ele a,, , Demonstrate. Daca x $iy sunt sunt complementate, atunci:(x A y)/\ (x'vy') = (x A y A x')v (x A y A y')= 0si dual. Deci xs\y are un complement si anume x'vy. Analog pentrux v y.

Exercitii.1. Aratati ca un i n t e r v a l [ a , b ] ~ { x e B \ a < x < b } intr-o algebra

booleana B nu este subalgebra booleana.2. Demonstrati ca orice interval [a,b] al unei latici booleene este o

latice booleana.3. Gasiti o latice modulara cu 7 elemente in care cornplementele

elementelor nu formeaza o sublatice.4. Aratati ca: x = 0 t - (x A /') v (X'A/) , x,t e B, unde B este o

algebra booleana.5. Demonstrati ca, intr-o algebra booleana B, unnatoarele afirmatii

sunt echivalente:i) x = y; ii) (x A v') v (X'A_>) = 0 .

6. Sa se generalizeze Exercitiul 2 pentru laticile inodularecomplementaie.

7. Aratati ca:a = (a A /;) v (x A (a v b}) co /; - ( A b) v (,V'A( v />)) .

8. Demonstrati ca: x A y < (x A z) v ( v A z'), Vx, y.z e B .9. Intr-o algebra booleana B, aratati ca urmatoarele afimiatii sunt

echivalente:/') a A x = b A x ;//') [(a A b') v (o'Afr)] A x = 0 ;///) 'AX =

KA7.ELE INFORMAT1CU ! 2 - Hnzcle atghrice ah: in

10. /' e filtru intr-o algebra booleana co /) l e F ;//) x & F,x'vy e F => \> e F .

11. Demonstrateca: ft = c (/J'AC) v (a A ft' ) v (a A c) = (a A c') v (ft A c') v ( A ft).

12. Aratati ca: a A ft < (a A x) v (ft A x') < a v ft, Va,ft ,x e 6 .13. Demonstrati ca multimea elementelor complementate dintr-o

latice distributiva L data, formeaza o sublatice a lui L care este algebrabooleana.

14. Demonstrati ca multimea elementelor care au complement unicdintr-o latice modulara L data, formeaza o sublatice a lui L care este algebrabooleana.

15. Daca o latice modulara complementata verifica condi^ia deminimalitate (orice submultime de elemente ale sale are eel putin unelement minimal), atunci ea verifica si conditia de maximalitate (oricesubmultime de elemente ale sale are eel putin un element maximal).

16. Intr-o latice distributiva care verifica conditia de maximalitate,orice element x admite o unica reprezentare ca o intersectie de elemente carenu pot fi scrise ca intersectii de alte elemente diferite de acestea.

17. Aratati ca orice latice distributiva este o sublatice o unei algebrebooleene.

18. Demonstrati ca o algebra booleana in care orice ideal esteprincipal, este finita, si reciproc.

8. Algebre Booleene i Inele Booleene8.1. Definitie. Un inel R in care toate elementele sunt idempotente

fata de multiplicare (V.v e R => x2 = x), se numeste inel boolean.

8.2. Propozitie. Orice inel boolean R este comulativ .fi decaracteristica 2.

^Demonstrate'. Daca x si v sunt elemente arbitrare din inelul booleanR, atunci utilizand defmitia:x I y - (x I- yXx + y) - x" 4 xy + yx + y - x + xy 4 yx i y , Vx,y e Rsi deci xy -f yx = 0, Vx,y c R (\)Pentru x = y, relatia (1) devine: 0 = x2 + x2 = x 4 x = 2x . ceca ceprobeaza ca inelul R este de caracteristica 2.

/ Daca in relatia ( 1 ) adunam xy in ambii membri. rezultxy = xy 4 xy 4 yx - yx , si deci inelul R este comutativ.

* 8.3. Teorema.* * 1. Putem defini pe multimea elementelor unei algebre booleene I

adunare fi o inmultire prin: x \-y~- (x A y')v (x'Ay)(2)

xy = x A y (3)pentru orice x,y e 6 fi astfel fata de aceste operatii multimea data devun inel boolean cu unitate ^(B), elemcntul Q fiind eel mai mic elemenlui B, iar 1 fiind eel mai mare.

II. Invers, putem defini pe un inel bolean R cu unitate o reuniuno intersectie prin formulele: xvy = x + y-xy

(4)(5)

pentru orice x,y&R, obtindnd o algebra booleana (B\R], eel maielement fiind 0 al lui R, iar eel mai mare 1 (imitatea) fiind lui R si x'= ](6)fiind complementul lui x.

Ul.Avem: ^(^ R)}~ R pentru orice inel boolean R si(B(^(/?)) ~ B pentru orice algebra booleana B.

I ft- Dcmonatratie: Adunarea definita prin (2) este comut' multiplicarea definita prin (3) este asociativa si comutativa, iar fi

element este idempotent fata de multiplicare.Cum: x -t- 0 = (x A 0') v (X'AO) - (x A 1) v 0 - x, xl = x A 1 = x.

rezuha ca 0 si 1 ale algebrei booleene sunt 0 si 1 ale inelului R.Din (2) observam ca: x 4 x --- (x A x')v (X'AX) - 0

si deci inversul aditiv al fiecarui element x exista si este chiar x.Vom arata ca adunarea definita prin (2) este asociativa

multiplicarea definita prin (3) este distributiva fata de adunare.Prin formulele lui De Morgan, in orice latice distributiva are loc

((x A y) v (x'Ay))' = (x A y)v (x'Ay'). (7)Din (7). utilizand distributivitatea in 5, rezulta in (S\B]\(x 4 y) 4 z -= (x A y')v (x'Ay)+ z --_ (((x A y')v (x'Ay)) A z')v (((x A y)

- (x A y'AZ') v (x'Ay A r') v (x A y A z) v (x'Ay'Az).Dar prin comutativitatea adunarii, definite prin (2): x + (y + z) = (z + )

84 : INFORMATK'// ('apilolul 2 - /tec/c ulghricv ale infonnalicli 85

Si x + (y + z) = (z + y)+x =(z A v A x) v (Z'A V'AX) v (Z'A v A x') v (z A V'AX') - x ^ (y -f z) .

In f inal , pentru orice triplet de elemente x, y, z din B,xy -t xz = (.v A y) + (x A z) = ((x A >')A(X'VZ'))V ((x'vy1) A (X'AZ'))-= (x A y A z') v (.v A y A z') v (X'AX A z)v ( V'AX A z) == (x A (y A z')) v (A A (y A z')) = x A ((y A z') v (/AZ)) = x(y I z),completand demonstratia priinei afirmatii a teoremei.

Fie acum un inel boolean R cu unitatea 1. Prin comutativitatea siasociativitatea operatiilor din R, reuniunea defmita prin (4) este comutativasi intersectia definita prin (5) este comutativa si asociativa. Mai mult,reuniunea este si asociativa(xv y)v z = \x + y xy)v z = x + y- xy+ z (x + y- xy)z == x + (y + z - yz) - x(y + z - yz) = x v (y + z - yz) - x v (y v z).

Identitatile de absorbtie se verifica de asemenea. Din (4) si (5) avem:x A (x v y) = x(x + y - xy) - x1 -f xy - x2y = x six v (A: A y) = x + xy - x 7~ y - x .

Rezulta ca 'B(^) este o latice. Sa aratam ca este distributiva:(x A y)v (x A z) - xy + xz - xyxz - xy f xz - xyz =x(y -t- z - yz) - x A (y v z).

Laticea (B(/?) are prim si ul t ini element pe 0 si 1 ale lui R:0 A x = Ox - 0 si I A x = Ix - x .

Mai mult, x(] - x) ~ x- - x2 - 0 si A- I (1 - .r) - .r(l ~x)--1, deci 1 - xeste complementul lui JT in (B(R).

Fie /J o algebra boolean;!. Prin (2) si (3) construim un inelboolean^,(tf). Pornind de la ^,(). prin:x(f) y = x + y- xy (7)xy = xy (8)construim o algebra booleana (8(^(5)).Din ul t ima relatie si din (3), rezulta x y - xy - x A y . Cum A si v stintduale. rezulta ca si este A si deci (B(^(S)) este izomorfa cu 5.

Similar, fie .A" un inel boolean cu unitatea 1. Formand algebrabooleana (/?). apoi ^((B(R)) prin:

x(&y= (x A y') v (.V'A_V) (9)x>y-x/\y (10)corespunzand lui (2) si (3), respectiv.

Din (10) si (5), x^ = jc A >' = xy . Mai departe. din (9), (6). (5) si (4)x@y = (^ A >'') v (jf 'A_y) = x(\ - y) v (l -- x)y =

= x ' + _v - 2xv - xy = xy 4 xy - xy = x -i- y , deci R .

Exercitii1. Aratati ca intr-o algebra booleana R au loc urmatoarele relatii.

Vx,yeB:a) x A (x'vy) = x A y , x v (x>y) = x v y ;b) x < y o x'vy ] x A y' = 0 ;c) x = y (x A y' ) v (X'A>>) = 0 o (x'vy) A (x v y' ) = 1 .

2. Stabiliti o corespondenta biunivoca intre idealele unei algebrebooleene si idealele inelului boolean asocial ei.

3. Idealul / al unei algebre booleene este interval daca si numai dacaa e 7 si a' f I sunt afirmatii echivalente.

4. Fie K un ideal intr-un inel boolean S. Atunci urmatoarele conditiisunt echivalente:

5. K maximal; b) K prim; c) V.v a S este indeplinita una dinconditiile s e K sau s'c. K , dar nu am^ele.

6. Fie S o algebra booleana; atunci urmatoarele afirmatii suntechivalente:

a)Secorp; b) S e domeniu de integritate; c) 5 are exact douaelemente.

7. Fie B o algebra booleana, a,b e B si / : B -> B o functie definitaprin /(x) = (x A a) v (b A x'). Aratati ca /(/(/(x))) = /(x) , Vx e B .

9. Algebre Booleene LibereIn t r -o algebra Boole A, consideram doua elemente x,y e A . Vrem sa

construim algebra booleana generata de elementelex si y.Vom proba ca orice algebra booleana generata de un numar f ini t dc

elemente, este finita.Sa consideram algebra booleana A generata de elementele x si y. Ea

va contine pe x', y' si de asemenea elementelex A y , x A y'. x'Ay , x'Ay'. (1)

Sa consideram acum reuniunile de unul sau mai multe astfel deelemente. Exista 2" astfe! de expresii corespunzand tuturor submultimilor

HA7J-LEINl-'ORMATICll _86

multimii formate din elementele din (1). O astfel de expresie o vom numiexpresie canonica disjunctive! (expresie polinomiala booleana disjunctive!).

Fie .S1 multimea tuturor elementelor lui A ce pot fi scrise ca expresiicanonice disjunctive in x si y. S e o subalgebra a lui A, fund inchisa fata dereuniune si fata de intersectie.(Se observa ca intersectia a oricaror douaelemente este egala cu 0). Cum

x - x A(_V v /) = (x A jy)v(x A /) si x'= X'A(_V v/)- (X'A>>)V (X 'AV' )>rezulta ca S contine elementele x, y, x' i y'.

Un argument similar pentru o algebra booleana A cu trei generator!arata ca fiecare element al ei poate fi scris ca o reuniune de urmatoarele optelemente de forma x" A yb A zc, unde x" e (x,x'}, si analog pentru yb i zc,.

Pentru o algebra booleana cu n generator!,x,,x2,...,xn, vor exista 2"

intersectii de elemente de forma x'1 A X ^ 2 A . . . A X / , unde pentru fiecare /,e, I -\x.' e [x^Xjf.

Fie { , ' } o multime de doua elemente, unde x, = x,, iar x, este' " '- ,\n

complementara. Multimea \e\e: n -- >| , ' j j este multimeaMultimea tuturor acestor 2" liste de expresii e\ determina 2" intersectii

x,1 AX2 2 A.. . AX]," e A . Daca S este o submultime oarecare de functii din

d'f I \{ . ' } , fie h(S] =1 V^x,"1 A x* A ...AX/ ), si /i(0) = 0 .

9.1 Teorema. Daca x,,x2 . . . . .xn .VMH? elemente ale algebrei Boole

A $i 8 - (Pl| . ' j I este algebra Boole a xubmultimilor S ale multimii c/cf'niH'tii | . ' | . alunci h Jcfinc^le wi morftstn h : B ----- > A tie algebreBoole, avclnJ ca imagine subalgebra lui A general a tie x,,x2 . . . . ,x,. .

Demonstrate J f-'ie .S1, T doua submultimi ale lui i , ' | Avem:

Cum x, v x,

/)(0) = 0 (prin convcntie).1 , rezulta ca 1 = (x, v x, )A ... A \xn v xn ).

( 'apitohil 2 - Bazi'le algbrice tile informaticii

Membrul drept, dezvohat folosind distributivitatea, conduce la 2" termer!

^O, ' j este H////JI

element al lui B.Fiecare element x, se scrie

x, = A (XM v x, , )A x, A(X,+] v xH l JA (2)care este imaginea prin h a unei submultimi S din \ , ' j , prin dezvoltacu ajutorul distributivitatii. Deci imaginea lui h contine orice element x,algebra booleana A s.i astfel h(S) este subalgebra generata de ekmer

XpX2,...,Xn .

9.2. Corolar.', Orice algebra booleana generata de n elen-,n

x,,x2,...,xB contine eel mult 2 elemente.

9.3. Teorema. Exista o algebra booleana B $i o list a S},S2,...,in elemente ale lui B cu proprietatea ca pentru orice lista x,,x2,...,xn

elemente ale algebrei booleene A exista exact un morfism h : B -- 5algebre booleene cu h(S,) = x, , Vr , / e n .

Demonstrate.'- \n algebra booleana S = (Pn , ' j Iconsideram,orice f e n submuhimea S, c; [ , ' j , cu S, = B e e \ ,' j ,e, = j.e 6 Sj et - . Formula (2) pentru h(S) arata ca orice S din B

forma:s^ oS n , . . . n .Prin (3), reiese ca orice morfism h : B ----- >A de algebre I

iS, a x, poate fi dat prin fomiula (2) pentru h. Astfel h este unic, c.c

9.4. Definitie. O algebra booleana B cu o lista S, avand prcdin Teorema 9.3 este numita algebra booleana libcra pc\S,,S2,...,Sn) de generator! libcri^ in exacta analogic cu modulele I

Conform teoremei 9.3 rezulta ca orice algebra booleana izcaceasta este de asemenea o algebra booleana libera cu n gener;mult, doua expresii booleene cu n litere Xi ,x 2 , . . . ,x n sunt egalalgebra booleana daca i numai daca ele sunt egale cand x,,x2.

HA7JH.I-: IN]-'ORMAT1CII

generatorii liberi ai algebrei booleene B, adica daca si numai daca cele douaexprcsii se reduc la aceeasj expresie canonica disjunctive.

De exemplu, expresiile X V ( J A X ' ) si (x/\y')\/y sunt egale, fiecaredin ele avand aceeasi expresie canonica disjunctive.

Exercitii1. Aratati ca sublaticea generata de o submultime finita cu n

elemente a unei latici distributive, confine eel mult 22 elemente.2. Aratati ca daca o algebra booleana A este generata de n elemente,

atunci A este libera daca si numai daca are exact 22 elemente.3. Fie A o lagebra booleana libera, generata de n elemente. Aratati ca

pentru orice m < n A contine eel putin C" subalgebre libere cu mgeneratori.

10. Algebre Dniversale10.1. Definitii.i) O algebra A este o pereche [S, F], unde S este o multime nevida

de elemente, iar F = ( f a ) a t l o multime specificata de operatii f t l , fiecareaplicand o multime S1*"' in 5", pentru un intrcg nenegativ corespunzatorn(a). Fiecare operatic / atribuie fiecarui /?(a)-tuplet (*i ,.>*()) deelemente din S o valoare fa\x,,...,x,^) din S. Daca n(a) - 1, operatia senumeste unara; daca n(a) = 2 , operatia se numeste binara, etc. Daca/?(a)- 0, operatia sc numeric zero-ara; ea selecteaza un element fixat din S(exemplu: elementul neutru intr-un grup. 0 sau 1 intr-o latice).

ii) Notam cu T aplicatia detinita pe multimea 7 de indici, cu valori inmultimea Na numerelor naturale. care asociaza fiecarei operatii aritalca san(a}. numita si iipul algebrei. Daca nu se specifica tipul, se intelege ca selucreaza cu algebre de acelasi t ip. Multimea S se mai numeste si multimesuporl a algebrei si cand nu este pericol de confuzie. putem nota algebra cuS. identificand-o cu multimea sa suport.Observatie. In definitia algebrei, se considera ca operatiile / Jbrmeaza oiamilie F, nu o multime de operatii. astfel ca putem considera distincteanumite operatii care lucreaza la fel. Putem identifies doua algebre t^-^1 ?'

(.'apitotul 2 - liazi'le nlc informaticii

[S,C] ( F - (fa ) t / i ; , G = (g,, ),.,), pentru care exista o bijectie b de la / la./,cu proprietatea ca fa = gh(,,), Va e / .

// 10.2.\Exemple. >/ ( 1) Un grup este o algebra [.S\F], cu F = { / ' ,g} , unde operatiaf:S*.S-*S este definita prin f ( x , y ) ~ x y si operatia g : S - > S estedefinita prin g(x) = x ~ ] , satisfac conditiile:

vii) /(x,/(^z))=y(/(x,y),z) [x(^z) =^ r _ . .

VV /^ J \J V O X I - ,:* , . .- - .

Observatie: e este elementul neutru al lui S.V2) O latice este o algebra [S,F], cu F = { f , g ] , unde