Proiectarea Algoritmilor

Curs
7.3/10 (3 voturi)
Domeniu: Calculatoare
Conține 1 fișier: pdf
Pagini : 141 în total
Cuvinte : 42152
Mărime: 1.79MB (arhivat)
Cost: Gratis
Profesor îndrumător / Prezentat Profesorului: Gheorghe Hazi
UNIVERSITATEA DIN BACĂU FACULTATEA DE INGINERIE

Cuprins

1. Introducere în proiectarea algoritmilor.4

1.1. Definiţii.4

1.2. Obiectul disciplinei.4

1.3. Proprietăţi ale algoritmilor.5

1.4. Date.7

1.5. Tipuri de prelucrări.7

1.6. Exerciţii.8

2. Descrierea algoritmilor.12

2.1. Limbaj algoritmic.12

2.2. Specificarea datelor.15

2.3. Exemple de algoritmi.16

2.4. Tehnica rafinării succesive şi subalgoritmi.21

2.5. Exerciţii.22

3. Verificarea corectitudinii algoritmilor.24

3.1. Etapele verificării corectitudinii.24

3.2. Elemente de analiză formală a corectitudinii.26

3.3. Exerciţii.30

4. Analiza complexităţii algoritmilor.32

4.1. Scopul analizei complexităţii.32

4.2. Timpi de execuţie.33

4.3. Ordin de creştere.37

4.4. Notaţii asimptotice.38

4.5. Etapele analizei complexităţii.42

4.6. Analiza empirică a complexităţii algoritmilor.42

4.7. Exerciţii.43

5. Metode elementare de sortare.46

5.1. Problematica sortării.46

5.2. Sortare prin inserţie.47

5.3. Sortare prin selecţie.49

5.4. Sortare prin interschimbarea elementelor vecine.50

5.5. Exerciţii.54

6. Tehnici de elaborare a algoritmilor: reducere şi divizare.56

6.1. Motivaţie.57

6.2. Algoritmi recursivi.58

6.3. Tehnica reducerii.61

6.4. Tehnica divizării.66

6.5. Exerciţii.70

7. Aplicaţii ale tehnicii divizării. Sortarea prin interclasare

şi sortarea rapidă.71

7.1. Introducere.71

7.2. Sortare prin interclasare.71

7.3. Sortare rapidă.74

7.4. Exerciţii.78

8. Tehnica alegerii local optimale ("greedy").80

8.1. Introducere.80

8.2. Principiul tehnicii.80

8.3. Verificarea corectitudinii si analiza complexităţii.83

8.4. Aplicaţii.84

8.5. Exerciţii.88

8.6. Anexa - Program pentru împachetare optimă (varianta 3).89

9. Tehnica programării dinamice.93

9.1. Introducere.93

9.2. Principiul tehnicii şi etapele aplicării.93

9.3. Aplicaţii.98

9.4. Exerciţii.105

10. Tehnica căutării cu revenire.107

10.1. Introducere.107

10.2. Principiul metodei şi structura generală a algoritmului.107

10.3. Aplicaţii.111

10.4. Exerciţii.117

Epilog. Sfaturi pentru proiectarea algoritmilor.118

Exerciţii suplimentare.122

Bibliografie.141

Extras din document

1. INTRODUCERE ÎN PROIECTAREA ALGORITMILOR

1.1. Definiţii

Un algoritm este o metodă de rezolvare pas cu pas a problemelor. O problemă este constituită din date de intrare şi un enunţ care specifică relaţia existentă între datele de intrare şi soluţia problemei. În cadrul algoritmului sunt descrise prelucrările necesare pentru a obţine soluţia problemei pornind de la datele de intrare. O definiţie mai precisă, în sensul cursului nostru, este:

Un algoritm este o succesiune bine precizată de prelucrări care aplicate asupra datelor de intrare ale unei probleme permit obţinerea în timp finit a soluţiei acesteia. Acesta trebuie să poată fi implementat pe un calculator.

Termenul de algoritm provine de la numele unui matematician persan, al-Khowarizmi (al-Kwarizmi), ce a trăit în secolul al IX-lea şi care a scris o lucrare despre efectuarea calculelor numerice într-o manieră algebrică. Primul algoritm se consideră a fi algoritmul lui Euclid (utilizat pentru determinarea celui mai mare divizor comun a două numere naturale). Termenul de algoritm poate fi înţeles în sens larg, nefiind neapărat legat de rezolvarea unei probleme cu caracter ştiinţific, ci doar pentru a descrie într-o manieră ordonată activităţi care constau în parcurgerea unei succesiuni de paşi (cum este de exemplu utilizarea unui telefon public sau a unui bancomat).

În matematică există o serie de algoritmi: cel al rezolvării ecuaţiei de gradul doi, algoritmul lui Eratostene (pentru generarea numerelor prime mai mici decât o anumită valoare), schema lui Horner (pentru determinarea câtului şi restului împărţirii unui polinom la un binom) etc.

