SUPORT DE CURS

ANUL II

Semestrul 2

Cluj–Napoca 2010

UNIVERSITATEA BABE Ş-BOLYAI, CLUJ-NAPOCA Centrul de Formare Continuă şi Învăţământ la Distanţă Facultatea de Ştiin ţe Economice şi Gestiunea Afacerilor Specializarea: Informatică Economică Disciplina: Algoritmi și structuri de date

2

3

C U P R I N S I. INFORMAŢII GENERALE

I.1. Date de identificare ale cursului 5 I.1.1. Date de identificare despre titularul de curs 5 I.1.2. Date de identificare curs şi contact tutori 5

I.2. Condiţionări şi cunoştinţe prerechizite 5 I.3. Descrierea cursului 5 I.4. Organizarea temelor din cadrul cursului 5

I.5. Materiale bibliografice obligatorii 6 I.6. Materiale şi instrumente necesare pentru curs 6 I.7. Calendar al cursului 6 I.8. Politica de evaluare şi notare 7

I.9. Elemente de deontologie academică 7 I.10. Studenţi cu dizabilităţi 7 I.11. Strategii de studiu recomandate 7 SUPORTUL DE CURS PROPRIU-ZIS:

MODULUL 1: INTRODUCERE ÎN ALGORITMI; ALGORITMI NUMERICI; REZOLVAREA NUMERICĂ A ECUAŢIILOR ALGEBRICE șI TRANSCENDENTE; CALCUL MATRICIAL 8 1.1. Scurt istoric al algoritmilor 8 1.2. Noţiunea de algoritm; caracteristici 9 1.3. Reprezentarea algoritmilor 12 1.4. Structuri de control 14 1.5. Rezolvarea numerică a ecuaţiilor algebrice sau transcendente 17 1.6. Calcul matricial 22 1.7. Rezolvarea sistemelor de ecuaţii algebrice liniare 25 1.8. Probleme propuse 30 MODULUL 2: ALGORITMI DE SORTARE 35 2.1. Timpul de execuţie și complexitatea unui algoritm 35 2.2. Noţiuni despre sortare 37 2.3. Metode de sortare care nu iau în considerare structura şi valorile cheilor 38 2.4. Metode de sortare care ţin cont de valorile cheilor 47 2.5. Metode de sortare care folosesc baze de numeraţie 48 2.6. Metode de sortare externă 50 MODULUL 3: TEHNICI DE PROGRAMARE 54 3.1. Recursivitatea 54 3.2. Tehnici de programare 56 MODULUL 4: STRUCTURI DE DATE 67 4.1. Aspecte generale 67 4.2. Fișierul 69 4.3. Tabloul 70

4

4.4. Tabela de dispersie 71 4.5. Lista liniară simplu înlănţuită 72 4.6. Lista liniară circulară simplu înlănţuită 74 4.7. Lista liniară dublu înlănţuită 74 4.8. Structura de tip stivă (LIFO Last In First Out) 75 4.9. Structura de tip coadă 76 4.10. Grafuri neorientate 77 4.11. Grafuri orientate 81 4.12. Arbori 85

5

INFORMA ŢII GENERALE I.1. Date de identificare ale cursului I.1.1. Date de identificare despre titularul de curs Nume: Lect. univ. dr. Cristian Bologa Cabinet: str. Th. Mihali, Nr. 58-60, Cluj-Napoca, Cabinet 436 Telefon: 0264-418652 Fax: 0264-412570 E-mail: cristian.bologa@econ.ubbcluj.ro I.1.2. Date de identificare curs şi contact tutori

Numele cursului: Algoritmi și structuri de date Codul cursului: EBS0080 Anul, Semestrul: Anul II, Semestrul 2 Tipul cursului: Obligatoriu Tutori: Lect. dr. Bologa Cristian Consultaţii: conform orarului afişat la începutul semestrului. I.2. Condiţionări şi cunoştin ţe prerechizite

Înscrierea la acest curs nu este condiţionată de parcurgerea altor discipline. Cu toate acestea, cunoştinţele dobândite prin aprofundarea disciplinei facultative „Introducere în programarea calculatoarelor”, sporesc considerabil abilităţile studenţilor la acest curs.

I.3. Descrierea cursului Cursul vizează următoarele aspecte: a) Insuşirea gândirii algoritmice; b) Descrierea algoritmilor folosind scheme logice sau pseudocod c) Codificarea utilizând limbajul C d) Cunoaşterea algoritmilor fundamentali şi a algoritmilor de sortare e) Insuşirea tehnicilor de programare f) Insuşirea utilizării principalelor structuri de date. I.4. Organizarea temelor din cadrul cursului

Parcurgerea acestei discipline va presupune atât întâlniri faţă în faţă, cât şi muncă individuală. Astfel, metodele utilizate pe parcursul predării cursului sunt: expunerea teoretică, prin mijloace auditive şi vizuale; explicaţia abordărilor conceptuale; rezolvări de probleme; răspunsuri directe la întrebările studenţilor. În ceea ce priveşte activitatea cursanţilor, se va încuraja participarea activă a studenţilor prin

6

problematizarea informaţiilor prezentate, implicarea în rezolvarea problemelor propuse; găsirea de soluţii alternative la problemele propuse.

Studentul are libertatea de a-şi gestiona singur, fără constrângeri, modalitatea şi timpul de parcurgere a cursului. Este însă recomandată parcurgerea succesivă a modulelor prezentate în cadrul suportului de curs, în ordinea indicată şi rezolvarea sarcinilor sugerate la finalul fiecărui modul.

I.5. Materiale bibliografice obligatorii [Bologa06] Bologa Cristian –Algoritmi şi structuri de date, Editura Risoprint, 2006. [Giumale96] Giumale C., Negreanu L., Călinoiu S., -Proiectarea şi analiza algoritmilor. Algoritmi de Sortare, ed. ALL, Bucuresti, 1996 [Negrescu01] Negrescu Liviu, -Limbajele C şi C++ pentru începători. Vol. 1 şi 2. Ed. Microinformatica, Cluj-Napoca, 1994 (reeditate 2001) Bibliografia suplimentară [Aho83] Aho A, Hopcroft J, Ullman J– Data Structures and Algorithms, Addison Wesley, 1983 [Cormen00] Cormen, Th.; Leiserson Ch; Rivest, R. -Introducere în Algoritmi, Ed Agora 2000 (traducere) [Knuth99] Knuth - Arta programării calculatoarelor, vol, 1, 2, 3, ed. Teora, 1999 (traducere) I.6. Materiale şi instrumente necesare pentru curs

În vederea participării la un nivel optim la activităţile cursului, este recomandat ca studenţii să aibă acces la următoarele resurse:

- calculator conectat la internet (pentru a putea accesa conţinutul cursului şi pentru a putea participa interactiv pe parcursul derulării acestuia);

- un mediu de programare ce utilizează un compilator C sau C++ I.7. Calendar al cursului Activit ăţi Tematica abordată Responsabilităţile

studenţilor Locul de desfăşurare

Întâlnire I: Activit ăţi didactice

Modulul 1 – Introducere în algoritmi; algoritmi numerici; rezolvarea numerică a ecuaţiilor algebrice și transcendente; calcul matricial

Parcurgerea bibliografiei. Rezolvarea de teme practice.

Va fi comunicat ulterior

Întâlnire II: Activit ăţi didactice

Modulul 2 – Algoritmi de sortare Modulul 3 – Tehnici de programare

Parcurgerea bibliografiei. Rezolvarea de teme practice.

Va fi comunicat ulterior

Întâlnire III: Activit ăţi didactice

Modulul 4 – Structuri de date Parcurgerea bibliografiei. Rezolvarea de teme practice.

Va fi comunicat ulterior

Examen final Susţinerea probei teoretice Susţinerea probei practice

Va fi comunicat ulterior

7

Calendarul activităţilor este unul orientativ, fiind susceptibil unor modificări ulterioare, acestea urmând să fie comunicate studenţilor. I.8. Politica de evaluare şi notare Evaluarea studenţilor se va efectua conform detalierii de mai jos: Nota aferentă părţii teoretice se compune din: -nota de la testul grilă din limbajul C, care va fi sustinut conform programării examinării intermediare(50%) -nota de la examenul scris din sesiunea de examene, care va consta dintr-un set de întrebari din materia predată la curs (50%) Nota aferentă părţii practice se compune din: -nota de la testul practic sustinut conform programării examinării intermediare (50%) -nota de la examenul practic sustinut în sesiunea de examene (50%) Ambele probe practice se vor susţine practic, la calculator, subiectele vor conţine câte o problemă care va fi rezolvată în limbajul C Nota finală va fi compusă din 2 componente egale, fiecare cu o pondere de 50% în nota finală: -nota aferentă părţii teoretice -nota aferentă părţii practice Promovarea examenului este condiţionată de obţinerea notei 5 la fiecare dintre cele 2 componente. I.9. Elemente de deontologie academică

Se aplică regulile generale de deontologie academică din UBB. I.10. Studenţi cu dizabilităţi În principiu pentru cursanţii cu dizabilităţi care nu se pot deplasa la sediul facultăţii se aplică 3 soluţii esenţiale:

• utilizarea Internet-ului şi a portalului după aceleaşi reguli ca la ceilalţi cursanţi; • utilizarea la nevoie a unui sistem webcam şi skype în cazul evaluărilor. • deplasarea la nevoie a titularului de curs la cerinţa cursantului la locaţia unde se

afla acesta. I.11. Strategii de studiu recomandate

Se recomandă parcurgerea sistematică a modulelor cuprinse în cadrul cursului, punându-se accent pe pregatirea individuală continuă a studenţilor şi pe evaluările formative pe parcursul semestrului. Se recomandă cursanţilor alocarea unui număr de cel puţin 6 ore săptâmânal pentru parcurgerea şi însuşirea cunoştinţelor necesare promovării cu succes a acestei discipline.

8

II. SUPORTUL DE CURS PROPRIU-ZIS

MODULUL NUM ĂRUL 1

NOȚIUNI DESPRE SISTEMELE INFORMA ȚIONALE ȘI SISTEMELE INFORMATICE

OBIECTIVE: Obiectivul primului modul este familiarizarea cu conceptul de

algoritm, cu structurile de bază din programarea structurată precum și crearea abilităţii de descriere a unui algoritm numeric utilizând scheme logice. In acest modul se vor elabora schemele logice ale principalelor metode de rezolvare a unei ecuaţii algebrice sau transcendente, inversa unei matrici precum și rezolvarea unui sistem de n ecuaţii cu n necunoscute. Algoritmii elaboraţi vor fi implementaţi apoi în limbajul C.

NOŢIUNI CHEIE Algoritm, program, pseudocod, schemă logică, structura secvenţială, structura alternativă, structura repetitivă, calcul matricial, rezolvarea unui sistem de n ecuaţii și n necunoscute

REZULTATE AŞTEPTATE:

Ca obiective, se vor atinge următoarele aspecte: -Insuşirea gândirii algoritmice; dezvoltarea deprinderii de elaborare a unui algoritm pentru a anumită problemă propusă. -Descrierea algoritmilor folosind scheme logice sau pseudocod -Codificarea algoritmilor utilizând limbajul C

1.1. Scurt istoric al algoritmilor

Algoritmii sunt cel mai statornic domeniu din lumea informaticii; mulţi algoritmi au rămas neschimbaţi în ultimii 50-60 de ani (bazele unora datând de câteva mii de ani), în timp ce limbajele de programare, tehnica de calcul, etc., au avut salturi uriaşe. Cea mai bună carte de programare: "The Art of Computer Programming", scrisă de D. E. Knuth, profesor în SUA a apărut pentru prima oară în anul 1968, la editura Addison Wesley, fiind tradusă în limba română la Editura Tehnică în 1974 sub titlul de "Tratat de programarea calculatoarelor". În anul 1998, cartea a fost reeditată tot la editura Addison Wesley, fiind tradusă apoi în 2000 la editura Teora sub titlul "Arta programării calculatoarelor". Modificările între cele două versiuni sunt minore, în timp ce tehnica de calcul a evoluat exponenţial. Bill Gates a afirmat că “Dacă te crezi un bun programator, citeşte Arta programării calculatoarelor a lui Knuth. Dacă poţi citi toată cartea, trimite-mi neapărat un CV”.

