Note de curs, clasele 9-10, 29 martie 2013

From Algopedia
Jump to: navigation, search

Teme din urmă

  • Cel mai mare dreptunghi gol: se dă un dreptunghi și n puncte în el. Să se găsească cel mai mare dreptunghi care nu conține niciun punct.
    • Cătălin a bâlbâit rezolvarea, rămâne pentru data viitoare.

Căutări pe stringuri

Generalități

  • Σ (alfabetul datelor de intrare)
  • pattern (subșirul căutat): P de lungime m
  • șirul în care căutăm: S de lungime n
  • lungimea unui șir x se notează cu |x|
  • shift (deplasare): un shift k suprapune patternul P[0...m-1] cu bucata din șir S[k...k+m-1]
  • shift valid: cele două șiruri suprapuse sunt egale
  • prefix (notație: ab)
  • sufix (notație: ab)
  • problema căutării: găsirea tuturor shifturilor valide

Proprietăți interesante:

  • tranzitivitatea: dacă ba și cb, atunci ca
  • dacă ab, atunci axbx pentru orice caracter sau șir x
  • dacă xz și yz, atunci:
    • xy dacă |x| < |y|
    • yx dacă |y| < |x|
    • x = y dacă |x| = |y|

Algoritmul naiv

  • Încercăm pe rând toate shifturile. Există n - m + 1 shifturi, iar verificarea unuia durează O(m)
  • complexitate O(m(n - m + 1)
  • problema algoritmului naiv este că ignoră niște informații utile despre pattern
    • exemplu: dacă patternul este abcdef, iar literele abcd s-au potrivit în shiftul curent (dar litera e nu), atunci aș putea sări următoarele trei shifturi, căci sunt garantat invalide
  • algoritmul naiv merge bine când toate literele din pattern sunt diferite -- O(n)
  • merge bine și dacă șirul de intrare este aleator; dacă d este mărimea alfabetului, atunci complexitatea este

O\left((n-m+1)\cdot (1+{\frac  {1}{d}}+{\frac  {1}{d^{2}}}+...+{\frac  {1}{d^{{m-1}}}})\right)=O\left((n-m+1)\cdot {\frac  {1-d^{m}}{1-d}}\right)<O(2n)

Rabin-Karp

  • exemplu pentru alfabetul Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
  • interpretăm patternul ca pe un număr de m cifre în baza 10
  • pe cazul general, nu putem stoca dm pe un tip de date întreg, deci lucrăm modulo k
  • alegem k astfel încât kd să încapă pe un tip de date întreg
  • când semnătura patternului și semnătura shiftului curent sunt egale, recurgem la comparația caracter cu caracter
  • tot O(mn) în cazul cel mai rău, dar O(m + n + mn/k) în practică

Cu automate finite

Am predat această secțiune pe fugă, mai mult prin exemple.

  • ce face următorul automat? (am desenat un automat cu două stări care acceptă șirurile de 0 și 1 terminate într-un număr par de 0)
  • ce face următorul automat? (am desenat un automat cu trei stări care acceptă șiruri de cifre divizibile cu 3)
  • să se deseneze un automat care acceptă șiruri terminate în 01
  • să se deseneze un automat care acceptă șiruri care conțin subșirul 001
  • să se deseneze un automat care acceptă șiruri care conțin subșirul abacaba
  • definiție formală pentru automate: un tuplu format din
    • Σ (alfabetul)
    • Q (mulțimea de stări)
    • q_0 (starea inițială)
    • F (mulțimea de stări finale)
    • δ : Q x Σ → Q (funcția de tranziție)
  • dacă construim δ, restul algoritmului merge în O(1) per caracter, deci O(m) în total
  • esența funcției δ: cel mai lung prefix care să fie și sufix
  • deci δ(q, a) = max { k | P[0...k-1] ⊐ P[0...q-1]a }
  • construcția naivă a funcției δ se face în O(m3 |Σ|)
  • KMP ne ajută să o construim în O(m), deci independent de mărimea alfabetului

Nu am avut timp să vorbim despre KMP.