Testul nr. 2 la Structuri de Date si Algoritmi - Tutunaru

Extras din document

1. Căutarea modelului în text. a)Programarea algoritmului de căutare a modelului în text după „Metoda directă” Cea mai simpla si mai putin eficienta metoda pentru a vedea unde un string apare in altul este sa verificam fiecare loc in care poate fi, unu cite unu, pentru a-l depista. Asadar, in primul rind vedem daca este o copie in primul character a multimii; daca nu, verificam daca e o copie incepind de la al doilea character, si asa mai departe. Intr-un caz normal noi verificam unul sau 2 caractere pentru fiecare pozitie gresita pentru a o depista, asadar complexitatea e O(n+m) pasi, unde n e lungimea multimii, n – este caracterul cautat; in cel mai rau caz cautarea unui string de tipul "aaaab" intr-un string de tipul "aaaaaaaaab" va lua O(nm) pasi. b) Programarea algoritmului Knuth-Morris Pratt. Calculeza un indicator determinist de marginire care este ca un suffix prin care se recunoaste in multime. Metoda de cautare a unui sir de caractere – model (pattern) P[0..m] intr-un sir de caractere sursa T[0..n], n>=m; construit pe functia - prefix π(P), fiind un exemplu clasic de programare dinamica, cu eficienta O(N+M); consta in deplasarea modelului P de-a lungul sursei T efectuata cu un numar mai mare de pozitii, in acelasi timp sa se memoreze partea de text care coincide cu modelul: evitam comparatiile inutile, creste viteza de cautare. Functia-prefix π(P) – determina prefixul maxim a lui P, care este, defapt, si sufixului lui P. Π(abracadabra) = abra;functia se aplica pentru a construi matricea k a lungimilor acestor prefixe, si determina daca modelul se contine in sursa sau/si cu cite pozitii trebuie sa deplasam modelul spre dreapta pentru a cauta o noua potrivire. 2. Grafuri. a) Noțiuni de bază. Modalitatea de prezentare în memoria calculatorului utilizînd diferite structuri de date. ...