STRUCTURI ALGORITMICE FUNDAMENTALE

STRUCTURI ALGORITMICE FUNDAMENTALE

1. Notiuni de teoria grafurilor

Definitia 1. Un graf neorientat G este definit prin perechea G = (V, E), unde V este o multime nevida de elemente numite varfuri, iar E este o multime (posibil vida) de perechi neordonate cu componente distincte ale lui V care se numesc muchii. Daca E este multimea vida spunem ca G este trivial. Daca multimea V este finita afirmam caracterul finit al grafului. Numarul elementelor multimii V determina ordinul grafului finit. O muchie cu varfurile x si y (numite extremitati) se noteaza prin [x,y] sau [y,x]. Spunem ca varfurile x si y sunt incidente muchiei [x,y].

Definitia Un digraf este definit printr-o pereche G=(V, E), unde V este o multime nevida de varfuri, iar E este o parte a produsului cartezian V x V ale carei elemente le numim arce. Un arc este notat prin (x,y) cu x y, unde x se numeste sursa sau extremitate initiala, iar y se numeste destinatie sau extremitate finala. Atributele : trivial, respectiv finit, pentru un digraf se definesc similar.

Definitia 3. Un graf (digraf) partial al unui graf (digraf) G = (V, E) este un graf (digraf) G₁ = (V, E₁), unde E₁ E, deci este graful (digraful) G insusi sau se obtine din G prin suprimarea anumitor muchii (arce).

Definitia 4. Un subgraf (subdigraf) al unui graf (digraf) G este un graf (digraf) H = (U, E'), unde U V, E' E, iar muchiile (arcele) din E' sunt toate muchiile (arcele) din E, care au ambele extremitati in multimea de varfuri U.

Uneori, arcele (muchiile) sunt etichetate. Daca etichetele sunt numere reale pozitive se spune ca digraful (graful) este ponderat.

In continuare vom considera numai grafuri (digrafuri) finite. De obicei un graf se reprezinta prin indicarea unor puncte din plan sau situate pe o sfera (ce corespund varfurilor) si a unor segmente de curba (sau de dreapta) pentru indicarea muchiilor (figura 1a). In cazul digrafurilor arcele sunt segmente de curba orientate, sensul fiind de la sursa spre destinatie (figura 1b).

Definitia 5. Fie G = (V,E) un digraf, iar x si y doua varfuri. Numim x-y drum (de lungime n) o secventa de varfuri D: v₀, v₁, , v_n daca v₀ = x, v_n = y , iar (v_i, v_i+1)IE pentru toti i, 0 i n-1. Varfurile x si y se numesc extremitatile drumului D. Un drum fara nici un arc este un drum trivial. Un x-y drum se numeste circuit (sau drum inchis) daca x=y; daca x y, se spune ca drumul este unul deschis. Circuitul este elementar daca toate varfurile circuitului, cu exceptia primului si a ultimului varf care coincid, sunt distincte doua cate doua.

Figura 1a Figura 1b

Definitia 6. Fie G = (V, E) un graf neorientat, iar x si y doua varfuri. Secventa de varfuri L: v₀, v₁, , v_n este un x-y lant (de lungime n) daca v_i, v_i+1 IE pentru toti i,

i n-1, iar x=v₀ si y=v_n. L este ciclu daca x=y. Atributul elementar, pentru un lant, poate fi introdus similar.

Definitia 7. Numim lant (drum) hamiltonian un lant (drum) elementar al unui graf care contine toate varfurile grafului.

Definitia 8. Fie G = (V, E) un graf netrivial. Spunem ca x, y I V sunt conectate in G daca exista un x-y lant in G. Graful G este un graf conex daca oricare doua varfuri din V sunt conectate in G. Daca G este un graf trivial (E multime vida) se accepta ca este graf conex. Daca G nu este conex atunci exista cel putin doua componente conexe (subgrafuri conexe maximale, disjuncte doua cate doua relativ la varfuri).

Un digraf G cu proprietatea ca pentru oricare doua varfuri x si y exista atat un x-y drum cat si un y-x drum in G se numeste tare conex.

In continuare, vom prezenta cateva probleme pentru a caror rezolvare pot fi utilizate grafuri.

Problema 1. Se considera localitatile L₁, L₂, , L_n, cu n intreg pozitiv nenul dat si o multime de perechi (i,j) cu 1 i, j n avand semnificatia: "Din localitatea i se poate ajunge direct in localiatea de destinatie j". Sa se verifice daca din oricare localitate se poate ajunge in oricare alta localitate.

Problema Sa se realizeze o retea cu n calculatoare astfel incat oricare doua calculatoare sa poata comunica intre ele, iar costul total al interconectarii sa fie minim. Se presupune cunoscut costul interconectarii in retea a oricaror doua calculatoare.

Problema 3. Un turist vrea sa calatoreasca din localitatea X in localitatea Y. Daca in tara respectiva exista n localitati si stiind timpul necesar pentru a ajunge (direct) dintr-o localitate in alta (cand este posibil) se cere sa se determine timpul minim in care turistul poate ajunge din X in Y (eventual trecand si prin alte localitati).

In continuare prezentam o metoda de reprezentare a algoritmilor folosind schemele logice. Acestea sunt introduse folosind terminologia teoriei grafurilor.

Scheme logice structurate

O transcriere grafica a etapelor (pasilor) unui algoritm este numita organigrama. De cele mai multe ori este folosita denumirea de "schema logica". Fiecarui pas, al algoritmului, i se asociaza un bloc ce constituie eticheta unui arc. Blocurile folosite intr-o schema logica descriu instructiuni (comenzi) sau predicate (expresii logice). Predicatele apar in cadrul instructiunii de ramificare. Celelalte instructiuni sunt:

1) Instructiunea START: eticheteaza arcul initial (acel arc in a carui extremitate initiala nu pot sosi alte arce). Orice schema logica are un unic arc initial. Acesta va indica punctul de unde incepe executia unui program.

