Teoria Complexitatii:
Obiectiv: oferirea de metode pentru clasificarea problemelor
computationale in functie de resursele necesare rezolvarii lor.
Clasificarea nu trebuie sa depinda de modelul computational,
ci doar de dificultatea intrinseca a problemei.
Prin "resurse necesare" se intelege memoria, numarul de
procesare etc., si in special timpul.
Conform Teoriei Informatiei, aproape orice algoritm
criptografic poate fi spart. Teoria Complexitatii ne spune
timpul necesar pentru aceasta.
Definitie
Algoritm: o metoda computationala bine definita, care preia un
input variabil si ofera un output dupa un numar finit de pasi
(program de calculator).
Definitie
Marimea unui input: numarul total de biti necesar pentru
reprezentarea sa in binar.
Exemple. (a) Fie n 2 N si sa presupunem ca n are k cifre binare.
Atunci
2k
Facultatea de Inginerie Matematica, Univ. Bucuresti
Documentul este oferit gratuit,
trebuie doar să te autentifici in contul tău.
