ASD Ćwiczenia 13

Zadanie 1

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\ {\textrm {lub}}\ S[i]=S[P[i]].$

Zadanie 2

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

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 (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'_{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

Udowdnij 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

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.

Dygresja Zadnie to było na Olimpiadzie Informatycznej pod nazwą pierowtek 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)$ oznaczanajmnieszy 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 algorytm Euklidesa z odejmowaniem, który liczy nwd(p,q). Zauważmy, żejeś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.