2) Instructiunea STOP: eticheteaza un arc final (acel arc din a carui extremitate finala nu pot pleca alte arce). O schema logica poate avea mai multe arce finale. Acestea indica oprirea executiei programului descris prin intermediul schemei logice.

3) Instructiunea CITESTE: eticheteaza un arc ce indica introducerea de la mediul de intrare (tastatura, disc etc.) a unei secvente de valori (numite date de intrare). Cuvantul CITESTE este insotit de variabilele ce descriu datele de intrare.

4) Instructiunea SCRIE: eticheteaza un arc ce indica inregistrarea la mediul de iesire (display, disc etc.) a rezultatelor (datelor de iesire). Cuvantul SCRIE este insotit de variabilele sau constantele ce desemneaza datele de iesire.

5) Instructiunea de atribuire: eticheteaza un arc cu eticheta v := e, unde v este o variabila, iar e este o expresie de acelasi tip (numeric sau logic) cu variabila v.

6) Instructiunea de ramificare este caracterizata prin n arce ce pleaca din acelasi punct, arce etichetate cu predicatele p₁, p₂, , p_n definite astfel incat:

p₁ or p₂ or or p_n = TRUE (adevarat) si

p_i and p_j = FALSE (fals) pentru oricare i j,

unde or, respectiv and, reprezinta operatiile logice sau, respectiv si.

Definitia 9. Se numeste schema logica (sau program sub forma de schema logica) un graf orientat, in care:

exista o unica instructiune START si cel putin o instructiune STOP;

orice varf (diferit de extremitatea finala a unei instructiuni STOP) este extremitatea initiala a unei unice instructiuni;

orice arc este etichetat cu una dintre instructiunile: START, STOP, CITE^TE, SCRIE, atribuire sau cu un predicat. In ultimul caz, extremitatea initiala a arcului trebuie sa coincida cu extremitatea initiala a unei instructiuni de ramificare.

pentru orice arc exista cel putin un drum care incepe cu instructiunea START, se termina cu o instructiune STOP si contine arcul considerat.

Schemele logice sunt folosite pentru descrierea algoritmilor. Se pot pune in evidenta structuri fundamentale precum:

