Sisteme de programe pentru timp real

Sisteme de programeSisteme de programepentru timp realpentru timp real

Universitatea “Politehnica” din Bucuresti

2005-2006

Adina Magda Florea

http://turing.cs.pub.ro/sptr_06

Structura curs

• Prelucrarea sirurilor de caractere

• Criptografie si criptosisteme

• Retele neurale

• Algoritmi genetici

• Retele Bayesiene

• Programare web

Informatii curs

Pagina Web a cursului

http://turing.cs.pub.ro/sptr_06

Notare

• Laborator 30%

• Tema de casa de semestru 20%

• Examen 50%

• Minimum 7 prezente la laborator

Curs Nr. 1&2

• Complexitatea calculului

• Probleme NP-complete

• Prelucrarea sirurilor de caractere

Complexitatea calculului

Analiza algoritmilor

• o “dimensiune” N

• timpul mediu (average case)

• timpul cel mai nefavorabil (worst case)

• limita a performantei

• deducerea timpului mediu

• identificarea operatiilor abstracte

Clasificarea algoritmilor

Timp de executie proportional cu:

• Constant• log N• N• N log N• N2

• N3

• 2N

Timpul de executie a unui

program

• C1 * f(N) + C2

• Ce inseamna “a fi

proportional cu” ?


• studiul cazului cel mai nefavorabil (worst case) ignorind factorii constanti

• notatia O mare• DEFINTIE: O functie g(N) se spune a fi

O(f(N)) daca exista constantele pozitive C0 si N0 astfel incat g(N) < C0 *f(N) pentru orice N > N0.

• limita superioara a performantelor unui algoritm


• O(f(N)) este o limita superioara si, in realitate, poate fi mult mai scazuta;

• intrarea ce determina cazul cel mai nefavorabil poate sa nu apara niciodata in practica;

• constanta C0 nu se cunoaste si s-ar putea sa nu fie mica;

• constanta N0 nu se cunoaste si s-ar putea sa nu fie mica.


• notatia • limita inferioara a performantelor unui

