ASD Ćwiczenia 13

Zadanie 1

Uzasadnij 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

Udowodnij, ż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

Udowodnij, ż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.

Zadanie 9

Udowdnij poprawność algorytmu KMP realtime

Rozwiązanie

Problem jaki musimy rozwiązać to właściwość algorytmu, którą nazwiemy opóżnieniem. Polega ona na tym, że w danym kroku algorytm może wciąż jeszcze rozważać właściwy prefiks aktualnego słowa i nie dotrzeć w ogóle do rozważenia bieżącej litery. Pokażemy jednak, że w momencie, kiedy nastąpi wystąpienie wzorca, kolejka zostanie opróżniona, co wystarczy do dowodu poprawności algorytmu.

Dowód przeprowadzimy nie wprost - załóżmy, że w tym kroku kolejka się nie opróżni i że jest to pierwsze wystąpienie wzorca, którego algorytm nie zdąża wyśledzić. Zacznijmy rozważanie działania algorytmu od ostatniego miejsca wcześniejszego od bieżącego, w którym kolejka się opróżnia. W tym momencie zachodzi $j<m$ (nawet jeżeli w owym kroku było wystąpienie wzorca w tekście, to ten warunek i tak będzie po tym kroku spełniony) oraz $|Kolejka|=0$. Pokażemy, że odtąd aż do miejsca wystąpienia wzorca zachodzić będzie niezmiennik

$|Kolejka|<m-j.$

Faktycznie, zastanówmy się co się może wydarzyć w dowolnym, kolejnym kroku algorytmu, a co może zmienić wartość zmiennej $j$:

Może być dwukrotnie wywołana instrukcja $j:=P[j]$. Wówczas $|Kolejka|$ wzrasta o $1$, $m-j$ wzrasta co najmniej o $2$, czyli niezmiennik dalej zachodzi.

Moze być raz wywołana instrukcja $j:=P[j]$, a raz $j:=j+1$ (w jakiejkolwiek kolejności). Wówczas $|Kolejka|$ się nie zmienia, $m-j$ pozostaje bez zmian lub wzrasta, co nie zaburza niezmiennika.

Mogą nastąpić dwie instrukcje powiększające $j$ o $1$. Wówczas $|Kolejka|$ maleje o $2$, $m-j$ także maleje o $2$, zatem niezmiennik pozostaje zachowany.

Kolejka \textit{nie} może się opróżnić, gdyż zakładamy, że to nie nastąpi przed aktualnie rozważanym wystąpieniem wzorca. Instrukcja $j:=P[m]$ również nie może wystąpić, ponieważ oznaczałoby to wcześniejsze od rozważanego niezauważone przez algorytm wystąpienie wzorca w tekście.

Zatem niezmiennik jest zachowany od ostatniego momentu opróżnienia kolejki do momentu niezauważonego wystąpienia wzorca. W chwili przetworzenia literki, która powoduje wystąpienie zachodzi $j=m$, czyli na mocy pokazanego niezmiennika $|Kolejka|<m-m=0$, $|Kolejka|<0$. To z kolei daje żądaną sprzeczność.

(Rozwiązanie opracował Jakub Radoszewski)