a) structura secventiala - formata din arce conectate etichetate cu instructiuni distincte de cea de ramificare. O structura secventiala formata din doua arce etichetate prin a, respectiv b se va nota prin SEQ(a,b) si are semnificatia " executa a urmat de b".

b) structuri decizionale (alternative) - contin, obligatoriu, cel putin un predicat si cel putin un bloc functional (instructiune alta decat START sau ramificativa). Structurile decizionale sunt de urmatoarele forme:

IF a; a, b) - Daca a atunci executa a altfel executa b (figura 2a).

IF0 a; a) - Daca a atunci a (figura 2b).

CASE(p₁,p₂,,p_n; a₁, a₂, , a_n) - Daca p₁ atunci a₁, daca p₂ atunci a₂, , daca p_n atunci a_n (figura 2c).

Figura 2a Figura 2b

Figura 2c

c) Structuri repetitive (structuri de tip ciclu, structuri iterative) - contin obligatoriu un bloc predicativ si un bloc functional care se executa de un numar finit de ori pana cand predicatul isi schimba valoarea. Sunt posibile trei situatii:

WHILE(a; a) - Cat timp conditia a este adevarata se executa a, apoi se continua cu urmatoarea instructiune (figura 3a: ciclu cu test initial)

REPEAT(a; a) - Repeta a pana cand conditia a este adevarata, apoi executa instructiunea urmatoare (figura 3b: ciclu cu test final).

FOR(a; a, b, c) - Este echivalenta cu SEQ(a, WHILE(a; SEQ(b, c))). Blocul a este un bloc de initializare. Blocul b descrie instructiunea ce se va executa cand conditia a este adevarata. Blocul c (prezentat explicit in aceasta structura) va descrie actualizarea starilor variabilelor programului cu rol deosebit in evaluarea conditiei a (figura 3c: ciclu cu contor).

Exemplul 1. Urmatoarea descriere reprezinta o secventa. Uneori secventele se pot eticheta.

ET1 SEQ (* figura 4)

Scrie 'Introduceti 3 numere:';

Citeste x,y,z;

media:=(x+y+z)/3;

Scrie 'Media = ',media;

ET1 END

Figura 3a Figura 3b

Figura 3c Figura 4

Eticheta secventei de mai sus este ET1, iar componentele secventei sunt actiuni codificate cu ajutorul conventiilor Pascal. Secventa descrie citirea a trei numere, calculul mediei aritmetice si afisarea rezultatului.

Exemplul Urmatoarele secvente ilustreaza structurile decizionale.

a) ET2 SEQ (* figura 5a *)

citeste x;

Daca (x>0) or (x=0) atunci Scrie 'Numar nenegativ'

Altfel Scrie 'Numar negativ';

ET2 END

b) ET3 SEQ (* figura 5b *)

Citeste titlu;

cod:=0;

Daca nume = 'algebra' atunci cod:=1;

Scrie cod;

ET3 END

c) ET4 SEQ (* studiu individual*)

zar:=1+random(6);

case zar of

1, 3, 5 : impar:=impar+1;

2, 4, 6 : par:=par+1;

end

ET4 END

Secventa ET2 descrie citirea unei valori (se presupune ca x este un numar) si afisarea unui mesaj in functie de semnul numarului x. Secventa ET3, citeste un titlu, iar daca se introduce 'algebra' atunci codul asociat este 1, in rest codul este 0. ]n final se scrie codul. Prin secventa ET4 se genereaza un numar aleator intre 1 si 6. Apoi se analizeaza paritatea numarului. Daca secventa ET4 s-ar repeta, atunci variabila impar ar contine numarul de aparitii ale numerelor impare. Similar, variabila par va reprezenta numarul numerelor pare generate.

Figura 5a    Figura 5b

Exemplul 3. Prin urmatoarele secvente exemplificam structurile repetitive: While, Repeat si For (Elaborarea schemelor logice este lasata ca exercitiu).

a) ET5 SEQ

Citeste x;

i:=1; cod:=0;

Cat timp ((i<n) or (i=n)) and (cod=0) executa

Daca x = a[i] atunci cod:=1 altfel i:=i+1;

