Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: Automate finite si KMP  (Citit de 8667 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
stef2n
Nu mai tace
*****

Karma: 218
Deconectat Deconectat

Mesaje: 641



Vezi Profilul
« : Februarie 20, 2009, 03:20:04 »

Comentarii la articolul Automate finite si KMP
Memorat

Exista 10 categorii de oameni: cei care inteleg sistemul binar si cei care nu il inteleg.
cristiprg
Strain


Karma: -2
Deconectat Deconectat

Mesaje: 23



Vezi Profilul
« Răspunde #1 : Februarie 04, 2010, 11:01:10 »

Cod:
daca q apartine A
          scrie "potrivire la pozitia " i - n + 1
nu ar trebui sa fie n - i + 1?  Confused
Memorat
Prostu
Nu mai tace
*****

Karma: 134
Deconectat Deconectat

Mesaje: 323



Vezi Profilul
« Răspunde #2 : Februarie 04, 2010, 13:22:02 »

Cod:
daca q apartine A
          scrie "potrivire la pozitia " i - n + 1
nu ar trebui sa fie n - i + 1?  Confused

Nu acolo este problema. Iteratorul 'i' trebuie sa il parcurga pe M, deci bucla pentru este intre 1 si lungimea lui M.
Am modificat codul in mod corespunzator. Multumim pentru observatie.
Memorat
alexandru92
Nu mai tace
*****

Karma: -191
Deconectat Deconectat

Mesaje: 496



Vezi Profilul
« Răspunde #3 : Aprilie 06, 2010, 07:44:45 »

Citat
k = 2; δ(1, a) = 3;
k n-ar trebui sa fie 1, sau ... ?
Memorat
APOCALYPTO
Nu mai tace
*****

Karma: 3
Deconectat Deconectat

Mesaje: 250



Vezi Profilul
« Răspunde #4 : Iulie 11, 2010, 20:03:47 »

Citat
k = 2; δ(1, a) = 3;
k n-ar trebui sa fie 1, sau ... ?
Cred ca ai dreptate.

Imi poate explica si mie cineva care stie bine ideea din spatele algoritmului KMP de ce
k <- pi[k] (linia 6 la functia prefix si linia 5 la functia KMP)?
Adica vreau sa stiu de ce functioneaza.
Memorat
ionutz32
Strain


Karma: 16
Deconectat Deconectat

Mesaje: 18



Vezi Profilul
« Răspunde #5 : Iulie 11, 2010, 21:17:38 »

Pai, sa zicem ca avem un sir pe care il parcurgem pentru a afla functia pi.
Cand suntem la pozitia i, prefixul parcurs pana acum va fi ceva de genul:

abacabadabacaba

Cand trecem la pozitia i+1, se mai adauga un caracter.
pi[i] (zis si k) indica sirul "abacaba" (cel mai lung prefix care e si sufix). Verificam daca noul caracter (de pe poz i+1) se potriveste cu cel de pe k+1, care e 'd'. Daca se potriveste, inseamna ca pi[i+1] <- k+1. Altfel, trecem la prefixul de lungime k al sirului, care e:

abacaba

pi[k] indica sirul "aba", iar k va primi valoarea lui pi[k] si se repeta pasii. Verificam daca noul caracter (de pe poz i+1) se potriveste cu cel de pe k+1, care e 'c'. Daca se potriveste, inseamna ca pi[i+1] <-k+1. Altfel, trecem la prefixul de lungime k al sirului, care e:

aba

pi[k] indica sirul "a", iar k <- pi[k]. Verificam daca noul caracter (de pe poz i+1) se potriveste cu cel de pe k+1, care e 'b'. Daca se potriveste, inseamna ca pi[i+1] <-k+1. Altfel, trecem la prefixul de lungime k al sirului, care e:

a

pi[k]=0, se va face o ultima verificare si daca nici de data asta nu coincide, pi[i+1] va fi 0.
Ideea e ca pe masura ce ne indreptam in sir spre stanga, prefixul de lungime k e acelasi cu sufixul de lungime k, in continuarea caruia trebuie pus caracterul de pe poz i+1.
Pe aceeasi idee se bazeaza si codul Algoritm_potrivire_KMP.
Memorat
APOCALYPTO
Nu mai tace
*****

Karma: 3
Deconectat Deconectat

Mesaje: 250



Vezi Profilul
« Răspunde #6 : Iulie 12, 2010, 09:39:13 »

Excelenta explicatie.
Multumesc mult Ionut!
Memorat
PlayLikeNeverB4
Nu mai tace
*****

Karma: 212
Deconectat Deconectat

Mesaje: 719



Vezi Profilul
« Răspunde #7 : Decembrie 01, 2010, 16:47:45 »

Bun articol. Am reusit sa inteleg dupa cateva ore de chinuiala. Pana la urma mi-am dat seama ca defapt algoritmul nu face decat sa caute in mod normal sirul N in M si verifica daca cumva exista mai multe potriviri care "se suprapun". Functia pi arata urmatorul loc unde e posibila aceasta suprapunere.
Memorat
VisuianMihai
De-al casei
***

Karma: -9
Deconectat Deconectat

Mesaje: 121



Vezi Profilul
« Răspunde #8 : Iulie 10, 2012, 18:31:35 »

Citat
    Q = {q0, q1, q2, q3}
    A = {q3}
    Σ = {a, b}
    δ =
Asta vad eu pe ecran. Asa trebuie sa fie la functia de potrivire δ ? Daca nu, imi puteti spune valoarea care lipseste?
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #9 : Iulie 10, 2012, 18:44:52 »

Functia delta este data de tabelul de mai jos. Prima coloana reprezinta nodul sursa, iar ultimele doua reprezinta nodurile destinatie in functie de caracterul citit (a sau b).
Memorat

Am zis Mr. Green
witsel
Strain


Karma: 0
Deconectat Deconectat

Mesaje: 15



Vezi Profilul
« Răspunde #10 : Decembrie 06, 2014, 15:49:26 »

vectorul pi reprezinta starile automatului, iar cu q doar parcurgem starile sau cum este?? ca nu am inteles foarte bine de ce nu scade q cu 1 ci se foloseste
while (q && A[q+1] != A)
            q = pi[q];
Adica am observat pe niste exemple ca asa este dar as vrea sa-mi explice cineva concret DE CE este asa.
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines