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
Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.