Scrie cod, i;

ET5 END

b) ET6 SEQ

repeta

zar:=1+random(6)

pana cand zar=6;

Scrie 'A aparut Numarul 6!';

ET6 END

c) ET7 SEQ

Citeste n; suma:=0;

Pentru i:=1 pana la n executa

SEQ Citeste x; suma:=suma+x END;

Scrie 'Suma =', suma;

ET7 END

Secventa ET5 descrie citirea unui element x si verificarea ipotezei: "Elementul x se afla printre cele n elemente din tabloul a". In secventa ET6 se descrie generarea repetata de numere pana la aparitia valorii 6. Secventa ET7, folosind variabila de contorizare i, citeste n numere, le calculeaza suma si apoi o afiseaza. Observati prezenta predicatului la iteratiile de tip While si Repeat.

Definitia 10. Un algoritm exprimat in functie de structurile SEQ, IF si WHILE se numeste structurat, schema logica asociata se numeste schema logica structurata, iar programul corespunzator se numeste program structurat.

Evident, familia algoritmilor structurati este nevida. Un rezultat foarte important afirma: Orice algoritm poate fi transformat intr-un algoritm structurat. Aceasta afirmatie are la baza teorema Bohm-Jacopini. Pentru a transforma o schema logica (nestructurata) intr-o schema logica structurata se poate folosi regula variabilei booleene (ce rezulta din demonstratia teoremei Bohm-Jacopini). Cititorul interesat de detalii poate consulta lucrarea: Corrado Bohm, Giuseppe Jacopini - Flow-diagrams, Turing Machines and languages with only two formation rules. Comm. ACM. 9 (May, 1966), 366-371.

Una din consecintele importante ale programarii structurate este eliminarea instructiunii de salt neconditionat (goto) din programe. Totusi, exista situatii cand instructiunea goto este utila. Lungimea programelor nu va creste, iar claritatea algoritmului nu va avea de suferit. Important este ca numarul instructiunilor goto folosite sa fie foarte mic.

3. Exercitii propuse

Sa se elaboreze algoritmi bazati pe structurile fundamentale pentru rezolvarea urmatoarelor probleme (cele marcate sunt considerate a avea un grad ridicat de dificultate):

Se considera N numere naturale distincte, strict pozitive, strict mai mici decat 2n si toate diferite de n. Sa se determine doua dintre aceste numere care au suma egala cu 2n.

La un concurs au participat m persoane care au avut de rezolvat n intrebari. Se cunoaste a_k numarul persoanelor care au raspuns corect la intrebarea k. Sa se determine cel mai mare numar p astfel incat sa existe sigur cel putin un concurent care a raspuns corect la minimum p intrebari si sa se determine si numarul celor care au raspuns corect la cel putin p probleme.

. Se considera un numar natural de n cifre toate nenule. Sa se formeze cu cifrele acestui numar si cu cifra zero un alt numar care se divide la prin n.

. Fie un tablou cu n < 10001 numere intregi, din domeniul 1..50000. Sa se partitioneze elementele acestui tablou in cat mai putine subsiruri strict crescatoare.

. Se citesc: numarul natural si n numere naturale x₁, x₂, ., x_n. Sa se determine numarul cifrelor 0 in care se termina produsul x₁x₂.x_n.

. Se citesc cele n cifre ale unui numar natural dat (in ordinea descrescatoare a rangului) si k un numar intre 1 si n. Care este cel mai mare numar care ramane dupa stergerea a k cifre, cu pastrarea, in numarul rezultat, a ordinii initiale a cifrelor.

. Se citeste numarul n. Sa se afiseze toate reprezentarile posibile ale numarului n ca suma de numere naturale consecutive. Exemplu: Pentru n = 15 avem: 15 = 1 + 2 + 3 + 4 + 5 = 4 + 5 + 6 = 7 + 8.

. Se considera ecuatia de gradul al doilea ax²+bx+c=0 (cu coeficienti reali si a nenul). Pentru n = 1, 2, ., 10 sa se afiseze suma:

,

unde x₁ si x₂ sunt radacinile ecuatiei.

