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 curs
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
Conținut arhivă zip
- Proiectarea Algoritmilor.pdf
Alții au mai descărcat și
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,...
INFORMATICA este stiinta care se ocupa cu studiul si elaborarea metodelor de prelucrare a informatiei cu ajutorul sistemelor automate de calcul....
Curs 1 Structuri de date Structurile de date erau definite în limbajul C drept organizarea datelor primare. În limbajul C++, acestea reprezinta o...
Lucrarea nr. 1 Determinarea experimentala a timpului de execuţie al unui program 1. Scopul lucrării - lucrarea prezintă aspecte legate de...
Reprezentarea cunoaşterii prin cadre şi scenarii Reprezentarea cunoaşterii prin cadre Se ştie că oamenii nu interpretează noile situaţii...
ALGORITMI. METODE DE DESCRIERE A ALGORITMILOR 1.1 Scurt istoric În secolul al IX-lea d.Hr., un matematician persan, Abu Abdullah Muhammed bin...
In rezolvarea problemelor utilizind strategii de cautare neinformata numarul de stari investigate inainte de a gasi o solutie poate ajunge...
Te-ar putea interesa și
Introducere Odata cu progresul tehnicii, calculatoarele au devenit elemente esentiale pentru implementarea sistemelor de reglare automata....
INTRODUCERE Actualitatea temei. în ultimele trei decenii în lumea educaţiei s-au produs schimbări de ordin principial, ca reacţie la...
Algoritmul de realizare a proiectelor finantate din fondurile comunitare 1. Realizarea unui proiect – rezumat „Proiect” a devenit unul dintre...
Programul ajuta la tinerea evidentei unui magazin de inchirieri auto Acest program contine functii ce ofera utilizatorului acestuia posibilitatea...
„Alex&Asociații .co” este o firmă de impresariat cu tradiție în România și cu extindere rapidă în exterior, care dorește să gestioneze date despre...
INTRODUCERE De la apariţia ei şi pînă astăzi informatica aparţinea în mare parte persoanelor cu înclinaţii spre științe exacte. Aceasta deoarece...
Fişiere organizate relativ În acest proiect am încercat crearea unui fişier organizat relativ. Programul gestionează produsele existente într-un...
Societatea comercială “SC JUST DISTRIBUTION” se ocupă cu achizitia de produse de curatenie pe care ulterior le vinde. Aceasta îşi desfăşoară...