Proiectarea algoritmilor

Acest manual este dedicat in special studentilor de la formele de invatamant ID (invatamant la Distanta)

si PU (Post universitare) de la Facultatea de Informatica a Universitatii "Alexandru Ioan Cuza" din Iasi.

Cartea se doreste a fi un suport pentru disciplinele Proiectarea Algoritmilor (ID) si Structuri de date si

Algoritmi (PU). Recomandam ca parcurgerea acestui suport sa se facain paralel cu consultarea materialul

electronic aflat pe pagina web a cursului la adresa http://www.infoiasi.ro/fcs/CS2101.php. De fapt

continutul acestei carti este o versiune simplificata a celui inclus pe pagina cursului. Din acest motiv

unele referinte apar ca nedefinite (marcate cu "??"). Toate acestea pot fi gasite pe pagina cursului.

Structura manualului este urmatoarea: Capitolul doi include definitia limbajului algoritmic utilizat

impreuna cu definitiile pentru cele doua functii principale de masurare a eficientei algoritmilor: complexitatea

timp si complexitatea spatiu. in capitolul trei sunt prezentati principalii algoritmi de sortare interna

bazati pe comparatii. Capitolul al patrulea este dedicat algoritmilor de cautare si a principalelor structuri

de date utilizate de acesti algoritmi. Tipurile de date utilizate pentru reprezentarea grafurilor sunt

prezentate in capitolul cinci. Un accent deosebit este pus pe algorimii de parcurgere a grafurilor. Capitolul

sase include doi algoritmi de enumerare utilizati foarte mult in aplicarea paradigmei "backtracking":

enumerarea permutarilor si enumerarea elementelor produsului cartezian. in capitolul sapte se prezinta

cateva consideratii generale privind paradigmele de proiectare a algoritmilor. Urmatoarele patru capitole

sunt dedicate principalelor paradigme de proiectare a algoritmilor: algoritmii "greedy", divide-et-impera,

programare dinamica si "backtracking". Ultimul capitol este dedicat problemelor NP-complete. Fiecare

capitol este acopaniat de o lista de exercitii.

1

Capitolul 2

Despre algoritmi

2.1 Limbaj algoritmic

2.1.1 Introducere

Un algoritm este o secventa finita de pasi, aranjata intr-o ordine logica specifica care, atunci cand este

executata, produce o solutie corecta pentru o problema precizata. Algoritmii pot fi descrisi in orice limbaj,

pornind de la limbajul natural pina la limbajul de asamblare al unui calculator specific. Un limbaj al

carui scop unic este cel de a descrie algoritmi se numeste limbaj algoritmic. Limbajele de programare

sunt exemple de limbaje algoritmice.

in aceasta sectiune descriem limbajul algoritmic utilizat in aceasta carte. Limbajul nostru este tipizat,

in sensul ca datele sunt organizate in tipuri de date. Un tip de date consta dintr-o multime de entitati de

tip data (valori), numita si domeniul tipului, si o multime de operatii peste aceste entitati. Convenim

sa grupam tipurile de date in trei categorii:

- tipuri de date elementare, in care valorile sunt entitati de informatie indivizibile;

- tipuri de date structurate de nivel jos, in care valorile sunt structuri relativ simple obtinute prin

asamblarea de valori elementare sau valori structurate iar operatiile sunt date la nivel de component

a;

- tipuri de date structurate de nivel inalt, in care valorile sunt structuri mai complexe iar operatiile

sunt implementate de algoritmi proiectati de catre utilizatori.

Primele doua categorii sunt dependente de limbaj si de aceea descrierile lor sunt incluse in aceata sectiune.

Tipurile de nivel inalt pot fi descrise intr-o maniera independenta de limbaj si descrierile lor sunt incluse

in capitolul ??. Un tip de date descris intr-o maniera indepenedenta de reprezentarea valorilor si implementarea

operatiilor se numeste tip de date abstract.

Pasii unui algoritm si ordinea logica a acestora sunt descrise cu ajutorul instructiunilor. O secventa

de instructiuni care actioneaza asupra unor structuri de date precizate se numeste program. in sectiunea

2.2 vom vedea care sunt conditiile pe care trebuie sa le indeplineasca un program pentru a descrie un

algoritm.

2.1.2 Modelarea memoriei

Memoria este reprezentata ca o structura liniara de celule, fiecare celula avand asociata o adresa si

putand memora (stoca) o data de un anumit tip (fig. 2.1). Accesul la memorie este realizat cu ajutorul

