Cautare in text, Graf, Arbori, Reprezentarea arborilor, Arbori binari, traversarea
Căutarea modelului în text
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.
Algoritmul 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.
Algoritmul Boyer Mour – incepe cautarea de la sfirsitul cuvintului
cautat, asadar poate sari peste lungimea cuvintului cautat la un pas.
Algoritmul preproceseaza sirul cautat. Foloseste infromatia prelucrata pentru a
sari peste sectiuni de text rezultind o contanta mai scurta de cautare decit in
alte algortimuri. In general, algoritmul se executa mai repede pe masura
cresterii lungimii textului cautat. – cauta aparitia lui P in T executind explicit
comparatii de caractere la diferite linii. In loc sa caute fiecare linie, se
cauta folosind informatii capatate la prelucrarea lui P pentru a omite cit mai
multe linii din T. Algoritmul incepe de la linia k=n, asadar inceputul lui P
este aliniat inceputului lui T. Cracterele in P si T sunt comparate incepind cu
indexul n in P si k in T, mutindu-se in jos: sirurile se comparate de la
sfirsitul spre inceputul lui P. Comparatiile continua pina cind se gaseste o
necoincidenta sau pina cind am ajuns la inceputul lui P (ceea ce inseamna ca au
coincis), dupa care linia e deplasata spre dreapta conform maximumului permis
de numarul de reguli. Compararea se executa dinnou la o alta linie, si procesul
se repeat pina cind linia este deplasata pina la sfirsitul lui T. Regulile de
deplasare sunt implementate intr-un table generat in timpul prelucrarii lui P.
Modalitatea de prezentare în memoria calculatorului utilizând diferite structuri de date
Numim graf o
pereche ordonată de mulțimi, notată G=(X,U), unde X este o mulțime finită
și nevidă de elemente numite noduri sau vârfuri, iar U este o mulțime de
perechi (ordonate sau neordonate) de elemente din X numite muchii (dacă sunt
perechi neordonate) sau arce (dacă sunt perechi ordonate). În primul caz,
graful se numește neorientat, altfel
acesta este orientat. Doua virfuri
unite printr-o muchie sunt adiacente.
Drum – succesiune de muchii. Lungimea drumului e egala cu numarul
muchiilor care il constituie. Drum simplu
– drum in care niciun virf nu se repeat. Gradul unui
nod particular v numărul de arce care sunt conectate la acel nod. Ciclu – drum simplu in care primul si
ultimul virf coincid; P = x0, ..., xk-1 este un drum în graful G și
xk-1x0 este o muchie în acest graf, atunci P + xk-1x0 este un ciclu. Aciclic – fara cicluri. Subgraf
– o parte din graf,fara citeva noduri si muchiile lor. Partial – toate nodurile,fara citeva muchii. Conex – neorientat, oricare 2 noduri au drum intre ele. Tare
conex – orientat, intre oricare 2 virfuri exista drum in 2 directii. In
graful neconex este problema
determinarii elementelor conxe.
Matrice de adiacenta – M(nxn), M(i,j)={1 –
daca (i,j) apartine U (listei muchiilor) si 0 – daca nu.}
Liste de adiacenta – o colectie de n pointeri < (1, 2, ... , n), fiecare
pointer continând adresa unei liste dupa regula urmatoare: L(i) da adresa
listei înlantuite care contine toti succesorii lui i.
Lista de muchii – Fiecare muchie a
grafului poate fi privita ca o inregistrare cu doua componente: cele doua varfuri care constitue
extremitatile muchiei.
Verificarea existenței ciclurilor
în graf
Ciclu – drum simplu in care primul si ultimul virf coincid; P = x0, ...,
xk-1 este un drum în graful G și xk-1x0 este o muchie în acest graf,
atunci P + xk-1x0 este un ciclu.
Conditia ca un arc (x,y) să nu formeze ciclu cu celelalte arce selectate se
poate exprima astfel: nodurile x si y
trebuie să se afle în componente conexe diferite. Initial fiecare nod formează
o componentă conexă, iar apoi o componentă
conexă contine toate
nodurile acoperite cu
arce din MST,
iar nodurile neacoperite formează alte componente conexe.
Arbori. Specificul programării problemei.
Arbore - un caz
particular de graf. – graf orientat, conex, aciclic. – daca exista un virf r
din care oricare alt virf poate fi ajuns pe un drum unic. Padure – multime de
arbori. Adincime a virfului – lungimea drumului dintre radacina si virf.
Inaltime a virfului – lungimea celui mai lung drum dintre acest virf si un virf
terminal. Inlatimea arborelui – inaltimea radacinii. Nivelul virfului –
inaltimea arborelui minus adincimea acestui virf. Reprezentarea arborelui cu
rradacini se face prin adrese ca in cazul listelor inalntuite. Fiecare virf v
fi numerotat in 2 locatii diferite, reprezentind formatia propriu zisa a
virfului (valoarea virfului), adresa celui mai virstnic fiu, si adresa
urmatorului frate. Gradul – numarul de succesori. Rprezentarea e posibila prin
liste generalizate si liste inlantuite.
Arbori. Reprezentare:
Reprezentare prin liste generalizate
Nodurile terminale
sunt elemente atomice, nodurile cu gradul mai mare decit 1 sunsubliste.
Reprezentare prin structuri înlănțuite
Conteaza ordinea
pointerilor; avind adresa unui nod se gasesc toti predecesorii.
Arbori binari
Operaţii asupra arborilor binari
Arborii binari sunt
una dintre cele mai importante structuri neliniare in teoria algoritmilor.
Structura de arbore se
refera la o relație de ramificare la nivelul nodurilor, asemănătoare aceleia
din cazul arborilor din natura. Arborii sunt constituiți din noduri interne
(puncte de ramificare) si noduri terminale (frunze). Fiecare nod are 0, 1 sau 2
succesori; fiecare nod are un singur predecesor, cu excepția rădăcinii care nu
are niciunul; succesorii fiecărui nod sunt ordonați (fiul stâng, fiul drept;
dacă este unul singur trebuie menționat care). Operatii: creare/inserare (Aloca memoria necesara unui nod; Citește
informația nodului si așează mesaje de invitație pentru crearea nodurilor
descendente (stâng si drept); daca numărul introdus este diferit de 0, se
apelează recursiv funcția pentru crearea subarborelui stâng stocându-se adresa
de legătura pentru accesul la descendenți. Urmează apoi apelul recursiv pentru
crearea subarborelui drept; daca numărul introdus este 0, atunci nodului i se
atribuie valoarea NULL. Funcția întoarce adresa nodului creat), stergere (se apelează recursiv ștergerea pentru descendentul
stâng; se apelează recursiv ștergerea pentru descendentul drept;se șterge nodul
curent); selectia câmpului de date
dintr-un nod si selectia descendentilor. Numarul maxim de noduri de pe nivelul
i al unui arbore binar este egal cu 2 la puterea (i-1). Numarul maxim de noduri
ale arborelui binar de adâncime h este egal cu 2 la puterea h, -1
Traversarea arborilor binari (A.B.)
Parcurgerea
arborelui binar – examinarea sistematica a nodurilor sale astfel incit fiecare
nod sa fie atins o singura data sau “vizitarea vârfurilor unui arbore”
Scopul
parcurgerii – prelucrarea informației asociate vârfurilor; transformarea
arborelui dintr-o reprezentare plana intr-o structura liniara.
Orice arbore
binar are 3 componente: rădăcina, subarborele stâng si subarborele drept.
Sunt 3 metode de
parcurgere a arborelui:
Preordine (rsd):
se vizitează rădăcina, se parcurge subarborele stâng, apoi subarborele drept.
Postordine (sdr):
se parcurge subarborele stâng, apoi subarborele drept, se vizitează rădăcina.
Inordine (srd):
se parcurge subarborele stâng, se vizitează rădăcina, se parcurge subarborele
drept.
Strategii de traversare arbori binari: 1, 2 10, 3 8 11 12, 4 9 13 14, 5 6 15, 7
traversare în preordine: prelucrare în ordinea: rsd: 1
2 3 4 5 6 7 8 9 10 11 12 13 14 15
traversare în inordine: prelucrare în ordinea: srd: 5
4 6 7 3 2 8 9 11 10 13 12 15 14
traversare în postordine: prelucrare în ordinea: sdr:
5 7 6 4 3 9 8 2 11 13 15 14 12 10 1