Cuvântul algoritm provine din pronunţia fonetică a numelui unui mare matematician persan pe nume Abu Ja`far Mohammed ibn Musa al-Khowarizmi (780-850). “Algorithm” provine de la “al-Khowarizmi”, ceea ce literal înseamnă “din orasul Khowarizm”. În prezent, acest oraş se numeşte Khiva şi se află în Uzbechistan. Acesta a folosit pentru prima dată reguli precise şi clare pentru a descrie procese de calcul

9

(operaţii aritmetice fundamentale) în opera sa “Scurtă carte despre calcul algebric”. Mai târziu, această descriere apare sub denumirea de algoritm în « Elementele lui Euclid » . Algoritmul lui Euclid pentru calculul celui mai mare divizor comun a două numere naturale este primul algoritm cunoscut în matematică. În timpul lui Adam Riese (sec XVI) se foloseau algoritmi pentru dublarea, înjumătăţirea sau înmulţirea unor numere. Alţi algoritmi apar în lucrările lui Stifer (1544) şi Cardano (1545). Chiar şi Leibnitz vorbeşte de algoritmi « de înmulţire ». Kronecker (1886) şi Dedekind (1888) dau naştere teoriei funcţiilor recursive care devine un concept important în teoria algoritmilor. De abia în deceniul trei şi patru al secolului XX teoria recursivităţii şi a algoritmilor prinde contur prin lucrările lui Skolem, Ackermann, Sudan, Godel, Church, Kleene, Turing etc. 1.2. Noţiunea de algoritm; caracteristici

Un algoritm este o noţiune fundamentală în informatică şi de aceea înţelegerea acsetui concept este esenţială.

Odăgescu [Odăgescu91] dă următoarea definiţie: "Un algoritm poate fi definit ca o funcţie f: D → F, unde F este mulţimea informaţiilor finale, iar D este mulţimea informaţiilor ini ţiale".

În [Apostol93] noţiunea de algoritm este definită astfel: “Algoritmul desemnează o mulţime exhaustivă şi univoc determinată de operaţii, împreună cu succesiunea în care trebuie aplicate asupra datelor iniţiale ale problemei, pentru a obţine soluţia. El este considerat mod de prezentare a procesului de rezolvare a problemelor şi suport după care se realizează programul“. “Soluţia unei probleme, din punct de vedere informatic, este dată printr-o mulţime de comenzi (instrucţiuni) explicite şi neambigue, exprimate intr-un limbaj de programare. Aceasta mulţime de instrucţiuni prezentată conform anumitor reguli sintactice formează un program. Un program poate fi privit şi ca un algoritm exprimat intr-un limbaj de programare. Totuşi, un algoritm descrie soluţia problemei independent de limbajul de programare în care este redactat programul”.

În [Albeanu00] un algoritm este descris astfel: “Prin algoritm vom înţelege o secvenţă finită de comenzi explicite şi neambigue care executate pentru o mulţime de date(ce satisfac anumite condiţii ini ţiale, conduce în timp finit la rezultatul corespunzător.”

Un algoritm este un instrument de rezolvare a unei probleme, fiind o succesiune

bine precizată de prelucrări care aplicate asupra datelor de intrare permit obţinerea în timp finit a soluţiei acesteia. Un algoritm este compus dintr-o mulţime finită de paşi, fiecare necesitând una sau mai multe operaţii. Pentru a fi implementabile pe calculator, aceste operaţii trebuie să fie definite, adică să fie clar ce anume trebuie executat şi să fie efective, adică o persoană dotată cu creion şi hârtie trebuie să poată efectua orice pas într-un timp finit. De exemplu, aritmetica cu numere întregi este efectivă. Aritmetica cu numere reale nu este efectivă, deoarece unele numere sunt exprimabile prin secvenţe infinite.

Un algoritm nu operează numai cu numere. Pe lângă algoritmii numerici există şi algoritmi algebrici şi algoritmi logici. Până şi o reţetă culinară, utilizarea unui telefon public sau a unui bancomat sunt în esenţă algoritmi. Practic în orice domeniu găsim

10

operaţii care se desfăşoară algoritmic dar nu orice problemă poate fi rezolvată algoritmic.

Sintetic, un algoritm şi un program pot fi definite astfel :

Program = exprimarea într-un limbaj de programare a unui algoritm Algoritm = exprimarea într-un limbaj de reprezentare a unui raţionament

Un program este o descriere precisă şi concisă a unui algoritm într-un limbaj de

programare. De aceea, noţiunile de « algoritm » şi « program » se folosesc uneori greşit ca sinonime.

Un program nu trebuie să satisfacă condiţia de finititudine precum un algoritm. De exemplu, un sistem de operare care se opreşte doar la închiderea calculatorului.

Algoritmizarea este o cerinţă fundamentală în rezolvarea oricărei probleme cu

ajutorul calculatorului. Experienţa a demonstrat că nu orice problemă poate fi rezolvată prin algoritmizarea rezolvării , adică prin descrierea unui algoritm de rezolvare. Atfel problemele se pot împărţi în 2 clase: clasa problemelor decidabile (o problemă este decidabilă dacă există un algoritm pentru rezolvarea ei) şi clasa problemelor nedecidabile (o problemă este nedecidabilă dacă nu există un algoritm pentru rezolvarea ei).

Există probleme care au apărut ulterior apariţiei calculatoarelor. Astfel a apărut “problema celor 4 culori” conform căreia orice hartă poate fi colorată folosind patru culori, astfel încât oricare două ţări cu frontiere comune să fie colorate diferit. Enunţarea problemei a fost făcută în anul 1852 de studentul englez Francis Guthri; problema a fost rezolvată în anul 1977 doar prin utilizarea calculatorului şi prin utilizarea unei metode noi (metoda Backtracking).

Există algoritmi cu caracter general, pentru clase largi de probleme şi algoritmi specifici unor probleme anume. Principalele categorii de algoritmi cu caracter general sunt: algoritmi de împărţire în subprobleme (“Divide et Impera”), algoritmi de căutare cu revenire (“Backtracking”), algoritmi de optim local (“Greedy”), algoritmi de programare dinamică etc.

Principalele caracteristici ale unui algoritm sunt:

-generalitatea – algoritmul trebuie să fie cât mai general astfel ca să rezolve o clasă cât mai largă de probleme şi nu o problemă particulară sau punctuală. El trebuie să poată fi aplicat oricărui set de date iniţiale ale problemei pentru care a fost întocmit. De exemplu algoritmul de rezolvare a ecuaţiei de gradul II ax2+bx+c=0 trebuie să rezolve toate cazurile pentru o mulţime infinită de date de intrare (a, b şi c aparţinând numerelor reale).

-claritatea– acţiunile algoritmului trebuie să fie clare, simple şi riguros specificate. Un algoritm trebuie să descrie cu precizie ordinea operaţiilor care se vor efectua.

-finitudinea –un algoritm trebuie să admită o descriere finită şi să conducă la soluţia problemei după un număr finit de operaţii. Orice metodă (algoritm) aplicat trebuie să conveargă spre soluţia problemei. în timp ce metoda matematică este corectă chiar dacă ea converge către soluţie doar la infinit, un algoritm trebuie să întoarcă rezultatul după un număr finit de paşi. Acolo unde matematica nu oferă o

11

demonstraţie, nici un algoritm nu va fi capabil să o ofere. De exemplu, pentru e verifica corectitudinea Conjecturii lui Goldbach: “Orice număr par se scrie ca sumă de două numere prime”, s-a putut uşor scrie un algoritm şi deşi programul elaborat a fost lăsat să ruleze pînă la valori extrem de mari, fără să apară nici un contra-exemplu, totuşi conjectura n-a putut fi astfel infirmată (dar nici demonstrată).

-corectitudinea – un algoritm trebuie să poată fi aplicat şi să producă un rezultat corect pentru orice set de date de intrare valide. De asemenea, un algoritm trebuie să prevadă modul de soluţionare a tuturor situaţiilor posibile care pot apare în rezolvarea unei probleme date. Principiul conform căruia “Errare humanum est” nu se aplică în cazul algoritmilor, aceştia nu vor greşi şi nu se vor plictisi niciodată şi vor duce programul la sfârşit indiferent de câte ori li se va cere. Orice eroare a unui program are în spate fie o greşeală în algoritm fie o transcriere eronată a algoritmului în programul elaborat pe baza lui. Corectitudinea este de 2 feluri: corectitudine totală (faptul că pentru orice date de intrare algoritmul determină valori corecte de ieşire) şi parţială (finititudinea algoritmului pentru orice set de date de intrare). Verificarea corectitudinii unui algoritm se poate face folosind:

- varianta experimentală prin testarea algoritmului pentru diverse instanţe ale problemei. Avantajul acestei variante îl constituie simplitatea iar dezavantajul îl constituie faptul că testarea nu poate acoperi întotdeauna toate variantele posibile de date de intrare

- varianta analitică se bazează pe demonstrarea funcţionării corecte a algoritmului pentru orice date de intrare, garantând astfel corectitudinea. Uneori este dificil de găsit o demonstraţie. Abordarea analitică conduce la o mai bună înţelegere a algoritmului şi la identificarea secventelor ce conţin eventuale erori. Demonstrarea analitică a corectitudinii unui algoritm presupune parcurgerea a 3 paşi: a)Identificarea precondiţiilor problemei (proprietăţile datelor de intrare) b)Identificarea postcondiţiilor problemei (proprietăţile rezultatelor) c)Demonstrarea faptului că pornind de la precondiţii şi aplicând prelucrările specificate în algoritm ajungem la satisfacerea postcondiţiilor

-performanţa – algoritmul trebuie să fie eficient privind resursele utilizate şi anume să utilizeze memorie minimă şi să se termine într-un timp minim.

-robusteţea – reprezintă abilitatea algoritmului de a recunoaşte situaţiile în care problema ce se rezolvă nu are sens şi de a se comporta în consecinţă (de exemplu, prin mesaje de eroare corespunzătoare). Un algoritm robust nu trebuie să fie afectat de datele de intrare eronate.

Este posibil ca pentru rezolvarea unei probleme să existe mai mulţi algoritmi. În

aceste cazuri, la alegerea algoritmului se ţine seama de diverse criterii cum ar fi: viteza de calcul, mărimea erorilor de calcul, spaţiul de memorie internă a calculatorului necesar programului corespunzător algoritmului, etc. De regulă, nu putem construi un algoritm care să satisfacă toate criteriile de performanţă. De aceea, se alege algoritmul care răspunde cel mai bine cerinţelor care se impun. În cadrul activităţii de cercetare şi elaborare de software din domeniul tehnologiei informaţiei este determinantă elaborarea, testarea şi implementarea de algoritmi cât mai performanţi.

12

1.3. Reprezentarea algoritmilor Algoritmii pot fi specificaţi:

• În limbaj natural • Pseudocod • Scheme logice • Diagrame arborescente • Tabele de decizie

Pseudocod

Limbajul pseudocod are o sintaxă şi semantică asemănătoare limbajelor de programare moderne, având o anumită flexibilitate în ceea ce priveşte sintaxa, în ideea că prin codificarea unui algoritm într-un limbaj de programare, operaţia să fie cât mai comodă. Semantica pseudocodului este apropiată de limbajele de programare utilizând însă cuvinte şi expresii uzuale din limbajul natural. Practic pseudocodul este un compromis între precizia unui limbaj de programare şi uşurinţa în exprimare a unui limbaj natural.

În dicţionarul de informatică pseudocodul este definit ca « limbaj utilizat în proiectarea şi documentarea programelor obţinut prin grefarea unor reguli sintactice pe limbajul natural. Structurile de control sunt reprezentate prin folosirea unor cuvinte cheie (dacă … atunci … altfel … execută … până când etc) şi printr-o anumită aliniere în pagină a liniilor ».

Limbajul pseudocod are două tipuri de propoziţii: propoziţii standard (corespund structurilor de control care vor fi prezentate în continuare) şi propoziţii nestandard (texte ce conţin părţi ale algoritmului încă incomplet elaborate, nefinisate). Comentariile în pseudocod se includ între acolade. Propoziţiile standard încep cu cuvinte cheie şi fie se scriu cu litere mari, fie se subliniază.

Pseudocodul este destul de flexibil, neexistând restricţii de definire a formei. Practic oricine poate crea un astfel de limbaj cu condiţia să utilizeze structuri de bază suficiente pentru a descrie orice algoritm. Pseudocodul reprezintă o metodă convenţională de notare şi exprimare a algoritmilor cu o sintaxă maleabilă ceea ce conduce la uşurinţa în descrierea şi înţelegerea algoritmului.

Scheme logice Prin schemă logică se înţelege o reprezentare grafică a unui algoritm în care fiecărui pas i se ataşează un simbol denumit bloc. Ordinea de parcurgere a blocurilor în schemele logice se precizează cu ajutorul săgeţilor. Simbolurile folosite în schemele logice au fost standardizate prin standardul X35 aprobat de ANSI (American National Standard Institute) în 1970, conform cu recomandările R1028/1969 ale ISO (International Standard Organization).

Într-o schemă logică se utilizează următoarele tipuri de blocuri: Blocul delimitator are forma unei elipse alungite şi marchează începutul

(START) sau sfârşitul (STOP) unei scheme logic. Acest tip de bloc mai poate specifica

13

începutul şi sfârşitul unei proceduri (subprogram), specificându-se în acest caz în interiorul său numele procedurii şi parametrii de intrare şi cei de ieşire. Sfârşitul procedurii este marcat printr-un bloc delimitator ce conţine cuvântul RETURN.

Fig. 1.1. Blocuri delimitatoare

Blocul de intrare/ ieşire are forma unui paralelogram sau a unui trapez. Acest

bloc se foloseşte la citirea datelor de intrare ale algoritmului şi afişarea rezultatelor.

Fig.1.2. Blocuri de intrare/ieşire

Blocul de calcul marchează calculul unor expresii şi atribuirea rezultatelor obţinute unor variabile. În blocurile de acest tip apar comenzi de forma:

v=e unde v este o variabilă, iar e este o expresie de tip compatibil cu v. Se evaluează expresia e, se converteşte dacă este cazul valoarea lui e la o valoare de tipul lui v iar valoarea obţinută este memorată în variabila v, vechea valoare pierzându-se. Observaţie: variabila poate apărea şi în expresie. De exemplu, i=i+1.

Fig 1.3. Blocul de calcul

Uneori în locul simbolului “=” pentru atribuire se folosesc simbolurile “:=” sau “←“.

Blocul de decizie are forma unui romb. El pune în evidenţă etapele de decizie sau punctele de ramificaţie ale algoritmului. Se evaluează condiţia: dacă este adevarată se continuă cu ramura având indicativul da, altfel cu ramura nu.

14

Fig. 1.4. Blocul de decizie

Blocul conector are formă de cerc. El se foloseşte pentru a conecta diferite

secvenţe ale unei scheme logice. Sunt utile atunci când se continuă descrierea algoritmului pe mai multe pagini. Pentru identificarea blocurilor perechi, în interiorul acestora se trece acelaşi număr. 1.4. Structuri de control

În anul 1968, matematicianul olandez Dijkstra a iniţiat cercetări în domeniul elaborării unei metodologii de elaborare a schemelor logice. La baza cercetărilor lui Dijkstra a stat o teoremă de structură a lui Bohm şi Jacopini. Această teoremă afirmă că orice schemă logică care are un singur punct de intrare şi un singur punct de ieşire poate fi reprezentată cu ajutorul a trei structuri de bază şi anume: -structura secvenţială (liniară) -structura alternativă - structura repetitivă

O schemă logică construită numai cu structuri de acest tip este numită schemă logică structurată. În anii ’70 a apărut conceptul de programare structurată fiind dezvoltat de E.W. Dijkstra în lucrările sale iar ulterior de N. Wirth şi C.A.R. Hoare. Un algoritm structurat conţine doar cele 3 structuri enumerate mai sus.

Structura secvenţială Cea mai simplă structură întâlnită în schemele logice este structura secvenţială.

Această structură reprezintă un proces de calcul format dintr-o operaţie elementară, cum este citirea unei valori sau o operaţie de atribuire, dar poate fi şi o combinaţie de alte structuri. Structura secvenţială indică execuţia succesivă a operaţiilor de bază şi a structurilor de control în ordinea în care apar în schema logică; în general, orice schemă logică cuprinde secvenţele:

• citirea datelor • iniţializarea variabilelor • prelucrări • tipărirea rezultatelor

Fig. 1.5. Structura secvenţială

15

Structura alternativă În funcţie de valoarea de adevăr a condiţiei, se execută una din secvenţe, după

care se trece la prelucrarea următoare; cele două ramuri se exclud mutual; este posibil ca una din ramuri sa fie vidă.

Fig. 1.6. Structura alternativă

Structura repetitivă cu condiţionare anterioară (WHILE-DO) Secvenţa se execută ciclic, cât timp condiţia este adevarată; dacă la prima

evaluare a condiţiei, aceasta este falsă, corpul nu se execută niciodată. În cadrul secvenţei A este necesar să se modifice valoarea unei variabile care să afecteze valoarea de adevăr a expresiei c. În caz contrar, vom ajunge la un ciclu infinit.

Fig. 1.7. Structura repetitivă cu condiţionare anterioară

Cele 3 structuri prezentate (secvenţială, alternativă şi repetitivă cu condiţionare

anterioară) sunt denumite structuri de bază. Orice algoritm poate fi reprezentat folosind cele 3 structuri de bază. În continuare prezentăm încă 2 tipuri de structuri, care sunt folosite în practică, dar care au la bază şi deci pot fi înlocuite de structurile de bază.

Structura repetitivă cu condiţionare posterioară (DO-UNTIL) Condiţia se evaluează dupa o primă execuţie a secvenţei (deci secvenţa se

execută cel puţin o dată); se revine la execuţia secventei, dacă nu este adevărată. Dacă condiţia este adevărată se încheie această secvenţă.

16

Fig. 1.8. Structura alternativă cu condiţionare posterioară

Structura repetitivă cu un număr cunoscut de paşi (DO-FOR) O variabilă numită generic contor, controlează ciclarea; contorul se iniţializează

cu o valoare iniţială (vali), iar ciclarea se realizează cât timp contor<=valf, o valoare finală; la sfârşitul corpului ciclului, variabila contor este actualizată, fiind mărită cu o valoare pas; pentru a nu se cicla la infinit, trebuie ca pas>0. Structura se poate folosi şi cu o valoare finală mai mică decât cea iniţială, caz în care avem pas<0. Această structură este o particularizare a structurii WHILE-DO.

Fig. 1.9. Structura repetitivă cu număr cunoscut de paşi

17

1.5. Rezolvarea numerică a ecuaţiilor algebrice sau transcendente

Separarea rădăcinilor

O ecuaţie de forma: f(x)=0, unde f:R→R se numeşte algebrică dacă funcţia f(x) este un polinom sau poate fi adusă la formă polinomială.

Dacă o ecuaţie nu este algebrică ea este transcendentă. De exemplu, ecuaţiile:

x+sin(x) = 0 ex – 1 = 0 sunt transcendente.

În general, pentru ecuaţiile algebrice sau transcendente nu se pot aplica metode

exacte de rezolvare. Dacă: f:[x min,xmax] →R, unde [xmin,xmax]∈R

orice valoare α pentru care f(α)=0 se numeşte rădăcină a ecuaţiei. O rădăcină aproximativă a ecuaţiei se înţelege o valoare β apropiată de valoarea exactă α, astfel încât fiind dată eroarea ε avem | x – x~ | < ε, unde ε∈R, ε>0. Determinarea rădăcinilor reale ale ecuaţiei f(x)=0 se face în 2 etape:

o separarea (izolarea) rădăcinilor adică stabilirea unei partiţii xmin<x1<x2<…<xM<xmax astfel încât orice subinterval [xi, xi+1] să conţină cel mult o rădăcină a ecuaţiei f(x)=0

o determinarea aproximativă a fiecărei rădăcini şi evaluarea erorii

O metodă de separare a rădăcinilor se bazează pe teorema lui Rolle. Această teoremă afirmă că între două rădăcini reale consecutive ale ecuaţiei f’(x)=0 există cel mult o rădăcină reală a ecuaţiei f(x)=0.

Dacă se pot determina rădăcinile x1,x2,… xM rădăcinile ecuaţiei f’(x)=0 atunci se poate forma şirul lui Rolle:

f(-∞), f(x1), f(x2), … f(xM), f(∞) În fiecare interval: (-∞,x1),(x1,x2),…(xi,xi+1), …(xM, ∞)

se află o rădăcină reală a ecuaţiei f(x)=0 dacă şi numai dacă funcţia f ia valori contrare la capetele intervalului adică dacă f(xi)⋅f(x i+1)<0. Această metodă deseori nu se poate aplica deoarece rezolvarea ecuaţiei f’(x)=0 este la fel de dificilă precum rezolvarea ecuaţiei f(x)=0. În schimb următoarea teoremă este des utilizată pentru separarea rădăcinilor unei ecuaţii.

18

Dacă o funcţie continuă f(x) admite valori de semn contrar la capetele unui interval [a,b], adică f(a)⋅f(b)<0 atunci în intervalul [a,b] se găseşte cel puţin o rădăcină a ecuaţiei f(x)=0 (mai precis un număr impar de rădăcini). Metodele de rezolvare a ecuaţiilor neliniare au un caracter iterativ şi se împart în două categorii:

o metode de partiţionare –se porneşte de la un interval în care se găseşte soluţia, iar acest interval se îngustează treptat, până la atingerea unei precizii date. Convergenţa acestor metode este garantată dar este mai lentă.

o metode de aproximare succesivă –se porneşte de la o aproximare iniţială, care se îmbunătăţeşte în paşi succesivi. Dacă procesul este convergent, vom putea obţine o soluţie aproximativă ce să atingă o precizie dată.

Metoda înjumătăţirii intervalului (a bisec ţiei sau dihotomiei) Metoda înjumătăţirii intervalului este cea mai simplă dintre metodele de

rezolvare a ecuaţiilor algebrice sau transcendente. Se consideră ecuaţia f(x)=0 (algebrică sau transcendentă) unde f este continuă pe

intervalul [a,b] şi există o singură rădăcină în acest interval. În consecinţă:

f(a)⋅f(b)<=0

Y-A

xis

X-Axis

a

b

c=(a+b)/2

f(a)

f(c)

f(b)

noul c

Fig. 1.10. Metoda înjumătăţirii intervalului

1)Dacă f(a)=0 atunci x=a este soluţie. 2)Dacă f(b)=0 atunci x=b este soluţie. 3)Dacă f(a)⋅f(b)<0 vom alege c=(a/b)/2 mijlocul intervalului. -Dacă f(a)⋅f(c)<0 atunci soluţia este în intervalul [a,c] deci vom face atribuirea b=c şi reluăm algoritmul de la pasul 1 -Dacă f(c)⋅f(b)<0 atunci soluţia este în intervalul [b,c], vom face atribuirea a=c şi reluăm algoritmul de la pasul 1. 4)Algoritmul se opreşte când |a-b|<=ε (eroarea maximă admisibilă).

19

Observaţii:

Dacă sunt îndeplinite condiţiile ini ţiale ale problemei, această metodă sigur converge spre soluţia unică (aproximativă) a ecuaţiei.

Metoda este simplă dar are cele mai slabe proprietăţi de convergenţă. Metoda secantei (corzii)

Metoda secantei este utilizată, ca şi metoda înjumătăţirii intervalului pentru găsirea rădăcinii α aflată în intervalul [a,b] în cazul în care f(a)⋅f(b)<0.

Y-A

xis

X-Axis

a

bf(a)

f(xi)

f(b)

xi

Fig. 1.11. Metoda secantei

Se duce o secantă care uneşte punctele (ai,f(ai)) şi (bi,f(bi)). Dacă xi este punctul în care secanta intersectează axa ordonatelor, atunci putem scrie ecuaţia corzii:

)a(f)b(f

)a(f)x(f

ab

ax

ii

ii

ii

ii

−−

=−−

şi având în vedere că f(xi)=0 vom obţine:

)a(f)b(f

)a(fb)b(fax

ii

iiiii −

−=

Metoda este identică cu cea a înjumătăţirii intervalului, dar în loc să folosim

mijlocul intervalului vom folosi punctul în care secanta care trece prin (ai,f(ai)) şi (bi,f(bi)) intersectează axa ordonatelor.

o Dacă f(ai)⋅f(x i)<=0 atunci soluţia este în intervalul [ai,xi] şi bi ← xi o Dacă f(xi)⋅f(bi)<=0 atunci soluţia este în intervalul [xi,bi] şi ai ← xi

20

Identic, algoritmul se opreşte în momentul în care |ai-bi|<=ε. Metoda aproximaţiilor succesive (metoda contracţiei) Se presupune că ecuaţia algebrică sau transcendentă f(x)=0 are o singură rădăcină reală α în intervalul [a,b]. Ecuaţia se poate scrie:

f(x) + x – x = 0 x = f(x) + x Notând F(x) = f(x) + x, ecuaţia iniţială se poate scrie: x = F(x). Dacă α este rădăcină a ecuaţiei f(x)=0 atunci ea va fi rădăcină şi pentru ecuaţia

x=F(x). Considerăm o valoare x0 o valoare iniţială, aproximativă pentru rădăcina exactă

α. Înlocuind această valoare în membrul drept al ecuaţiei, se obţine o aproximaţie îmbunătăţită a rădăcinii:

x1=F(x0)

Repetând acest procedeu vom obţine un şir de iteraţii succesive: x1=F(x0), x2=F(x1), … xi+1=F(xi) Condiţia de convergenţă este următoarea: Presupunând că F(x) este derivabilă pe intervalul [a,b], şirul de iteraţii de mai sus converge dacă: |F’(x)| ≤ λ < 1, oricare ar fi x∈[a,b].

Algoritmul metodei aproximaţiilor succesive este următorul: 1. Se citesc aproximaţia iniţială x, precizia Eps si numărul maxim de iteraţii Nmax. 2. Se construieşte funcţia F(x) = x + f(x). 3. a)Se iniţializează contorul de iteraţii It ← 0; b)Dacă s-a atins precizia dorita (|f(x)|<Eps) sau numărul maxim de iteraţii (It=Nmax) se opreşte ciclarea şi se trece la pasul 4. c)Se trece la o noua iteraţie: It ← It+1; d)Calculul noii aproximaţii: x ← F(x) e)Se revine la pasul 3b 4. După ieşirea din bucla iterativă: a)Dacă |f(x)|<Eps atunci procesul a fost convergent iar soluţia aproximativă este x. b)Dacă |f(x)|>=Eps şi It=Nmax, se afişează mesajul "Depăşire număr maxim de iteraţii; proces divergent".

21

Metoda lui Newton (a tangentei) În acest caz, punctul faţă de care se stabileşte intervalul reprezintă intersecţia

tangentei dusă la curba y=f(x) cu axa ordonatelor. Fie x0 punctul în care se duce tangenta la y=f(x). Alegerea punctului x0 se face

astfel încât: f(x0)⋅f ’’ (x0)>0

aceasta asigurând apartenenţa lui x1 la intervalul [a,b].

Y

-Axi

s

X-Axis x0

f(x0)

x1

f(x1)

Fig. 1.12. Metoda lui Newton Putem scrie ecuaţia tangentei:

y-f(x0)=f’(x0)(x1-x0)

iar pentru y=0 (pe axa ordonatelor) obţinem:

)x(f

)x(fxx

0'

001 −=

Se duce o tangentă la y=f(x) în punctul de coordonate (x1,f(x1)) obţinând o nouă

aproximaţie x2. Procedeul se repetă ducând o tangentă la curba f(x) în punctul de coordonate (xi,f(xi)).

Astfel vom obţine un şir de aproximaţii:

)x(f

)x(fxx

i'

ii1i −=+ cu i=0,1,2, …

Se iterează până când eroarea absolută corespunzătoare unor aproximaţii consecutive xi şi xi+1 devine mai mică sau egală cu o eroare maximă admisibilă ε, impusă de utilizator:

|xi-xi+1|<=ε.

22

Metoda lui Newton este mai rapid convergentă decât metoda substituţiilor succesive. Condiţia este ca derivata funcţiei f(x) să nu fie prea complicată. 1.6. Calcul matricial Introducere în calculul matricial O matrice A de dimensiune m x n reprezintă un tablou având m linii şi n coloane astfel: a11 a12 … a1n a21 a22 … a2n … am1 am2 … amn Astfel matricea conţine elementele a(i,j), cu i=1,m şi j=1,n.

Transpusa matricii A se notează AT şi se face schimbând liniile cu coloanele. a11 a21 … am1 a12 a22 … am2 … a1n a2n … anm

O matrice la care numărul de linii este egal cu numărul de coloane este o matrice pătratică.

O matrice de tipul 1 x n (deci o linie şi n coloane) se numeşte matrice linie. O matrice de tipul m x 1 (deci m linii şi o coloană) se numeşte matrice coloană. O matrice se numeşte matrice nulă dacă toate elementele ei sunt egale cu 0. Elementele aij ale unei matrici pătratice A(n,n) pentru care i=j formează

diagonala principală a matricii. Elementele pentru care i+j=n+1 formează diagonala secundară a matricii.

O matrice pătratică se poate transpune simetrizând toate elementele faţă de diagonala principală. O matrice pătratică A este simetrică dacă şi numai dacă AT=A. O matrice pătratică este antisimetrică dacă şi numai dacă AT=-A adică aij=-aji, oricare ar fi i=1,n, j=1,n.

O matrice pătratică este superior triunghiulară dacă şi numai dacă aij=0, oricare ar fi i>=j.

O matrice pătratică este inferior triunghiulară dacă şi numai dacă aij=0, oricare ar fi i<=j.

O matrice pătratică este superior trapezoidală dacă şi numai dacă aij=0, oricare ar fi i>j.

O matrice pătratică este inferior trapezoidală dacă şi numai dacă aij=0, oricare ar fi i<j.

O matrice pătratică este diagonală dacă şi numai dacă aij=0, oricare ar fi i<>j. Dacă la o matrice diagonală aij=1, oricare ar fi i=j, atunci matricea este o matrice

unitate. O matrice pătratică este ortogonală dacă şi numai dacă A-1=AT adică A⋅AT=I

(unde I este matricea unitate). Se dau 2 matrici A(m,n) şi B(m,n). Cele două matrici sunt egale (şi se notează

A=B) dacă aij=bij, oricare ar fi i=1,m, j=1,n.

23

Se dau 2 matrici A(m,n) şi B(m,n). Matricea C(m,n) se numeşte suma matricilor A şi B dacă cij = aij + bij oricare ar fi i=1,m, j=1,n.

Pentru a înmulţi o matrice cu un scalar, se înmulţeşte fiecare element al matricei cu acel scalar. Produsul a două matrici Două matrici A(m,n) şi B(l,p) se pot înmulţi dacă numărul de coloane al primei matrici este egal cu numărul de linii al celei de a doua, deci dacă n=l. Dacă n=l atunci A(m,n)⋅B(l,p)=C(m,p).

o elementul c11 se obţine însumând produsele elementelor dintre prima linie a

matricii A cu prima coloană a matricii B, ∑=

=n

kkkbac

11111

o elementul c12 se obţine însumând produsele elementelor dintre prima linie a

matricii A cu a doua coloană a matricii B, ∑=

=n

kkkbac

12112

o formula generală pentru cij este ∑=

=n

kkjikij bac

1

pentru i=1,m şi j=1,p

Pentru produsul a 2 matrici pătratice, algoritmul necesită n3 înmulţiri şi (n-1)n2 adunări scalare.

Algoritmul în pseudocod este următorul: Citeşte m,n,p,A(m,n),B(n,p) Pentru i=1 la m execută Pentru j=1 la p execută c(i,j)=0; Pentru k=1 la n execută c(i,j)=c(i,j)+a(i,k)*b(k,j) Sf-pentru Sf-pentru Sf-pentru Afi şează C(m,p) Inversa unei matrici

Inversa unei matrici pătratice A, notată A-1 este matricea care îndeplineşte condiţia:

A⋅A-1=A-1⋅A=I (unde I este matrice unitate). O matrice este inversabilă dacă şi numai dacă determinantul asociat ei este

nenul. O astfel de matrice se numeşte nesingulară. Inversa unei matrici se poate calcula cu formula:

*1-

det

1= A

AA unde det A este determinantul matricei A iar A* este matricea adjunctă a

matricei A. Pentru a obţine matricea adjunctă se fac următoarele operaţii:

24

o Se obţine matricea transpusă AT a matricei A o Se calculează elementele matricii adjuncte a*

ij prin calcularea determinantului matricei ce se obţine prin eliminarea liniei i şi coloanei j, valoare ce se înmulţeşte cu (-1)i+j. Acest procedeu este greoi. De aceea, pentru a calcula inversa unei matrici se

foloseşte următoarea teoremă: Dacă printr-un şir finit de operaţii elementare o matrice se aduce la matricea unitate, atunci aplicând aceleaşi operaţii asupra unei matrici unitate, se va obţine matricea inversă. Prin operaţii elementare se înţelege:

o înmulţirea unei linii cu o constantă o schimbarea a 2 linii între ele o înmulţirea unei linii cu o constantă şi adunarea ei la o altă linie.

Pentru a calcula inversa unei matrici, extindem matricea la dreapta cu o matrice unitate. a11 a12 … a1n 1 0 ... 0 a21 a22 … a2n 0 1 ... 0 … ... an1 an2 … ann 0 0 ... 1 Pasul 1:

• Dacă a11=0 atunci căutăm un ai1<>0 pentru i=2,n. o Dacă nu se găseşte atunci se dă mesaj “Matrice neinversabilă” şi se

opreşte algoritmul. o Dacă se găseşte, se schimbă linia 1 cu linia i.

• Se împarte linia 1 cu a11 deci 11

1

1 =a

aa

j

j pentru i=1,2n (atenţie: toate operaţiile se

fac asupra matricei extinse). • Se înmulţeşte linia 1 cu ak1 şi se scade din linia k. Deci akj=akj-akj⋅a1j pentru

j=2,2n şi k=2,n. După pasul 1 matricea arată astfel: 1 a12 … a1n a1 n+1 a1 n+2 ... a1 2n

0 a22 … a2n a2 n+1 a2 n+2 ... a2 2n

… ... 0 an2 … ann an n+1 an n+2 ... an 2n

După pasul i-1 matricea arată astfel: 1 0 …0 ...a1i ... a1n a1 n+1 a1 n+2 ... a1 2n

0 1 …0 ...a2i ... a2n a2 n+1 a2 n+2 ... a2 2n

… ... 0 0 ...1 ...ai-1 i ... ai-1n ai-1 n+1 ai-1 n+2 ... ai-1 2n 0 0 ...0 ...ai i ... ai n ai n+1 ai n+2 ... ai 2n

... ... 0 0 …0 ...ani ... ann an n+1 an n+2 ... an 2n

Pasul i:

• Dacă ai i=0 atunci căutăm un aki<>0 pentru k=i+1,n.

25

o Dacă nu se găseşte atunci se dă mesaj “Matrice neinversabilă” şi se opreşte algoritmul.

o Dacă se găseşte, se schimbă linia i cu linia k.

• Se împarte linia i cu aii deci ii

ij

ij a

aa = pentru j=i+1,2n.

• Se înmulţeşte linia k cu aki şi se scade din linia k. Deci akj=akj-aki⋅aij pentru j=i,2n şi k=1,n-{i}.

După pasul n, partea stângă (matricea de inversat) a ajuns, în urma operaţiilor

elementare, la matricea unitate, iar partea dreaptă (care a pornit de la matricea unitate) constituie inversa matricei. 1.7. Rezolvarea sistemelor de ecuaţii algebrice liniare

Metodele de rezolvare a sistemelor de ecuaţii liniare pot fi împărţite în două

categorii: a)metode exacte (directe) -sunt algoritmi finiţi pentru calculul unor soluţii aşa zis exacte a sistemelor de ecuaţii liniare. Aici se pot menţiona: metoda lui Gauss, metoda lui Gauss-Jordan etc. O dată cu creşterea ordinului sistemului se pot acumula erorile de rotunjire, denaturând soluţiile. b)metode iterative –permit găsirea soluţiei sistemelor de ecuaţii liniare cu o anumită precizie într-un număr finit de paşi, pe baza unui proces iterativ convergent infinit. Există cazuri când metodele iterative nu converg. O metodă este iterativă dacă soluţia X se obţine astfel: k

kxX

∞→lim=

Fiecare iteraţie k se obţine pe baza a h iteraţii precedente: xk=Fk(xk-1, xk-2, … xk-h) Dacă F nu depinde de k atunci avem de-a face cu o metodă iterativă staţionară. Dacă h=1 adică xk=F(xk-1) atunci vorbim despre o metodă iterativă cu un singur nod.

Procesul este întrerupt după un număr finit de paşi în momentul atingerii unei anumite precizii date. Astfel de metode sunt metoda lui Jacobi şi metoda lui Gauss-Seidel.

Metoda lui Gauss Metoda lui Gauss constă în transformări elementare aplicate matricii sistemului şi şirului termenilor liberi, până la aducerea matricii sistemului la o formă superior trapezoidală, urmată apoi de substituirea succesivă, în sens invers, a necunoscutelor, obţinându-se astfel vectorul soluţiei.

26

Pornim de la următorul sistem de n ecuaţii cu n necunoscute: a11x1 + a12x2 + … + a1jxj + … +a1nxn=b1

…

ai1x1 + ai2x2 + … + aijxj + … +ainxn=bi … an1x1 + an2x2 + … + anjxj + … +annxn=bn Pasul 1:

• Dacă a11=0 căutăm un ai1<>0, pentru i=2,n. o Dacă nu găsim, tipărim un mesaj “Metoda lui Gauss nu se poate utiliza” şi oprim execuţia algoritmului

o Dacă am găsit un ai1<>0, atunci schimbăm linia 1 cu linia i între ele (inclusiv termenii liberi corespunzători).

• Pentru i=2,n, calculăm 11

11-←

a

aaaa

ij

ijij , pentru j=1,n. (deoarece prima linie este

înmulţită cu 11

i1

a

a- şi adunată la linia i). Astfel, se înmulţeşte prima linie cu

11

21

a

a- şi se adună la linia 2. Se înmulţeşte prima linie cu

11

31

a

a- şi se adună la linia

3 ş.a.m.d. până la ultima linie. • Având în vedere că operaţiile făcute asupra matricei sistemului trebuie efectuate

şi asupra vectorului termenilor liberi vom avea: 11

11-←a

abbb i

ii , pentru i=2,n.

Pasul i: Sistemul a ajuns la următoarea formă: a11x1 + a12x2 + … + a1ixi + … +a1nxn=b1

…

aiixi + … +ainxn=bi

ai+1ixi + … +ai+1nxn=bi+1 … anixi + … +annxn=bn

• Dacă aii=0 căutăm un aki<>0, pentru k=i+1,n. o Dacă nu găsim, tipărim un mesaj “Metoda lui Gauss nu se poate utiliza” şi oprim execuţia algoritmului

o Dacă am găsit un aki<>0, atunci schimbăm linia k cu linia j între ele (inclusiv termenii liberi corespunzători).

27

• Pentru k=i+1,n, calculăm ii

kiij

kjkj a

aaaa -← , pentru j=i,n. (deoarece linia i este

înmulţită cu ii

ki

a

a- şi adunată la linia k). Astfel, se înmulţeşte linia i cu

ii

1i+i

a

a- şi se

adună la linia i+1. Se înmulţeşte linia i cu ii

2i+i

a

a- şi se adună la linia i+2 ş.a.m.d.

până la ultima linie. • Având în vedere că operaţiile făcute asupra matricei sistemului trebuie efectuate

şi asupra vectorului termenilor liberi vom avea: ii

kiik a

abbb -←k , pentru k=i+1,n.

După pasul n sistemul arată astfel: a11x1 + a12x2 + … + a1ixi + … ………+a1nxn=b1

…

an-1n-1xn-1+an-1nxn=bn-1

annxn=bn

Rezolvarea sistemului se poate face astfel:

• nn

nn a

bx =

• 1-1-

1-1-1-

-=

nn

nnnnn a

xabx

• ii

n

jiji

i a

xab

x

∑1+i=j

-

= , pentru i=n-1,1

Prezentăm în continuare schema logică aferentă rezolvării unui sistem de n

ecuaţii şi n necunoscute folosind metoda lui Gauss:

28

START

CITESTE n,a,b

a(i,i)=0DA

“metoda lui Gauss nu se poate folosi”

NU

STOP

k=1

i=1

Cauta_pivot(i,k)

k<>0DA

Schimba_linii(i,k) NU

k<>0DA

Aplica_transf(i) NU

i=i+1

i<=n-1&&k

DA

Nu

a(n,n)=0

k=0

DA

NU

k=0DA NU

Determ_solutii()

x(i),i=1,n

Cauta_pivot(i,k)

k=i+1

a(k,i)<>0DA

Return(k)NU

k=k+1

k<=n

NU

Return(0)

Schimba_linii(i,k)

j=i+1

a(i,j)<-> a(k,j)

j=j+1

j<=n

DA

b(i)<-> b(k)

Return

Aplica_transf(i)

k=i+1

P=a(k,i)/a(i,i)

j=i

a(k,j)=a(k,j)-a(i,j)*p

j=j+1

j<=n

DA

b(k)=b(k)-b(i)*p

k=k+1

k<=n

DA

Return

Determ_solutii()

X(n)=b(n)/a(n,n)

i=n-1

s=0

j=i+1

s=s+a(i,j)*x(j)

j=j+1

j<=n

1

1

DA

x(i)=(b(i)-s)/a(i,i)

i=i-1

i>=1

DA

Return

Fig. 1.13. Metoda lui Gauss

29

Observaţie: Erorile de rotunjire în calculul elementelor matricii sunt cu atât mai mici cu cât elementul pivot este mai mare în valoare absolută (deoarece eroarea la împărţire este cu atât mai mică cu cât împărţitorul este mai mare). De aceea, algoritmul se poate modifica în sensul de a căuta ca element pivot elementul maxim de pe coloana curentă în loc de a ne opri la primul element diferit de zero.

Metoda Gauss-Jordan

Este o formă modificată a metodei lui Gauss. Deosebirea constă în faptul că matricea sistemului este transformată în matricea unitate. În acest caz soluţia este oferită de coloana termenilor liberi.

Metoda iterativă Jacobi Conform acestei metode, se rezolvă prima ecuaţie a sistemului după x1, a doua

după x2 etc. x1=t1+s12x2+ … +s1nxn xi=si1x1+si2x2 +….+ti+…+sinxn … xn=sn1+sn2x2+…+tn unde sii=0 pentru i=1,n sij=-aij/aii pentru j=1,n, i=1,n, j≠i ti=bi/aii

Sistemul se poate scrie matricial astfel: X=T+S⋅X Vom rezolva acest sistem prin metoda aproximaţiilor succesive. Pentru

aproximaţia de ordinul zero vom lua coloana termenilor liberi X0=T. Xk=T+S⋅X(k-1), k=1,2, … Deci vom avea: xi

(0)=ti

xi(k)=ti+ ∑

≠=

−n

ij,1j

)1k(jij xs k=1,2,…

Condiţia de oprire: εxx ki

ki

ki ≤ | - |max=∆ )1()()( pentru i=1,n.

În cazul în care numărul de iteraţii depăşeşte un anumit număr maxim de iteraţii fixat, iar condiţia de oprire nu este satisfăcută, atunci nu există convergenţă şi în consecinţă metoda lui Jacobi nu se poate folosi.

30

Condiţia de convergenţă a metodei Jacobi este ca elementele de pe diagonala principală să fie dominante în valoare absolută. De exemplu, pentru sistemul de 3 ecuaţii cu 3 necunoscute: 4x1+x2+2x3=16 x1+2x2+5x3=12 x1+3x2+x3=10 -pentru prima linie 4>1+2 “Adevărat” -pentru a doua linie 2>1+5 “Fals” –se impune schimbarea liniei 2 cu linia 3. După schimbare: -pentru a doua linie 3>1+1 “Adevărat” -pentru a treia linie 5>1+2 “Adevărat”

Metoda iterativă Gauss-Seidel Creşte viteza de convergenţă a metodei Jacobi. În calculul componentei xi

(k) a aproximaţiei soluţiei sistemului de la pasul k se utilizează componentele x1

(k), x2(k), …xi-

1(k) deja calculate în locul componentelor x1

(k-1), x2(k-1), … xi-1

(k-1) de la iteraţia anterioară aşa cum se întâmplă în cazul metodei Jacobi. 1.8. Probleme propuse

Se citeşte un număr întreg reprezentând o temperatură în grade Fahrenheit. Să se afişeze această temperatură exprimată în grade Celsius, utilizând formula: C = (5 / 9) * (F - 32).

Să se scrie un program care determină dacă un an este bisect sau nu. Anii bisecţi sunt divizibili cu 4, excepţie făcând cei care sunt divizibili cu 100, care trebuie să fie divizibil şi cu 400.

Se citeşte un număr natural n. Să se verifice dacă n este prim sau nu.

Se citeşte un număr natural n. Să se genereze şirul primelor n numere prime.

Se citeşte un număr natural n. Să se descompună în factori primi.

Se citeşte un număr natural n. Să se numere câte cifre conţine acest număr.

Se citeşte un număr natural n. Să se numere câte cifre distincte conţine acest număr.

Se citeşte un număr natural n şi o cifră c. Să se indice numărul de apariţii ale cifrei c în cadrul numărului n.

Se citeşte un număr întreg. Să se convertească numărul în baza 16.

31

Se citeşte un şir de caractere reprezentând un număr în baza 16. Să se afişeze numărul convertit în baza 10.

Se citeşte un număr întreg n. Să se verifice dacă numărul este divizibil cu diferenţa dintre cifra maximă şi cea minimă.

Se citeşte un număr întreg n. Să se calculeze numărul maxim care se poate forma din cifrele acestui număr.

Se citeşte un număr natural n. Să se verifice dacă numărul n este palindrom sau nu. Un număr este palindrom dacă este egal cu inversul lui. Exemplu: 121 este palindrom 121=121 123 nu este palindrom 123<>321 Se citeşte un număr exprimat în baza p (p<=100. Să se convertească acest număr în baza q (q<=10).

Să se verifice, până la un număr dat n, conjectura lui Goldbach. Aceasta afirmă că orice număr par se poate scrie ca sumă de două numere prime. Pentru toate numerele mai mici decât n, să se afişeze o descompunere în sumă de două numere prime.

Se citeşte un număr natural n. Să se genereze elementele şirului lui Fibonacci mai mici decât n, fără a folosi un şir. fibo(0)=fibo(1)=1; fibo(n)=fibo(n-1)+fibo(n-2)

Se citeşte un număr natural n. Să se genereze un şir ce va conţine primele n numere Fibonacci. Să se afişeze acest şir.

Se citeşte un număr natural n. Să se genereze toate numere perfecte mai mici decât n. Un număr este perfect dacă este egal cu suma divizorilor săi. Exemplu: 6=1+2+3; 28=1+2+4+7+14

Se citesc două numere naturale m şi n. Să se calculeze cel mai mic multiplu comun al celor două numere.

Se citeşte un şir de n numere întregi. Să se elimine duplicatele din acest şir, astfel încât în şir să rămână doar o singură dată fiecare element.

Se citesc 2 şiruri de m respectiv n numere întregi direct ordonate crescător. Să se

interclaseze cele 2 şiruri astfel încât să se obţină un al 3-lea şir direct ordonat crescător format din elementele celor 2 şiruri.

Se citeşte un număr întreg n. Să se genereze şirul 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, … n, n, … n unde n apare de n ori.

Se citeşte un număr întreg n, n>16. Să se calculeze 2n. Având în vedere că acest număr, pentru un n mare, nu poate fi reprezentat exact, se va simula înmulţirea cu 2 folosind un şir compus din cifrele numărului.

32

Se citesc m şi n lungimile a 2 numere întregi foarte lungi. Se citesc apoi cele m

cifre reprezentând numărul a şi n cifre reprezentând numărul b. Fiecare număr se va păstra în câte un şir ce va conţine cifrele sale. Să se calculeze într-un al 3-lea şir suma celor două numere foarte mari.

Se citesc m şi n lungimile a 2 numere întregi foarte lungi. Se citesc apoi cele m cifre reprezentând numărul a şi n cifre reprezentând numărul b. Fiecare număr se va păstra în câte un şir ce va conţine cifrele sale. Să se calculeze într-un al 3-lea şir produsul celor două numere foarte mari.

Să se scrie un program care calculează valoarea seriei:

nS

n)1(...

4

1

3

1

2

11

−++−+−=

Să se scrie un program care calculează valoarea numărului PI, ştiind că acesta

este determinat de seria:

...)11

1

9

1

7

1

5

1

3

11(4 +−+−+−=π

Se citesc coeficienţii unui polinom de gradul n şi o valoare reală v. Să se

calculeze valoarea polinomului în punctul v.

Se citesc coeficienţii unui polinom de gradul n. Se citeşte un număr natural k, k<n. Să se afişeze toate derivatele de ordinul k ale acestui polinom.

Se citesc coeficienţii unui polinom de gradul n. Se citeşte un număr natural k, k<n şi o valoare v reală. Să se calculeze valoarea derivatei de ordinul k a polinomului în punctul v.

Se citeşte de la tastatură un şir de caractere reprezentând un număr întreg (eventual semn, urmat de un şir de cifre). Să se convertească acest număr într-un întreg (explicitarea funcţiei atoi() cu prototipul în math.h sau stdlib.h). Conversia se face până la primul caracter ce nu poate face parte din numărul întreg.

Se citeşte de la tastatură un şir de caractere terminat cu EOF. Să se numere caracterele albe (spaţiu, retur de car, tabulator) din acest şir de caractere.

Se citeşte de la tastatură un şir de caractere terminat cu EOF. Un cuvânt este orice succesiune de unul sau mai multe caractere diferite de blanc, tab sau linie nouă. Să se numere cuvintele distincte din acest şir de caractere.

Să se scrie un program care determină şi afişează procentele de apariţie a literelor din cadrul unui fişier text. Caracterele diferite de litere sunt ignorate iar literele mari sunt tratate la fel ca şi literele mici.

33

Să se găsească soluţia aproximativă a ecuaţiei x3-4x+3=0 folosind metoda înjumătăţirii intervalului şi un număr de 10 iteraţii, ştiind că ecuaţia admite o soluţie în intervalul [0,2.5] Să se găsească eroarea absolută ε ştiind că soluţia exactă este α=1. Să se rezolve ecuaţia f(x)=x⋅sin(x)-1, ştiind că admite o soluţie în intervalul [PI/2, 2,35PI/2] folosind metoda secantei. Să se rezolve ecuaţia f(x)=x3-3x+1 folosind metoda substituţiilor succesive, ştiind că cele trei soluţii se găsesc în intervalul [-2,-1], [0,1] şi [1,2]. Să se găsească o soluţie aproximativă a ecuaţiei f(x)= x3-3x+1 folosind metoda lui Newton şi pornind de la intervalul [0,1], cu o eroare maximă admisibilă de 0.001.

Se dă o matrice A(m,n). Să se afişeze valorile tuturor punctelor “şa” împreună cu poziţia lor. Un element A(i,j) este punct “şa” dacă el este elementul maxim pe linia i şi în acelaşi timp elementul minim pe coloana j. REZUMAT Acest modul este compus din trei părţi: prima parte începe cu prezentarea

unui scurt istoric al algoritmilor, caracteristicile noţiunii de algoritm, modalităţi de reprezentare a algorimilor, structurile de bază din programarea structurată. Al doua parte are ca scop prezentarea principalelor metode de rezolvare numerică a ecuaţiilor algebrice și transcendente. Al treia parte urmărește problematica calculului matricial. Sunt prezentate metode de rezolvare a unui sistem de n ecuaţii cu n necunoscute.

Intreb ări recapitulative

Ce este un algoritm? Ce este un program? Care este diferenţa dintre un algoritm şi un program? Care sunt caracteristicile unui algoritm? Care sunt modalităţile de reprezentare a unui algoritm? Ce este limbajul pseudocod? Ce este o schemă logică? Ce tipuri de blocuri se utilizează într-o schemă logică? Care sunt cele 3 structuri de bază dintr-un algoritm? Definiţi următoarele noţiuni: structura secvenţială, structura alternativă, structura repetitivă cu condiţionare anterioară, structura repetitivă cu condiţionare posterioară, structura repetitivă cu număr cunoscut de paşi. Daţi un exemplu de ecuaţie transcendentă. Cum definiţi rădăcina unei ecuaţii. Cum definiţi rădăcina aproximativă a unei ecuaţii. Enunţaţi Teorema lui Rolle. Explicaţi metoda înjumătăţirii intervalului. Explicaţi metoda secantei. Explicaţi metoda aproximaţiilor successive. Explicaţi metoda lui Newton. Definiţi următoarele noţiuni: matrice, transpusa unei matrici, matrice pătratică, matrice linie, matrice coloană, matrice nulă, diagonala

34

principală a unei matrici, diagonala secundară a unei matrici, matrice simetrică, matrice antisimetrică, matrice superior triunghiulară, matrice inferior triunghiulară, matrice superior trapezoidală, matrice inferior trapezoidală, matrice diagonală, matrice unitate, matrice ortogonală, inverse unei matrici Daţi algoritmul în pseudocod sau sub formă de schemă logică pentru produsul a 2 matrici Daţi algoritmul în pseudocod sau sub formă de schemă logică pentru aflarea inversei unei matrici pătratice Daţi algoritmul în pseudocod sau sub formă de schemă logică pentru produsul a 2 matrici Descrieţi algoritmul metodei lui Gauss Explicaţi diferenţa dintre metoda lui Gauss şi metoda lui Gauss-Jordan Descrieţi algoritmul metodei iterative Jacobi Explicaţi diferenţa dintre metoda iterativă Jacobi şi Gauss-Seidel

Bibliografie [Negrescu01], [Bologa06] cap 1, 2, 3, 4, 5, 6

35

MODULUL NUM ĂRUL 2

ALGORITMI DE SORTARE OBIECTIVE Cunoașterea principalilor algoritmi de sortare NOŢIUNI CHEIE Complexitate, timp de execuţie, sortare REZULTATE AŞTEPTATE

După parcurgerea acestui modul, cursanţii vor cunoaște principiile de bază ale sortării, tipurile de sortare și principalele metode de sortare utilizate în practică.

2.1. Timpul de execuţie şi complexitatea unui algoritm Analiza complexităţii are ca scop stabilirea resurselor necesare pentru execuţia unui algoritm pe o anumită maşină de calcul. Prin resurse se înţelege:

o spaţiul de memorie necesar pentru stocarea datelor utilizate de algoritm o timpul de execuţie pentru realizarea prelucrărilor din cadrul algoritmului

Progresele tehnologice din ultima perioadă fac ca importanţa mărimii memoriei

solicitate de un algoritm să scadă ca importanţă. Ceea ce trebuie să intereseze programatorul este reducerea timpului de execuţie al programului. Problema care apare este de a putea estima acest timp de execuţie al unui algoritm fără a face efectiv programarea lui, adică fără a-l măsura în cadrul unor execuţii ale programului cu diverse seturi de date.

Timpul de execuţie al unui program depinde de 2 categorii de factori: o externi –cum ar fi frecvenţa procesorului, capacitatea memoriei interne, calitatea

codului generat de compilator o interni problemei ce urmează a fi rezolvate.

Pentru simplificare, în cazul complexităţii, volumul datelor unui algoritm este caracterizat de un singur număr întreg (notat cu n), deşi multe probleme nu pot fi definite astfel. De exemplu, în problemele de grafuri, contează atât numărul de noduri din graf cât şi numărul de arce.

Noţiunea de timp de execuţie T(n) poate avea mai multe semnificaţii: o cazul cel mai defavorabil. În cazul unui algoritm de sortare ascendent, acest timp

este dat (în general) de sortarea unui vector având elementele în ordine descrescătoare.

o cazul mediu, adică raportul dintre suma timpului necesar pentru toate seturile de date posibile şi numărul de seturi. Timpul mediu în cazul unui algoritm de sortare se bazează pe un vector de elemente generat aleator.

o cazul cel mai favorabil. Pentru un algoritm de sortare, acest caz este dat (în general) de un vector deja sortat. Complexitatea unui algoritm este un indicator al dependenţei dintre dimensiunea

datelor de intrare şi numărul de instrucţiuni executate de algoritm. Complexitatea se estimează în general prin timpul de execuţie maxim necesar în cazul cel mai defavorabil, precum şi cel necesar în cazul mediu şi cazul cel mai favorabil. Bineînţeles, timpul de execuţie depinde de numărul datelor iniţiale ale problemei sau de valoarea lor

36

dar ceea ce ne interesează priveşte algoritmul folosit. Problema timpului se pune pentru valori mari ale lui n.

Se defineşte complexitatea unui algoritm ca fiind T(n)=O(f(n)) dacă în expresia complexităţii termenul dominant are forma c*f(n), unde c este o constantă. Dacă T(n) este timpul cerut de algoritm, determinarea expresiei lui T(n) este deseori greu de realizat. Pentru unii algoritmi se poate găsi o valoare minimă şi una maximă, valori care diferă în termenul dominant printr-o constantă multiplicativă.: c1*f(n)<=T(n)<=c2*f(n), pentru orice n>n0 Spunem că T(n)=O(f(n)) dacă există două constante pozitive n0 şi c astfel încât T(n)<=cf(n) pentru orice n>n0. Pentru valori mari ale lui n se observă că O(c*f(n)) este similar cu a exprima o complexitate de tip O(2*n) sau cu O(n/2). În schimb, pentru valori mici ale lui n, un algoritm de complexitate O(n) având un timp de execuţie de forma T(n)=k*n necesită un timp mai mare decât un algoritm de complexitate O(n2) De asemenea O(f(n)+g(n)) este identic cu O(f(n) dacă f(n)>=g(n). De exemplu O(n2+n) este identic cu a scrie O(n2), deoarece într-o funcţie polinomială termenul de grad maxim este dominant. Un algoritm la care timpul de execuţie nu depinde de dimensiunea problemei este un algoritm de timp constant a cărui complexitate se notează cu O(1). Timpul de execuţie al unui algoritm de complexitate O(n) creşte liniar (direct proporţional) cu valoarea lui n. Un algoritm liniar are complexitatea O(n), unul pătratic O(n2) iar unul cubic O(n3). Un algoritm se numeşte polinomial dacă are o complexitate egală cu O(p(n)) unde p(n) este o funcţie polinomială. O altă clasă de algoritmi sunt cei exponenţiali . Sunt asimilaţi algoritmilor exponenţiali şi cei de forma n*ln(n) deşi matematic nu sunt nici polinomiali nici exponenţiali. Algoritmii polinomiali sunt preferaţi celor exponenţiali, aceştia din urmă devenind inutilizabili pentru valori mari ale lui n. Trebuie avute în vedere următoarele aspecte:

o un algoritm exponenţial poate fi mai eficient decât unul polinomial pentru valori mici ale lui n. Astfel f(n)=2n ia valori mai mici decât f(n)=n5 pentru n<=20.

o există algoritmi exponenţiali care se comportă acceptabil pentru probleme particulare.

Pentru exemplificare prezentăm un tabel care prezintă evoluţia timpului de execuţie al unui program funcţie de tipul de complexitate şi de valoarea lui n. n O(n) O(n*ln(n) O(n2) O(n3) O(2n) 2 2 1,38 4 8 4 5 5 8,04 25 125 32 10 10 23 100 1.000 1.024 20 20 59 400 8.000 1.048.576 30 30 102 900 27.000 1.073.741.824

40 40 147 1.600 64.000 1,09E+12

50 50 195 2.500 125.000 1,12E+15

100 100 460 10.000 1.000.000 1,26E+30

1000 1.000 6.907 1.000.000 1.000.000.000 1,07E+301

37

În cazul în care dispunem de un calculator capabil să efectueze 109 instrucţiuni/secundă, timpul necesar pentru execuţia unui algoritm evoluează astfel: n O(n) O(n*ln(n)) O(n2) O(n3) O(n4) O(n10) O(2n) 1.000 000.000.1

1s

000.000.1

10s

000.1

1s

1s

17 min

3,2*1013 ani

3,2*10283 ani

10.000 000.000.1

10s

000.000.1

130s

000.1

100s

17 min

116 zile

? (∞)

? (∞)

106 000.1

1s

000.1

20s

17 min

32 ani

3*107 ani

? (∞)

? (∞)

Din datele prezentate rezultă că trebuie evitate problemele de complexitate

exponenţială pentru valori mari ale lui n. Este necesară găsirea în locul lor a unor algoritmi de complexitate polinomială, deoarece algoritmii exponenţiali sunt inutilizabili pentru valori mari ale lui n. În cazul problemelor nerecursive, analiza complexităţii este relativ simplă, timpul de execuţie putând fi determinat având la bază numărul de cicluri conţinute unele în altele precum şi numărul de paşi din cadrul fiecărui ciclu. În cazul problemelor recursive, estimarea timpului de execuţie se face folosind inducţia, folosind şi o reprezentare grafică a arborelui de apeluri generat de funcţia recursivă. Astfel, o funcţie recursivă care nu aparţine unui ciclu va genera n apeluri în cazul unei probleme de dimensiune n, în cazul în care recursivitatea se bazează pe o relaţie de tipul f(n)=g(f(n-1)). Altfel se pune problema în cazul unei relaţii recurente de tipul f(n)=g(f(n-1))+g(f(n-2)) aşa cum se întâlneşte în cazul generării numerelor lui Fibonacci folosind o funcţie recursivă. În cazul unui algoritm la care numărul de apeluri este egal cu înălţimea arborelui binar de apeluri (în cazul în care la fiecare apel se alege numai unul din cei doi succesori posibili), cum ar fi algoritmul de căutare binară într-un vector ordonat, complexitatea este de ordinul O(ln(n)). În cazul algoritmilor recursivi, la care numărul de apeluri este egal cu numărul de noduri din arbore (cum ar fi căutarea într-un arbore binar oarecare), complexitatea este de ordinul O(n*ln(n)).

2.2. Noţiuni despre sortare

Sortarea este o operaţie des întâlnită în rezolvarea problemelor de natură algoritmică. Problema sortării unei mulţimi de obiecte se poate reduce la problema sortării cheilor asociate acestora. După ce cheile sunt sortate, folosind informaţia de asociere (care leagă cheia de obiectul căreia îi aparţine), se pot rearanja obiectele în ordinea în care au fost aranjate cheile lor.

Dându-se o secvenţă de elemente caracterizate de valorile e1, e2, ... en ∈E, operaţia de sortare este operaţia de găsire a unei permutări a secvenţei ei1, ei2, ... ein astfel încât eij ≤ eik, oricare ar fi ij ≤ ik, unde “≤” este o relaţie de ordine definită peste mulţimea E.

38

Există o dependenţă între reprezentarea datelor ce trebuie sortate şi alegerea algoritmului de sortare. Astfel, algoritmii de sortare se împart în:

o algoritmi interni –în cazul acestora, secvenţa de sortat este păstrată în memoria internă

o algoritmi externi –secvenţa de sortat este păstrată pe un suport extern. Pentru a putea exemplifica această clasificare, ne putem imagina operaţia de sortare a unui pachet de cărţi de joc. Sortarea internă a lor presupune toate cărţile puse pe masă şi vizibile iar sortarea externă presupune că doar cartea din vârful pachetului este vizibilă. Aranjarea elementelor în ordine ascendentă a valorilor se numeşte sortare ascendentă iar aranjarea într-o ordine descrescătoare a cheilor duce la o sortare descendentă. În continuare, ne vom referi la sortarea ascendentă (chiar dacă nu se explicitează întotdeauna acest fapt). Algoritmii pot fi uşor modificaţi pentru a permite sortarea descendentă.

O metodă de sortare se spune că este stabilă dacă după sortare, ordinea relativă a elementelor cu chei egale coincide cu cea iniţială, element esenţial în special în cazul în care se execută sortarea după mai multe chei.

O cerinţă fundamentală care se formulează faţă de metodele de sortare a tablourilor se referă la utilizarea cât mai economică a zonei de memorie disponibile. Astfel, algoritmii care utilizează doar zona de memorie alocată tabloului, fără a fi necesar un tablou suplimentar se numesc sortări "în situ".

Sortările la care complexitatea este de ordinul O(n2) se numesc metode directe de sortare. O complexitate mult mai bună o prezintă metodele avansate de sortare, la care O(nlog(n)).

2.3. Metode de sortare care nu iau în considerare structura şi valorile cheilor

Sortare ordinară

Cel mai simplu algoritm de sortare (dar şi cel mai ineficient) se bazează pe următorul principiu: un şir este sortat dacă prin parcurgerea lui de la început până la sfârşit, fiecare element este mai mic decât succesorul. Dacă această condiţie nu este îndeplinită, inversăm cele 2 elemente. Sortarea se încheie în momentul în care parcurgerea şirului se face fără a fi necesară nici o inversare (fiecare element este mai mic decât succesorul său). Corectitudinea metodei: algoritmul este un algoritm finit, iar elementele şirului sunt sortate în cazul în care parcurgem şirul fără a fi nevoiţi să facem o inversare.

Complexitatea metodei –Indicatorii specifici care se analizează în cazul complexităţii algoritmilor de sortare sunt numărul de comparaţii de chei şi numărul de atribuiri de elemente (numit şi mutări de chei). Dacă notăm cu Nc numărul de comparaţii de chei şi cu Mc numărul de mutări de chei avem: Cazul cel mai defavorabil (şir sortat descrescător): Nc=n(n-1); Mc=3n(n-1)/2. Cazul cel mai favorabil (şir sortat crescător): Nc=n-1; Mc=0.

39

Cazul mediu: În general, cazul mediu este mai greu de definit. Uneori se ia o medie între cazul cel mai favorabil şi cazul cel mai nefavorabil. În cazul acestei metode, putem considera: Nc=(n+1)(n-1)/2; Mc=3n(n-1)/4. Complexitatea metodei este O(n2). Metoda este stabilă datorită faptului că pentru elemente egale nu se face inversare, deci ele îşi vor păstra ordinea şi după sortare. O variantă îmbunătăţită a acestui algoritm, presupune compararea fiecărui element alt şirului cu toate celelalte elemente, făcându-se interschimbarea atunci când elementul mai mare are indexul mai mic. Sortare prin selecţie (Selection Sort) Principiul acestei metode este următorul: şirul este împărţit în 2 părţi: o “Parte stânga” sortată şi o “Parte dreapta” nesortată. Iniţial “Partea stângă” este vidă iar “Partea dreapta” conţine tot şirul. Se caută minimul din “Partea dreapta” şi se adaugă la sfârşitul “Părţii stânga”. Algoritmul se încheie în momentul în care “Partea dreaptă” mai conţine un singur element. Acest ultim element este maximul din şir deci, în final, “Partea stânga” va conţine toate elementele şirului sortate, iar “Partea dreapta” devine vidă.

Corectitudinea metodei: Vom arăta că la terminarea fiecărui ciclu după i avem

proprietatea a[1]..a[i] sortat, pentru i=1,n. Iniţial, a[1]..a[n] este nesortat. După primul pas, în a[1] va fi minimul din a[1]...a[n] iar ceea ce era n a[1] s-a pus în indexul minimului. Deci a[1] este sortat, fiind o secvenţă de un număr. Presupunând că la terminarea pasului i, proprietatea a[1]...a[i] sortat este adevărată. Vom demonstra că după pasul i+1, proprietatea a[1]..a[i+1] sortat este adevărată. Astfel: -se calculează minimul din a[i+1]...a[n] -minimul este adus pe poziţia i+1 iar elementul de pe poziţia i+1 este mutat la indexul minimului. În acest moment a[1]...a[i+1] este sortat pentru că a[1]...a[i] este sortat iar a[i+1]<=a[k], oricare ar fi k=1,i (altfel s-ar fi ales mai devreme ca minim). Astfel, inducţia este încheiată. Metoda este stabilă; în cazul unor elemente egale, datorită faptului că căutarea de minim se face de la stânga la dreapta, deci un element cu cheie egală care se află mai la stânga va rămâne şi după sortare mai la stânga decât altul cu aceeaşi cheie.

Complexitatea metodei: Numărul de comparaţii de chei este independent de ordinea iniţială a cheilor . Nc=(n2 –3n +2) / 2 Numărul atribuirilor este cel puţin 3 pentru fiecare valoare a lui i. Mc=3(n-1) Complexitatea metodei este O(n2). Observaţie: o altă variantă a metodei de sortare prin selecţie foloseşte o “Parte dreapta” sortată (iniţial vidă) şi o “Parte stânga” nesortată (ce conţine iniţial tot şirul). Algoritmul caută maximul din “Partea stângă” (căutând de la dreapta la stânga pentru asigurarea stabilităţii metodei) şi îl adaugă la începutul “Părţii dreapta” (sortate). Algoritmul se încheie în momentul în care “Partea stângă” mai conţine un singur element.

40

Sortare prin inserţie (Insertion Sort) Analog ca la sortarea prin selecţie, şirul este împărţit în 2 părţi: o “Parte stânga” sortată şi o “Parte dreapta” nesortată. Iniţial “Partea stângă” este vidă iar “Partea dreapta” conţine tot şirul. La sortarea prin inserţie se ia primul element din “Partea dreaptă”, care se inserează la locul său din “Partea stângă”. Sortarea prin inserţie directă (Direct Insertion Sort)

În cazul acestei variante de inserţie, căutarea poziţiei în care se inserează elementul curent se face decremental, prin parcurgerea “Părţii stânga” de la dreapta spre stânga, până la găsirea poziţiei de inserare.

Corectitudine: pentru cazul i=1, secvenţa de un singur element este deja sortată. Presupunem adevărată afirmaţia a[1]..a[i] sortat, urmând să demonstrăm că este valabilă şi pentru i+1. După terminarea pasului i vom avea i=i+1. După parcurgerea instrucţiunilor din ciclu, a[i+1] va fi inserat în poziţia corespunzătoare din a[1]...a[i], deci a[1]...a[i+1] va fi sortat.

Complexitate: Cazul cel mai favorabil: Ciclul while nu se execută niciodată (vectorul este direct sortat crescător). În acest caz: Nc=n-1, Mc=3*(n-1) Cazul cel mai nefavorabil: Ciclul while se execută până când la atingerea primului element din partea sortată, adică se execută de i-1 ori. În acest caz: Nc=n(n-1)/2, Mc=(n2 +5n –6) / 2 Cazul mediu: Dacă cazul cel mai defavorabil înseamnă i-1 execuţii ale ciclului while (pentru pasul i) iar cazul cel mai favorabil 0 execuţii, atunci în cazul mediu, este necesară parcurgerea a jumătate din şirul a[1]...a[i-1] deci Nc=(n2 + n - 2) / 4, Mc= (n2 +11n –12) / 4. Complexitatea metodei este O(n2). Observaţie: analog ca la sortarea prin selecţie, o altă variantă a sortării prin inserţie porneşte de la o “Parte stânga” a şirului nesortată şi o “Parte dreapta” nesortată (iniţial vidă). Se va lua ultimul element din “Partea stângă” (nesortată) care se va insera la locul ei în “Partea dreaptă” (sortată). Algoritmul se încheie în momentul în care “Partea stângă” devine vidă. În acest moment, “Partea dreaptă” (care conţine tot şirul) este sortată. Sortare prin inserţie directă folosind o santinelă –această variantă de inserţie foloseşte înaintea primului element al şirului o valoare foarte mică, mai mică decât oricare din cheile din vector. Această valoare simplifică înaintarea în “Partea stângă” sortată, având garanţia că nu vom depăşi marginea stânga a şirului Rolul santinelei este ca elementul care va fi adus pe prima poziţie să fie comparată cu o valoare sigur mai mică. Pentru această variantă de sortare, elementele şirului vor avea indicii de la 1 la n. Observaţie: În cazul variantei de sortare prin inserţie în care şirul sortat se formează în “Partea dreaptă” (prin preluarea ultimului element din “Partea stângă”

41

nesortată şi inserarea lui în “Partea dreaptă”), santinela se va găsi după ultimul element al şirului şi va avea o valoare foarte mare (mai mare decât oricare din elementele şirului). Sortarea prin metoda bulelor (Bubble Sort)

Principiul acestei metode este următorul: se parcurge şirul, schimbându-se valori adiacente, dacă este cazul. La prima parcurgere cheia de valoare maximă migrează spre ultima poziţie. La a doua parcurgere, cheia de valoare imediat inferioară celei maxime migrează spre penultima poziţie. Datorită acestor migrări, metoda a fost denumită astfel, deoarece elementele de valori mari se ridică la suprafaţă asemenea unor bule.

Metoda se aseamănă oarecum cu sortarea prin selecţie, doar că partea sortată se formează în “Partea dreaptă” a şirului, aceasta crescând până când toate elementele sunt cuprinse în ea.

Corectitudinea metodei: Dacă parcurgem şirul de la stânga spre dreapta şi interschimbăm poziţiile a 2 elemente atunci când nu sunt aşezate crescător, în final pe ultima poziţie vom avea valoarea maximă.

Metoda este stabilă datorită instrucţiunii if care în cazul unor elemente egale nu face interschimbare, deci un element care se află mai în stânga nu va trece peste un element de aceeaşi valoare aflat în dreapta lui.

Complexitatea metodei este de ordinul O(n2). Numărul comparaţiilor este constant şi are valoarea Nc=(n2 –3n +2) / 2

Valorile minimă, maximă şi medie al numărului de mutări de chei sunt: Mmin=0 Mmax=3C=3(n2 –3n +2) / 2 Mmed=3(n2 –3n +2) / 4

Sortare prin amestecare (Shaker Sort) Reprezintă o variantă a sortării prin metoda bulelor cu următoarele îmbunătăţiri:

o la fiecare parcurgere a tabloului, se memorează indicele ultimei interschimbări făcute astfel încât la următoarea parcurgere un capăt al subtabloului va fi marcat de acest indice

o se schimbă alternativ sensul de parcurgere al subtablourilor pentru două treceri succesive Complexitatea metodei este de ordinul O(n2).

Sortare prin inserţie prin diminuarea incrementului (Shell Sort)

Algoritmul a fost propus de D.L. Shell în anul 1959. Punctul de plecare a fost faptul că sortarea prin inserţie directă este lentă, deoarece interschimbă doar elemente adiacente. În cazul în care cel mai mic element se află pe ultima poziţie în vectorul de sortat, atunci vor fi necesare n-1 interschimbări pentru a-l aduce în poziţia corectă.

42

Având în vedere acest fapt, algoritmul Shell Sort permite interschimbarea unor elemente care se află la distanţe mai mari unele de altele, micşorând astfel timpul de execuţie. Algoritmul Shell Sort defineşte noţiunea de vector h sortat. Un vector este h sortat dacă luând tot al h-lea element pornind din orice poziţie obţinem o secvenţă sortată. Algoritmul începe cu valori mai mari ale lui h, continuând apoi cu valori din ce în ce mai mici ale lui h. În momentul în care h=1 (vectorul este 1-sortat) şirul este sortat în întregime. Considerăm un exemplu în care avem un şir cu n=15 elemente astfel: 11 15 3 7 9 2 13 1 5 12 6 14 10 8 4 Şirul de secvenţe h propus este: 13, 4, 1. 1. Pentru h =13 vom avea 2 secvenţe: i={0,13} → (11,8) →sortare⇒ (8,11) i={1,14} → (15,4) →sortare⇒ (4,15) Şirul devine: (8,4,3,7,9,2,13,1,5,12,6,14,10,11,15) 2. Pentru h=4 vom avea 4 secvenţe: i={0,4,8,12} → (8,9,5,10) →sortare⇒ (5,8,9,10) i={1,5,9,13} → (4,2,12,11) →sortare⇒ (2,4,11,12) i={2,6,10,14} → (3,13,6,15) →sortare⇒ (3,6,13,15) i={3,7,11} → (7,1,14) →sortare⇒ (1,7,14) Şirul devine: (5,2,3,1,8,4,6,7,9,11,13,14,10,12,15) 3. Pentru h=1 se face inserţie directă obişnuită şi se obţine vectorul sortat: (1,2,3,4,5,6,7,8,9,10,11,12,13,14,15) Există mai multe posibilităţi de a alege secvenţele de numere h. Studiile făcute, în mare parte empirice, au arătat că una din secvenţele cu rezultatele cele mai bune este: 1,4,13, ... i=3*i+1. Există şi secvenţe foarte proaste cum ar fi: 1,2,4,8,... în care elementele din poziţiile pare nu sunt comparate cu elementele din poziţiile impare. până în momentul h=1, conducând spre performanţe scăzute ale algoritmului. Sortările h-secvenţelor se fac în general folosind inserţii directe. În cazul în care, în loc de a utiliza inserţii directe pentru sortarea h-secvenţelor, se utilizează sortarea prin metoda bulelor, metoda obţinută se numeşte Brick Sort.

Complexitatea: Numărul de comparaţii este mărginit superior de n3/2 ceea ce

conduce spre ideea că algoritmul Shell Sort are o complexitate bună, fiind pretabil pentru sortarea şirurilor de dimensiuni mari. Sortare rapidă (Quick Sort)

Acest algoritm a fost inventat de C.A.R.Hoare în 1962 şi este un algoritm recursiv care se bazează pe principiul “Divide et Impera”. Pentru a înţelege mai bine acest algoritm, recomandăm mai întâi parcurgerea capitolului de recursivitate (respectiv cel care descrie principiile metodei “Divide et Impera”). Acesta este cel mai rapid

43

algoritm de sortare cunoscut, pentru un şir cu n>1000 elemente algoritmul fiind de cel puţin 1,5-2 ori mai rapid ca alt algoritm de sortare.

Principiul acestei metode este următorul: Se alege un element pivot din tabloul ce trebuie sortat. Tabloul este astfel partiţionat în 2 subtablouri, alcătuite de o parte şi de alta a acestui pivot, astfel: elementele mai mari decât pivotul sunt mutate în dreapta pivotului iar elementele mai mici în stânga pivotului. Cele 2 subtablouri sunt sortate în mod independent prin apeluri recursive ale algoritmului.

Astfel un şir iniţial a[l]...a[r] va fi partiţionat în 2 vectori a[l]...a[i-1] şi

a[i+1]...a[r] cu proprietatea că orice element din a[l]...a[i-1] este mai mic decât a[i] şi orice element din a[i+1]...a[r] este mai mare decât a[i]. Algoritmul are următoarele etape:

o se selectează elementul pivot; fie p acest element o se caută de la stânga la dreapta care este primul element mai mare decât p; fie

acesta ak o se caută de la dreapta la stânga care este primul element mai mic decât p; fei

acesta am o se permută cele 2 numere găsite (se inversează elementul ak cu elementul am) o se continuă procesul de căutare/permutare până când 2 elemente, unul mai mic şi

unul mai mare decât p se vor afla unul lângă celălalt o se va insera pivotul p între cele 2 numere, obţinându-se o suită de 3 elemente

ordonate crescător, cu p la mijloc. Astfel toate elementele din stânga lui p vor fi mai mici decât p şi toate elementele din dreapta lui p vor fi mai mari decât p

o procesul se repetă independent, prin alegerea altor pivoţi, atât pentru subşirul din stânga, cât şi pentru subşirul din dreapta lui p

o la terminarea procesului de sortare a elementelor tuturor subşirurilor obţinute, rezultă o aşezare în ordine crescătoare a tuturor elementelor din şirul ini ţial de n elemente

Observaţii:

1) Nu există nici un test pentru ieşirea celor 2 indici i şi j din limitele l şi r. Indicele i începe din l şi tinde spre r. Indicele i nu va putea depăşi valoarea r deoarece, în cazul în care nu găseşte până la r un element mai mare sau egal cu pivotul, vom ieşi cu i egal cu r deoarece elementul a[i] este egal cu el însuşi (a[r]). Deci santinela pentru indicele i este chiar elementul pivot a[r]. Pentru j este nevoie de o santinelă, şi aceasta este a[0] care este iniţializat cu valoarea minimă posibilă (-MAXINT pentru numere întregi).

2) După ieşirea din ciclul for (când i>=j), determinarea indicelui elementului cu care este interschimbat pivotul se face după următorul raţionament: a[i]>=a[r] şi elementele din secvenţa a[l]..a[i-1] <= a[r]; similar pentru j se poate afirma că a[j]<=a[r] şi elementele din secvenţa a[j+1]...a[r] >=a[r]. Dacă se alege i ca şi poziţie de interschimbare, elementele din secvenţa a[i+1]...a[r] >=a[r] iar a[i]>=a[r] atunci interschimbarea elementelor a[i] cu a[r] conduce spre o partiţie dreapta corectă. Dacă, în mod greşit, s-ar fi ales ca indice de interschimbare valoarea j, elementele din secvenţa a[j+1]...a[r} >=a[r] dar faptul că parcurgerea dreapta s-a oprit la j nu poate conduce decât la concluzia că a[j}<=a[r].

44

3) Alegerea ca element pivot a extremităţii finale a secvenţei de sortat nu este obligatorie. Analog, se poate alege ca element pivot extremitatea stângă a secvenţei de sortat, caz în care nu mai este nevoie de santinela stânga a[0] ci de o santinelă egală cu MAXINT după ultimul element al şirului. În acest caz indicele de interschimbare va fi j.

4) Performanţele foarte bune ale acestui algoritm se datorează ciclului intern scurt, nefăcându-se decât incrementare/decrementare de index şi comparaţie cu o valoare fixă. De asemenea, renunţarea la santinela necesară (stânga în cazul pivotului extremitate dreaptă respectiv santinelă dreapta în cazul pivotului extremitate stânga) ar impune introducerea unui test suplimentar într-unul din ciclurile while, fapt ce ar conduce la o scădere de performanţă a algoritmului.

5) Condiţia de ieşire din recursivitate este r>l. Dacă am fi folosit r>=l atunci fiecare element din şir ar fi fost folosit o dată ca pivot în partiţii triviale (de un singur element), ceea ce ar scădea de asemenea performanţa algoritmului.

6) Algoritmul se dovedeşte ineficient în cazul unor vectori deja sortaţi, prin degenerarea partiţiilor şi generarea a n apeluri succesive, foarte costisitoare ca timp de execuţie. În acest caz s-ar ajunge la o complexitate de ordinul O(n2) (în mod normal ea trebuie să fie de O(nlog(n)). Pentru acest caz, algoritmul va fi modificat în sensul de a alege ca element pivot nu una din extremităţile secvenţei de sortat ci o poziţie aleatoare, înainte de a începe procesul de partiţionare. Corectitudine: Algoritmul de sortare rapidă este un algoritm care utilizează metoda “Divide et

Impera”. La fiecare apel recursiv se parcurg cele 3 etape caracteristice acestei tehnici de programare.

o Descompunerea şirului în 2 subşiruri de dimensiuni mai mici o Rezolvarea recursivă a subproblemelor pentru a obţine satisfacerea proprietăţii

că elementele din stânga pivotului să fie mai mici decât pivotul iar elementele din dreapta să fie mai mari decât pivotul.

o Recompunerea subproblemelor pentru a obţine şirul ini ţial sortat Quick Sort partiţionează şirul ini ţial a[l,r] în 2 subşiruri a[l,i-1] şi a[i+1,r] şi

aduce în a[i] un element astfel încât să avem satisfăcută proprietatea: orice element din a[l]...a[i-1]<=a[i] şi orice element din a[i+1]...a[r]>=a[i].

Complexitate: Cazul cel mai favorabil este ca la fiecare partiţionare, subvectorul partiţionat să se împartă în 2 părţi aproximativ egale. Timpul de execuţie pentru un şir de dimensiune n va fi dat de relaţia de recurenţă: T(n)=2T(n/2)+n (relaţie tipică pentru algoritmi de tipul Divide et Impera). În consecinţă, avem o complexitate de ordinul O(nlog2(n)). În cazul cel mai nefavorabil (vector deja sortat), complexitatea este de ordinul O(n2). În cazul mediu, complexitatea este de ordinul O(nlog2(n)). Pentru n=10 numărul de operaţii poate fi n3/2 ≈ 32, n2=100, nlog2(n) ≈ 33 iar pentru n=1000 n3/2 ≈ 31623, n2=1.000.000, nlog2(n) ≈ 9966 (de aproximativ 100 de ori mai rapid decât un algoritm de sortare cu complexitate O(n2)).

45

Sortare prin interclasare (Merge Sort) Algoritmul de sortare prin inserţie este eficient pentru valori mici ale lui n (n<=16). De aceea, sortarea prin interclasare propune o sortare bazată pe principiul Divide et Impera, care să utilizeze sortarea prin inserţie pentru valori mici ale lui n, rezultate prin descompunerea şirului ini ţial în subşiruri. Algoritmul Merge Sort se bazează pe 3 paşi esenţiali:

o separarea tabloului în 2 părţi de mărimi cât mai apropiate o sortarea acestor părţi prin apeluri recursive, până la atingerea unor valori mici

ale lui n pentru care se aplică sortarea prin inserţie sau până la atingerea unor subşiruri de 1 element (cazul banal)

o interclasarea părţilor sortate obţinându-se direct un şir ordonat crescător

O variantă simplificată a sortării prin interclasare permite divizarea recursivă a şirului până la obţinerea unor subşiruri de un singur element, urmată apoi de interclasarea pornind de la acestea.

Algoritmul în pseudocod este următorul:

function merge_sort(a,l,r) Dacă l<r Atunci m=(l+r)/2 merge_sort(a,l,m); merge_sort(a,m+1,r);

interclaseaza(a,l,m,r); Sf-Dacă

Corectitudine: Demonstraţia se face prin inducţie. Presupunem că la pasul k sunt 2k vectori sortaţi crescător care se interclasează, deci se obţin 2k-1 vectori sortaţi crescător. Când au mai rămas doar doi vectori de sortat se obţine prin interclasare un singur vector de dimensiune n sortat crescător. Complexitate: Sortarea prin interclasare are o complexitate de ordinul O(nlog(n)).

Observaţii finale: Nu există algoritmi de sortare care să aibă, în cel mai defavorabil caz, un ordin de complexitate mai mic decât O(nlog(n)). Sortare prin metoda ansamblelor (Heap Sort) Sortarea prin metoda ansamblelor este cunoscută şi sub denumirea de “sortare pe bază de arbore”, deoarece vectorul de sortat, organizat ca o movilă, corespunde unui arbore. O arbore heap (o movilă) este un arbore binar cu proprietatea că cheia fiecărui nod din arbore este mai mare decât cheile descendenţilor (deci fiecare nod are o cheie mai mică sau egală cu cea a tatălui său). Pentru a înţelege mai bine această metodă de sortare, se recomandă citirea noţiunilor introductive legate de arbori, prezentate într-un alt subcapitol.

46

Un heap poate fi reprezentat şi sub forma unui tablou. Astfel, dacă v este un tablou care conţine reprezentarea unui heap avem următoarea proprietate: Elementele v[i]..v[n] îndeplinesc condiţia de structură a heapului: ∨ j>i avem: v[j]>v[2*j], dacă 2*j≤n, respectiv v[j]>v[2*j+1] dacă 2*j+1≤n. Evident, pentru valori ale lui j mai mari decât n/2 nu se pune problema îndeplinirii condiţiilor de mai sus. Există 2 variante de sortare prin metoda ansamblelor:

A. cea în care generarea heapului se face prin retrogradări repetate B. cea în care generarea heapului se face prin inserări repetate

A. Principiul acestei metode este următorul: Heapul se construieşte de jos în sus

(de la dreapta spre stânga). La fiecare pas i, elementul a[i] trebuie să fie mai mare decât oricare din elementele a[2*] şi a[2*i+1] (dacă acesta din urmă există, doar în cazul în care nodul ar avea 2 succesori şi doar unul). Dacă această condiţie nu este îndeplinită, pe poziţia i este adus elementul maxim, urmând să se verifice ca succesorii elementului interschimbat (copil) să îndeplinească în continuare condiţia de heap. După crearea secvenţei heap, elementul cu cheia cea mai mare din secvenţă se va găsi pe prima poziţie şi va fi apoi mutată în spatele secvenţei (extremitatea stângă), fiind ignorat de paşii următori, care vor continua cu restul secvenţei. Algoritmul se aseamănă oarecum cu sortarea prin selecţie, la fiecare creare de secvenţă heap, în vârful ei se va găsi elementul maxim al secvenţei.

Observaţie: Există şi o altă variantă de heap în care cheia fiecărui nod este mai mare sau egală cu cea a tatălui său. Algoritmul diferă puţin în acest caz faţă de algoritmul prezentat. Practic, nu mai este necesară mutarea primului element pe ultima poziţie, fiind necesară doar câte o fază de retrogradare pentru fiecare nou minim inclus în partea sortată.

Corectitudine: Conform definiţiei movilei, în vârf se găseşte elementul de valoare maximă. Extrăgând acest element si ducându-l pe ultima poziţie, vom reorganiza heapul astfel încât în vârful movilei va trece un nou element de valoare maximă.

Complexitate: Cazul cel mai defavorabil este cel la care la fiecare retrogradare se parcurg toate nivelurile. Complexitatea algoritmului Heap Sort este de ordinul O(nlog2(n)). Deşi este cel mai slab algoritm din clasa O(nlog2(n)), complexitatea bună îl face comparabil cu algoritmul de sortare rapidă, nefiind un algoritm recursiv. Având în vedere acest fapt (viteză bună cu un consum mic de memorie), se pretează utilizarea acestui algoritm şi pentru valori mari ale lui n.

B. În cazul generării heapului prin inserări repetate, se consideră pentru început un heap format dintr-un singur element, după care celelalte elemente vor fi inserate în acest heap.

Complexitate: În cazul operaţiei insert, în cazul cel mai defavorabil se parcurge o ramură care leagă un nod terminal de rădăcină. Complexitatea este dată în acest caz de

47

adâncimea arborelui. Dacă n este numărul de noduri din arbore, 2k<=n<=2k+1 iar adâncimea arborelui este k+1. 2k-1<n<=2k+1-1 deci k<=log2(n)<k+1 deci k=log2(n). Complexitatea este O(log2(n)). 2.4. Metode de sortare care ţin cont de valorile cheilor Sortare prin compartimentare (BinSort)

Se poate aplica în cazul în care avem n chei, valori de tip întreg cuprinse în intervalul 1..n neexistând astfel duplicate. Principiul metodei este următorul: locul elementului a[i] este pe poziţia i. Astfel avem următoarea secvenţă de sortare: comp_sort(A,B,n) Pentru i=1 la n execută b(a(i))←a(i) Sf-pentru

Se observă că, în acest caz, complexitatea algoritmului este de ordinul O(n),

fiind necesar un singur ciclu de n iteraţii pentru a obţine şirul sortat. Algoritmul se poate optimiza (în sensul de a nu mai necesita un al doilea şir)

folosind următorul algoritm: se parcurge tabloul a, verificându-se dacă elementul a[i] are cheia egală cu i. Dacă nu, se interschimbă elementele a[a[i]] cu a[i]. Dacă după fiecare interschimbare, elementul a[k] se găseşte la un indice i<>k, se va interschimba din nou a[i] cu a[k]. Odată ce un element îşi ocupă poziţia bună (adică a[i]=i), el nu va mai fi deplasat de pe această poziţie. comp_sort(A,n) Pentru i=1 la n execută Cât-timp a(i)!=i execută interschimbă(a[i],a[a[i]]) Sf-cât-timp Sf-pentru

Sortare prin numărare (Count Sort) Principiul acestei metode se bazează pe următoarea afirmaţie: într-o mulţime formată cu elementele unui vector, poziţia finală a unui element din mulţime este egală cu numărul de elemente mai mici decât el. Sortarea prin numărare se aplică în cazul în care avem de sortat un şir de numere naturale care se găsesc într-un interval [vmin, vmax]. Se foloseşte un şir auxiliar având vmax - vmin poziţii în care se memorează la poziţia i numărul de apariţii în şirul original al numărului i+vmin. În final se generează un nou şir din şirul auxiliar, care va fi şirul ini ţial sortat. Dacă între valoarea maximă şi cea minimă este o diferenţă mare, algoritmul devine foarte costisitor din punct de vedere al spaţiului de memorie şi al complexităţii. Din acest motiv, acest algoritm nu este o soluţie pentru cazul general, fiind numai o justificare a faptului că este posibilă o sortare prin numărare (în cazul unei plaje mici în care să se încadreze elementele numere întregi ale şirului).

48

Metoda se numeşte şi sortarea prin determinarea distribuţiilor cheilor. Complexitatea: Iniţializarea vectorului count are o complexitate O(nmax) unde nmax este numărul maxim de elemente existent în intervalul [vmax, vmin]. Faza de numărare (al doilea ciclu al funcţiei de sortare) are o complexitate O(n), unde n este numărul de elemente al şirului de sortat. Al treilea ciclu (de generare a şirului sortat) va avea o complexitate O(nmax+n) în cazul cel mai defavorabil (toate numerele sunt egale) şi O(nmax) în cazul cel mai favorabil (toate numerele sunt distincte). 2.5. Metode de sortare care folosesc baze de numeraţie

Aceste metode presupun că cheile de sortare sunt numere zecimale pozitive (pentru numere negative având în vedere reprezentarea lor, avem nevoie de algoritmi modificaţi). Algoritmul consideră cheile ca şi numere reprezentate într-o anumită bază de numeraţie R (radix) şi procesează cifrele individuale ale numărului. Pentru implementarea pe sisteme de calcul se pretează metodele care utilizează R=2 şi care permit operarea cu biţii ce formează numerele. În sortarea radix cu R=2 operaţia fundamentală necesară este extracţia unui set continuu de biţi dintr-un număr.

Presupunem că avem de sortat o carte cu 1000 pagini având paginile individuale într-o ordine aleatorie. Algoritmul radix cu R=10 presupune crearea a 10 teancuri distincte, primul conţinând paginile între 1 şi 100, teancul 2 între 101 şi 200 până la teancul 10 conţinând paginile între 901 şi 1000. Se sortează pe rând fiecare grupă, aplicând aceeaşi metodă după cifra zecilor. Fiecare grupă astfel nou formată se sortează după cifra unităţilor. Sortare radix prin interschimbare (Radix Exchange Sort)

Principiul acestei metode este următorul: rezultatul comparaţiei a două chei este determinat numai de valoarea biţilor din prima poziţie la care ele diferă (considerând biţii de la stânga spre dreapta). Astfel, se sortează elementele tabloului astfel încât toate elementele ale căror chei încep cu un bit zero să fie trecute în faţa celor care încep cu 1; se formează astfel două partiţii ale tabloului iniţial. Cele două partiţii se sortează independent, în fiecare din ele se aplică aceeaşi metodă, pentru bitul următor. Rezultă astfel 4 partiţii iar fiecare din ele se vor sorta după al treilea bit ş.a.m.d. Astfel rezultă o abordare recursivă a acestei metode de sortare, procesul desfăşurându-se analog ca la metoda Quicksort: se parcurge tabloul de la stânga spre dreapta până se găseşte o cheie care începe cu 1; se parcurge apoi de la dreapta spre stânga până se găseşte o cheie care începe cu 0; se interschimbă cele două chei; se continuă în acest mod până când indicii de parcurgere se întâlnesc; în acest moment tabloul are două partiţii. Se reia procedura, considerând al doilea bit, pentru fiecare din partiţiile rezultate.

Exemplificăm sortarea Radix prin interschimbare pentru a sorta următorul tablou

de numere întregi: 2, 0, 5, 1, 7, 3, 4 şi 6. Având în vedere că toate au valori sub 8, ele necesită doar 3 biţi; considerăm un apel al funcţiei de sortare cu b=3. În urma sortării va rezulta şirul: 0, 1, 2, 3, 4, 5, 6, 7. Considerăm numere consecutive doar pentru

49

simplitatea reprezentării, dar algoritmul poate utiliza orice numere întregi pozitive (bineînţeles ele trebuie să se încadreze în limitele tipului propus pentru tabloul ce urmează a fi sortat). Sortare radix directă (Straight Radix Sort)

Principiul acestei metode este următorul: Se sortează cheile examinând biţii lor de la dreapta spre stânga. La pasul i, cheile sunt deja sortate după ultimii i-1 biţi ai lor. Sortarea după bitul i constă în extragerea elementelor a căror bit i este 0 şi plasarea lor înaintea elementelor a căror bit i este 1.

Sortarea după acest principiu nu este stabilă. De aceea, această metodă trebuie să fie combinată cu sortarea prin numărare (având în vedere că trebuie sortat stabil un tablou cu doar 2 valori: 0 şi 1).

Corectitudine: Algoritmul realizează într-o primă etapă o distribuţie pe grupe a tuturor elementelor în funcţie de bitul cel mai puţin semnificativ. Apoi aceste grupe se concatenează în ordine. Algoritmul continuă cu următorul bit (la stânga) până la bitul cel mai semnificativ. Rezultă că în urma ultimei treceri, vectorul iniţial este sortat.

Demonstraţia se face prin inducţie. Fie propoziţia P(i): “Elementele şirului sunt sortate după cheile a[i..n]”. Presupunem P(i) adevărată. Aplicând o sortare stabilă după cheia a[i-1], elementele vor fi sortate după această cheie, cu precizarea că, pentru chei a[i-1] egale, se păstrează ordinea dinaintea sortării după cheia a[i-1] (adică sortarea este stabilă). Deci elementele sunt sortate după cheile a[i-1..n] iar P(i-1) este adevărată.

Observaţii : Algoritmul de sortare Radix directă se poate îmbunătăţi prin considerarea nu doar a unui singur bit, ci a mai multor biţi concomitent. Timpul de sortare scade astfel prin reducerea numărului de treceri. Şirul care păstrează numărul de apariţii va trebui să aibă 2m poziţii, unde m este numărul de biţi consideraţi la o singură trecere. Numărul de biţi b trebuie să fie multiplu de m deoarece algoritmul divide biţii cheilor într-un număr întreg de părţi de dimensiune egală, care se procesează deodată. Programul C prezentat mai sus este deci un caz particular, având m=1. Dacă se alege pentru m o valoare suficient de mare, se poate obţine o metodă de sortare foarte eficientă (cu condiţia să existe spaţiul suplimentar de memorie solicitat de tabloul ce conţine numărul de apariţii). În cazul în care m=4 este necesar un tablou suplimentar de 16 locaţii iar pentru m=8 sunt necesare 256 locaţii, care sunt valori acceptabile. Pentru m=8 şi o cheie pe 16 biţi sunt necesare 2 treceri, algoritmul fiind practic liniar.

Ambele metode de sortare radix sortează un şir de întregi într-un timp O(n*b), unde n este numărul de elemente şi b este lungimea cheii în biţi. Dacă utilizăm varianta cu m biţi consideraţi la o singură trecere, numărul de treceri va fi m/b.

Timpul de execuţie poate fi aproximat ca fiind n*log(n) deoarece dacă toate cheile sunt diferite, b trebuie să fie cel puţin log(n). Sortarea prin interschimbare examinează în medie n*log(n) biţi. La sortarea a n chei de câte b biţi, ambele sortări Radix examinează de regulă mai puţini decât n*b biţi.

50

2.6. Metode de sortare externă Multe aplicaţii de sortare implică procesarea unor fişiere foarte mari, care nu încap în întregime în memorie. Aceste metode sunt denumite metode de sortare externă şi prezintă anumite particularităţi:

o dacă în cazul sortărilor interne aveam un acces direct la oricare din elementele structurii de date sortate, în cazul acestor metode de sortare, accesul depinde de tipul de structură folosită. Astfel, în cazul unor structuri cu acces secvenţial, elementele structurii pot fi accesate doar utilizând funcţiile prim şi succesor astfel:

o prim(S), succesor(prim(S),S), succesor(succesor(prim(S),S),S) ... o Cu excepţia primului element, accesul la un element de rangul i se face doar prin

parcurgerea secvenţială a elementelor de rang 1...i-1, după care avem acces la elementul de rang i. Astfel, costul accesării unui element într-o structură secvenţială este foarte ridicat

o într-o structură cu acces secvenţial, interschimbarea unor elemente, nu se poate face la fel de rapid ca în cazul unui vector.

o pe lângă criteriile de complexitate prezentate în cadrul sortărilor interne, la cele externe se urmăresc şi numărul de faze în cadrul unui pas şi numărul de paşi de sortare. Faza de sortare reprezintă grupul de operaţii care conduc la parcurgerea integrală sau rescrierea integrală a informaţiei conţinute iniţial în structura de sortat. Pasul de sortare reprezintă mulţimea minimă a fazelor de sortare care, prin aplicare repetitivă, conduce la sortarea structurii iniţiale.

o sortările externe utilizează un anumit număr de structuri de manevră. Acest număr constituie un nou indicator de apreciere a eficientei unui algoritm de sortare externă. În general, în cazul sortărilor externe, colecţiile de date ce urmează să fie sortate

sunt denumite şi fişiere sau benzi. Având în vedere că nu este posibil transferul întregii colecţii de date în memorie, sortarea internă urmată de rescrierea colecţiei sortate pe suportul extern, majoritatea sortărilor externe utilizează următoarea strategie: se face o primă parcurgere a structurii care se sortează, structură care se împarte în blocuri care încap în memorie. Dacă datele ce urmează a fi sortate ocupă un volum de n ori mai mare decât spaţiul de memorie de care dispunem, colecţia se va împărţi în n subcolecţii care vor fi transferate succesiv în memoria internă. Pentru fiecare din aceste subcolecţii se face pe rând câte o sortare internă după care se salvează pe disc în structuri intermediare, după care se interclasează două câte două subcolecţiile sortate, obţinându-se în final sortarea dorită. Pentru a efectua un număr cât mai mic de operaţii de transfer, se recomandă interclasarea subcolecţiilor de dimensiuni minime până la obţinerea întregii colecţii sortate.

Din punct de vedere al tehnicii folosite, se observă că sortările externe utilizează Divide et Impera, fişierul care urmează să fie sortat fiind împărţit în părţi care vor fi sortate şi apoi interclasate. Sortare prin interclasare utilizând 3 benzi

Fie a secvenţa care urmează să fie sortată. Principiul acestei metode este următorul:

51

o Secvenţa a se împarte în 2 jumătăţi, pe care le denumim b şi c o Se interclasează b cu c obţinându-se câte un element din fiecare, rezultând

perechi ordonate care vor forma o nouă secvenţă a o Pentru noua secvenţă a se repetă primii doi paşi, combinându-se perechile

ordonate în quadruple ordonate o Se repetă primii doi paşi, dublând de fiecare dată lungimea subsecvenţelor de

interclasat, până la atingerea întregii secvenţe

Această metodă necesită deci 3 fişiere pe disc, corespunzătoare secvenţelor a,b şi c (deci cel de sortat plus cele 2 fişiere intermediare pentru manevre). În cadrul acestei metode o trecere se compune din două faze: înjumătăţirea şi interclasarea.

Algoritmul utilizează o variabilă p care specifică numărul de elemente care se procesează deodată; iniţial, p=1. La fiecare trecere, se parcurg următoarele etape:

� se copiază câte p elemente din fişierul iniţial, alternativ, în cele 2 fişiere intermediare până când atingem marca de sfârşit de fişier pentru fişierul iniţial

� se interclasează secvenţele de lungime p din fişierele intermediare refăcându-se astfel întreg fişierul iniţial

� p se multiplică cu 2, pentru ca la următoarea trecere să se proceseze blocuri de lungime dublă Algoritmul se încheie în momentul în care p depăşeşte numărul de elemente ale

secvenţei de sortat.

Complexitate: Numărul de comparaţii este egal cu numărul cheilor din benzile b şi c care sunt

interclasate şi trecute apoi în banda a. În cazul cel mai defavorabil, cheile sunt dispuse în benzile b şi c astfel încât la terminarea ciclului principal while, unul din fişiere se găseşte pe eof iar celălalt mai are o înregistrare care trebuie copiată în banda a. În cazul cel mai favorabil, toate cheile din banda b sunt mai mici decât cheile din banda c sau invers.

În cazul sortărilor externe, critice sunt citirile şi scriere din chei din memoria operativă pe disc şi invers. Comparaţiile între chei, având în vedere că respectivele chei se găsesc deja în memoria internă sunt mult mai rapide decât operaţiile de citire/scriere pe bandă.

Datorită dublării lui p la fiecare pas, numărul de treceri ale algoritmului este proporţional cu log2(n), unde n este numărul de elemente ale secvenţei. Algoritmul este optim din punct de vedere al numărului de benzi folosite.

Sortarea prin interclasare este stabilă, deci două înregistrări având aceeaşi cheie vor rămâne în aceeaşi ordine relativă şi după sortare.

Un algoritm asemănător, cel de interclasare folosind 4 benzi, utilizează un număr mai ridicat de benzi (cu 1) dar evită faza de înjumătăţire. Sortare prin interclasare utilizând 4 benzi Această metodă reprezintă o îmbunătăţire a sortării prin interclasare utilizând 3 benzi, prin combinarea fazei de înjumătăţire cu cea de interclasare. Astfel, la interclasarea p-uplelor nu se constituie o singură secvenţă (ca la sortarea prin interclasare) ci 2p-uplele formate se distribuie imediat pe alte 2 benzi. Astfel dispare

52

faza de înjumătăţire, consumatoare de timp, îmbunătăţindu-se astfel performanţele algoritmului. Metoda este denumită şi sortarea echilibrată utilizând o singură fază. Se utilizează 4 benzi, una fiind secvenţa ce urmează să fie sortată şi 3 benzi de manevră. La fiecare pas, 2 benzi sunt benzi sursă iar celelalte 2 sunt benzi destinaţie, acestea inversându-şi rolurile după fiecare pas. Algoritmul parcurge următoarele etape:

o la prima trecere secvenţa a se distribuie alternativ câte p=1 elemente în fişierele b şi c

o p-uplele de pe fişierele b şi c se interclasează şi se distribuie alternativ în fişierele a şi d. Fişierele b şi c sunt în această fază fişiere sursă iar fişierele a şi d sunt fişiere destinaţie. la fiecare trecere se interschimbă statutul fişierelor sursă cu cel al fişierelor destinaţie

o se dublează p, se interclasează subsecvenţe de lungime p din fişierele sursă şi se distribuie în fişierele destinaţie Algoritmul se încheie în momentul în care p depăşeşte numărul de elemente ale

fişierului de sortat. Rezultatul (fişierul sortat) se va găsi în fişierul b. Sortare prin interclasare naturală

Algoritmul utilizează 3 fişiere, a şi b fiind fişiere intermediare iar c fiind fişierul de sortat. Spre deosebire de metoda anterioară, la care monotoniile au lungime fixată stabilită (1,2,4,8 ... elemente), în cazul acestei metode, având în vedere că în fişier putem găsi secvenţe deja sortate, delimitarea subsecvenţelor utilizează aceste monotonii. O monotonie este o secvenţă ai ... aj cu i<=j, care are următoarele proprietăţi: 1<=i<=j<=n ak<=ak-1 oricare ar fi k=i,j-1. ai<ai-1 pentru i<>1 aj>aj+1 pentru j<>n.

Există şi monotonii de 1 element, în cazul în care i=j. Sortarea naturală interclasează monotoniile, bazându-ne pe proprietatea că dacă se interclasează două secvenţe a câte m monotonii, se obţine o secvenţă cu exact m monotonii. Fiecare trecere a algoritmului are 2 faze alternative:

� defalcarea –reprezintă delimitarea monotoniilor din cadrul fişierului sursă c şi distribuirea acestora pe fişierele a şi b.

� interclasarea –fişierele a şi b se interclasează, rezultând un nou fişier sursă c

In faza de defalcare monotoniile găsite sunt depuse alternativ în fişierele a şi b, astfel încât fie cele două fişiere vor conţine câte un număr egal de monotonii, fie în fişierul a va fi o monotonie în plus faţă de fişierul b. După interclasarea monotoniilor perechi, monotonia nepereche va fi recopiată în c. Sortare prin interclasare multiplă echilibrată (sortare multicăi) Îmbunătăţeşte algoritmul de sortare prin interclasare naturală, în sensul reducerii numărului de treceri prin distribuirea monotoniilor pe mai mult decât două fişiere. Astfel, dacă se interclasează r monotonii şi se distribuie pe n benzi, pe fiecare bandă se vor obţine r/n monotonii, iar la următoarea interclasare-distribuire vor rezulta r/(n2) monotonii, apoi r/(n3) etc. Numărul de treceri în acest caz va fi log(n) (unde n n este

53

numărul de elemente din fişierul de sortat). Algoritmul de sortare prin interclasare naturală poate fi considerat o interclasare multiplă cu 2 căi). Dacă se utilizează n fişiere, interclasarea se va face pe n/2 căi. Pentru a gestiona aceste n fişiere se utilizează un vector de n elemente pentru a păstra situaţia fişierelor (active sau vide). Pe măsură ce avansează procesul de sortare, se reduce numărul monotoniilor precum şi cel al fişierelor active. Sortarea se încheie când ajunge, la o singură monotonie şi deci un singur fişier activ, fişier care este sortat. REZUMAT Al doilea modul abordează tematica vastă a algoritmilor de sortare. Se vor

parcurge atât algoritmi de sortare internă (folosind metode care nu iau în considerare structura și valorile cheilor, metode care ţin cont de valorile cheilor respectiv metode care utilizează baze de numeraţie) și algoritmi de sortare externă.

Intreb ări recapitulative

Care sunt cazurile pentru care se calculează timpul de execuţie? Ce este complexitatea unui algoritm? Definiţi algoritmii liniari, polinomiali şi exponenţiali Ce este sortarea? De câte feluri sunt algoritmii de sortare? Ce înseamnă sortare “in situ”? Când o sortare este stabilă? Descrieţi algoritmul sortării prin selecţie Descrieţi algoritmul sortării prin inserţie directă Descrieţi algoritmul sortării prin inserţie folosind o santinelă Descrieţi algoritmul sortării prin metoda bulelor Descrieţi algoritmul sortării prin amestecare Descrieţi algoritmul sortării prin diminuarea incrementului Descrieţi algoritmul sortării rapide Descrieţi algoritmul sortării prin interclasare Descrieţi algoritmul sortării prin metoda ansamblelor Descrieţi algoritmul sortării prin compartimentare Descrieţi algoritmul sortării prin numărare Descrieţi algoritmul sortării radix prin interschimbare Descrieţi algoritmul sortării radix directe Descrieţi algoritmul sortării prin interclasare utilizând 3 benzi Descrieţi algoritmul sortării prin interclasare utilizând 4 benzi Descrieţi algoritmul sortării prin interclasare naturală Descrieţi algoritmul sortării prin interclasare multiplă echilibrată

Bibliografie [Knuth99], vol. 3, cap. 5.2, [Cormen00], 2.1, 6, 7; [Bologa06] cap. 7, [Giumale96]

54

MODULUL NUM ĂRUL 3

TEHNICI DE PROGRAMARE OBIECTIVE Scopul acestui modul este prezentarea principalelor tehnici de

programare utilizate, ca modalităţi generale de rezolvare a algoritmilor. Având în vedere ca unele utilizează recursivitatea, modulul prezintă și principiile de bază ale recursivităţii.

CUVINTE CHEIE

Recursivitate, Tehnici de programare, Backtracking, Branch and Bound, Divide et Impera, Greedy, Metode euristice, Programare dinamică

REZULTATE AŞTEPTATE

Cunoașterea tehnicilor de progamare permite cursanţilor să le utilizeze în rezolvarea diverselor probleme de programare.

3.1. Recursivitatea

Recursivitatea este una din noţiunile fundamentale ale informaticii. Utilizarea

frecventă a recursivităţii s-a făcut după anii '80. Recursivitatea, folosită cu multă eficienţă în matematică, s-a impus în programare odată cu apariţia unor limbaje de nivel înalt, ce permit scrierea de module ce se autoapelează. Astfel PASCAL, LISP, ADA, ALGOL, C sunt limbaje recursive, spre deosebire de FORTRAN, BASIC, COBOL care sunt nerecursive. Recursivitatea este un mecanism general de elaborare a programelor. Ea a apărut din necesităţi practice (transcrierea directă a formulelor matematice recursive) şi reprezintă acel mecanism prin care un subprogram (procedură, funcţie) se autoapelează. Un algoritm recursiv poate avea un echivalent nerecursiv şi invers. Timpul mare de execuţie şi spaţiul ridicat de memorie utilizat de un algoritm recursiv recomandă, atunci când este posibil, utilizarea unui algoritm nerecursiv. Totuşi, în cazul transformării algoritmului recursiv într-unul iterativ, acesta din urmă poate deveni mai complicat şi mai greu de înţeles. De multe ori, soluţia unei probleme poate fi elaborată mult mai uşor, mai clar şi mai simplu de verificat, printr-un algoritm recursiv.

Implementarea recursivităţii are la bază structura de date denumită stivă. Stiva este acea formă de organizare a datelor (structură de date) cu proprietatea că operaţiile de introducere şi scoatere a datelor se fac în vârful ei. O stivă funcţionează după principiul LIFO („Last in First Out”, în traducere „Ultimul intrat, primul ieşit”). Atunci când o procedură sau o funcţie se autoapelează se depun în stivă:

o valorile parametrilor transmişi prin valoare. Pentru toţi parametrii-valoare se vor crea copii locale apelului curent (în stivă), acestea fiind referite şi asupra lor făcându-se modificările în timpul execuţiei curente a procedurii (funcţiei). Când execuţia procedurii (funcţiei) se termină, copiile sunt extrase din stivă, astfel încât modificările operate asupra parametrilor-valoare nu afectează parametrii efectivi de apel, corespunzători. Zona de memorie aferente copiilor locale se dealocă în momentul revenirii la funcţia apelantă.

55

o adresele parametrilor transmişi prin referinţă. În acest caz nu se crează copii locale, ci operarea se face direct asupra spaţiului de memorie afectat parametrilor efectivi, de apel.

o valorile tuturor variabilelor locale (declarate la nivelul procedurii sau funcţiei). Pentru fiecare apel recursiv al unei proceduri (funcţii) se crează copii locale ale tutoror parametrilor transmişi prin valoare si variabilelor locale, ceea ce duce la risipă de memorie. Din punct de vedere al modului în care se realizează autoapelul, există două

tipuri de recursivitate: directă şi indirectă. În cazul recursivităţii directe procedura (sau funcţia) se autoapelează (în corpul

său). Exemplul clasic este definirea funcţiei factorial: n!=(n-1)!⋅n, 0!=1, n∈N. Calculul valorii 3! decurge astfel:

Fig. 3.1 Apelurile recursive pentru 3!

Recursivitatea indirectă are loc atunci când o procedură (funcţie) apelează o altă procedură (funcţie), care la rândul ei o apelează pe ea. Un astfel de exemplu ar fi următorul: Se consideră două valori reale, pozitive a0,b0 şi n un număr natural. Definim şirul: an=(an-1+bn-1)/2 bn=an-1bn-1

Orice algoritm recursiv are o condiţie de oprire pusă de programator, în caz contrar se va umple stiva (datorită propagării la nesfârşit a autoapelului) şi aplicaţia va genera eroare (Stack Overflow –Depăşire de stivă). De asemenea, în cazul unui număr mare de autoapelări, există posibilitatea ca să se umple stiva, caz în care programul se va termina cu aceeaşi eroare.

O funcţie recursivă trebuie astfel scrisă încât să respecte regulile: o funcţia trebuie să poată fi executată cel puţin o dată fără a se autoapela o funcţia recursivă se va autoapela într-un mod în care se tinde spre atingerea

situaţiei de execuţie fără autoapel.

56

Exemplul 1. Calculul valorii n !.

#include<stdio.h> #include<conio.h> void main(void) { int n ; int fact(int) ; clrscr() ; scanf(“%d“,&n) ; printf(“%d !=%d“,n,fact(n)); getch(); } int fact(int n) { if ( !n) return 1 ; else return (n*fact(n-1)); } 3.2. Tehnici de programare

Tehnicile de programare sunt modalităţi generale de elaborare a algoritmilor.

Ele reprezintă doar nişte tipare de organizare a acţiunilor ("scheme" de algoritmi), nu garantează şi succesul acestora. Pentru a avea succes trebuie îndeplinite nişte condiţii suplimentare, care sunt specifice şi se demonstrează separat pentru fiecare problemă în parte.

Metoda backtracking În practică se întâlnesc un număr mare de probleme care au un număr mare de

soluţii, dar doar o parte din ele îndeplinesc condiţiile specifice problemei. Pentru astfel de cazuri, se indică utilizarea metodei backtracking, care evită generarea soluţiilor inutile. O abordare simplistă a acestui gen de probleme poate fi următoarea: Se generează toate soluţiile posibile după care se elimină cele care nu îndeplinesc condiţiile specifice. În cele mai multe cazuri o astfel de abordare este păguboasă, dacă nu chiar imposibilă.

Metoda backtracking se foloseşte în rezolvarea problemelor care îndeplinesc simultan următoarele condiţii : • soluţia lor poate fi pusă sub forma unui vector S=x1,x2,x3…xn cu x1∈A1,x2∈A2,.....,xn∈An; • mulţimile A1,A2,A3…An sunt multimi finite, iar elementele lor se consideră că se

află într-o relaţie de ordine bine stabilită • există anumite relaţii între componentele x1, x2,… xn, numite condiţii interne • nu se dispune de o altă metodă de rezolvare, mai rapidă. Mulţimea A=A1xA2x…xAn se numeşte spaţiul soluţiilor posibile. Soluţiile posibile care îndeplinesc condiţiile interne se numesc soluţii rezultat. Observaţii : � nu pentru toate problemele n este cunoscut de la început;

57

� x1,x2,x3…xn pot fi la rândul lor vectori; � mulţimile A1,A2,A3…An pot coincide.

La întâlnirea unei astfel de probleme, dacă nu cunoaştem această tehnică suntem tentaţi să generăm toate elementele produsului cartezian A1×A2×A3…×An şi fiecare element să fie testat dacă este soluţie. Metoda de generare a tuturor soluţiilor posibile şi apoi de determinare a soluţiilor rezultat prin verificarea îndeplinirii condiţiilor interne necesită foarte mult timp (timpul cerut de această investigare exhaustivă este exponenţial). În cadrul tehnicii backtracking nu se generează toate soluţiile posibile, ci numai acelea care îndeplinesc anumite condiţii specifice problemei, numite condiţii de interne (în unele lucrări de specialitate acestea mai sunt numite şi condiţii de validare). În cadrul acestei tehnici, elementele vectorului x primesc pe rând valori, în sensul că lui xk i se atribuie o valoare numai dacă au fost atribuite deja valori lui x1, x2, xk-1. Odată o valoare pentru xk stabilită, nu se trece direct la atribuirea de valori lui xk+1, ci se verifică condiţiile de continuare referitoare la x1, x2, xk care stabilesc situaţiile în care are sens să trecem la determinarea unei valori pentru xk+1.

Conceptual, tehnica backtracking caută sistematic soluţia într-un spaţiu al soluţiilor organizat sub forma unui arbore. Fiecare nod din arbore defineşte o stare a problemei. Toate drumurile de la rădăcină la frunze formează spaţiul stărilor. O soluţie a problemei reprezintă acele stări pentru care există drum de la rădăcină la un nod etichetat cu un n-uplu. Pot exista arbori statici (în cazul în care arborele astfel construit nu depinde de instanţa problemei) şi arbori dinamici (în cazul în care alegerea valorii xi depinde de una sau mai multe valori din mulţimea {x1, x2, xi-1}).

Nodurile pot fi clasificate astfel: -nod viu –este un nod pentru care nu s-au generat încă descendenţi -e-nod –este un nod în expansiune; acesta este un nod viu pentru care procesul

de generare al descendenţilor este în curs. -nod mort –este un nod generat care fie nu are descendenţi fie toţi descendenţii

s-a generat deja. În cazul metodei backtracking, se aplică strategia depth-first. Astfel, pentru e-

nodul curent se identifică un descendent care devine nod e-nod curent, procesul continuând recursiv până la epuizarea tuturor nodurilor vii.(toate nodurile devin noduri moarte).

Un exemplu pentru strategia de parcurgere depth-first este prezentat în figura următoare:

1

2 98

3 4

65 7

10 11

Fig. 3.2. Parcurgerea în adâncime (depth first)

Nodurile sunt etichetate în sensul parcurgerii depth-first.

58

Tehnica Backtracking are la bază un principiu extrem de simplu:

• se construieşte soluţia pas cu pas: x1x2x3…xn; • dacă se constată că, pentru o valoare aleasă, nu avem cum să ajungem la soluţie, se

renunţă la acea valoare şi se reia căutarea din punctul în care am rămas

Algoritmul acestei tehnici poate fi descris astfel:

1)se alege primul element x1 ce aparţine lui A1 2)se presupun generate elementele x1,x2,x3…xk-1 aparţinând mulţimilor A1 A 2 A3…Ak-1 pentru generarea lui xk se alege primul element din Ak disponibil şi pentru valoarea aleasă se testează îndeplinirea condiţiilor de continuare. Pot apărea următoarele situaţii : a)nu s-a găsit un astfel de element, caz în care se reia căutarea considerând generate elementele x1,x2,x3…xk-1 iar xk se reia de la urmatorul element al mulţimii A k rămas netestat b)a fost găsit, caz în care se testează dacă acesta îndeplineşte condiţiile de continuare, aparând astfel alte două posibilităţi: b1) xk îndeplineşte condiţiile de continuare. Dacă s-a ajuns la soluţia finală (k=n) atunci se afişeaza soluţia obtinută. Dacă nu s-a ajuns la soluţia finală se trece la generarea elementului următor xk+1; b2) xk nu îndeplineste condiţiile de continuare. Se încearcă următoarea valoare disponibila din Ak. Dacă nu se găseşte nici o valoare în Ak care să îndeplinească condiţiile de continuare, se revine la elementul xk-1 şi se reia algoritmul pentru o nouă valoare a acestuia. Algoritmul se încheie când au fost luate în considerare toate elementele lui x1.

Implementarea algoritmului nerecursiv de backtracking, îl descriem în continuare în pseudocod:

k<-1 Cât timp (k>0) //k creşte şi scade alternativ până la 0

Dacă (k>n) //adevărat în cazul în care avem o soluţie //completă

Afiseaza_solutia(); k<-k-1; //pentru a permite căutarea unei noi

//soluţii Altfel Dacă mai există valori candidat pentru x[k] Atribuie următoarea valoare candidat; Dacă x[k] este acceptabil k<-k+1; //se trece la următorul element Sf-dacă Altfel x[k]=0; //x[k] nu este acceptabil

k<-k-1; //se încearcă găsirea unei noi valori //pentru x[k-1]

Sf-dacă Sf-dacă

59

Sf-cat timp Backtrackingul poate fi recursiv sau nerecursiv. Implementarea în pseudocod a unui backtracking recursiv este următoarea: Pentru val de la <v1> la <vn> execută st[p]← val dacă valid(p) returnează true dacă <soluţia este finală> atunci apel tipar (p) altfel auto-apel bktr (p+1) Sfârşit-pentru.

Observaţii :

Tehnica Backtracking are ca rezultat obţinerea tuturor soluţiilor problemei. În cazul în care se cere o singură soluţie se poate forţa oprirea atunci când ea a fost găsită.

Algoritmii bazaţi pe metoda backtracking au în general o complexitate mare (exponenţială). Totusi, stiva de apeluri nu va conţine niciodată mai mult de n apeluri neterminate (iar acest n oricum nu poate fi prea mare, deoarece timpul total de executie ar fi prea mare) şi de aceea riscul de "stack overflow" este mic. Trebuie reduse la maxim variabilele locale sau parametri transmişi prin valoare de dimensiuni mari, pentru a încărca cât mai puţin stiva la fiecare apel. Numărul de operaţii într-un algoritm bazat pe backtracking poate fi micşorat dacă folosim condiţii de continuare "tari", care elimină cât mai multe alegeri greşite la fiecare pas şi astfel de mai puţine ori ne vom vedea nevoiţi să ne întoarcem înapoi pentru a construi o altă secvenţă de soluţie.

Problemele rezolvate prin aceasta metodă necesită un timp îndelungat şi de aceea este bine să utilizăm metoda numai atunci când nu avem la dispoziţie un alt algoritm mai eficient.

Backtracking-ul elementar este o metodă care permite utilizarea tehnicii backtracking pentru probleme la care soluţia se prezintă sub formă de vector. Pentru problemele pentru care soluţia de prezintă sub forma unui vector cu mai multe dimensiuni, vorbim de utilizarea metodei de backtracking generalizat (numit şi backtracking în plan).

Metoda Branch and Bound Metoda Branch and Bound (ramifică şi mărgineşte) este asemănătoare cu metoda Backtracking însă diferă în primul rând prin ordinea de parcurgere a spaţiului soluţiilor posibile (spaţiul de stări). De aceea este numită Backtracking cu constrângeri. În metoda Branch and Bound, spaţiul stărilor este parcurs într-un mod mai « inteligent », fără a putea ajunge la un ciclu infinit, dacă problema are soluţie, chiar dacă spaţiul valorilor posibile (spaţiul stărilor) este infinit. Dacă în cazul metodei backtracking arborele soluţiilor se parcurge în adâncime (depth first), în cazul metodei Branch and Bound traversarea se face în lăţime (breadth first). În cazul traversării în

60

adâncime, pentru e-nodul curent se generează toţi descendenţii şi se trec în lista de noduri vii sau moarte (în funcţie dacă au sau nu descendenţi). Se trece la următorul e-nod, care se alege din lista nodurilor vii. Strategia breadth first organizează lista nodurilor vii ca o coadă (în timp ce în cazul metodei backtracking, care realizează parcurgerea în adâncime, această listă este organizată ca o stivă).

Un exemplu pentru strategia de parcurgere breadth-first este prezentat în figura următoare:

1

2 43

5 6

109 11

7 8

Fig. 3.3. Parcurgerea în lăţime (breadth first) Nodurile sunt etichetate în sensul parcurgerii breadth-first.

Metoda conţine în esenţă două acţiuni specifice : � branch (ramifică) → construirea sau determinarea prin ramificare a drumurilor

de continuare şi � bound (delimitează) → eliminarea continuărilor (ramurilor) ineficiente sau

eronate. Prin eliminarea unor ramuri, porţiuni întregi ale spaţiului de căutare a soluţiei rămân astfel dintr-o dată delimitate şi “izolate”. Această strategie de delimitare din mers a anumitor “regiuni” ale spaţiului de

căutare a soluţiilor este cea care permite reducerea ordinului de mărime a acestui spaţiu. Soluţia aceasta este eficientă doar dacă câştigul oferit prin reducerea spaţiului de căutare (scăzînd efortul suplimentar depus pentru determinarea şi eliminarea din mers a continuărilor ineficiente) este substanţial. În cazul metodei Branch and Bound dispunem de o mulţime S finită de stări posibile, care conţine o stare iniţială s0 precizată şi o stare finală sf cunoscută sau care poate fi recunoscută (sau admisă ca stare finală) având la bază cerinţele problemei (condiţiile impuse). Pot exista mai multe stări finale şi notăm cu F⊂S mulţimea lor. Dintr-o stare s se poate trece în mai multe stări s1, s2, …sj printr-o transformare de forma : T :S→P(S), T(s)={ s1, s2, …sj} pentru s∈S. Se cere să se se determine o succesiune de stări, plecând de la starea iniţială dată s0 şi aplicând succesiv transformarea T, să ajungem la starea finală sf∈F, adică să se determine şirul stărilor de forma s0, s1, …sk pentru care sk=sf ∈F iar si+1∈T(si), pentru i=0,1..k-1. Pentru a ajunge la starea finală vom utiliza o mulţime de stări active (posibile spre continuare către starea finală) din care vom alege acea stare care este cât mai aproape de starea iniţială şi de starea finală (distanţa faţă de starea iniţială + distanţa faţă de starea finală să fie minimă). Distanţa faţă de starea iniţială se poate determina ca fiind numărul de transformări aplicate stării ini ţiale pentru a obţine respectiva stare : d1 :S-N, d1(s)=n dacă există stările s1, s2, …sn astfel ca :

61

s1∈T(s0), s2∈T(s1), … sn∈T(sn-1). Distanţa de la o stare si∈S la starea finală sf este în general greu de calculat. De cele mai multe ori se poate determina doar după ce am rezolvat problema în întregime. Din această cauză va trebui căutată o aproximantă a acesteia, care să poată fi calculată pentru problema concretă dată. Criteriul de alegere a unei stări din mulţimea stărilor active Sa constă în determinarea stării sc care realizează minimul sumei distanţei d1 şi d2: d1(sc)+d2(sc) =min{d1(s)+d2(s) | s∈Sa} Strategia Branch and Bound este următoarea: iniţial mulţimea stărilor active Sa se iniţializează cu {s0} iar pentru o mulţime de stări active obţinută la un moment dat se alege o stare sc de continuare (stare curentă) iar în locul ei se depune mulţimea stărilor ce se ramifică din ea Sa=Sa-{sc} ∪T(sc). Dacă printr-o astfel de transformare (ramificare) am ajuns la o stare finală sf∈T(sc) atunci problema e rezolvată. Problema care se pune în cazul metodei Branch and Bound este de a ne asigura la început că problema are soluţie, în caz contrar putând ajunge la un ciclu infinit. Metoda Branck and Bound poate fi exprimată în pseudocod astfel: Function Branch_and_Bound Citeşte s0; //citim starea initială Sa={s0}; //ini ţializăm mulţimea stărilor active Repetă sc=Alege(Sa); //starea care realizează min (d1+d2) Sa=Sa-{sc}; //se extrage starea aleasă din mulţimea stărilor active St=T(sc); //se ramifică starea curentă Pentru fiecare s∈St execută Pred(s)=sc; //reţine calea de întoarcere pentru tipărirea soluţiei Sf-pentru Sa=Sa∪St; //depunem în Sa mulţimea stărilor ce se ramifică din //starea curentă Până când Sa=∅ sau St conţine o stare finală Dacă Sa=∅ atunci tipareşte_mesaj(“Problemă fără solutie”); Altfel sk=sf; //pornim de la starea finală Repetă Tipăreşte sk; //tipărim starea curentă sk=Pred(sk); //continuăm cu predecesorul lui sk Până când sk=s0; //până ajungem la starea iniţială s0

Tipăreşte(sk); //tipărim şi starea iniţială Sf-dacă

Metoda Divide et Impera

« Dezbină şi stăpâneşte” –Este principiul de guvernare enunţat de Machiavelli în formularea Divide Ut Regnes – „dezbină pentru a domni” Metoda de programare Divide et Impera constă în împărţirea problemei iniţiale de dimensiuni [n] în două sau mai multe subprobleme de acelaşi tip şi de dimensiuni mai reduse. Se presupune că fiecare din problemele în care a fost descompusă problema iniţiala, se poate descompune în alte subprobleme, la fel cum a fost descompusă problema iniţială sau se reduc la o problemă banală. Împărţirea în subprobleme are loc

62

până când dimensiunea acestora devine suficient de mică pentru a fi rezolvate în mod direct (cazul de bază, probleme care admit o rezolvare imediată). După rezolvarea subproblemelor se execută faza de combinare a rezultatelor în vederea rezolvării întregii probleme . Metoda Divide Et Impera se poate aplica în rezolvarea unei probleme care îndeplineşte următoarele condiţii : 4se poate descompune în două sau mai multe subprobleme ; 4aceste suprobleme sunt independente una faţă de alta (o subproblemă nu se rezolvă pe baza alteia şi nu foloseşte rezultatele celeilalte) ; 4aceste subprobleme sunt similare cu problema iniţială; 4la rândul lor subproblemele se pot descompune (dacă este necesar) în alte subprobleme mai simple; 4aceste subprobleme simple se pot soluţiona imediat prin algoritmul simplificat. Deoarece puţine probleme îndeplinesc condiţiile de mai sus, aplicarea metodei este destul de rară. Complexitatea algoritmilor bazaţi pe metoda Divide et Impera este în general bună (de multe ori pătratică, chiar n * log(n) sau logaritmică). Etapele rezolvării unei probleme în cadrul acestei metode sunt :

• descompunerea problemei iniţiale în subprobleme independente, similare problemei de bază, de dimensiuni mai mici;

• descompunerea treptată a subproblemelor în alte subprobleme din ce în ce mai simple, până când se pot rezolva imediat, prin algoritmul simplificat;

• rezolvarea subproblemelor simple; • combinarea soluţiilor găsite pentru construirea soluţiilor subproblemelor de

dimensiuni din ce în ce mai mari ; • combinarea ultimelor soluţii determină obţinerea soluţiei problemei iniţiale.

Întrucât metoda este în esenţă recursivă, ea se implementează cel mai natural folosind subprograme recursive. Dacă dorim totuşi să facem o implementare iterativă, va trebui sa folosim în program o stivă în care să încărcăm subproblemele apărute şi nerezolvate, pe care să o gestionăm explicit. În pseudocod, reprezentarea rezolvării unei probleme prin această metodă arată astfel: procedure rezolva(x:problema); begin if {x e divizibil in subprobleme} then begin {divide pe x in parti x1,...,xk} rezolva(x1); {...} rezolva(xk); {combina solutiile partiale intr-o} {solutie pentru x} end else {rezolva pe x direct} end;

63

Metoda Greedy Metoda Greedy (greedy = lacom) este o metodă generală de proiectare a

algoritmilor care constă în construirea soluţiei globale optimale printr-un şir de soluţii cu caracter de optim local atunci când este posibilă exprimarea “optimului global” ca o combinaţie de o “optime locale”. Algoritmii greedy sunt în general simpli şi sunt folositi la probleme de optimizare, cum ar fi: să se găsească cea mai bună ordine de executare a unor lucrări, să se găseasca cel mai scurt drum într-un graf etc.

Această metodă se aplică problemelor în care se dă o mulţime A cu n elemente şi se cere să se determine o submulţime B⊆ A care să îndeplinească anumite condiţii pentru a fi acceptată. Este posibil să existe mai multe mulţimi acceptabile (soluţii posibile). De aceea se cere să se determine o soluţie posibilă care fie să maximizeze fie să minimizeze o anumită funcţie obiectiv dată. Această soluţie posibilă se numeşte soluţie optimă. Folosind metoda Greedy vom obţine cu siguranţă o soluţie posibilă maximală dar nu avem garanţia că elementul adăugat este acel element maximal pentru care funcţia obiectiv este maximizată/minimizată (cu alte cuvinte putem obţine doar un optim local, nu optimul global). Un element odată adăugat la soluţia curentă nu va mai putea fi eliminat pentru a se încerca în locul lui alte elemente şi de aceea complexitatea algoritmilor Greedy este mică (polinomială, de regulă pătratică sau chiar liniară). Fiecare element al lui M este testat o singură dată dacă trebuie sau nu să fie adăugat la soluţia curentă iar verificările respective se fac de regulă în timp polinomial în raport cu numărul celorlalte elemente din M şi din soluţia curentă.

Tehnica Greedy poate fi privită ca o particuarizare a metodei Backtracking în care se renunţă la mecanismul de întoarcere. Privitor la cele două tehnici de programare, putem formula următoarele observaţii: -ambele oferă soluţii sub forma unui vector -în timp de backtracking-ul oferă toate soluţiile unei probleme, tehnica Greedy oferă o singură soluţie, nu obligatoriu cea optimă. Aplicarea unui anumit algoritm pentru tehnica Greedy impune şi demonstrarea că acesta conduce la soluţia optimă. -metoda Greedy nu dispune de mecanismul de întoarcere, specific metodei Backtracking -metoda Greedy conduce la un timp de calcul polinomial. Dacă mulţimea din care se face alegerea are n elemente iar soluţia are tot n elemente, se vor face n alegeri, fiecare cu n teste, rezultând un algoritm cu o complexitate O(n2). Uneori la acest timp se adaugă şi cel necesar sortării ini ţiale a mulţimii de elemente, deci la timpul de mai sus se va adăuga şi un timp minim O(n*log2n) necesar algoritmului de sortare.

În cazul metodei Greedy vorbim de: o mulţime de candidaţi (lucrări de executat, vârfuri ale grafului etc) o funcţie care verifică dacă o anumită mulţime de candidaţi constituie o soluţie posibilă, nu neapărat optimă a problemei o funcţie care verifică dacă o mulţime de candidaţi este fezabilă, adică dacă este posibil să completăm această mulţime astfel încât să obţinem o soluţie posibilă, nu neapărat optimă, a problemei o funcţie de selecţie care indică la orice moment care este cel mai promiţător dintre candidaţii încă nefolosiţi

64

o funcţie obiectiv care dă valoarea unei soluţii (timpul necesar executarii tuturor lucrarilor intr-o anumita ordine, lungimea drumului pe care l-am gasit etc); aceasta este funcţia pe care urmărim să o optimizăm (minimizăm/maximizăm).

Un algoritm greedy construieşte soluţia pas cu pas astfel:

1. se iniţializează mulţimea soluţiilor (B) cu mulţimea vidă (B={}) 2. se alege un anumit element x∈ A care, conform funcţiei de selecţie, este cel mai

promiţător candidat 3. se verifică dacă elementul ales poate fi adăugat la mulţimea soluţiilor, dacă da atunci

va fi adăugat (B=B∪{ x}). Dacă, după o astfel de adăugare, mulţimea de candidaţi selectaţi nu mai este fezabilă, eliminăm ultimul candidat adăugat iar acesta nu va mai fi niciodată considerat. Dacă, după adăugare, mulţimea de candidaţi selectaţi este fezabilă, ultimul candidat adăugat va rămâne de acum încolo în ea.

4. procedeul continuă repetitiv cu pasul 2, până când au fost determinate toate elementele din mulţimea soluţiilor

Metoda Greedy nu caută să determine toate soluţiile posibile (care ar putea fi

prea numeroase) şi apoi să aleagă din ele pe cea optimă, ci caută să introducă direct un element x în soluţia optimă. Conform acestui algoritm prima soluţie găsită va fi totodată o posibilă soluţie optimă a problemei. Soluţia optimă nu este în mod necesar unică: se poate ca funcţia obiectiv să aibă aceeaşi valoare optimă pentru mai multe soluţii posibile. Descrierea formală a unui algoritm Greedy general este: function greedy(C) {C este mulţimea candidaţilor} S←Ø {S este mulţimea în care construim soluţia} while not solutie(S) and C ≠Ø do x ← un element din C care maximizează/minimizează select(x) C ← C \ {x} if fezabil(S U {x}) then S ← S U {x} if solutie(S) then return S else return “nu există soluţie”

Metode euristice

În funcţie de specificul problemei, un algoritm greedy poate conduce la soluţia

optimă sau la o soluţie destul de bună, deşi suboptimală. Există probleme pentru care nu se cunosc algoritmi care să genereze soluţia optimă. Pentru problemele care nu se cunosc algoritmi care necesită timp polinomial, se caută soluţii, chiar dacă nu optime, care să se obţină în timp util. Multe din aceste soluţii se găsesc folosind tehnica Greedy.

Se poate întâmpla ca efortul de implementare a unui astfel de algoritm să fie prea mare faţă de scopul urmărit. În astfel de cazuri se preferă utilizarea unor algoritmi care rezolvă problema dată mult mai rapid, cu efort mai mic, cu riscul de a nu furniza obligatoriu cea mai bună soluţie (optimă), ci doar soluţii acceptabile, care eventual pot

65

fi îmbunătăţite. Pentru unele probleme practice aceste soluţii pot fi considerate soluţii aproximative, care pot fi de multe ori mai mult decât satisfăcătoare.

Un algoritm euristic este deci un algoritm care furnizează o soluţie aproximativă, nu neapărat optimă, care poate fi implementată uşor şi dă rezultate în timp util, de ordin polinomial.

În practică, metodele euristice sunt de multe ori eficiente, fiind considerate satisfăcătoare pentru beneficiar dacă diferenţele între soluţia obţinută şi cea optimă este acceptabilă.

Un exemplu pentru acest tip de abordare îl constituie problema comis-voiajorului. Fiind date n localităţi şi distanţele dintre ele, se cere să se determine traseul de lungime minimă pe care comis-voiajorul trebuie să-l parcurgă astfel încât să viziteze toate localităţile şi să se întoarcă în localitatea din care a plecat, trecând doar o singură dată prin fiecare localitate.

O rezolvare euristică a acestei probleme foloseşte următoarea strategie: vom alege întotdeauna ce mai apropiată localitate (faţă de cea în care ne aflăm la un moment dat) dintre cele nevizitate. Un traseu fiind un circuit închis, putem considera ca punct de pornire oricare din localităţile date. Algoritmul va alege, pe rând, diverse localităţi de start, va determia traseul corespunzător după strategia de mai sus iar în final va alege traseul de lungime minimă. Această metodă euristică nu ne garantează alegerea optimă, dar din mai multe trasee acceptabile, îl vom alege pe cel mai bun (scurt).

Programare dinamică

Metoda programării dinamice se poate aplica problemelor în care soluţia este rezultatul unui şir finit de decizii optim dintr-un anumit punct de vedere. Se presupune că avem un sistem care se poate afla în mai multe stări posibile şi în urma fiecărei decizii trece dintr-o stare în alta.

Se presupune în plus ca problema verifică una din următoarele condiţii, numite principii de optimalitate (vom nota cu Si stările si Di deciziile): I ->Dacă şirul D1, ..., Dn duce sistemul în mod optim din S0 în Sn, atunci pentru orice 1 <= k <= n, şirul Dk, ..., Dn duce sistemul în mod optim din Sk-1 în Sn. II->Dacă şirul D1, ..., Dn duce sistemul în mod optim din S0 în Sn, atunci pentru orice 1 <= k <= n, şirul D1, ..., Dk duce sistemul în mod optim din S0 în Sk. III->Dacă şirul D1, ..., Dn duce sistemul în mod optim din S0 în Sn, atunci pentru orice 1 <= k <= n, şirul D1, ..., Dk duce sistemul in mod optim din S0 în Sk, iar şirul Dk+1, ..., Dn duce sistemul în mod optim din Sk în Sn (pentru k<n). S0, ..., Sn sunt nişte stări oarecare din mulţimea stărilor posibile, iar cu Di sistemul trece din Si-1 în Si. Oricare din principiile de optimalitate de mai sus exprimă faptul ca optimul total implică optimul parţial. Evident, optimul parţial nu implică neapărat optimul total. De exemplu, într-un graf fie Dxy drumul cel mai scurt între x şi y iar Dyz drumul cel mai scurt între y şi z. Nu putem trage concluzia că drumul cel mai scurt între x şi z este format din Dxy şi Dyz; acestea reprezintă fiecare câte un optim parţial dar acest drum nu este un optim total.

66

Deci oricare din principiile de optimalitate afirmă doar ca optimul total poate fi găsit printre optimele parţiale, nu indică însă şi care din ele este; putem căuta optimul total doar printre optimele parţiale, ceea ce reduce considerabil căutarea.

Modul de cautare a optimului total printre optimele parţiale depinde forma în care este îndeplinit principiul de optimalitate şi se face pe baza unor relaţii de recurenţă deduse din structura problemei şi anume: -dacă este îndeplinit în forma I, spunem că se aplica metoda înainte; în acest caz, pe baza unor relaţii de recurenţă se calculează optimurile de la stările mai depărtate de final în funcţie de optimurile de la stările mai apropiate de final şi se determină deciziile ce leagă aceste optime între ele (se merge deci de la sfârşit către început); în final se găseşte optimul total, apoi se determină şirul de decizii care îl realizează compunând deciziile calculate anterior mergând de la început către sfârşit. -dacă este îndeplinit în forma II, spunem că se aplică metoda înapoi; în acest caz calculele recurente se fac de la început spre sfârşit, iar in final se află optimul total şi se determină şirul de decizii care îl realizează compunând deciziile de la sfârşit către început. -dacă este îndeplinit în forma III, spunem că se aplica metoda mixtă; în acest caz pe baza unor relaţii de recurenţă se calculează optimurile între stările mai îndepărtate între ele în funcţie de cele între stări mai apropiate între ele şi se determină deciziile care interconectează aceste optimuri; în final se află optimul total, apoi se determină şirul de decizii care îl realizeaza mergând de la capete spre interior (se determină prima şi ultima decizie, apoi o decizie intermediară, apoi câte o decizie intermediară între cele două perechi succesive, etc.) REZUMAT Modulul de tehnici de programare urmărește principalele tehnici utilizate în

programare: backtracking, branch and bound, divide et impera, greedy respectiv metode euristice și programare dinamică.

Intreb ări recapitulative

Explicaţi recursivitatea directă. Explicaţi recursivitatea indirectă. Principiile şi algoritmul tehnicii backtracking. Principiile şi algoritmul metodei Branch and Bound. Principiile şi algoritmul metodei Divide et Impera. Principiile şi algoritmul metodei Greedy. Ce este un algoritm euristic? Principiile de optimalitate în cazul programării dinamice; modalităţi de căutare a optimului total.

Bibliografie [Aho83], cap. 2.1, 2.2, 2.3, 2.4 [Bologa06] cap. 8

67

MODULUL NUM ĂRUL 4

STRUCTURI DE DATE OBIECTIVE Scopul acestui modul este prezentarea principalelor structuri de

date utilizate în programare. CUVINTE CHEIE

Fișier, tablou, tabelă de dispersie, listă liniară simplu înlănţuită, listă liniară dublu înlănţuită, stivă, coadă, graf neorientat, graf orientat, arbore

REZULTATE AŞTEPTATE

Modulul oferă studenţilor cadrul general de proiectare și implementare a structurilor de date. Structurile de date înlănţuite sunt des utilizate în programare, de aceea deprinderea utilizării lor este esenţială.

4.1. Aspecte generale

O dată reprezintă un model de reprezentare al informaţiei. Dacă aceasta reprezintă o entitate indivizibilă din punct de vedere al informaţiei pe care o reprezintă vorbim despre o dată elementară sau scalară. În aplicaţii, datele se prezintă de cele mai multe ori sub forma unor colecţii de date, a căror principală caracteristică este modalitatea de organizare. Între elementele unei colecţii de date se pot identifica anumite relaţii care determină pe mulţimea respectivă o anumită structură, adică un anumit mod de organizare, astfel încât să faciliteze prelucrarea respectivelor date.

O structură de date este o colecţie organizată de date peste care s-a definit un set de operaţii care pot fi efectuate cu datele respective. În cadrul unei structuri este necesar să se definească relaţiile structurale existente în cadrul mulţimii datelor de prelucrat precum şi metodele de reprezentare şi manipulare a unor asemenea structuri.

Structurile de date care au aceeaşi organizare şi se bazează pe acelaşi set de operaţii formează un anumit tip de structură de date. Astfel, putem clasifica structurile de date în 2 categorii:

• structuri de date de tip standard (sau predefinite). Acestea sunt disponibile în marea majoritate a limbajelor de programare şi se împart la rândul lor în două categorii:

o structuri de date elementare (numite tipuri de date), în care valorile sunt entităţi de informaţie indivizibile. Tipurile de date ce pot fi folosite depind de fiecare limbaj în parte.

o structuri de date de nivel scăzut -sunt structuri relativ simple obţinute prin asamblarea de valori elementare sau valori structurate iar operaţiile sunt date la nivel de componentă. Din această categorie de structuri de date face parte: mulţimea, tabloul şi articolul, în general acestea fiind deja implementate în cadrul limbajelor de programare.

• structuri de date de nivel înalt, sunt structuri complexe, operaţiile fiind implementate utilizând algoritmi proiectaţi de către utilizatori. Aceste tipuri de structuri permit prelucrări eficiente ale datelor.

68

O altă clasificare după tipul de acces la elementele structurii, le grupează pe acestea în 2 categorii:

o cu acces direct –La o structură cu acces direct putem referi o anumită componentă a structurii fără a ţine cont de restul componentelor. O astfel de structură este tabloul, care permite referirea la un anumit element utilizând un indice care precizează poziţia elementului în cadrul tabloului.

o cu acces secvenţial –În cadrul unei structuri cu acces secvenţial, accesul la o anumită componentă se face prin traversarea unor componente din acea structură. Un astfel de acces se întâlneşte în cadrul structurilor dinamice înlănţuite, în cadrul cărora căutarea unui anumit element se face utilizând un pointer care va indica pe rând diverse elemente din cadrul structurii până la identificarea elementului căutat (în cazul unei proceduri de căutare). În cazul structurilor ordonate există o anumite ordine a poziţiilor elementelor

colecţiei, prin care succesorul unui element din colecţie se găseşte pe poziţia imediat următoare. Sistemul de relaţie între elementele unei astfel de structuri are deci la bază arhitectura poziţiilor, fiind astfel exterior elementelor colecţiei referite de structură. Astfel, relaţiile între elementele colecţiei sunt implicite iar aceste structuri se mai numesc şi structuri implicite. Implementarea unei astfel de structuri presupune alocarea în prealabil a unor locaţii succesive de memorie, suficient de mare încât să satisfacă cerinţele potenţiale în ceea ce priveşte numărul de elemente ale structurii, în care se vor putea încărca şi prelucra elemente. Faptul că zona de memorie alocată este de o dimensiune nemodificabilă constituie un handicap şi limitează potenţialul unei astfel de structuri.

Structurile înlănţuite (explicite) sunt caracterizate prin includerea informaţiilor privind poziţia elementului succesor şi/sau predecesor în compoziţia fiecărui element al structurii. Succesorul şi/sau predecesorul unui element este identificat prin intermediul informaţiilor de înlănţuire conţinute de elementul respectiv. Astfel, sistemul de relaţii al elementelor este înregistrat în structura acestora deci este explicit. Un tablou este o structură implicită în timp de o listă liniară simplu înlănţuită este o structură explicită. Dacă structurile sunt create pentru a fi utilizate în memoria internă ele se numesc structuri interne. Acestea au o durată determinată de viaţă, ele dispar fie odată cu oprirea programului, fie sunt create şi distruse în anumite momente ale execuţiei programului. Structurile create pentru a fi reprezentate pe un suport extern de memorare sunt denumite structuri externe (exemplu: fişierele de date). Structurile externe au caracter permanent, de lungă durată.

Asupra unei structuri de date se pot executa mai multe operaţii: � crearea –reprezintă operaţia de memorare pe suportul de reprezentare (intern sau

extern) a unor elemente ce vor constitui starea iniţială a structurii de date � actualizarea –este o operaţie care permite: adăugarea unor noi elemente la o

structură deja creată; modificarea valorilor unor componente ale structurii; ştergerea (suprimarea) unor elemente componente ale structurii

� consultarea –permite accesul la valorile elementelor structurii pentru prelucrarea valorii acestora

� sortarea –permite aranjarea elementelor structurii după nişte criterii stabilite, pe baza unui criteriu de ordonare, în funcţie de valoarea sau valorile unor chei, componente ale elementelor structurii

� ventilarea –reprezintă operaţia de descompunere (desfacere) a unei structuri de date în două sau mai multe structuri (componente)

69

� fuzionarea –este operaţia de combinare a elementelor a două sau mai multe structuri într-una singură Alte operaţii definite pe colecţia referită de o structură derivă din caracterul

static sau dinamic al acesteia. Astfel, structurile pot fi clasificate şi după posibilitatea ca operaţiile să îi afecteze sau nu structura. Corespunzător caracterului static sau dinamic al colecţiei de date avem două tipuri de structuri: statice şi dinamice. Pentru fiecare tip de structură operaţiile sunt specifice. Structurile statice sunt colecţii finite, nemodificabile în timp. Acestea au pe tot parcursul existentei lor acelaşi număr de componente şi în aceeaşi ordine. Sistemul de relaţii are un rol secundar în determinarea operaţiilor definite pe structurile statice. Acestea sunt dominant dependente de compoziţia colecţiei referită de structură. Structurile dinamice sunt colecţii potenţial infinite, modificabile în timp (numărul de elemente depinzând de spaţiul de memorie disponibil în care se poate aloca spaţiu pentru elementele structurii). Structurile dinamice îşi pot modifica structura, în sensul modificării numărului şi poziţiei componentelor. Operaţiile caracteristice structurilor dinamice sunt dominant depedendente de sistemul de relaţii definit peste colecţie. Pentru structurile dinamice, specifice sunt următoarele operaţii:

� crearea colecţiei � explorarea (traversarea) colecţiei în scopul determinării elementelor care

compun colecţia sau al determinării apartenenţei sau neapartenenţei unui element oarecare la colecţie

� inserarea, modificarea sau ştergerea unui anumit element din colecţie � identificarea succesorului sau al predecesorului unui element conform cu

sistemul de relaţii definit peste colecţie 4.2. Fişierul Fişierul este o structură de date externă fiind o colecţie ordonată de date aflată pe un suport extern de memorare. Din punct de vedere logic, componentele unui fişier se numesc articole. Zona de memorie utilizată pentru înregistrarea unui articol se numeşte înregistrare. Un articol este alcătuit din mai multe câmpuri. În funcţie de lungimea unui articol (mărime exprimată în octeţi, egală cu suma lungimilor componentelor unui articol, adică a câmpurilor) avem:

o fişiere cu articole de lungime fixă o fişiere cu articole de lungime variabilă

Evidenţierea articolului curent se face cu ajutorul unui pointer de fişier. Acest pointer indică în permanenţă articolul curent dintr-un anumit fişier. La deschiderea unui fişier acest pointer se poziţionează automat pe primul articol al fişierului. Prin anumite comenzi de pozitionare, putem modifica valoarea acestui indicator de înregistrare, fie trecând la următorul articol, fie prin poziţionarea directă pe un articol cu un anumit indicativ. Sfârşitul fi şierului este evidenţiat printr-o marcă specială, denumită EOF (End of File), care indică faptul că am depăşit ultimul articol şi practic ne găsim la sfârşitul fişierului. Un fişier se caracterizează printr-o anumită metodă de organizare. Prin modul de organizare se înţelege o serie de reguli după care se memorează informaţia pe suportul extern. Alegerea unui anumit mod de organizare va influenţa şi modalitatea de acces la articolele din cadrul fişierului.

70

Există două modalităţi de acces în cazul fişierelor: • accesul secvenţial –reprezintă modalitatea de acces la articolele fişierului printr-

o parcurgere secvenţială, articol după articol până la regăsirea articolului dorit • accesul direct presupune regăsirea articolului dorit direct, pe baza adresei

respectivului articol, neţinând astfel seama de restul articolelor din cadrul fişierului

După modul de organizare al fişierelor distingem: � fişiere secvenţiale –înregistrarea articolelor din fişier de face în locaţii

consecutive. Organizarea secvenţială impune o singură metodă posibilă de acces la înregistrări şi anume accesul secvenţial.

� fişiere relative –organizarea relativă impune înregistrarea articolelor în funcţie de valoarea unei chei, având la bază valori ale unui/unor câmpuri din respectivul articol. Într-o astfel de organizare, informaţiile sunt organizate în celule de aceeaşi lungime, numărul căsuţei indicând poziţia relativă a căsuţei în cadrul fişierului. Pentru a înregistra un articol într-un fişier cu organizare relativă, se va calcula valoarea cheii, care va decide locaţia de memorie în care va fi salvat respectivul articol. Căutarea unui anumit articol se poate face folosind fie un acces secvenţial (ineficient pentru o organizare a fişierului de acest tip) sau un acces direct aflând pe baza cheii adresa de memorie la care este memorat articolul având o cheie dată.

� fişiere indexate –în cazul acestui tip de organizare, articolele sunt înregistrate secvenţial, în locaţii consecutive de memorie. Paralel cu fişierul care conţine articolele propriu-zise, este gestionat şi unul sau mai multe fişiere index. Aceste fişiere index se crează pe baza unor chei de indexare. Accesul la un articol dint-un fişier indexat, se face prin explorarea tabelei de indecşi până la întâlnirea indexului ce conţine o cheie dată după care accesul va fi direct în fişier la articolul corespunzător, pe baza adresei astfel determinate.

4.3. Tabloul

Fiind dat un număr natural k şi An={1,2,…ni} i=1,k unde Ani conţine primele ni numere naturale, atunci tabloul este o funcţie f:An1xAn2x..Ank->T unde T este o mulţime oarecare.

Un tablou este o colecţie omogenă de date în care fiecare element poate fi identificat pe baza unui index, colecţia asigurând acces direct şi timp de acces constant pentru fiecare element al ei.

Dacă k=1 atunci tabloul este unidimensional iar componentele sunt identificate cu ajutorul unui singur indice. Dacă k=2 tabloul este o matrice şi vom avea nevoie de 2 indici pentru a identifica o componentă. Numărul maxim de dimensiuni pe care îl putem folosi în cazul tablourilor n-dimensionale depinde de fiecare limbaj de programare în parte.

Observaţie: în funcţie de specificul fiecărui limbaj de programare, implementarea unui tablou va avea mulţimea de indecşi diferită astfel: limbajul Pascal utilizează indici pentru tablouri pornind în general de la valoarea 1 (dar ei pot varia între orice limite întregi) în timp ce în limbajul C indicii pornesc de la 0.

71

Caracteristicile acestui tip de structură sunt: -este o structură ordonată, succesorul fiecărui element se găseşte în locaţia următoare de memorie. Numerotarea locaţiilor de memorie permite accesarea directă a oricărui element, folosind numerele asociate locaţiilor de memorie (indici sau indecşi). -este o structură statică, datorită imposibilităţii modificării în timp (în cursul execuţiei programului) a dimensiunii acesteia. Deci este necesară estimarea dimensiunii unui tablou în timpul scrierii programului. Poziţia fiecărui element rămâne neschimbată, ceea ce se pot modifica fiind valorile fiecărui element al tabloului. -tabloul poate fi văzut şi ca o mulţime de perechi de forma (index, valoare) unde index aparţine unei mulţimi a indecşilor iar valoare unei mulţimi a valorilor.

Structurarea elementelor din mulţimea T într-un tablou ne va permite să ştim de exemplu care este primul sau ultimul element din tablou. Vom putea accesa elementul i sau elementul de pe linia i şi coloana j a unei matrici. Acest mod de structurare este ineficient în cazul în care numărul elementelor variază în limite largi, deoarece va trebui să precizăm încă din faza de compilare a programului numărul maxim de elemente ale tabloului. Ordinea de memorare a componentelor este dată de ordinea lexicografică definită peste indici. În cazul unui tablou bidimensional (matrice), în general reprezentarea în memorie se face pe linii (elementele primei linii urmate apoi de elementele celei de a doua linii ş.a.m.d.), după cum o matrice poate fi văzută ca un vector de linii.

4.4. Tabela de dispersie

Principala diferenţă dintre un vector obişnuit şi o tabelă de dispersie constă în modul în care se determină poziţia (adresa) unde se introduce un nou element. O valoare nouă nu se adaugă în prima poziţie liberă ci într-o poziţie care să permită regăsirea rapidă a acestei valori, fără a fi necesară o căutare prin vector. Astfel se calculează poziţia în care va fi inserat elementul în tabela de dispersie în funcţie de valoarea ce trebuie inserată. Calculul se face atât la inserare cât şi la regăsire. Procedura de calcul a indicelui pornind de la valoarea ce urmează a fi inserată se numeşte şi metodă de dispersie. Această metodă trebuie să asigure o împrăştiere cât mai uniformă a cheilor pe vectorul alocat pentru memorarea lor. O metodă generală de calcul a adresei din cheie foloseşte un cod hash (numit şi cod de dispersie) (un număr natural obţinut pe baza cheii, transformată cu ajutorul unei funcţii de dispersie) iar restul împărţirii codului hash la dimensiunea vectorului va reprezenta indicele respectivului element în tabela de dispersie.

Funcţia de dispersie (hashing) este definită astfel: f : K → H

unde K este mulţimea cheilor iar H este o mulţime de numere naturale. Pentru obţinerea codului hash se folosesc diverse metode. De exemplu, în cazul

şir de caractere se poate folosi o metodă care calculează suma ponderată a codurilor caracterelor ce compun respectivul şir de caractere.

Funcţia f nu este injectivă iar două chei pentru care f(k1)=f(k2) se spune că intră în coliziune. Orice metodă se foloseşte pentru generarea codului hash, se vor obţine inevitabil “sinonime”, adică coduri hash identice şi deci poziţii identice pentru valori diferite ale unor elemente ce urmează a fi inserate în tabela de dispersie. Sinonimele se

72

numesc şi coliziuni pentru că mai multe elemente îşi dispută aceeaşi poziţie în tabela de dispersie.

Asupra funcţiei f se impun două condiţii: -valoarea ei pentru un număr k∈K să rezulte cât mai simplu şi rapid -să minimizeze coliziunile

Pentru rezolvarea coliziunilor există 2 metode:

a) Calcularea unei noi adrese în acelaşi vector pentru sinonimele care găsesc ocupată poziţia rezultată din calcul. În acest caz fie se caută prima poziţie liberă, fie se aplică o a doua metodă de dispersie.

b) Metode care plasează coliziunile în afara vectorului principal. Se pot folosi fie un vector auxiliar, fie liste înlănţuite de sinonime care pleacă din poziţia rezultată din calcul pentru fiecare grup de sinonime. Vor exista astfel mai multe liste, fiecare conţinând înregistrări cu aceleaşi cod de dispersie. Aceste metode asigură un timp mai bun de regăsire dar folosesc mai multă memorie. Există posibilitatea de extindere nelimitată dar performanţele de căutare ale unui anumit element se vor degrada semnificativ.

.

.

.

.

.

.

.

.

Lista de depasire pentru elementul 3

Lista de depasire pentru elementul 1

Lista de depasire pentru elementul n

1

2

3

4

n

Fig.4.1. Tabela de dispersie

4.5. Lista liniară simplu înlănţuită

O listă liniară (numită şi listă înlănţuită -”Linked List”) este o colecţie de n>=0 elemente x[1], … x[n] toate de un tip oarecare, numite noduri între care există o relaţie de ordine determinată de poziţia lor relativă. Ea este deci o mulţime eşalonată de elemente de acelaşi tip având un număr arbitrar de elemente. Numărul n al nodurilor se numeşte lungimea listei. Dacă n=0, lista este vidă. Dacă n>=1, x[1] este primul nod iar x[n] este ultimul nod. Pentru 1<k<n, x[k] este precedat de x[k-1] şi urmat de x[k+1].

Acest tip de structură de date se aseamănă cu o structură standard: tipul tablou cu o singură dimensiune (vector), ambele structuri conţinând elemente de acelaşi tip iar

73

între elemente se poate stabili o relaţie de ordine. Una dintre deosebiri constă în numărul variabil de elemente care constituie lista liniară, dimensiunea acesteia nu trebuie declarată şi deci cunoscută anticipat (în timpul compilării) ci se poate modifica dinamic în timpul execuţiei programului, în funcţie de necesităţi. Astfel utilizatorul nu trebuie să fie preocupat de posibilitatea depăşirii unei dimensiuni estimate iniţial, singura limită fiind mărimea zonei heap din care se solicită memorie pentru noile elemente ale listei liniare. Un vector ocupă în memorie un spaţiu continuu de memorie, pe când elementele unei liste simplu înlănţuite se pot găsi la adrese nu neapărat consecutive de memorie.

O altă deosebire avantajează vectorii, deoarece referirea unui element se face prin specificarea numărului de ordine al respectivului element, pe când accesul la elementele unei liste liniare se face secvenţial, pornind de la capul listei (adresa primului nod al listei) până la ultimul element al ei, ceea ce măreşte uneori considerabil timpul de acces la un anumit element. Pentru o listă liniară este obligatoriu să existe o variabilă, declarată în timpul compilării, denumită cap de listă care să păstreze adresa primului element al listei. Aceasta va fi fie o variabilă globală fie va fi transmisă ca parametru fiecărei funcţii care doreşte să exploateze lista. Pierderea acestei valori va duce la imposibilitatea accesării elementelor listei liniare.

Pentru implementarea dinamică a unei liste liniare (folosind pointeri), nodurile listei vor fi structuri ce conţin două tipuri de informaţie:

o câmpurile ce conţin informaţia structurală a nodului, numite într-un cuvânt INFO

o câmpurile ce conţin informaţia de legătură, numite LINK ce vor conţine pointeri la nodurile listei. Înlănţuirea secvenţială a elementelor unei liste se face utilizând variabile de tip pointer, care specifică adresa de memorie a elementelor adiacente. Fiecare nod are un predecesor şi un succesor (mai puţin elementele prim şi ultim dacă lista nu este circulară). Listele înlănţuite cu un singur câmp de legătură se numesc liste simplu înlănţuite

(legătura indică următorul element din listă) iar cele cu 2 câmpuri de legătură liste dublu înlănţuite (o legătură indică nodul precedent iar cealaltă nodul succesor).

În cazul listelor simplu înlănţuite, fiecare element al listei conţine adresa următorului element al listei. Ultimul element poate conţine ca adresă de legătură fie constanta NULL (sau constanta 0 care nu indică nici un alt element), fie adresa primului element al listei, în cazul listelor liniare circulare.

. . .

Cap lista

0. . .

Fig. 4.2. Lista liniară simplu înlănţuită

În consecinţă, un element al unei structuri din categoria listelor liniare trebuie să

aibă o structură de tip articol (record), în care cel puţin un element este de tip pointer, iar restul câmpurilor vor constitui informaţia utilă asociată fiecărui element.

În C, o listă simplu înlănţuită se poate defini astfel:

74

typedef struct LISTA { int cheie; //informaţia propriu-zisă // alte informaţii struct LISTA *urm; //informaţia de legătură, pointer spre următorul //element al listei } lista;

Se observă că definiţia acestui tip de structură este recursivă adică conţine un element (informaţia de legătură) care foloseşte tipul în curs de definire.

Se vor defini variabile de tipul lista, de exemplu: lista *prim,*p,*q;

Principalele operaţii care se fac asupra unei liste liniare sunt:

-creare (inserare într-o listă iniţial vidă) -inserare nod -ştergere nod -traversare listă -căutare nod 4.6. Lista liniară circulară simplu înlănţuită

Lista circulară simplu înlănţuită este tot o listă liniară simplu înlănţuită cu deosebirea că nu există ultimul element, adică pointerul de legătură al ultimului nod al listei nu indică valoarea NULL ci indică spre primul element al listei.

4.7. Lista liniară dublu înlănţuită

Listele dublu înlănţuite sunt tot liste liniare, cu deosebirea că fiecare element al listei are două referinţe: una spre elementul precedent şi una spre elementul succesor.

În C, definirea unei liste dublu înlănţuite se poate face astfel: typedef struct LISTAD { int cheie; //informaţia propriu-zisă // alte informaţii struct LISTAD *pred, * suc; //informaţiile de legătură: pointer spre

//predecesor şi pointer spre succesorul //acestui element

} listad; Se vor defini variabile de tipul lista, de exemplu: listad *prim,*p,*q;

75

.

Cap lista

. . .NULL

.. .. NULL

.

Fig. 4.3. Lista liniară dublu înlănţuită

4.8. Structura de tip stivă (LIFO Last In First Out)

O stivă (în engleză stack) este o structură de tip LIFO (Last In First Out =ultimul intrat primul ieşit) şi este un caz particular al listei liniare în care toate inserările (depunerile –în engleză push) şi ştergerile (sau extragerile -în engleză pop) (în general orice acces) sunt făcute la unul din capetele listei, numit vârful stivei. Acest nod poate fi citit, poate fi şters sau în faţa lui se poate insera un nou nod care devine cap de stivă.

push pop

Fig. 4.4. Mecanismul de stivă Pentru înţelegerea mecanismului unei stive, se poate folosi reprezentarea

manevrării într-un depou a vagoanelor de cale ferată sau a unui vraf de farfurii din care putem depune şi extrage doar în şi din vârful vrafului. Stivele sunt legate şi de algoritmii recursivi, la care salvarea variabilelor dintr-o funcţie care se apelează recursiv se face având la bază un mecanism de tip stivă.

O stivă poate fi implementată ca o listă liniară pentru care operaţiile de acces (inserare, ştergere, accesare element) sunt restricţionate astfel: -inserarea se face doar în faţa primului element al listei (capul listei) -accesarea respectiv ştergerea acţionează doar asupra primului element al listei

O stivă poate fi implementată folosind o structură de date statică sau dinamică.

76

În abordarea statică, stiva poate fi organizată pe un spaţiu de memorare de tip tablou unidimensional.

În abordarea dinamică, implementarea unei stive se poate face folosind o structură de tip listă liniară simplu înlănţuită în care inserarea se va face tot timpul în capul listei iar ştergerea de asemenea se va face în capul listei. 4.9. Structura de tip coadă

O coadă (în engleză queue) este o structură de tip FIFO (First In First Out = Primul venit primul servit), în care toate inserările se fac la un capăt al ei (numit capul cozii) iar ştergerile (extragerile) (în general orice acces) se fac la celălalt capăt (numit sfârşitul cozii). În cazul cozii, avem nevoie de doi pointeri, unul către primul element al cozii (capul cozii), iar altul către ultimul său element (sfârşitul cozii). Există şi o variantă de coadă circulară, în care elementele sunt legate în cerc, iar cei doi pointeri, indicând capul şi sfârşitul cozii, sunt undeva pe acest cerc.

push pop

Fig. 4.5. Mecanismul de coadă

Se poate face o analogie cu o cale ferată pe un singur sens sau cu obişnuita coadă la un ghişeu oarecare la care primul venit este şi primul servit. Pentru gestiunea unei cozi sunt necesari doi indicatori: -un indicator care indică primul element ce urmează a fi scos -un indicator care indică unde va fi pus următorul element adăugat la coadă Într-o abordare statică, o coadă poate fi implementată folosind un spaţiu de memorare de tip tablou unidimensional. În acest caz, adăugări şi ştergeri repetate în coadă deplasează conţinutul cozii la dreapta, faţă de începutul vectorului. Pentru evitarea acestei deplasări, o soluţie este ca fiecare operaţie de extragere din coadă să fie acompaniată de deplasarea la stânga a conţinutului cozii cu o poziţie. În acest caz, primul element care urmează să fie eliminat din coadă va fi întotdeauna pe prima poziţie, indicatorul care să indice elementul ce urmează să fie scos pierzându-şi utilitatea. Dezavantajul acestei soluţii îl reprezintă necesitatea deplasării întregului set de elemente din coadă rămase cu o poziţie. În implementarea propusă în continuare, depunerea se face la începutul tabloului, depunere precedată de decalarea tuturor elementelor cu o poziţie la dreapta. Extragerea se face începând cu primul element din partea dreaptă. Într-o abordare dinamică, o coadă poate fi implementată folosind o listă liniară simplu înlănţuită la care operaţiile de acces sunt restricţionate corespunzător. Există două abordări: -una în care adăugarea se face tot timpul la începutul listei liniare simplu înlănţuite iar extragerea se face de la sfârşitul listei

77

-cea de a doua, în care adăugarea se face la sfârşitul listei iar extragerea se face din capul listei. 4.10. Grafuri neorientate Definiţii :

Se numeşte graf neorientat o pereche ordonată de mulţimi (X, U), X fiind o mulţime finită şi nevidă de elemente numite noduri sau vârfuri, iar U o mulţime de perechi neordonate (submulţimi cu două elemente) din X, numite muchii.

G=(X,U) Pentru o muchie se poate folosi notaţia (xi,xj) sau (xj,xi) având aceeaşi

semnificaţie şi deci nereprezentând muchii diferite în cazul unui graf neorientat. Exemplu:

1

2

3

5

4

6

7

8

Fig. 4.6. Graful neorientat G=(X,U)

Pentru graful de mai sus mulţimea vârfurilor este X={1,2,3,4,5,6,7,8} iar mulţimea muchiilor este: U={[1,2],[1,3],[1,4],[2,4],[2,5],[3,4],[4,5],[6,7]}.

Două muchii cu extremitate comună se numesc adiacente. Muchia [x,y] se numeşte incidentă cu vârfurile x şi y iar x şi y sunt extremităţile muchiei [x,y].

Un graf parţial al grafului G=(X,U) este un graf Gp=(X,V) astfel încât V⊆U, adică Gp are aceeaşi mulţime de vârfuri ca G iar mulţimea de muchii V este chiar U sau o submulţime a acesteia. Exemplu de graf parţial:

1

2

3

5

4

6

7

8

Fig.4.7. Graf parţial al grafului G

78

Un graf parţial al unui graf se obţine păstrând aceeaşi mulţime de vârfuri şi eliminând o parte din muchii. Un subgraf al unui graf G=(X,U) este un graf H=(Y,V) astfel încât Y⊂X iar V conţine toate muchiile din U care au ambele extremităţi în Y. Exemplu de subgraf al grafului G obţinut prin eliminarea nodului 4:

1

2

3

5

6

7

8

Fig.4.8. Subgraf al grafului G

Gradul unui vârf este numărul muchiilor incidente cu acel vârf (sau, altfel spus,

numărul de noduri adiacente cu acesta). Gradul unui vârf x se notează cu d(x). În cazul grafului G, d(1)=2; d(4), d(8)=0; Un vârf care are gradul 0 se numeşte vârf izolat. Un vârf care are gradul 1 se numeşte vârf terminal. În cazul grafului G, vârful 8 este vârf izolat iar vârfurile 6 şi 7 sunt izolate. Un graf este regulat dacă toate nodurile au acelaşi grad. Se numeşte graf complet un graf care are proprietatea că orice două noduri diferite sunt adiacente (deci există muchie între oricare două noduri).

Un drum într-un graf este o mulţime ordonată de noduri ale grafului: (x1, x2, ..., xk), cu proprietatea că există în graf toate arcele de forma (xi,xi+1) cu i = 1,...,k-1.

Un drum elementar este un drum în care fiecare nod apare o singură dată. Un drum simplu este un drum în care fiecare arc apare o singură dată. Se numeşte lanţ într-un graf G=(X,U) succesiunea de muchii (x1,x2), (x2,x3),

…(xi-1,xi), unde x1,x2,... xi aparţin lui X. x1 şi xi reprezintă extremităţile acestui lanţ. Un lanţ este de fapt un drum în care arcele nu au neapărat acelaşi sens de parcurgere.

Lungimea unui lanţ reprezintă numărul de muchii din care acesta este format. Un lanţ este elementar dacă, cu excepţia eventual a extremităţilor, celelalte

vârfuri diferă. Un lanţ compus este un lanţ care nu este format numai din muchii distincte. Un lanţ pentru care extremităţile coincid (deci x1=xi) se numeşte ciclu. Un ciclu

este un circuit în care arcele nu au neapărat acelaşi sens de parcurgere. Un ciclu este elementar dacă este format doar din noduri distincte, excepţie

făcând primul şi ultimul nod. Un circuit este un drum pentru care extremităţile coincid.

79

Un graf este conex dacă pentru orice pereche de noduri există un lanţ care le uneşte.

O componentă conexă a unui graf este un subgraf al grafului de referinţă, maximal în raport cu proprietatea de conexitate (între oricare 2 vârfuri există lanţ şi nu există un alt subgraf al grafului de referinţă care să îndeplinească proprietatea de mai sus şi să conţină acest subgraf).

Un graf este conex dacă admite o singură componentă conexă.

Reprezentarea grafurilor neorientate: Pentru reprezentarea grafurilor neorientate se pot utiliza matricea de adiacenţă,

listele de adiacenţă şi vectorul muchiilor. Matricea de adiacenţă este pentru graful G=(X,U) având n noduri şi m muchii

este o matrice pătratică A(n,n) având proprietatea: a(i,j)=1 dacă există muchia (i,j)∈U şi 0 în caz contrar.

Listele de adiacenţă se utilizează în cazul în care numărul de muchii ale grafului este mult mai mic decât numărul nxn (reprezentând numărul de elemente din matricea de adiacenţă a aceluiaşi graf). Pentru reprezentarea listelor de adiacenţă se poate folosi o alocare statică sau dinamică (utilizând un tablou unidimensional de pointeri spre liste simplu înlănţuite). Definirea tabloului de pointeri (pentru un graf cu maxim 20 de noduri) poate fi făcută astfel: struct l_a {int nod; l_a *next;}; l_a *L[20]; Astfel L[0] este un pointer spre structura l_a ce conţine lista vecinilor pentru primul nod, L[1] pentru al doilea nod etc..

Vectorul muchiilor Cele m muchii ale unui graf pot fi reprezentate utilizând un tablou de m elemente structuri, fiecare structură conţinând cele două extremităţi ale muchiei. struct muchie { int nodi, nodf;} struct muchie MUCHII[20]; Fiecare element al tabloului mai sus definit reprezintă o structură ce conţine 2 noduri reprezentând extremităţile unei muchii.

80

Parcurgerea grafurilor neorientate: Prin parcurgerea grafurilor neorientate se înţelege vizitarea vârfurilor într-o anumită ordine, ordine dată de un anumit criteriu. Astfel, există două metode de parcurgere:

o Parcurgerea în lăţime (Breadth First) o Parcurgerea în adâncime (Depth First)

Parcurgerea în lăţime presupune parcurgerea tuturor vârfurilor grafului

începând de la un vârf dat. Astfel, după vizitarea vârfurlui de pornire, se vizitează toate vârfurile adiacente cu acesta care nu au fost vizitate încă, după care se continuă cu primul vârf adiacent cu vârful de pornire şi se vizitează toate vârfurile adiacente cu acesta nevizitate încă şi aşa mai departe pentru restul vârfurilor. Parcurgerea în adâncime presupune după alegerea şi traversarea vârfului de pornire, traversarea primului vecin nevizitat încă, pentru acest vecin se traversează primul său vecin nevizitat şi aşa mai departe. În cazul în care un vârf nu mai are vecini nevizitaţi, ne întoarcem la nodul anterior, iar pentru acel nod căutăm următorul vecin nevizitat încă.

În ambele modalităţi de traversare, dacă graful nu este conex, nu se vor putea parcurge toate nodurile. Drumuri într-un graf

Matricea de adiacenţă A(n,n) a unui graf G=(X,U) evidenţiază drumurile de lungime 1 între oricare 2 noduri ale grafului. Pentru a găsi drumurile de lungime 2 între 2 noduri ale unui graf se procedează astfel. Se consideră două noduri x

i şi x

j ∈X. Existenţa unui drum de lungime 2 între ele

presupune existenţa unui nod xk∈X, cu proprietatea că există atât arcul (x

i,x

k) cât şi

arcul (xi,x

k). Pentru a vedea dacă acest arc există, se poate lua pe rând fiecare nod al

grafului şi verificăm dacă există sau nu ambele arce ((xi,x

k) şi (x

i,x

k)). Aceasta este

echivalent cu a verifica dacă în matricea de adiacenţă există vreun indice k astfel încât elementul k al liniei i şi elementul k al coloanei j să fie ambele egale cu 1. Acest lucru este echivalent cu a verifica dacă elementul de pe poziţia (i,j) din A2

este diferit de 0. Numărul de drumuri de lungime 2 dintre x

i şi x

j este dat de valoarea elementului A2(i,j).

Generalizând, numărul de drumuri de lungime k dintre xi şi x

j este dat de

valoarea elementului Ak(i,j). Dacă între nodurile x

i şi x

j există un drum de lungime ≥ n atunci el va conţine un

număr de noduri mai mare sau egal nu n+1 şi, cum în graf sunt doar n vârfuri, este clar că cel puţin unul, să zicem x

k, va apărea de două ori. Vom avea în acest caz un drum de

la xi până la prima apariţie a lui x

k, şi un drum de la ultima apariţie a lui x

k la x

j.

Eliminând toate nodurile dintre prima apariţie a lui xk şi ultima apariţie a sa vom obţine

un drum de la xi la x

j, în care x

k apare o singură dată. Aplicând acest procedeu pentru

toate nodurile care apar de mai multe ori pe drum, vom obţine un drum de la xi la x

j, în

care fiecare nod apare o singură dată (deci un drum elementar), care are evident cel mult

81

n-1 arce. În concluzie, dacă există vreun drum de la xi la x

j atunci există şi un drum

elementar şi, deci, va exista o putere a lui A, între A1 şi An-1, în care poziţia (i,j) este diferită de 0. Pentru deciderea existenţei unui drum între oricare două noduri este suficientă, deci, calcularea doar a primelor n-1 puteri ale lui A. Grafuri ponderate:

Într-un graf neorientat, fiecărei muchii i se poate asocia o pondere (un cost). Putem considera un graf neorientat fără ponderi ca fiind o particularizare a unui graf cu costuri, fiecare muchie având costul 1. Această pondere (sau cost) va exprima intensitatea relaţiei dintre 2 noduri ale grafului.

Reprezentarea unui astfel de graf G=(X,U) se face utilizând o matrice a ponderilor P(n,n) a cărei elemente se definesc astfel: p(i,j) = 0 dacă i=j p(i,j) = c(i,j) în cazul în care (i,j) este o muchie din U unde c(i,j) este costul muchiei (i,j). p(i,j) = ∞ în restul cazurilor

Utilizarea grafurilor ponderate este des întâlnită în practică. Cel mai sugestiv

exemplu este cel al unei reţele de oraşe, nodurile grafului reprezentând oraşele, muchiile reprezentând legăturile (şoselele) dintre oraşe iar costul lor este dat de distanţa dintre oraşe. Grafuri hamiltoniene:

Un lanţ elementar care conţine toate nodurile unui graf se numeşte lanţ hamiltonian.

Un ciclu elementar care conţine toate vârfurile grafului se numeşte ciclu hamiltonian.

Graful care conţine un ciclu hamiltonian se numeşte graf hamiltonian. Grafuri euleriene:

Un lanţ simplu care conţine toate muchiile unui graf este un lanţ eulerian. Un ciclu eulerian este un ciclu care conţine toate muchiile grafului. Un graf eulerian este un graf care conţine un ciclu eulerian.

Condiţie necesară şi suficientă: Un graf este eulerian dacă şi numai dacă oricare vârf al său are gradul par. 4.11. Grafuri orientate

Numim graf orientat, o pereche ordonată de mulţimi G=(X,U), unde X este o mulţime finită şi nevidă numită mulţimea nodurilor (vârfurilor) iar U este o mulţime formată din perechi ordonate de elemente ale lui X, numită mulţimea arcelor. Prin perechi ordonate nu se înţelege că un arc este mai mare decât altul, ci pur şi simplu se face deosebirea între un arc de forma (xi,xj) şi un altul de forma (xj,xi) (arcul (xi,xj) este diferit de arcul (xj,xi)). În cazul grafurilor neorientate, muchiile nu au o direcţie deci pot fi parcurse în ambele sensuri.

82

1

2

3

5

4

6

7

8

Fig. 4.9. Graf orientat

În graful din figura de mai sus avem X={1,2,3,4,5,6,7,8} şi U={(1,1),(1,2),(1,3),(2,4),(2,5),(3,4),(4,1),(4,5),(6,7)}.

Un exemplu de graf orientat este reţeaua de străzi a unui oraş. Străzile sunt muchii în graf iar intersecţiile reprezintă vârfurile grafului. Din punct de vedere al traficului rutier, vorbim de un graf orientat deoarece există atât străzi cu 2 sensuri cât şi străzi cu sens unic. Din punct de vedere pietonal, acest graf este neorientat, deoarece orice stradă poată fi parcursă pe jos în ambele sensuri.

Un arc are forma u=(x,y), unde x este extremitatea iniţială, iar y este extremitatea finală a arcului. Arcul “iese” din nodul x şi “intr ă” în nodul y. Analog ca la grafurile neorientate, nodurile x şi y sunt adiacente, iar arcul u şi nodul x sunt incidente (la fel arcul x şi nodul y). Nodul y se numeşte succesor al lui x, iar nodul x se numeşte predecesor al lui y. Un arc de forma (x,x), care iese din nodul x şi intră tot în nodul x, se numeşte buclă (exemplu arcul (1,1) în figura de mai sus).

Într-un graf putem avea şi două sau mai multe arcuri identice. Gradul exterior al unui vârf x, notat d*(x), reprezintă numărul arcelor care ies

din nodul x, adică numărul arcelor de forma (x,z) ε U. Gradul interior al unui vârf x, notat d-(x), reprezintă numărul arcelor care intră

în nodul x, adică numărul arcelor de forma (y,x) ε U. Gradul total al unui vârf x, dintr-un graf orientat, este un număr natural ce

reprezintă suma gradelor interior şi exterior şi este egal cu numărul arcelor incidente cu vârful. Exemplu: pentru graful de mai sus: d*(1)=3, d*(2)=2, d*(5)=0 d-(1)=2, d-(5)=2, d-(6)=0. În cazul unui graf orientat, un nod x este izolat dacă d*(x)= d-(x)=0.

Se definesc mulţimile:

( ) ( ){ }UyxXyx ∈,∈=Γ+ reprezintă mulţimea nodurilor ce constituie extremităţi finale

ale arcelor care pleacă din nodul x (mulţimea succesorilor lui x).

83

( ) ( ){ }UxyXyx ∈∈=Γ− , reprezintă mulţimea nodurilor ce constituie extremităţi iniţiale

ale arcelor care intră în nodul x (mulţimea predecesorilor lui x). ω+(x) = {u = (x,y)| u ε U} reprezintă mulţimea arcelor care ies din nodul x. ω-(x) = {u = (y,x)| u ε U} reprezintă mulţimea arcelor care intră în nodul x. Γ +(1)={1,2,3}, Γ +(2)={4,5}, Γ +(5)={} Γ -(1)={1,4}, Γ -(5)={2,4}, Γ -(6)={} ω+(1)={(1,1),(1,2),(1,3)}, ω+(2)={(2,4),(2,5)}, ω+(5)={} ω-(1)={(1,1),(4,1)} ω-(5)={(2,5),(4,5)} ω-(6)={} Se numeşte drum în graful G, un şir de noduri D={x1, x2, x3, …, xk}, unde x1, x2, x3, …, xk ∈ x, cu proprietatea că oricare două noduri consecutive sunt adiacente, adică există arcele [x1, x2], [x2, x3], …, [xk-1,xk] care aparţin lui U. Deosebirea unui drum faţă de un lanţ constă în faptul că de-a lungul unui arc ne putem deplasa numai în sensul dat de orientarea arcului.

Un graf este tare conex dacă între oricare două noduri există cel puţin un drum. Un graf este simplu conex dacă între oricare două noduri există cel puţin un lanţ.

Observaţie: Pentru grafuri neorientate noţiunile de tare conex şi simplu conex sunt echivalente, graful numindu-se doar conex O componentă tare conexă a unui graf G = (X,U) este un subgraf al lui G care este tare conex şi nu este subgraful nici unui alt subgraf tare conex al lui G (altfel spus, între oricare două noduri din componentă există cel putţn un drum şi nu mai există nici un nod în afara componentei legat printr-un drum de un nod al componentei). Reprezentarea grafurilor orientate Ca şi în cazul grafurilor neorientate, există mai multe forme de reprezentare, cea mai întâlnită fiind matricea de adiacenţă. Ca şi în cazul grafurilor neorientate, elementele matricii de adiacenţă A(n,n) se determină astfel: a(i,j)=1 dacă există arcul (i,j) a(i,j)=0 în caz contrar. Matricea de adiacenţă în cazul grafurilor orientate nu este simetrică (precum cea pentru grafuri neorientate) (deoarece existenţa arcului (i,j) nu implică în nici un fel existenţa unui arc (j,i)). Suma elementelor de pe linia k reprezintă gradul exterior al vârfului k iar suma elementelor de pe coloana k reprezintă gradul interior al vârfului k În cazul grafului orientat prezentat mai sus această matrice arată astfel:

84

1 2 3 4 5 6 7 8 1 1 1 1 0 0 0 0 0 2 0 0 0 1 1 0 0 0 3 0 0 0 1 0 0 0 0 4 1 0 0 0 1 0 0 0 5 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 1 0 7 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 Grafurile orientate se pot reprezentra şi cu ajutorul matricei de incidenţă B care se defineşte astfel: b(i,j) = 1, dacă arcul [xi,xj] are extremitatea iniţială în xi b(i,j) = -1, dacă arcul [xi,xj] are extremitatea finală în xi b(i,j) = 0, în rest. O altă formă de reprezentare a grafurilor orientate este matricea vârfuri-arce. Pentru un graf G=(X,U) cu n vârfuri şi m arce (u1, u2, .. um), această matrice are n linii şi m coloane iar elementele ei se definesc astfel: v(i,j)= 1 dacă nodul i este o extremitate iniţială a arcului uj v(i,j)= -1 dacă nodul i este o extremitate finală a arcului uj v(i,j)= 0 dacă nodul i nu este o extremitate a arcului uj

Pentru reprezentarea grafurilor orientate se pot utiliza şi listele vecinilor. Pentru fiecare nod x se construiesc 2 liste ale vecinilor: L*(x) este lista vecinilor succesori şi conţine nodurile ce sunt extremităţi finale ale arcelor care ies din nodul x. L-(x) este lista vecinilor predecesori şi conţine nodurile ce sunt extremităţi ini ţiale ale arcelor care intră în nodul x. Un graf orientat poate fi privit şi ca un vector de arce, un arc fiind o înregistrare cu 2 componente, acestea fiind nodurile care constituie extremităţile arcului. Astfel avem nodul din care iese arcul (nodul de început al arcului) şi nodul în care intră arcul (nodul de sfârşit al arcului). Exemplu: struct arc { int nodi, nodf;} struct arc ARCE[50]; Implementarea unui graf utilizând pointeri Pentru a defini un graf utilizând pointeri, vom defini următoarele structuri: typedef struct NODL { struct NODG *nod; //nodul adiacent indicat struct NODL *urml; //pointer spre următorul nod în lista de adiacenţe } nodl;

85

typedef struct NODG { int cheie; … informaţii struct NODL *inc_lista, *sfarsit_lista; //începutul şi sfârşitul listei de adiacenţă struct NODG *urmg; //pointer spre următorul nod al grafului } nodg; struct nodg *incG, *sfG; //începutul şi sfârşitul listei de noduri din graf Drumul optim într-un graf Una din problemele care apar foarte des în practică este găsirea drumului optim între două noduri ale unui graf. Formalizarea problemei drumului optim este următoarea: "Fiind dat un graf G = (X,U) şi o funcţie care asociază fiecărui arc o valoare reală, să se găsească, pentru o pereche dată de noduri, drumul (drumurile) de valoare optimă (minimă sau/şi maximă) între cele două noduri şi valoarea acestuia (acestora)". Valoarea unui drum este dată de suma valorilor arcelor care îl compun. Pentru problema drumului optim s-au elaborat mai multe categorii de algoritmi, după cum urmează: 1. Algoritmi prin calcul matricial (Bellman-Kalaba, I. Tomescu, Bellman-Schimbell); 2. Algoritmi prin ajustări succesive (Ford); 3. Algoritmi prin inducţie (Dantzig); 4. Algoritmi prin ordonare prealabilă a vârfurilor grafului; 5. Algoritmi prin extindere selectivă (Dijkstra).

4.12. Arbori

Un arbore se defineşte ca o mulţime de noduri având următoarele proprietăţi: o există un nod special numit rădăcină o celelalte noduri sunt partiţionate în n (>=0) seturi disjuncte nTTT ,...,, 21 , fiecare

din aceste seturi fiind arbori la rândul lor. Aceste seturi se numesc subarbori ai nodului rădăcină.

În cazul arborilor, în locul noţiunilor de “varfuri” şi “muchii”, se folosesc

termenii sinonimi de “noduri “ respectiv “arce”.

Se consideră un graf G=(X,U) .Următoarele afirmaţii sunt echivalente: 1. G este arbore; 2. G este un graf conex, minimal în raport cu această proprietate (adică

eliminând un arc oarecare, se obţine un graf ne-conex respectiv se creează două componente conexe) (deci un arbore este un graf conex cu număr minim de arce);

3. G este un graf fără cicluri, maximal în raport cu această proprietate (adică adăugând un arc oarecare, unind astfel două noduri neadiacente, se obţine un graf care are cel puţin un ciclu). Un arbore este deci pentru o mulţime de

86

noduri dată, graful cu numărul maxim de arce astfel încât să se păstreze proprietatea că nu are cicluri.

Predecesorul (părintele) unui nod se defineşte astfel: Un nod x din care porneşte

un arc către nodul y se spune că este predecesorul nodului y. Succesorul (descendentul sau fiul) unui nod se defineşte astfel: Un nod y către

care există o legătură directă din nodul x se spune că este succesorul nodului x. Ordinea legăturilor spre fii este importantă şi de aceea vorbim de fiul stâng şi

fiul drept al unui nod. Într-un arbore, fiecare nod poate avea mai mulţi succesori, dar un singur

predecesor, cu excepţia unui singur nod (nodul rădăcină) care nu are nici un predecesor (în nodul rădăcină nu intră nici un arc). Cu excepţia rădăcinii, în fiecare nod al unui arbore intră un singur arc. Orice arbore cu n noduri are n-1 arce.

Un arbore poate fi privit şi ca o extindere a unei liste liniare. Astfel, un arbore în care fiecare nod are un singur succesor, pe aceeaşi parte, este de fapt o listă liniară.

Structura de arbore este o structură ierarhică, cu noduri aşezate pe diverse niveluri, cu relaţii de tip părinte-fiu între noduri. Fiecare nod are o anumită înălţime faţă de rădăcină; toţi succesorii unui nod se află pe acelaşi nivel şi au aceeaşi înălţime. Rădăcina arborelui se află pe nivelul 0, descendenţii direcţi ai acesteia pe nivelul 1, descendenţii direcţi ai unui nod de pe nivelul i se află pe nivelul i+1. Nodurile fii ale aceluiaşi nod se numesc noduri gemene (engleză siblings).

Adâncimea unui nod reprezintă lungimea drumului dintre rădăcină şi acest nod. Înălţimea unui nod este lungimea celui mai lung drum dintre acest nod şi un nod

terminal. Înălţimea arborelui este înălţimea rădăcinii. Nivelul unui nod este înălţimea arborelui, minus adâncimea acestui nod. O frunză (numită şi nod terminal) este un nod care nu are nici un fiu. Gradul unui nod reprezintă numărul de descendenţi din nod. Dacă gradul

rădăcinii este 0, arborele este format doar din nodul rădăcină. Gradul unui arbore reprezintă maximul din mulţimea gradelor tuturor nodurilor. Lungimea căii unui anumit nod reprezintă numărul de ramificări de la rădăcină

la acel nod. Lungimea căii nodului rădăcină este 0, lungimea căii descendenţilor direcţi ai rădăcinii este 1, etc.

O mulţime de arbori disjuncţi formează o pădure.

După gradul nodurilor arborelui, arborii se clasifică în: -arbori binari: arbori de grad 2 (fiecare nod are cel mult 2 descendenţi) -arbori multicăi: arbori cu un număr oarecare de descendenţi (pot avea grad mai mare decât 2).

Într-un arbore multicăi, nodurile pot avea un număr oarecare de descendenţi. Pentru a putea defini în C structura unui nod al unui astfel de arbore vom proceda astfel: typedef struct nod_arb { int nr; //informaţia din nod int nr_fii; //numărul de fii al nodului curent struct nod_arb *adr_fii[nr_max_fii]; //adresele nodurilor fiu } NOD_ARB;

87

Nr_max fii va conţine numărul maxim de fii pe care îi poate avea un nod.

Construirea unui arbore multicăi se poate face astfel: -pentru fiecare nod se citeşte informaţia utilă şi numărul de fii (<=nr_max_fii) -nodurile se citesc în postordine iar adresele lor pot fi păstrate într-o stivă până la apariţia nodului al cărui fiu sunt. În acest moment, adresele fiilor se extrag din stivă completându-se astfel adresele nodului tată (către nodurile fii). După aceasta adresa nodului tată se depune în stivă iar algoritmul continuă până când în stivă singurul nod rămas va fi nodul rădăcină al arborelui.

Traversarea arborilor

Traversarea arborilor presupune parcurgerea tuturor nodurilor arborelui. În funcţie de ordinea în care sunt considerate nodurile arborelui, avem mai multe tipuri de traversare a arborilor.

o Traversare în adâncime (depth search): se vizitează fiecare subarbore descendent al nodului rădăcină, în acelaşi mod, apoi se vizitează nodul rădăcină.

o Traversare în lăţime (breadth search): se vizitează nodurile pe nivele, pornindu-se de la nivelele cele mai de sus spre nivelele mai mari, pe fiecare nivel, considerându-se nodurile într-o anumită ordine, de exemplu de la stânga la dreapta.

Arbori binari

Un arbore binar este format dintr-un nod rădăcină şi maxim 2 descendenţi care la rândul lor sunt arbori binari.

b

a c

g

e

d

f

Fig.4.10. Arbore binar

Un arbore binar poate avea două reprezentări: o reprezentare statică şi una dinamică. Reprezentarea statică a arborelui binar din figura de mai sus este următoarea:

88

inf(i) st(i) dr(i) t(i) 1 a 0 0 2 2 b 1 3 0 3 c 4 7 2 4 d 5 6 3 5 e 0 0 4 6 f 0 0 4 7 g 0 0 3

Reprezentarea dinamică a aceluiaşi arbore binar este următoarea:

b st dr

Adr rad

a st dr c st dr

d st dr g st dr

e st dr f st dr

Fig. 4.11.Reprezentarea dinamică a unui arbore binar

O implementare în C a acestui tip de înregistrare poate fi următoarea: typedef struct nod { int cheie; struct nod *st; struct nod *dr; } NOD; Descendenţa unei persoane din punct de vedere al strămoşilor poate fi

reprezentată sub forma unui arbore binar (rădăcina este persoana a cărui strămoşi se investighează iar frunzele reprezintă cei mai îndepărtaţi strămoşi). Fiecare nod în acest arbore are doi descendenţi adică 2 părinţi, dacă aceştia sunt cunoscuţi, eventual unul sau niciunul dacă aceştia nu pot fi cunoscuţi).

Eficienţa deosebită a arborilor binari se remarcă în cazul operaţiei de căutare a unui anumit element în arbore. Utilizând un arbore cu 106 noduri, vor fi necesare aproximativ log2106 paşi pentru căutarea unor elemente.

89

Traversarea unui arbore binar:

Pentru arborii binari, se pot considera următoarele traversări: o Traversare în preordine: se vizitează nodul rădăcină, apoi subarborele stâng şi

în final subarborele drept (R St Dr). o Traversare în inordine: se vizitează subarborele stâng, apoi nodul rădăcină şi în

final subarborele drept (St R Dr) o Traversare în postordine: se vizitează subarborele stâng, apoi subarborele drept şi în final nodul rădăcină (St Dr R) Pentru fiecare din cele 3 traversări, la vizitarea fiecărui subarbore se aplică din

nou aceeaşi regulă de vizitare Traversarea în preordine a arborelui din figura de mai sus dă naştere următorului

şir: b a c d e f g. Pentru traversarea în inordine vom avea: a b e d f c g. Pentru traversarea în postordine vom avea: a e f d g c b. Un arbore binar este complet dacă fiecare nod care nu este frunză are exact doi

descendenţi (deci gradul oricărui nod este 0 sau 2). Un arbore binar este echilibrat, dacă înălţimile subarborilor stâng şi drept ai

nodului rădăcină diferă prin cel mult 1. Un arbore binar echilibrat se mai numeşte arbore AVL. Într-un arbore binar echilibrat toate frunzele sale se găsesc pe ultimele două niveluri.

Un arbore binar total echilibrat este un arbore binar care îndeplineşte

următoarea condiţie: numărul nodurilor oricărui subarbore stâng diferă cu cel mult 1 în plus faţă de numărul nodurilor subarborelui corespunzător drept.

Un arbore binar se numeşte de căutare dacă satisface următoarea proprietate: Orice cheie din subarborele stâng al unui nod x este mai mică decât cheia din nodul x iar orice cheie din subarborele drept al unui nod x este mai mare sau egală cu cheia din nodul x. Consecinţa acestei proprietăţi este că traversând în inordine nodurile arborelui binar de căutare obţinem un şir crescător (după valoarea unei chei) de articole.

8

6 12

4 7

2 5

9

10

Fig. 4.12. Arbore binar de căutare

90

Traversând în inordine arborele binar de căutare din figura de mai sus, obţinem un şir ordonat crescător: 2 4 5 6 7 8 9 10 12.

Cheia maximă şi cheia minimă dintr-un arbore binar de căutare sunt uşor de găsit: cheia minimă se găseşte în nodul cel mai din stânga (la care ajungem avansând succesiv cu un pointer numai pe legături de tipul “succesor stâng”, pornind de la rădăcină). Cheia maximă se află în nodul cel mai din dreapta.

Un arbore binar complet este un heap dacă, având definită o relaţie de ordine asupra informaţiei conţinute în nodurile arborelui, avem (pentru fiecare nod al arborelui): nod ≤ nod subarbore stâng şi nod ≤ nod subarbore drept (deci cheia fiecărui nod din arbore este mai mare decât cheile descendenţilor sau altfel spus fiecare nod are o cheie mai mică sau egală cu cea a tatălui său). REZUMAT Ultimul modul urmărește principalele structuri de date, cu accentul pe

structurile înlănţuite. In acest modul se vor implementa structuri de tip listă simplu și dublu înlănţuită, stive, cozi, arbori și grafuri.

Intreb ări recapitulative

Ce este o structură de date? Clasificări ale structurilor de date Operaţii asupra unei structuri de date Ce este un fişier şi care sunt modalităţile de organizare şi de acces în cadrul unui fişier? Ce este un tablou şi ce caracteristici are? Principiul de creare a unei tabele de dispersie; rezolvarea coliziunilor Caracteristicile unei liste liniare simplu înlănţuite Caracteristicile unei liste liniare dublu înlănţuite Ce este o stivă şi care sunt particularităţile ei? Ce este o coadă şi care sunt particularităţile ei? Definiţi următoarele noţiuni: graf neorientat, graf parţial, subgraf al unui graf, graf regulat, graf complet, drum într-un graf, drum elementar, drum simplu, lanţ într-un graf, lanţ elementar, lanţ compus, ciclu, ciclu elementar, circuit, graf conex, componentă conexă a unui graf Modalităţi de reprezentare a grafurilor neorientate Modalităţi de parcurgere a grafurilor neorientate Definiţi următoarele noţiuni: lanţ hamiltonian, ciclu hamiltonian, graf hamiltonian, lanţ eulerian, ciclu eulerian, graf eulerian Definiţi următoarele noţiuni: graf orientat, gradul exterior al unui vârf, gradul interior al unui vârf, graf tare conex, graf simplu conex, componentă tare conexă a unui graf Modalităţi de reprezentare a grafurilor orientate Definiţi următoarele noţiuni: arbore, noduri gemene, adâncimea unui nod, înălţimea unui nod, înălţimea arborelui, nivelul unui nod, frunză într-un arbore, gradul unui nod, gradul unui arbore, arbore binar, arbore multicăi, arbore binar complet, arbore binar echilibrat, arbore binar total echilibrat, arbore binar de căutare Modalităţi de traversare a unui arbore oarecare Modalităţi de traversare a unui arbore binar

Bibliografie [Aho83], cap. 3, 6, 7; [Bologa06] cap. 9