Textové informační systémy 8.6.2007
1.
a)
Automat najde 2 vyskyty vzorku s maximalne 2 chybami celkem.
b)
Odpověď: 9
c)
Odpověď: 12
tenis
-----
tDD--
--DiD
--DDs
--Dis
tIIis
tRR--
--Ris
tRD--
--RiD
tDR--
--RDs
-IRis
2.
N = 22
beta (22) = 10110
beta' (22) = 0110
alfa ( | beta(22) | ) = alfa (5) = 00001
gamma (22) = 000101001
omega = B0.B1. ... Bk.0
Bk = beta (22) = 10110
Bk-1 = beta ( | Bk | - 1 ) = beta (4) = 100
Bk-2 = beta ( | Bk-1 | -1 ) = beta (2) = 10
| B0 | = 2 => Bk-2 == B0
omega = 10100101100
3.
Karp-Rabinovo vyhledavani - pouziti hashovaci funkce. Misto prikladani
vzorku k textu na vsech pozicich, kontroluje shodu jen tam, kde
podretezec textu vypada "podobne". Podobnost urcuje hashovaci funkce.
Hashovaci funkce by mela byt efektivne vycislitelna a mela by dobre
separovat ruzne retezce.
Vyhledavani je v nejhorsim pripade kvadraticke, ale prumerne O(T+V).
4.
var TEXT: array[1..T] of char; VZOREK: char;
I := 1;
TEXT [T+1] := VZOREK;
while (TEXT[I] <> VZOREK) do
begin
if TEXT[I+1] = VZOREK then break;
I := I+2;
end;
FOUND := (I<T) OR (TEXT[T] = VZOREK);
vystup v promenne FOUND : ano/ne.
5.
a)
NE
b)
X = abcde;
Y = fghij;
R(X,Y) = 5;
DIR(X,Y) = 5;
DIRT(X,Y) = 5;
stale vyuziva pouze funkce R-Replace.
c)
T=(a^100).baaaaa
V=baaaaa
6.
7.
G = ({S},{a,b},P,S)
P = { 0: S -> bS,
1: S -> a,
2: S -> bSS}
0: bS
0: bbS
1: bba
2: bSS
2: bbSSS
2: bbbSSSS
0: bbbbSSSS
1: bbbbaSSS
1: bbbbaaSS
1: bbbbaaaS
1: bbbbaaaa