ANALIZA ALGORITMURILOR. Complexitatea algoritmtilor.

Complexitatea si clasificarea algoritmilor

Algoritmul reprezinta o succesiune finita de operatii (instructiuni, comenzi) cunoscute, care ,fiind executate intr-o ordine bine stabilita , furnizeaza solutia unei probleme.Teoria complexitiieste o ramur ainformaticiicare se ocup cu studiereacomplexitii algoritmilor. Complexitatea reprezint puterea de calcul necesar implementrii unuialgoritm. Ea are dou componente principale, i anume complexitatea n timp i cea n spaiu. Complexitatea n spaiu se refer la volumul de memorie necesar calculelor, iar cea n timp se refer la timpul necesar efecturii calculelor, ambele fiind exprimate ca funcii den, undeneste mrimea datelor de intrare.ALGORITMULProceduriFunctiiInstructiuniCu ajutorul limbajelor de programareTexte scrise intr-un limbajde comunicare intre oameniFormule matematiceSchemelogicePrograme care pot fi derulate pe calculatorAnaliza algoritmilor nV(n)T(n)Volumul de memorie interna necesara p-u pastrarea datelor cu care opereaza algoritmul.Este un nr. natural ce caracterizeaza marimea datelor de intrare ale unui algoritm .Timpul necesar executarii algoritmului.Aplicarea practica a unui algoritm este posibila numai atunci cind necesarul de memorie si timpul cerut nu se incalca restrictiile impuse de mediul de programare si capacitatea de prelucrare a calculatorului utilizat.Cind putem aplica un algoritm functionabil?Clasificarea algoritmilorIn Functie de complexitateIn functie de implementareIn functie de design (metoda)In functie de domeniul de studiu In functie de complexitateAlgoritmi polinomialiUn algoritm se numeste polinomial daca termenul dominant are forma Cnk , adica Q(n) ~ Cnk ; T(n)~ Cnk , Unde: n este caracteristica datelor de intrare;C o constanta pozitivaK un numar natural.

Complexitatea temporala a algoritmilor polinomiali este redata prin notatia O(nk) care se citeste algoritm cu timpul de executie de ordinul nk sau , mai pe scurt, algoritm de ordinul nk . Exemple :n1, n2 , n3 , n4 etc. ExponentialUn algoritm se numeste exponential daca termenul dominant are forma Ckn , adica Q(n)~ Ckn ; T(n) ~ Ckn, unde k>1. Complexitatea temporala a algoritmilor exponentiali este redata prin notatia O(kn )

Tot exponentiali se considera si algoritmii de complexitate n log n .

Nederminist polinomial Se studiaza in cursurile avansate de informatica si este mai rar aplicat

Polinomiali vs Exponentiali Din comparatia vitezei de crestere a functiilor exponentiala si polinomiala rezulta ca algoritmii exponentiali devin inutilizabili chiar pentru valori nu prea mari ale lui n. In functie de complexitatea temporala se considera ca o problema este usor rezolvabila daca pentru solutionarea ei exista un algoritm polinomial. O problema pentru care nu exista un algoritm polinomial se numeste dificila. Aceasta clasificarea se refera doar la algoritmii in care n ia valori mari. In caz cind n ia valori mici , situatia poate fi inversa.In funtie de implementare recursivi (se invoca pe ei insisi ) / iterativi (au constructii repetitive) ; logici (controleaza deductii logice) ; seriali (un singur procesor si o singura instructiune executata la un moment dat ) /paraleli (mai multe procesoare care executa instructiuni in acelasi timp) ; deterministici (o decizie exacta la fiecare pas) / nedeterministici ( rezolva problema plecand de la presupuneri ) ;

In functie de design (metoda) imparte si stapaneste ( imparte problema in una sau mai multe instante mai mici) ; programare dinamica (cauta structuri optimale -o solutie optimala a problemei poate fi construita plecand de la solutiile optimale ale subproblemelor ) metoda Greedy (cauta tot structuri optimale cu deosebirea ca solutiile la subprobleme nu trebuie sa fie cunoscute la fiecare pas; alegerea Greedy serefera la ce arata mai bine la un moment dat) .

In functie de domeniul de studiu

de cautarede sortarenumerici algoritmi de grafuri de geometrie computationala de invatare automata de criptografie etc.

Importanta algoritmilor Ne furnizeaza rezolvarea problemelor dificile in diferite domenii ( avind un algoritm bine stabilit). Au realizat:

Soltan Vasile Rosca Valentina