algoritm (f1(N) (“big omega”)

• DEFINTIE: O functie g(N) se spune a fi (f1(N)) daca exista o constanta pozitiva C0 astfel incit g(N) C0 * f1(N) pentru un numar infinit de mare de valori ale lui N.

Complexitatea calculului pentru algoritmi recursivi

• Descompunerea recursiva a problemei in subprobleme

• Timpul de executie pentru acesti algoritmi este determinat de dimensiunea si numarul subproblemelor, precum si de costul descompunerii

• CN = complexitatea pentru o intrare de dimensiune N

• CN NLa fiecare apel recursiv se elimina cate un element de

intrare: CN = CN-1+1 int sum(int n)

{ if (n==) return 1; return n+sum(n-1); }

• CN N2/2Un algoritm care necesita parcurgerea intrarii si elimina

un element la fiecare apel recursiv: CN = CN-1 + N, pentru N 2, cu C1 = 1

bubble(int a[], int N) /* bubble sort recursiv */

• CN logN

Algoritmul injumatateste intrarea la fiecare apel recursiv: CN = CN/2 + 1, pentru N 2, cu C1 = 0 (pt deducere N=2n)

int binsearch(int a[], int key, int l, int r)

• CN 2N

Algoritmul imparte intrarea in doua parti la fiecare pas si apoi prelucreaza recursiv fiecare parte (“Divide and conquer”): CN = 2*CN/2 + 1, pentru N 2, cu C1 = 0

rigla(int l, int r, int h

/* Desenarea marcajelor pe o rigla */

• CN NlogNAlgoritm recursiv care isi imparte intrarea in doua parti

la fiecare pas, prelucreaza recursiv fiecare parte si face o trecere liniara peste intrare, fie inainte, fie dupa divizarea intrarii (“Divide and conquer”) :

CN = 2 * CN/2 + N, pt N 2, cu C1 = 0.

quicksort(int a[], int l, int r)

• Insertion sort N

• Bubble sort

• Quicksort

• Heapsort

• Mergesort

• Sequential search

• Binary search

• Binary tree search

• Shortest path V, E

• Depth-first search

• Breadth-first search

• Min. spanning tree

• N2/4, N2/8

• N2/4, N2/4

• N logN, N2

• N logN, N logN

• N logN, N logN (sp N)

• N, N/2

• logN, logN

• N, logN

• E sau V2

• V+E sau V2

• V+E sau V2

• (E+V) log V – pr. q.

• E log E - Kruskal

Probleme NP-complete

• “grele” si “usoare”

• Problema usoara: “Exista o cale de la x la y cu cost M ?

• Problema grea: “Exista o cale de la x la y cu cost M ?

• Algoritmi “eficienti” si algoritmi “ineficienti”

Probleme NP-complete

• P: multimea tuturor problemelor ce pot fi solutionate prin algoritmi deterministi, in timp polinomial

• NP: multimea tuturor problemelor ce pot fi rezolvate prin algoritmi nedeterministi, in timp polinomial

• NP =? P

Clasa problemelor NP-complete

• Clasa de echivalenta: daca o problema din NP poate fi rezolvata eficient, atunci toate pot fi rezolvate la fel

• Se poate demonstra echivalenta problemelor NP-complete din punct de vedere al algoritmilor de rezolvare

• Pentru a demonstra ca o problema X din NP este NP-completa este necesar sa se demonstreze ca o problema NP-completa (Y, cunoscuta) poate fi transformata in timp polinomial - redusa polinomial la problema X

• Presupunem ca problema ciclului hamiltonian (CH) este NP-completa (Y) si dorim sa vedem daca cea a comis-voiajorului (CV) este NP-completa (X)

• Trebuie ca Y sa fie redusa polinomial la X

• Instanta a CH => se construieste o instanta a CV:

• oraseCV = noduri din grafCH

• distante perechi oraseCV = 1 daca exiata arcCH

» = 2 daca nu exista arcCH

Se cere CV sa gaseasca un ciclu care include toate orasele si are suma ponderilor V, numarul de noduri din graf – acesta trebuie sa corespunda unui ciclu hamiltonian

Am demonstrat ca CV este NP-completa

• Este o expresie booleana data realizabila ?

• Dandu-se un graf neorientat, exista un ciclu hamiltonian continut in el (ciclu ce include toate nodurile) ?

• Problema comis-voiajorului: Fiind dat un graf cu ponderi intregi pozitive si un intreg K, sa se gaseasca un ciclu care include toate nodurile si a carui suma a ponderilor sa fie K (sau minima).

• Exista un K-clique intr-un graf neorientat G? (K-clique – un subgraf complet - orice pereche de puncte din subgraf este legata de un arc - al lui G cu K noduri)

Exemple de probleme NP-complete

Este un graf neorientat colorabil cu k culori ? (G este k-colorabil daca exista o atribuire de intregi 1, 2, ... k, reprezentand culori, pentru nodurile din G, astfel incat nu exista doua noduri adiacente de aceeasi culoare. Numarul cromatic al lui G este cel mai mic k pentru care G este k-colorabil.)

Exista o acoperire de noduri de dimensiune K intr-un graf neorientat ? ( G = (V, E), o acoperire de noduri este un subset S V astfel incit fiecare arc din G este incident intr-un nod din S, card(S) = K.)

• Problema izomorfismului subgrafurilor: este un graf neorientat G izomorf cu un subgraf al unui alt graf neorientat G’ ?

Problema Knapsack: Fiind data secventa de intregi S = i1, i2, ... in si un intreg K, exista o subsecventa a lui S a carei sume este exact K ?

Pentru o familie de multimi S1, S2, … Sn, exista o acoperire de multimi formata dintr-o sub-familie de multimi disjuncte ?

• Problema planificarii taskurilor: Dandu-se un “deadline” si o multime de taskuri de lungimi variabile, ce trebuie executate pe doua procesoare identice, se pot aranja aceste taskui in asa fel incit “deadline”-ul sa fie respectat ?

Cum se poate evita complexitatea?

• algoritm polinomial dar suboptimal; rezulta o solutie apropiata de cea mai buna

• se foloseste direct algoritmul exponential daca dimensiunea intrarii nu este mare

• algoritm exponential cu euristici

Algoritmi de identificare a sirurilor de caractere

• Introducere

• Algoritmul cautarii directe

• Algoritmul Knuth-Morris-Prat

• Algoritmul Boyer-Moore

• Algoritmul Rabin-Karp

• Algoritmul deplaseaza-aduna

1 Introducere

• Identificarea (recunoasterea) sabloanelor in siruri de caractere

• sir – a, lungime N • sablon – p, lungime M• Fiind dat un sir de lungime N

a = a1a2a3...aN, si un sablon de lungime M

p = p1p2p3...pM, se cere sa se gaseasca multimea de pozitii

{ i 1 i N-M+1 a.i. aiai+1…ai+M-1 = p }

Introducere

• Prima aparitie / toate aparitiile• Cum difera de cautarea unei chei• Scurt istoric• Algoritmul fortei brute. Are un timp al cazului cel mai nefavorabil

proportional cu N*M, dar in multe cazuri practice, timpule mediu este proportional cu N+M.

• In 1970, S.A. Cook a demonstrat teoretic, folosind un model de masina abstracta, ca exista un algoritm de identificare a sabloanelor cu timpul cel mai nefavorabil proportional cu N+M. Pornind de la modelul lui Cook, D.E. Knuth, J.H. Morris si V.R. Pratt au construit un astfel de algoritm.

• R.S. Boyer si J.S. Moore au descoperit, in 1976, un algoritm chiar mai rapid decit (2) in multe aplicatii, deoarece examineaza in multe cazuri numai o parte din caracterele textului.

• In 1980, R.M. Karp si M.O. Rabin au observat ca problema identificarii sabloanelor nu este mult diferita de o problema standard de cautare si au descoperit un algoritm aproape la fel de simplu ca cel al fortei brute, dar care are virtual intotdeauna timpul proportional cu M+N.

2 Algoritmul cautarii directe

int cautsablon1(char *p, char *a) { int i = 0, j = 0; /* i este pointerul in text */ int M = strlen(p); /* j este pointerul in sablon*/ int N = strlen(a);

do { while ((i < N) && (j<M) && (a[i]==p[j])) {i++;j++;} if (j==M) return i-M; i- = j-1; j = 0; } while (i<N);return i;

}

Algoritmul cautarii directe

int cautsablon2(char *p, char *a) { int i, j;

int M = strlen(p); int N = strlen(a); for (i=0, j=0; j<M && i<N; i++, j++) while (a[i] != p[j])

{ i- = j-1; j = 0;}

if (j==M) return i-M; else return i;

}

Se introduce santinela pla sfarsitul lui a

Algoritmul cautarii directe

• Proprietate: Algoritmul cautarii directe necesita, in cazul cel mai nefavorabil, un numar de maxim N*M comparatii de caractere.

• Timpul de rulare este proportional, pentru cazul cel mai defavorabil, cu M*(N-M+1), si cum M << N obtinem valoarea aproximativa N*M.

• Cazul cel mai nefavorabil poate apare, de exemplu, la prelucrarea imaginilor binare.

• In multe aplicatii de prelucrare a textelor, bucla interioara se executa rareori si timpul de rulare este proportional cu N+M.

3. Algoritmul Knuth-Morris-Pratt

Idee• startul fals al identificarii consta din caractere

deja cunoscute• a – sir, i – index in sir, N

• p – sablon, j – index in sablon, M

• Caz particular: primul caracter din sablon nu mai apare in sablon i

sir: 1000001000000 a

sablon: 1000000 p

j

nu i = i – j + 1 da – nu se modifica i si j = 0

Caz general

sir: 1010100111 a

sablon: 10100111 p

j=4

• i trebuie decrementat. Cu cat?

• Se poate cunoaste aceasta valoare – depinde de caracterul din sablon Daca nepotrivirea intre sir si sablon apare pe pozitia j in sablon, si Exista un k [0, j-1] pentru care

p[0] ... p[k-1] = p[j-k] ... p[j-1]

atunci o posibila identificare intre sir si sablon poate apare incepand cu caracterul din sir a[i-k] si caracterul din sablon p[j-k].

j = 4, k=2

p[0] p[1] = p[j-k] p[j-1], adica p[0] p[1] = p[2] p[3]

Caz generalTrebuie cautat k maxim cu aceasta proprietate.• Daca nu exista k cu ac. proprietatea atunci cautarea se

reia de la pozitia i si j=0.• Daca exista un astfel de k atunci

i = i – k, j = 0 .• Se calculeaza valorile unui vector next[M] pt pj p

= cu cat trebuie decrementat i la aparitia unei nepotriviri pe pozitia j

• next[j] = numarul maxim de caratere nr de la inceputul sablonului care identifica cu ultimele nr caractere din sablon pana la pozitia j-1 = kmax cu proprietatea anterioara

Vectorul next10100111 next[4] = 2 j = 4 Reluare cautare i = i – next[j], j = 0

Cum se calculeaza next[j]? Metoda informala, legata de implementare Metoda formala, bazata pe modelul formal al unui automat

finit determinist care recunoaste un sablon intr-un sir, pentru un alfabet dat.

• Se gliseaza o copie a primelor j caractere din sablon peste sablon de la stanga la dreapta, incapand cu primul caracter din copie suprapus cu al doilea caracter din sablon

• Se opreste glisarea daca: (a) toate caracterele suprapuse (pana la j-1) coincid sau (b) primul caracter al copiei ajunge pe pozitia j.

Vectorul next - exemplu j next[j] sablon si copie sablon 1 0 10100111 0 matches

12 0 10100111 0 matches

10 10

3 1 10100111 101 101 1 match

4 2 10100111 1010 1010 2 matches

5 0 10100111 10100 10100 10100 0 matches 10100

6 1 10100111 101001 1 match

7 1 10100111 1010011 1 match 1010011

Vectorul next• Caracterele identice definesc urmatorul loc posibil in care

sablonul se poate identifica cu sirul, dupa ce se gaseste o nepotrivire pe pozitia j (caracterul p[j]).

• Distanta cu care trebuie sa ne intoarcem in sir este exact next[j], adica numarul de caractere care coincid.

• Este convenabil next[0] = -1.

Cum facem sa nu ne intoarcem in sir?• a[i] != p[j] se reia de la i – next[j] si j = 0• Dar primele next[j] caractere incepand de la pozitia i – next[j]

din sir = primele next[j] caractere din sablon i nemodificat si j = next[j]

Exemplu

i = 4 ar trebui i = 2 si j = 0

sir: 1010100111 a

sablon: 10100111 p

j=4

next[4] = 2

acelasi efect daca i nemodificat si j = 2

Algoritmul Knuth-Morris-Prattint cautKMP(char *p, char *a) { int i, j; int M=strlen(p); int N=strlen(a); initnext(p); for (i=0, j=0; j<M && i<N; i++, j++) while ((j>=0) && (a[i] != p[j])) j = next[j]; if (j==M) return i-M; else return i; }

Obs: Pt. j = 0 si a[i] != p[0] este necesar ca i+, j = 0 deci next[0] = -1

Calculul vectorului next

void initnext(char *p)

{ int i,j, M=strlen(p);

next[0] = -1;

for (i=0, j=-1; i<M; i++, j++, next[i]=j)

while ((j>=0) && (p[i] != p[j]))

j=next[j];

}

Obs:

• Dupa incrementarile i++ si j++ avem p[i-j] … p[i-1] = p[0]…p[j-1]

• Identificarea efectueaza maxim M+N comparatii de caractere

Algoritm pentru sablon fix

sfs0 s1 s2 s3 s4 s5 s61 0 1 0 0 1 1 1

1

s7

Caracterele din sirul de intrare total diferite de cele din sablonsunt citite numai in s0, pe tranzitia s0 p s0, p p0.

Automatul citeste un nou caracter de intrare numai pentru tranzitiile “la dreapta”, i.e., daca caracterul din sir se potriveste cu sablonul.

Altfel automatul se intoarce fara a citi un nou caracter (acesta este motivul pentru care nu sunt etichetate si tranzitiile “la stinga”).

Algoritm pentru sablon fix

int cautKMP1(char *a) { int i=-1;

sm: i++; s0: if (a[i]!=‘1’) goto sm; i++; s1: if (a[i]!=‘0’) goto s0; i++; s2: if (a[i]!=‘1’) goto s0; i++; s3: if (a[i]!=‘0’) goto s1; i++; s4: if (a[i]!=‘0’) goto s2; i++; s5: if (a[i]!=‘1’) goto s0; i++; s6: if (a[i]!=‘1’) goto s1; i++; s7: if (a[i]!=‘1’) goto s1; i++; return i-8;}

Caracteristici KMP• Algoritmul KMP presupune precompilarea sablonului, ceea

ce este justificat daca M « N, adica textul este considerabil mai lung decat sablonul;

• Algoritmul KMP nu decrementeaza indexul din sir, proprietate folositoare mai ales pentru cautarile pe suport extern;

• Algoritmul KMP da rezultate bune daca o nepotrivire a aparut dupa o identificare partiala de o anumita lungime. In cazul in care aceste situatii sunt o exceptie, algoritmul nu aduce imbunatatiri semnificative;

• Algoritmul KMP imbunatateste timpul cazului cel mai nefavorabil, dar nu si timpul mediu.

4 Algoritmul Boyer-Moore

UN EXEMPLU DE CAUTARE RAPIDA

UTARE

UTARE

UTARE

UTARE

UTARE

• Potrivit daca intoarcerea in text nu este dificila

Algoritmul Boyer-Moore

• Vectorul skip – se defineste pentru fiecare caracter din alfabet

• arata, pentru fiecare caracter din alfabet, cat de mult se sare (se deplaseaza sablonul la dreapta) in sir daca acest caracter a provocat nepotrivirea

• rutina initskip – initializeaza skip:

• skip[index(p[j])] = M-j-1, j=0,M-1 pentru caracterele din sablon

• skip[index(c)] = M pentru restul de caractere din alfabet


int caut_BM(char *p, char*a) { int i, j, t;

int M=strlen(p), N = strlen(a); initskip(p); for (i=M-1, j=M-1; j>=0; i--, j--) while (a[i]!=p[j])

{ t = skip[index(a[i])]; i+ = (M-j > t) ? M-j : t; if (i >= N) return N; j = M-1;

return i+1;

}


• Combinarea a doua metode pentru a afla exact cu cat trebuie deplasat la dreapta sirul: metoda prezentata si metoda vectorului next din algoritmul Knuth-Morris-Prat, in varianta de la dreapta la stinga, pentru ca apoi sa se aleaga in skip cea mai mare valoare.

• In conditiile acestei modificari, este valabila urmatoarea proprietate.

• Proprietate: Algoritmul Boyer-Moore face cel mult M+N comparatii de caractere si foloseste N/M pasi, daca alfabetul nu este mic si sablonul este scurt.

5. Algoritmul Rabin-Karp

Idee• Considera textul ca fiind o memorie mare si

trateaza fiecare secventa de M caractere a textului ca o cheie intr-o tabela de dispersie (hash).

• Trebuie sa calculam functia de dispersie pentru toate secventele posibile de M caractere consecutive din text si sa verificam daca valorile obtinute sunt egale cu functia de dispersie a sablonului.

• Artificiu pt. a nu tine toata tabela de dispersie in memorie.

Calculul functiei hash

• h(k)=k mod q, unde k este numarul de caractere din sir, iar q (dimensiunea tabelei) este un numar prim mare.

• q poate fi chiar foarte mare deoarece tabela hash nu se tine in memorie

• Functia de dispersie pentru pozitia i din text se calculeaza pe baza valorii acestei functii pentru pozitia i-1

• Se transforma grupuri de M caractere in numere, prin impachetare ca reprezentare intr-o anumita baza

• Aceasta corespund la a scrie caracterele ca numere in baza d, unde d este numarul de caractere posibile din alfabet.

Calculul functie hash

• O secventa de M caractere consecutive a[i]…a[i+M-1] corespunde:

y = a[i]*dM-1 + a[i-1]*dM-2 + … + a[i+M-1]• Presupunem ca stim valoarea lui h(y) = y mod q.• Deplasarea in text cu o pozitie la dreapta corespunde

inlocuirii lui y cu

y1 = (y - a[i]*dM-1)*d + a[i+M]• Consideram d=32 (sau orice multiplu de 2 corespunzator)• Cum facem sa nu memoram valorile functiei hash pentru

toate grupurile de M caractere din sir?

Calculul functiei hash pt. y1 pe baza lui ySe cunoaste ca:

(a + b) mod q = (a mod q + b mod q) mod q

(a * b) mod q = (a * (b mod q)) mod q

Se doreste sa se arate ca:

(a0 * x + a1) mod q = ((a0 mod q) * x + a1) mod q

Demonstratie:

(a0 * x + a1) mod q = ((a0 * x) mod q + a1 mod q) mod q =

= [(x(a0 mod q)) mod q + a1 mod q] mod q = ((a0 mod q) x + a1) mod q

Noul sir impachetat y1 se obtine din y astfel (slide precedent):

y1 = (y - a[i] * dM-1) * d + a[i+M]

Cum se calculeaza y1 mod q pe baza lui y :

y1 mod q = ((y – a[i] * dM-1) * d + a[i+M]) mod q

= ( (y – a[i] * dM-1) mod q * d + a[i+m]) mod q

Algoritmul Rabin-Karpint caut_RK(char *p, char *a){ int i;long int dM=1, h1=0, h2=0;

int M=strlen(p), N=strlen(a);

for (i=1; i<M; i++) dM = (d*dM) % q;

// calculeaza d**(M-1) mod q in dM

for (i=0; i<M; i++)

{h1 = (h1*d + index(p[i]))%q;

// functia hash pt sablon

h2 = (h2*d + index(a[i]))%q;

// functia hash pt text

}

for (i=0; h1!=h2; i++)

{h2 = (h2 + d*q - index(a[i])*dM)%q;

// d*q se adauga pt a mentine expresia >0

h2 = (h2 * d + index(a[i+M]))%q;

if (i > (N-M)) return N;

}

return i;}

Caracteristici RK• Algoritmul Rabin-Karp are destul de probabil o complexitate

timp liniara.

• Algoritmul are timpul proportional cu N+M, dar el gaseste doua siruri cu valori de dispersie egale.

• In aceste conditii, trebuie sa comparam sablonul cu cele M caractere din sir, pentru cazul coliziunilor.

• Deci, din punct de vedere teoretic, acest algoritm ar putea sa fie tot O(NM), in cazul cel mai defavorabil, in care toate sabloanele gasite ar fi coliziuni putin probabil, deoarece q este mare; in practica, algoritmul foloseste N+M pasi.

• Daca sablonul se cauta de mai multe ori, el poate fi considerat o cheie, iar textul poate fi organizat in stucturi eficiente de cautare, cum ar fi arbori binari, tabele de dispersie, etc.

6. Algoritmul deplaseaza-aduna

Idee• Algoritmul reprezinta starea cautarii ca un

numar, si fiecare pas in cautare (identificare) este descris printr-un numar de operatii aritmetice si logice

• Acest lucru este posibil daca numerele folosite sunt suficient de mari pentru a putea reprezenta toate starile posibile in cursul rularii

Algoritmul deplaseaza-aduna

Se poate generaliza usor la urmatoarele cazuri:

1. “Don’t care symbols”, deci identificarea cu orice caracter pe o pozitie

2. Identificarea cu un caracter dintr-o clasa de caractere (un interval)

3. Identificarea cu un caracter din complementul unei clase.

4. Identificarea cu un numar dat K de nepotriviri

5. Identificarea mai multor sabloane in paralel.

Ipotezea - sirul (de lungime N) in care se executa cautare

p - sablonul (de lungime M)

i - index in sablon

j - index in text

• Se foloseste un vector cu M componente, care reprezinta cele M posibile stari in cautare: indexul i indica starea intre pozitiile 1…i ale sablonului si pozitiile (j-i+1)…j ale textului

• M comparatoare de siruri care ruleaza in paralel si citesc concurent aceeasi pozitie din sir

Ipoteze• starei - p[1]…p[i] ? a[j-i+1] … a[j]

• {sji}, i=1,M – multime de stari dupa citirea

caracterului j din sir

• sji = numarul de nepotriviri intre

p[1]…p[i] si a[j-i+1] …a[j]

• Apare identificare daca sjM = 0

Exemplu• Pozitia j-1 de cautare in text – se

calculeaza sj-1i

i i sji-1

sablon a b a b c 1 1





sir c b b a b a b a b c a b a

j-1

• Sablonul ababc (M=5)

• Sir: cbbabababcaba

sji = numarul de nepotriviri intre p[1]…p[i] si a[j-i+1] …a[j]

Exemplu• Se avanseaza in text la

pozitia j – se calculeaza sji

j

i i sj-1i Ti[a] sj

i

a b a b c 0 0

a b a b c 1 1 0 0

a b a b c 2 0 1 2

a b a b c 3 3 0 0

a b a b c 4 0 1 4

c b b a b a b a b c a b a 5 5 1 1

Definitii• Se defineste T[x] pentru x • Ti[x] = 0 daca pi = x, i=1,M

= 1 in caz contrar(prin compararea fiecarui caracter x din alfabet cu p[0]

…p[M])

• Se observa relatia

sji = sj-1

i-1 + Ti[aj] i=1,M• Identificarea apare daca sj

M = 0• Cuvant w• b biti necesari pentru a reprezenta o stare

Definitii

• Vector de stari reprezentat ca un numar in baza 2b

• Pentru identificare exacta b = 1

• sji = 0 daca p[0]..p[i] = a[j-i+1]..a[j]

= 1 in caz contrar

• sjM = 0 atunci starej < 2M-1

1

01 2

M

i

ibjisstare

j

DefinitiiActualizare la citirea unui nou caracter:• deplasez vect. de stari cu b pozitii la stanga = avans

cu 1 pozitie in text• actualizez starile pe baza lui T si fac o operatie

potrivita

• starej = (starej << b) op T[aj]

• Obs: Operatia nu trebuie sa produca transport pt. sji

care sa afecteze sji+1

• Pentru b=1 op = sau logic

Definitii• Reprezint T tot ca un numar in baza 2b

• unde, x, (cond) = 1 daca cond adevarata= 0 in caz contrar

Exemplub=1, = {a, b, c, d} p = ababcT[a] = 11010 T[b] = 10101T[c] = 01111 T[d] = 11111starea initiala este 11111

T x x pib i

i

M

[ ] ( )

10

1

2

Exemplu

Sablon ababc

Sir a b d a b a b a b c

T[x] 11010 10101 11111 11010 10101 …………..

Stare 11110 11101 11111 11110 11101 ….

(11111)

starej-1 << b | T[aj] = starej

Algoritmul deplaseaza-aduna

#define CUVANT 32

#define B 1

#define MAXSIM 128

In variabila lim vom calcula 2B(M-1)

Algoritmul deplaseaza-adunaint caut_shadd(char *p,char *a) {unsigned int state, lim, first, initial; unsigned int T[MAXSIM]; int i, j, matches, M=strlen(p), N=strlen(a); if(M>CUVINT) {printf("\n Error: Utilizati dim. sablon<dim.

cuvint\n"); return -1; } /* preprocesare */ for(i=0; i<MAXSIM; i++) T[i]=~0; lim=0; for(i=0,j=1; i<M; i++,j<<=B) { T[p[i]] &= ~j; lim |= j; } lim = ~(lim>>B);

Algoritmul deplaseaza-aduna - continuare

/* cautare */ matches=0; initial = ~0; first=p[0]; i=0; while (i<N) { while(i<N && a[i]!=first) i++; state=initial; do { state=(state<<B) | T[a[i]]; if (state<lim) matches++; /* identificare pe poz i-M+1 */ i++; } while(state!=initial); } return matches;}

Caracteristici• Este nevoie de b*M*|| biti suplimentari de memorie si daca b*M w,

atunci este nevoie de || cuvinte de memorie suplimentare.

• Construirea tabelei T se face intr‑un timp proportional cu:

• Complexitatea cautarii, pentru cazul cel mai nefavorabil si pentru cazul mediu este

unde

este timpul necesar calculului unui numar constant de operatii cu intregi de M*b biti, folosind un cuvint de lungime w biti.

• In practica (sabloane de 32 sa 64 biti), timpul mediu si cel mai nefavorabil este O(N).

OM b

wM

OM b

wN

M b

w

Extinderea algoritmului la identificarea

claselor de sabloane • x

• * [x1x2…xn] - clasa {x1} sau {x1x2…xn} - complement


claselor de sabloane Exemplu: = {a, b, c, d}.

Sablonul [Aa]b{b}*{bd} se potriveste peste (sub)sirurile Abaca, abcda, dar nu si peste abbac sau ababb.

Doua dimensiuni: lungimea M a sablonului si dimensiunea descrierii sablonului, notata cu M1.


claselor de sabloane

Exemplu: = {a, b, c, d}.

Sablonul este a{b}[ab]b{abc}.

M = 5 si M1 = 15.

T[a] = 11000 T[b] = 10011

T[c] = 11101 T[d] = 01101

T x x clasaib i

i

M

[ ] ( )

10

1

2

Algoritmul pt calculul lui Tvalinit 111...111 (w biti)for i = 1 to M do

if p1 = ‘*’ or pi este un complement

then valinit valinit & 111…0i…111

endfor

for i = 1 to || do T[xi] valinitendfor

for i = 1 to M do

foreach x pi do

if pi este un complement

then T[x] T[x] | 000…1i…000

else T[x] T[x] & 111…0i…111

endforeach

endfor

70

Implementarea calculului lui T

void tinit(char *p)

{ unsigned int T[MAXSYM], initval, mask=1;

int i=0, M=0, M1=strlen(p);

/* calculeaza initval<-initval & 111..0i..111 */

initval=~0;

while(i<M1)

{ M++;

if(p[i]=='*')initval&=~mask;

else if(p[i]=='{'){initval&=~mask;

while(p[i]!=EOS &&

p[i]!='}') i++;}

else if(p[i]=='[')

while(p[i]!=EOS && p[i]!=']')i++;

mask<<=B;i++;

}71

Implementarea calculului lui T - continuare

/* calculeza T[xi]<-initval pentru fiecare xi din alfabet*/

for(i=0;i<MAXSYM;i++)T[i]=initval;/* Actualizeaza T[x], cu x din sablon */ i=0; mask=1; while(i<M1)

{ if(p[i]=='{') while(p[++i]!='}') T[p[i]]|=mask;

else if(p[i]=='[')while(p[++i]!=']')

T[p[i]]&=~mask; else T[p[i]]&=~mask;

i++; mask<<=B;}

72

Identificarea cu max k nepotriviriFiecare stare individuala poate fi reprezentata printr-un numar de maxim O(logM) biti.

- daca sjM k, am gasit o identificare cu maximum k

nepotriviri

· - operatorul op este adunarea

- Deoarece ne intereseaza numai k nepotriviri, este suficient sa alegem

b = sup|log2(k+1)| + 1

Problema transportului – un bit de transport (overflow) pt fiecare stare

73

Identificarea cu max k nepotriviri- Obtinerea unei noi stari:

starej+1=(starej << b) + T[xj+1]

- Conditia de identificare cu max k nepotriviri

sjM + overfj < (k+1) * 2b(M-1)

Cazul • Sablonul ababc

• Alfabetul {a, b, c, d}

• T construit anterior

• k = 2, b = 3 (b = sup|log2(k+1)| + 1)

74

Exemplu• Sablonul ababc• Alfabetul {a, b, c, d}• T construit anterior• k = 2, b = 3• starea initiala 00000• overflow initial 44444

sir a b d a bT[x] 11010 10101 11111 11010 10101stare 11010 20201 13121 02220 32301overf 44440 44400 44000 40000 00000

sir a b a b cT[x] 11010 10101 11010 10101 01111stare 30020 10301 10020 10301 00121overf 04000 40000 04000 40000 04000

75

Algoritmul pentru max k nepotriviri

mask 1Mb0…0…………12b0…01b0…0

lim (k+1) << (M-1)*bstare 0 overf maskfor i = 1 to N do

stare (stare << b) + T[ai]

overf (overf << b) | (stare & mask) stare stare & ~mask if (stare+overf) < lim

then identificare la pozitia i-M+1

endfor

76

Sisteme de programe pentru timp real

Documents

Transcript of Sisteme de programe pentru timp real