Soluţia problemei se obţine prin execuţia algoritmului. Algoritmul poate fi executat pe o maşină formală (în faza de proiectare şi analiză) sau pe o maşină fizică (calculator) după ce a fost codificat într-un limbaj de programare. Spre deosebire de un program, care depinde de un limbaj de programare, un algoritm este o entitate matematică care este independentă de maşina pe care va fi executat. Dacă până acum aţi scris programe, este posibil ca, la unele probleme, să fi avut dificultăţi în găsirea soluţiei de rezolvare. Atunci când aţi găsit o soluţie nu ştiaţi dacă ea este cea mai bună. Această carte vă va îndruma cum să lămuriţi asemenea probleme.

1.2. Obiectul disciplinei

Obiectul disciplinei de „Proiectarea algoritmilor” îl reprezintă studiul algoritmilor din perspectiva elaborării şi analizei lor. Elaborarea unui algoritm necesită:

Preview document

Proiectarea Algoritmilor - Pagina 1
Proiectarea Algoritmilor - Pagina 2
Proiectarea Algoritmilor - Pagina 3
Proiectarea Algoritmilor - Pagina 4
Proiectarea Algoritmilor - Pagina 5
Proiectarea Algoritmilor - Pagina 6
Proiectarea Algoritmilor - Pagina 7
Proiectarea Algoritmilor - Pagina 8
Proiectarea Algoritmilor - Pagina 9
Proiectarea Algoritmilor - Pagina 10
Proiectarea Algoritmilor - Pagina 11
Proiectarea Algoritmilor - Pagina 12
Proiectarea Algoritmilor - Pagina 13
Proiectarea Algoritmilor - Pagina 14
Proiectarea Algoritmilor - Pagina 15
Proiectarea Algoritmilor - Pagina 16
Proiectarea Algoritmilor - Pagina 17
Proiectarea Algoritmilor - Pagina 18
Proiectarea Algoritmilor - Pagina 19
Proiectarea Algoritmilor - Pagina 20
Proiectarea Algoritmilor - Pagina 21
Proiectarea Algoritmilor - Pagina 22
Proiectarea Algoritmilor - Pagina 23
Proiectarea Algoritmilor - Pagina 24
Proiectarea Algoritmilor - Pagina 25
Proiectarea Algoritmilor - Pagina 26
Proiectarea Algoritmilor - Pagina 27
Proiectarea Algoritmilor - Pagina 28
Proiectarea Algoritmilor - Pagina 29
Proiectarea Algoritmilor - Pagina 30
Proiectarea Algoritmilor - Pagina 31
Proiectarea Algoritmilor - Pagina 32
Proiectarea Algoritmilor - Pagina 33
Proiectarea Algoritmilor - Pagina 34
Proiectarea Algoritmilor - Pagina 35
Proiectarea Algoritmilor - Pagina 36
Proiectarea Algoritmilor - Pagina 37
Proiectarea Algoritmilor - Pagina 38
Proiectarea Algoritmilor - Pagina 39
Proiectarea Algoritmilor - Pagina 40
Proiectarea Algoritmilor - Pagina 41
Proiectarea Algoritmilor - Pagina 42
Proiectarea Algoritmilor - Pagina 43
Proiectarea Algoritmilor - Pagina 44
Proiectarea Algoritmilor - Pagina 45
Proiectarea Algoritmilor - Pagina 46
Proiectarea Algoritmilor - Pagina 47
Proiectarea Algoritmilor - Pagina 48
Proiectarea Algoritmilor - Pagina 49
Proiectarea Algoritmilor - Pagina 50
Proiectarea Algoritmilor - Pagina 51
Proiectarea Algoritmilor - Pagina 52
Proiectarea Algoritmilor - Pagina 53
Proiectarea Algoritmilor - Pagina 54
Proiectarea Algoritmilor - Pagina 55
Proiectarea Algoritmilor - Pagina 56
Proiectarea Algoritmilor - Pagina 57
Proiectarea Algoritmilor - Pagina 58
Proiectarea Algoritmilor - Pagina 59
Proiectarea Algoritmilor - Pagina 60
Proiectarea Algoritmilor - Pagina 61
Proiectarea Algoritmilor - Pagina 62
Proiectarea Algoritmilor - Pagina 63
Proiectarea Algoritmilor - Pagina 64
Proiectarea Algoritmilor - Pagina 65
Proiectarea Algoritmilor - Pagina 66
Proiectarea Algoritmilor - Pagina 67
Proiectarea Algoritmilor - Pagina 68
Proiectarea Algoritmilor - Pagina 69
Proiectarea Algoritmilor - Pagina 70
Proiectarea Algoritmilor - Pagina 71
Proiectarea Algoritmilor - Pagina 72
Proiectarea Algoritmilor - Pagina 73
Proiectarea Algoritmilor - Pagina 74
Proiectarea Algoritmilor - Pagina 75
Proiectarea Algoritmilor - Pagina 76
Proiectarea Algoritmilor - Pagina 77
Proiectarea Algoritmilor - Pagina 78
Proiectarea Algoritmilor - Pagina 79
Proiectarea Algoritmilor - Pagina 80
Proiectarea Algoritmilor - Pagina 81
Proiectarea Algoritmilor - Pagina 82
Proiectarea Algoritmilor - Pagina 83
Proiectarea Algoritmilor - Pagina 84
Proiectarea Algoritmilor - Pagina 85
Proiectarea Algoritmilor - Pagina 86
Proiectarea Algoritmilor - Pagina 87
Proiectarea Algoritmilor - Pagina 88
Proiectarea Algoritmilor - Pagina 89
Proiectarea Algoritmilor - Pagina 90
Proiectarea Algoritmilor - Pagina 91
Proiectarea Algoritmilor - Pagina 92
Proiectarea Algoritmilor - Pagina 93
Proiectarea Algoritmilor - Pagina 94
Proiectarea Algoritmilor - Pagina 95
Proiectarea Algoritmilor - Pagina 96
Proiectarea Algoritmilor - Pagina 97
Proiectarea Algoritmilor - Pagina 98
Proiectarea Algoritmilor - Pagina 99
Proiectarea Algoritmilor - Pagina 100
Proiectarea Algoritmilor - Pagina 101
Proiectarea Algoritmilor - Pagina 102
Proiectarea Algoritmilor - Pagina 103
Proiectarea Algoritmilor - Pagina 104
Proiectarea Algoritmilor - Pagina 105
Proiectarea Algoritmilor - Pagina 106
Proiectarea Algoritmilor - Pagina 107
Proiectarea Algoritmilor - Pagina 108
Proiectarea Algoritmilor - Pagina 109
Proiectarea Algoritmilor - Pagina 110
Proiectarea Algoritmilor - Pagina 111
Proiectarea Algoritmilor - Pagina 112
Proiectarea Algoritmilor - Pagina 113
Proiectarea Algoritmilor - Pagina 114
Proiectarea Algoritmilor - Pagina 115
Proiectarea Algoritmilor - Pagina 116
Proiectarea Algoritmilor - Pagina 117
Proiectarea Algoritmilor - Pagina 118
Proiectarea Algoritmilor - Pagina 119
Proiectarea Algoritmilor - Pagina 120
Proiectarea Algoritmilor - Pagina 121
Proiectarea Algoritmilor - Pagina 122
Proiectarea Algoritmilor - Pagina 123
Proiectarea Algoritmilor - Pagina 124
Proiectarea Algoritmilor - Pagina 125
Proiectarea Algoritmilor - Pagina 126
Proiectarea Algoritmilor - Pagina 127
Proiectarea Algoritmilor - Pagina 128
Proiectarea Algoritmilor - Pagina 129
Proiectarea Algoritmilor - Pagina 130
Proiectarea Algoritmilor - Pagina 131
Proiectarea Algoritmilor - Pagina 132
Proiectarea Algoritmilor - Pagina 133
Proiectarea Algoritmilor - Pagina 134
Proiectarea Algoritmilor - Pagina 135
Proiectarea Algoritmilor - Pagina 136
Proiectarea Algoritmilor - Pagina 137
Proiectarea Algoritmilor - Pagina 138
Proiectarea Algoritmilor - Pagina 139
Proiectarea Algoritmilor - Pagina 140
Proiectarea Algoritmilor - Pagina 141