. Scrieti un program pentru a discuta natura si semnul radacinilor unei ecuatii de gradul al doilea.

. Pentru numerele intregi nenule a si b sa se determine numerele intregi x si y astfel incat cel mai mare divizor comun al numerelor a si b sa se scrie sub forma ax + by. Generalizare pentru n numere a₁, a₂, ., a_n.

. Fie un poligon (nu neaparat convex) specificat prin varfurile sale su in punct P(x₀, y₀). Studiati pozitia relativa a punctului P in raport cu poligonul dat (situat in interior, pe laturi sau in exterior).

. Se considera o multime de puncte din plan. Acoperirea convexa a multimii este data de poligonul convex de arie minima ce contine in interior sau pe frontiera toate punctele multimii. Scrieti un program pentru determinarea acoperirii convexe a unei multimii date.

. Se considera o multimecu n segmente si un dreptunghi ale carui laturi sunt paralele cu axele sistemului de coordonate. Sa se determine portiunile acele segmente care traverseaza interiorul dreptunghiului, precum si portiunile acestora aflate in interior.

. Se considera, la intrare, n dreptunghiuri ce au laturile paralele cu axele. Care este interiorul intersectiei tuturor dreptunghiurilor date.

. Se considera o multime de puncte din plan. Care este cercul de raza minima ce contine, in interior, toate pounctele date.

. Se considera o multime de puncte din plan. Care este cercul cu centrul in interiorul acoperirii convexe dar de raza maxima care nu contine, in interior, nici unul din punctele multimii.

. Determinati toti factorii primi si puterile maxime ale acestora din discompunerea unui numar natural dat n.

. Implementati, folosind tablouri unidimensionale, algoritmul lui Eratostene pentru determinarea numerelor prime.

. Un numar perfect este acela egal cu suma divizorilor sai mai mici decat el (exemplu: 6 = 1 + 2 + 3). Afisati toate numerele perfecte mai mici ca 500.

. Considerati un tablou unidimensional cu n elemente si k un numar intre 1 si n. Plasati al k-lea element pe prima pozitie, al k+1 - lea element pe pozitia 2 etc. Elementul initial pe pozitia 1 va fi plasat pe pozitia n-k+1 s.a.m.d.

. Aranjati elementele unui tablou astfel incat elementele aflate initial pe pozitii pare, sa apara in sirul final, dupa toate elementele aflate initial pe pozitii impare (exemplu: 1,2,3,4,5,6,7,8

. Fie un tablou unidimensional cu numere pseudo-aleatoare din intervalul 1..maxint si p un numar din acelasi domeniu. Sa se parttioneze tabloul initial astfel incat elementele mai mici sau egale cu p sa se aflate la inceputul tabloului, iar elementele mai mari decat p sa se afle in portiunea finala.

. Fie o multimie de linii cu text de lungime arbitrara. Reformatati textul astfel incat, la afisare, pe fiecare linie sa nu apara mai mult de n caractere (exemplu: 55. Cuvintele nu se vor desparti in silabe, iar paragrafele vor ramane indentate.

. Fiind dat un text si un cuvant, vedeti de cate ori apare cuvantul in textul considerat.

. Sa se obtina scrierea romana a unui numar intreg de 4 cifre (dat sub forma araba).

Bibliografie:

G. Albeanu, Algoritmi si limbaje de programare, Editura FRM, Bucuresti, 2000.

G. Albeanu, Luminita Radu, Algoritmica si programare in limbajul Pascal, Editura FRM, Bucuresti, 2001.

D. Knuth, Arta programarii calculatoarelor. Volumul I: Algoritmi fundamentali, Teora, Bucuresti, 1999.

Corrado Bohm, Giuseppe Jacopini - Flow-diagrams, Turing Machines and languages with only two formation rules. Comm. ACM. 9 (May, 1966), 366-371.

I. Vaduva, Sisteme informatice, Tipografia Universitatii Bucuresti, 1981.

Gh. Barbu, I. Vaduva, M. Bolosteanu, Bazele Informaticii, Editura Tehnica, 1995.