Note de curs, clasele 11-12, 16 noiembrie 2012
From Algopedia
Jump to navigationJump to search
Automate finite
- Lema de pompare, reluată rapid
- limbajul L = {w ∈ {0,1}* | w este un șir binar care este multiplu de n} este regulat pentru orice n
- demonstrație prin construirea unui DFA
- folosirea unui DFA pentru căutarea unui subșir
- exemplu: DFA pentru subșirul abacaba
Căutări de șiruri
- noțiuni: pattern, shift valid / invalid, prefix, sufix
- definiție: căutarea înseamnă găsirea tuturor shifturilor valide
- algoritm naiv: O(m n)
- aruncă informație la gunoi, de exemplu când pattern-ul P are toate caracterele diferite
- pe șiruri aleatoare
Algoritmul Rabin-Karp
- precalcularea lui 10m
- lucrăm modulo q astfel încât b * q să se încadreze în tipul de date.
- false positives (exemplu)
Automate finite. Algoritmul Knuth-Morris-Pratt
- automate finite: O(m|Σ|) pentru construcție. Exemplu: abacaba
- funcția de sufix: σ(x) = max {k | Pk ⊐ x}. σ(x) este minim 0 și maxim m când P ⊐ x.
- construcția automatului, δ(q, a) = σ(Pqa)
- demonstrație: automatul este în starea σ(Ti) după citirea caracterului T[i], deci va fi în starea m (de acceptare) doar dacă tocmai a găsit șablonul P
- demonstrație că σ(xa) ≤ σ(x) + 1, adică săgețile merg doar spre stânga.
- calculul automatului: naiv O(m3 |Σ|), poate fi adus la O(m |Σ|)
- KMP: sare peste toate shifturile invalide
- funcția π[q] = max{k | k < q și Pk ⊐ Pq }
- demonstrație că se calculează în O(m) - metoda potențialului