variabilelor. O variabila este caracterizata de:

- un nume cu ajutorul careia variabila este referita,

- o adresa care desemneaza o locatie de memorie si

- un tip de date care descrie natura valorilor memorate in locatia de memorie asociata variabilei.

Daca in plus adaugam si valoarea memorata la un moment dat in locatie, atunci obtinem o instanta

a variabilei. O variabila este reprezentata grafic ca in fig. 2.2a. Atunci cand tipul se subintelege din

2

712

lungime integer

a

Figura 2.1: Memoria

b)

lungime integer 712 lungime 712

a)

Figura 2.2: Variabila

context, vom utiliza reprezentarea scurta sugerata in 2.2b. Convenim sa utilizam fontul type writer

pentru notarea variabilelor si fontul mathnormal pentru notarea valorilor memorate de variabile.

2.1.3 Tipuri de date elementare

Numere intregi. Valorile sunt numere intregi iar operatiile sunt cele uzuale: adunarea (+), inmultirea

(- ), scaderea (- ) etc.

Numere reale. Deoarece prin dataintelegem o entitate de informatie reprezentabilain memoria calculatorului,

domeniul tipului numerelor reale este restrans la submultimea numerelor rationale. Operatiile

sunt cele uzuale.

Valori booleene. Domeniul include numai doua valori: true si false. Peste aceste valori sint definite

operatiile logice and, or si not cu semnificatiile cunoscute.

Caractere. Domeniul include litere: 'a', 'b', , 'A', 'B', , cifre: '0', '1', , si caractere

speciale: '+', '*', Nu exista operatii.

Pointeri. Domeniul unui tip pointer consta din adrese de variabile apartinand la alt tip. Presupunem

existenta valorii NULL care nu refera nici o variabila; cu ajutorul ei putem testa daca un pointer refera

sau nu o variabila. Nu consideram operatii peste aceste adrese. Cu ajutorul unei variabile pointer, numita

pe scurt si pointer, se realizeaza referirea indirecta a unei locatii de memorie. Un pointer este reprezentat

grafic ca in fig. 2.3a. Instanta variabilei pointer p are ca valoare adresa unei variabile de tip intreg. Am

notat integer* tipul pointer al carui domeniu este format din adrese de variabile de tip intreg. Aceasta

conventie este extinsa la toate tipurile. Variabila referita de p este notata cu *p. in fig. 2.3b si 2.3c sunt

date reprezentarile grafice simplificate ale pointerilor.

Pointerii sunt utilizati la manipularea variabilelor dinamice. O variabila dinamica este o variabila care

poate fi creata si distrusa in timpul executiei programului. Crearea unei variabile dinamice se face cu

ajutorul subprogramului new. De exemplu, apelul new(p) are ca efect crearea variabilei *p. Distrugerea

(eliberarea spatiului de memorie) variabilei *p se face cu ajutorul apelului delete(p) al subprogramului

delete.

2.1.4 Instructiuni

Atribuirea. Sintaxa:

- variabila- - - expresie-

unde - variabila- este numele unei variabile iar - expresie- este o expresie corect formata de acelasi tip cu

- variabila-

R. E. Bellman and S. E. Dreyfus. Applied Dynamic Programming. Princeton University Press,

1962.

[CLR93] T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. MIT Press, 1993.

[Cro92] Cornelius Croitoru. Tehnici de baza in optimizarea combinatorie. Editura Universitatii

"Al.I.Cuza", Iasi, 1992.

[GJ79] Michael R. Garey and David S. Johnson. Computers and Intractability: A Guige to the Theory

of NP-Completeness. W.H.Freeman and Company, San Francisco, 1979.

[HS84] E. Horowitz and S. Sahni. Fundamentals of Computer Algorithms. Computer Science Press,

1984.

[HSAF93] E. Horowitz, S. Sahni, and S. Anderson-Freed. Fundamentals of Data Structures in C. Computer

Science Press, 1993.

[Knu76] D.E. Knuth. Sortare si cautare, volume 3 of Tratat de programarea calculatoarelor. Editura

tehnica, Bucuresti, 1976.

[Luc93] D. Lucanu. Programarea algoritmilor: Tehnici elementare. Editura Universitatii "Al.I.Cuza",

Iasi, 1993.

[MS91] B.M.E. Morret and H.D. Shapiro. Algorithms from P to NP: Design and Efficiency. The

benjamin/Cummings Publishing Company, Inc., 1991.

117