ASD Ćwiczenia 13

Zadanie 1

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

Rozwiązanie

Niech $S[i]$ będzie rozmiarem minimalnego pokrywającego słowa dla prefiksu $x[1..i]$. Poprawność wynika z następującego faktu: \ $S[i]=i\ {\textrm {lub}}\ S[i]=S[P[i]].$

Zadanie 2

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

Rozwiązanie

Wystarczy wykazać, że

$P'[i]=j,\ P'[j]=k>0\ \Rightarrow \ i\geq 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=\Omega (\log m)$

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'_{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'_{n}cc$ to przy wczytywaniu $|F_{n}-1|$-ego symbolu algorytm ma opóżnienie logarytmiczne, iterujemy $\Omega (\log n)$ razy operację: $j:=P'[j]$.

Zadanie 4

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

Rozwiązanie

Zdefiniujmy:

$D(u)=\{k:1\leq k\leq n$ oraz $u^{(k)}>w^{(j)}$ dla pewnego $j\}$,
$D(w)=\{k:1\leq k\leq 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

Weźmy graf, którego węzłami są litery, a 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.

Dygresja Zadanie to było na Olimpiadzie Informatycznej pod nazwą pierwotek abstrakcyjny. Ciekawe jest to, że problem robi się NP-zupełny gdy wszytkie słowa wejściowe mają długość 3.

Zadanie 7

Udowodnij następującą ciekawą własność kombinatoryczną okresowości w tekstach. Niech $nwd(p,q)$ oznacza najmniejszy wspólny dzielnik p,q.

Lemat [Lemat o okresowości]

Jeśli x ma okresy p, q oraz $p+q\leq |x|$, to $nwd(p,q)$ jest również okresem x.

Rozwiązanie

Lemat ten wynika z poprawności algorytmu Euklidesa z odejmowaniem, który oblicza nwd(p,q). Zauważmy, że jeśli $p>q$ są okresami, to p-q też jest okresem.

Zadanie 8

Lemat o okresowości można wzmocnić, osłabiając założenia. Udowodnij następujący lemat.

Lemat [Silny lemat o okresowości]

Jeśli x ma okresy p, q oraz $p+q\leq |x|+nwd(p,q)$, to $nwd(p,q)$ jest również okresem x.

Rozwiązanie

Indukcja ze względu na p+q.