Extras din laborator
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
Preview document
Conținut arhivă zip
- Analiza Algoritmilor.doc
Alții au mai descărcat și
Cunoasterea duratei de timp de la semanat pâna la rasaritul plantelor mai are însemnatate si pentru obtinerea unor productii cat mai timpurii. Daca...
In multe aplicatii este nevoie de un element care sa prezinte 2 stari diferite, cu posibilitatea de a trece dintr-o stare in cealalta, fara sau in...
Cerintele sistemului operational Odata ce a fost definita nevoia si abordarea tehnica, e necesar sa le tranlatam intr-un “scenariu...
Te-ar putea interesa și
INTRODUCERE În lucrarea de fața tratez metodele Huffman de codificare și comprimare a datelor, necesare pentru elaborarea unor algoritmi optimi...
-Introducere- Motivul alegerii acestei lucrări este de a înţelege mai bine cum un algoritm matematic de generare poate fi implementat în cadrul...
1. Analiza componentelor principale3 În această primă parte a proiectului am aplicat analiza componentelor principale (ACP) pe o matrice de date...
I. Analiza algoritmilor genetici 1.1. Algoritmi evoluţionişti Algoritmii evoluţionişti au la bază câteva principii ale evoluţiei: supravieţuirea...
Analiza algoritmilor Complexitatea algoritmilor Estimarea necesarului de memorie Masurarea timpului de executie Estimarea timpului cerut de...
Adnotare Memoriul explicativ conţine rezultatele obţinute pe parcursul procesului de proiectare şi implementare a programului. În memoriul...
1. Introducere Analiza matematică a complexităţii algoritmilor poate fi dificilă în cazul unor algoritmi care nu sunt simpli, mai ales dacă este...
Analiza algoritmilor 1. Să se genereze o matrice pătratică de dimensiune n cu elementele 1,2,…,n2 așezate în spirală. Exemplu pentru o matrice...