Proiectarea Algoritmilor

Imagine preview
(7/10 din 3 voturi)

Acest curs prezinta Proiectarea Algoritmilor.
Mai jos poate fi vizualizat cuprinsul si un extras din document (aprox. 2 pagini).

Arhiva contine 1 fisier pdf de 141 de pagini .

Profesor: Gheorghe Hazi

Iti recomandam sa te uiti bine pe extras, cuprins si pe imaginile oferite iar daca este ceea ce-ti trebuie pentru documentarea ta, il poti descarca.

Fratele cel mare te iubeste, acest download este gratuit. Yupyy!

Domeniu: Calculatoare

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ă:

Fisiere in arhiva (1):

  • Proiectarea Algoritmilor.pdf

Alte informatii

UNIVERSITATEA DIN BACĂU FACULTATEA DE INGINERIE