Conținut arhivă zip

  • Proiectarea Algoritmilor.pdf

Alții au mai descărcat și

Microprocesoare

Microprocesoare 1. PREZENTARE FUNCTIONALA Intrebarile la care vom incerca sa raspundem in urmatoarele paragrafe sunt: ce este un microprocesor?...

Rețele de Calculatoare

Lucrarea Modele si solutii pentru administrarea reteleor de calculatoare contine o prezentare succinta a protocolului de administrare SNMP...

Gestiunea Bazei de Date a unei Librării

Introducere Aplicaţia realizează gestiunea activităţii unei librării: - Înregistrează într-o bază de date cărţile care se găsesc în librărie; -...

Lucrul cu Numere Mari

De multe ori , in probleme, apar situatii cand este nevoie sa memoram numere intregi foarte mari (de ordinul sutelor de cifre), iar uneori trbuie...

Baza de Date a unui Catalog Scolar Limbajul de Programare C

1. Tema proiectului Se cere sa se realizeze o baza de date care sa simuleze un catalog scolar. Pentru realizarea bazei de date se vor folosi: o...

Proiectarea și Analiza Algoritmilor

//Varianta A: Arbori B :structura , cel mai lung cuvant,cel mai mare cuvant din arbore. #define N 2 #define M 4 //Strunctura necesara pentru...

Crearea unui Arhivator și a Unui Dezarhivator

Introducere „Un calculator, nu face ceea ce vrei tu sa faca, dar ceea ce îi spui sa faca” - Legea lui Murphy C/C++ sunt limbaje, si sunt...

Algoritmi GREEDY

Pusi in fata unei probleme pentru care trebuie sa elaboram un algoritm, de multe ori "nu stim cum sa incepem". Ca si in orice alta activitate,...

Ai nevoie de altceva?