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 | Pkx}. σ(x) este minim 0 și maxim m când Px.
  • 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 PkPq }
  • demonstrație că se calculează în O(m) - metoda potențialului