Embedded Files
Context
Context
Cuprins:
Cuprins:
Definitie algoritm
Caracteristici algoritmi
Definitie structura de date
Clasificare structuri de date
Corectitudinea algoritmilor
Eficienta algoritmilor
Masura de complexitate asimptotica
1. Ce este un algoritm?
1. Ce este un algoritm?
Intai, o Problema computationala este formata dintr-o multime de Intrari (Inputs) si o multime de Iesiri (Outputs).
Exista o relatie de corespondenta intre Intrari si Iesiri in asa fel incat unele Iesiri sunt Solutii pentru unele dintre Intrari.
Exemplu: pentru problema determinarii pozitiei unui maxim dintrun vector, daca exista mai multe maxime, oricare dintre acestea este Solutie.
Denumim Instanta a unei probleme computationale, un caz particular cu Intrari si Iesiri fixate.
De exemplu pentru instanta 2 8 5 8, problema maximului are solutii pozitia 1 si 3 pentru vector indexat de la zero.
Prin urmare problema computationala este definita generic, de exemplu:
Problema determinarii maximului: Pentru un vector de dimensiune arbitrara n, sa se intoarca pozitia unui maxim.
Un Algoritm este o secventa finita de instructiuni care descriu obtinerea unei Solutii pentru orice Intrare a unei probleme computationale.
De exemplu, pentru problema sortarii crescatoare unui vector:
O Intrare reprezinta o secventa de numere de dimensiune arbitrara n.
O Iesire bine definita ar putea sa fie specificata ca fiind orice permutare a intrarilor.
O Solutie ar fi orice permutare care respecta faptul ca elementele permutate sunt in ordine crescatoare (daca exista duplicate exista mai multe permutari, deci exista mai multe solutii, conform acestei definitii).
2. Caracteristicile algoritmilor:
2. Caracteristicile algoritmilor:
Generalitate
Claritate
Finititudine
Corectitudine
Performanță
Robustețe
Descrierea algoritmilor:
Descrierea algoritmilor:
Limbaj natural / Pseudocod
Diagramă (schemă logică)
Program
3. Structuri de date
3. Structuri de date
O Structura de date reprezinta o organizare a informatiei folosita pentru eficientizarea accesului si modificarii datelor.
Structurile de date sunt definite prin ansamblul:
colectie de valori
relatii intre acestea
operatiile pe acestea
In sensul acestei definitii, structurile de date sunt abstracte, dar scopul lor este sa fie implementate in limbaje de programare.
Pentru acest scop exista in C/C++ facilitatile de limbaj struct si class.
In timp ce struct este doar o alaturare de inregistrari/records, class doreste sa permita definirea a mai multor tipuri de comportament (toate operatiile se definesc ca si metode, putem avea constructor, destructor etc.).
Alcatuirea structurilor de date
Alcatuirea structurilor de date
Structurile de date sunt formate din agregarea (alaturarea):
tipurilor de date simple:
numere întregi,
numere reale,
caractere
pointeri (catre tipuri simple, catre tablouri, catre structuri)
structuri de date definite anterior
tablouri (array) de tipuri de date simple sau structuri definite anterior
4. Structurile de date pot fi clasificate după diferite criterii:
4. Structurile de date pot fi clasificate după diferite criterii:
Dupa tipul elementelor:
omogene
neomogene
Dupa modul de localizare a elementelor structurii:
cu acces direct (e.g. prin numarul de ordine)
cu acces secvential (accesul la un element se face parcurgand toate elementele aflate inaintea lui.
Dupa locul unde sunt create (tipul de memorie):
interne (in memoria interna)
externe
Dupa timpul de utilizare:
temporare
permanente
Dupa stabilitatea structurii:
statice: tablou, şir de caractere, fişier
dinamice(majoritatea celor bazate pe pointeri): lista, stiva, coada, graf, arbore
Operatii care se pot realiza asupra structurilor de date:
Operatii care se pot realiza asupra structurilor de date:
Creare
Consultare/Interogare
Actualizare
Sortare
Copiere / Mutare
Divizare / Reuniune
Stergere
5. Corectitudinea algoritmilor:
5. Corectitudinea algoritmilor:
Corectitudine logica a unui program => Algoritmul analizat produce rezultatul dorit dupa efectuarea unui numar finit de operatii.
Cu alte cuvinte, daca Iesirea este Solutie atunci algoritmul este Corect.
Modalitati de verificare a corectitudinii
Modalitati de verificare a corectitudinii
Experimentala (prin testare): algoritmul este executat pentru un set de date de intrare => relativ simpla dar nu garanteaza corectitudinea
Formala (prin demonstrare): se demonstreaza ca algoritmul produce rezultatul corect pentru orice set de date de intrare care satisface cerintele problemei => dificila in aplicarea pentru algoritmi complecsi, dar garanteaza corectitudinea
Preconditii si postconditii:
Preconditii si postconditii:
Preconditii = proprietati satisfacute de datele de intrare
Postconditii = proprietati satisfacute de datele de iesire (rezultate)
Exemplu: Sa se determine valoarea maxima dintr-un sir nevid.
Preconditii: n>=1 (secventa este nevida)
Postconditii: m (valoarea maxima) = max{x[i]; 1<=i<=n} (sau m >=x[i] pentru orice i) => m contine cea mai mare valoare din x[1..n]
Asertiuni:
Asertiuni:
Asertiune = afirmatie (adevarata) privind starea algoritmului
Limbajele de programare permit specificarea unor asertiuni si generarea unor exceptii daca asertiunea nu este satisfacuta. In C: “assert.h” .
Etapele verificarii corectitudinii:
Etapele verificarii corectitudinii:
Identificarea preconditiilor si a postconditiilor
Adnotarea algoritmului cu asertiuni astfel incat:
Preconditiile sa fie satisfacute
Asertiunea finala sa implice postconditiile
Fiecare pas de prelucrare asigura modificarea starii algoritmului astfel incat asertiunea urmatoare sa fie adevarata.
Cum se demonstreaza formal?
Cum se demonstreaza formal?
Prin inductie.
Sa presupunem ca dorim sa demonstram corectitudinea lui Bubble Sort.
void bubbleSort(int array[], int n) {
for (int step = 0; step < n; ++step) {
for (int i = 0; i < n - step; ++i) {
if (array[i] > array[i + 1]) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}
}
}
}
Demonstratie:
Demonstratie:
Propozitia P(i) = la pasul i, vectorul sortat cu Bubble Sort contine pe ultimele i pozitii cele mai mari i elemente in ordine crescatoare.
Obs: Pentru i=n intreg vectorul este sortat.
Cazul de baza
P(0) = adevarat, sunt 0 elemente la final
P(1) = adevarat, dupa 1 trecere, maximul din vector ajunge pe ultima pozitie.
(Mai exact, odata atins maximul, se va interschimba de fiecare data.)
Pasul de inductie
Daca presupunem P(k) = adevarat, demonstram P(k+1) adevarat.
Al k+1 -lea "maxim" ajunge pe pozitia n-k-1.
In plus, ultimele n-k elemente sunt sortate din cauza ca P(k) este adevarat
=> P(k+1) adevarat
6. Eficienta algoritmilor:
6. Eficienta algoritmilor:
Analiza eficienţei unui algoritm => determinarea resurselor de care acesta are nevoie pentru a produce datele de ieşire.
Resurse
timpul de executare
spatiu de memorie
Obs: Modelul masinii pe care va fi executat algoritmul nu presupune existenta operatiilor paralele (operatiile se executa secvential).
Cum masuram eficienta algoritmilor?
Cum masuram eficienta algoritmilor?
Benchmark? => masuram exact timpul sau spatiul necesar executarii algoritmului implementat.
Problema? Daca schimbam masina pe care ruleaza implementarea, poate spatiul necesar nu variaza, dar timpul masurat variaza conform specificatiilor calculatorului respectiv.
=> Avem nevoie de mecanisme pentru a determina eficienta algoritmilor care nu depind de masina pe care rulam algoritmul.
Metoda formala pentru determinarea eficientei nu este altceva decat numararea operatiilor necesare terminarii algoritmului.
Notatie: T(n) – timp de rulare al unui algoritm (in general masurat in nr. de comparatii sau de mutari/atribuiri)
Cazuri:
cel mai favorabil / best case
mediu / average case
cel mai nefavorabil / worst case (ofera o limita superioara a timpului de executare, avem certitudinea ca executarea algoritmului nu va dura mai mult)
Cel mai adesea se foloseste cazul cel mai nefavorabil si cel mediu pentru a descrie performanta unui algoritm.
7. Complexitatea asimptotica
7. Complexitatea asimptotica
Algoritmii se clasifica natural in clase de complexitate conform functiei T(n) care descrie numarul de operatii elementare.
De exemplu, pentru limita superioara a timpului T(n) a rularii unui algoritm, clasa de complexitate se determina eliminand factorii constanti din expresia T(n) si pastrand termenii cu cea mai rapida crestere.
Mai jos avem definitiile formale ale celor mai utilizate masuri ale complexitatii asimptotice.
Cea mai utilizata este notatia O (margine superioara).
Google Sites
Report abuse