Analiza Algoritmilor

Imagine preview
(8/10 din 2 voturi)

Acest laborator prezinta Analiza Algoritmilor.
Mai jos poate fi vizualizat un extras din document (aprox. 2 pagini).

Arhiva contine 1 fisier doc de 6 pagini .

Profesor: andrei mogos

Iti recomandam sa te uiti bine pe extras 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: Automatica

Extras din document

Problema 1:

Consideram algoritmii InsertionSort, BubbleSort si MergeSort din Tema 1.

Cerinte: alegeti unul dintre algoritmii InsertionSort si BubbleSort si aratati ca este partial corect. Aratati ca algoritmul MergeSort este partial corect. Pentru functia 'Merge' considerati varianta dezvoltata de voi in Tema 1 .

Demonstratie prin deductie directa

I=Zn Pi(A,n)= A  vector cu n elemente

O=Zn Po(A,n)= A - vector sortat cu n elemente

Op 1. La fiecare ciclu din primul for (pentru i=k) se aduce pe pozitia A[k] cel mai mic element din subvectorul A[k:n-1]

Dem:

Fie i=k.

Pornind de la pozitia n-1, va compara fiecare element cu cel dinaintea lui si le va interschimba, daca acesta este mai mic. Asfel se va aduce in pozitia k elementul cel mai mic din subvectorul A[k :n-1]

Op 2. Efectuand Op 1 pentru i=0 : n-1 va rezulta un vector ce are pe pozitia i cel mai mic din subvectorul A[i,n-1] A=[p0,p1,p2,p3,p4,p5&.pn-1] cu proprietatea ca:

pi=min(pi:n-1) pi pj , i<j p0 p1 &pi &pn-1 vectorul este sortat

BubbleSort este partial corect

Fisiere in arhiva (1):

  • Analiza Algoritmilor.doc

Alte informatii

analiza algoritmilor tema 2