ASD Ćwiczenia 13

Uzasadnić opoprawność algorytmu obliczającego długość najkrótszego słowa pokrywającego dany tekst.

Rozwiązanie

Niech $S[i]$ będzie rozmiarem minimalnego pokrywajćego słowa dla prefiksu $x[1..i]$. Poprawność wynika z następującego faktu: \ $S[i]=i\text{<mrow data-mjx-texclass="ORD">lub</mrow>}S[i]=S[P[i]].$

Zadanie 1

Słowem pokrywającym tekst x taki tekst y, którego wystąpienia w x pokrywają cały tekst x. Na przykład aba pokrywa ababaaba, natomiast nie pokrywa tekstu abaaababa. Obliczyć długość najkrótszego słowa pkrywającego dany tekst x.

Rozwiązanie

Niech $S[i]$ będzie rozmiarem minimalnego pokrywajćego słowa dla prefiksu $x[1..i]$. Algorytm wykorzystuje następujący fakt: \ $S[i]=i\text{<mrow data-mjx-texclass="ORD">lub</mrow>}S[i]=S[P[i]].$ \ Następujący algorytm liczy długość minimalnego słowa pokrywającego tekstu x. Liczymy wartości $S[i]$ najmniejszej długości minimalnego słowa pokrywającego $x[1\dots i]$ dla każdego $1\le i\le n$. W $i$-tej iteracji algorytm pamięta jaki jest ``znany zakres każdego minimalnego słowa pokrywającego.

Rysunek 3: $i$-ta iteracja algorytmu, dla $i=15$, oraz słowa $x=abaabababaababa\dots$. Tuż przed rozpoczęciem tej iteracji mamy $P[i]=8$, $q=S[8]=3$, $Zakres[3]=13$. Po zakończeniu $i$-tej iteracji

mamy $S[15]=3,Zakres[3]=15$, ponieważ $i-Zakres[3]\le q$.

Algorytm Rozmiar-Minimalnego-Pokrycia

---

for $i:=2$ to $n$ do
   $Zakres[i]=i,S[i]=i$

for $i:=2$ to $n$ do
   if $P[i]>0$ oraz $i-Zakres[S[P[i]]\le S[P[i]]$ then
      $S[i]:=S[P[i]]$; $Zakres[S[P[i]]:=i$;

return $S[n]$;

----------------------------------------------------------------------

Zadanie 2

Udowodnić, że w wersji on-line algorytmu KMP mamy $delay=O(logm)$

Rozwiązanie

Wystarczy wykazać, że

$P^{\prime }[i]=j,P^{\prime }[j]=k>0\Rightarrow i\ge k+j$

Fakt ten wynika z lematu o okresowości i z definicji tablicy P'.

----------------------------------------------------------------------

Zadanie 3

Udowodnić, że w wersji on-line algorytmu KMP mamy $delay=\mathrm{\Omega }(logm)$

Rozwiązanie

Słowa Fibonacciego definiujemy następująco:

$F_0=a,F_1=ab,F_{n+1}=F_n\cdot F_{n-1}$

Na przykład: $F_3=abaab,F_4=abaababa,F_5=abaababaabaab.$

Niech $F{\text{'}}_n$ oznacza słowo Fibonacciego z obciętymi ostatnimi dwoma symbolami. Jeśli jako wzorzec weżmiemy słowo Fibonacciego $F_n$, a jako tekst słowo $F{\text{'}}_{n}cc$ to przy wczytywaniu $|F_n-1|$-ego symbolu algorytm ma opóżnienie logarytmiczne, iterujemy $\mathrm{\Omega }(\log n)$ razy operację: $j:=P^{\prime }[j]$.

----------------------------------------------------------------------

Zadanie 4

Udowdnij poprawność algorytmu na cykliczną równoważność słów.

Rozwiązanie

Zdefiniujmy:

$D(u)=\{k:1\le k\le n$ oraz $u^{(k)}>w^{(j)}$ dla pewnego $j\}$,
$D(w)=\{k:1\le k\le n$ oraz $w^{(k)}>u^{(j)}$ dla pewnego $j\}$.

Skorzystamy z prostego faktu: Jeśli $D(u)=[1..n]$ lub $D(w)=[1..n]$, to $u,w$ nie są równoważne.

Poprawność algorytmu wynika teraz z tego, że po każdej głównej iteracji zachodzi niezmiennik:

$D(w)\supseteq [1..i]$\ oraz \ $D(u)\supseteq [1..j]$.

----------------------------------------------------------------------

Zadanie 5

Dla jakich tekstów algorytm na cykliczną równoważność słów wykonuje maksymalną liczbę porównan symboli

Rozwiązanie

Dla tekstów postaci $1^{*}201,1^{*}20$ o tej samej długości.

----------------------------------------------------------------------

Zadanie 6

Mamy zbiór słów, każde długości dwa, obliczyć długość minimalnego tekstu który zawiera wszystkie słowa.

Rozwiązanie

Wezmy graf, węzłami są litery, słowa wejściowe odpowiadają krawędziom. Wystarczy znalezć minimalną liczbę krawędzi które trzeba dołożyć do grafu by miał on ścieżkę Eulera.

----------------------------------------------------------------------

Zadanie ? ???????

Rozwiązanie

????????????.

----------------------------------------------------------------------

Zadanie ?

???????

Rozwiązanie

????????????.