Algoritmi

Laborator
6/10 (1 vot)
Domeniu: Calculatoare
Conține 1 fișier: pdf
Pagini : 5 în total
Cuvinte : 1709
Mărime: 9.86KB (arhivat)
Cost: Gratis
Profesor îndrumător / Prezentat Profesorului: Andrei Grigoras
Facultatea de informatica , Iasi .Despre arbori optimi de cautare si algorimi de cautare. Laborator 4

Extras din document

Definitii:

Algoritm: o procedura de calcul bine definita care primeste la intrare o multime

de valori (input) si produce la iesire un alt set de valori (output).

Instantele unei probleme: multimea tuturor intrarilor din care se poate calcula

o solutie pentru problema

Corectitudine: un alg e corect daca pt fiecare instanta el furnizeaza

rezultatele corecte (rezolva problema).

Analiza unui algoritm: identificarea resurselor necesare (timp calcul, memorie,

latime banda de comunicare, etc.)

Modelul tehnologiei pe care se implementeaza alg: un procesor cu memorie RAM,

multiprocesor cu memorie partajata, fiecare avand proprii algoritmi.

Instrumente matematice de analiza a alg:

analiza combinatorica discreta, teoria probabilitatii, identificarea

termenilor cei mai semnificanti dintr-o formula

Cazuri de analiza: cel mai bun (favorabil), cel mai rau (defavorabil), caz mediu

de complexitate

Eficienta asimptotica a alg: determinarea gradului de crestere

Notatii asimptotice:

- Complexitatea unui algoritm este o functie bine definita.

- De obicei ne intereseaza doar gradul de crestere al acesteia, deoarece

el influenteaza cel mai mult pentru o instanta a problemei de

dimensiune mare.

- Fie f(n) functia de complexitate a unui algoritm.

- Se numesc functii asimptotice pozitive functiile f(n) care au valoare

pozitiva pt orice n suficient de mare.

- Notatiile asimtotice urmatoare folosesc doar functii asimtotice

pozitive.

Notatie asimptotica limitata strans la ambele capete: Q()

Q(f(n)) = {g(n) | exista c1>0, c2>0, n0>0 ai

0<=c1*f(n)<=g(n)<=c2*f(n) pt orice n>n0 }

fie g(n) = 1/2n^2 - 3n

Atunci pt a arata ca g(n) apartine Q(f(n)), adica notam ca

g(n)=Q(f(n)), tre sa gasim constantele pozitive c1,c2,n0 astfel

incat 0<=c1*f(n)<=g(n)<=c2*f(n) pt orice n>n0.

Aratam ca g(n)=Q(n^2). Din calcule, rezulta ca pt n0=7, avem c1=1/14

si c2=1/2

Notatie asimptotica limitata strans superior: O()

O(f(n)) = {g(n) | exista c>0 si n0>0 ai

0<=g(n)<=c*f(n) pt orice n>n0}

Notam ca o functie g(n) aprtine lu O(f(n)) prin g(n)=O(f(n))

O(f(n)) reprezinta timpu de rulare al unui algoritm pt cazu cel mai

defavorabil. De exemplu pt sortarea prin insertie, pentru cazul cel

mai favorabil avem timpu de rulare O(n).

Notatie asimptotica limitata strans inferior: W()

W(f(n)) = {g(n) | exista c>0 si n0>0 ai

0<=c*f(n)<=g(n) pt orice n>n0}

Teorema: Pt orice f(n) si g(n), avem f(n)=Q(g(n)) dsnd f(n)=O(g(n)) si

f(n)=W(g(n))

Notatii asimptotice in ecuatii:

Dc notatia asmpt. apare ca unic element in partea dr. a unei ecuatii,

f(n)=O(g(n)) atunci semnifica f(n) apartine O(g(n)).

Dc notatia apare intr-o formula in partea dreapta, atunci o interpretam

ca pe o functie anonima k(n) care apartine lui O(g(n)).

Ex: 2n^2+3n+1 = 2n^2+Q(n) -> k(n)=3n+1=Q(n).

Notatia o():

Echivalentu lu O() insa fara limitare stransa:

o(f(n)) = {g(n) | pt orice c>0 exista n0>0 ai

0<=g(n)<=c*f(n) pt orice n>n0}

ex: 2n=o(n^2), insa 2n^2 != o(n^2).

Notatia w():

similar cu o() pentru limitare inferioara.

ex: n^2=w(n), n^2 != w(n^2)

Preview document

Algoritmi - Pagina 1
Algoritmi - Pagina 2
Algoritmi - Pagina 3
Algoritmi - Pagina 4
Algoritmi - Pagina 5

Conținut arhivă zip

Alții au mai descărcat și

Baza de Date Firma Termopane

Tema aleasa: baza de date firma termopane; Numele firmei: SC SPECT-TERM SRL; 1. PARTEA DE EXCEL Lansarea în execuţie a programului Excel. Am...

Baza de Date Firma de Incaltaminte SC Sport SRL

Proiectul conţine 6 pagini în Microsoft Excel printre care şi pagina de start, o pagina in Microsoft Acces şi una în HTML. Tema aleasă de mine...

Viata la Inaltime - Pagina Web

Motivaţia alegerii temei Experienţa didactică arată că elevii sunt mai puţin atraşi de probleme, abandonează repede când întâmpină greutăţi şi au...

Baze de Date - Compania Carte 2009

„Cartea 2009” este o companie care se ocupa cu distributia de carte in Romania. „Cartea 2009” dispune de un lant de peste 300 de librarii situate...

Indrumator Laborator SDTP

Lucrarea nr. 1 Structura de arbore. Arbori generalizati 1. Scopul lucrarii este prezentarea structurii de arbore si a operatiilor de baza ce se...

Indrumar Laborator Arhitectura Microprocesoarelor

Îndrumar de laborator 1 INTRODUCERE ÎN STUDIUL MICROSISTEMELOR LECTRONICE 1. Obiectul lucrarii Lucrarea îsi propune o introducere în studiul...

Ai nevoie de altceva?