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)

Zadanie 9

Udowdnij że algorytm Oszczędny KMP wykonuje co najwyżej 3/2 n porównań

Rozwiązanie

By wykazać, że algorytm Oszczędny-MP wykonuje co najwyżej ${\frac {3}{2}}n$ porównań, pogrupujemy te porównania w dwie szufladki: $A$ i $B$ . Pokażemy, że w szufladce $A$ będzie co najwyżej $n$ porównań, a w szufladce $B$ co najwyżej ${\frac {n}{2}}$ porównań.

Do szufladki $A$ wrzucamy:

Wszystkie udane porównania dokonane w trakcie szukania wzorca $x'$ .

Wszystkie nieudane porównania pierwszej litery wzorca $x'$ (czyli litery $b$ ), dokonane w trakcie szukania wzorca $x'$ .

Wszystkie porównania początkowych liter $a$ , za wyjątkiem porównań na tych pozycjach, gdzie wcześniej szukaliśmy litery $b$ --- pierwszej litery wzorca $x'$ --- i nie znaleźliśmy jej.

Do szufladki $B$ wrzucamy wszystkie pozostałe porównania, czyli:

Wszystkie nieudane porównania dokonane w trakcie szukania wzorca $x'$ , za wyjątkiem nieudanych porównań pierwszej litery; są to nieudane porównania dokonywane w momencie, gdy znaleźliśmy już jakiś niepusty prefiks $x'$ .

Porównania początkowych liter $a$ na tych pozycjach, gdzie wcześniej szukaliśmy litery $b$ i nie znaleźliśmy jej.

Zauważmy, że w algorytmie MP pozycje tekstu, na których nigdy nie było żadnego udanego porównania to dokładnie te pozycje, na których nie udało się znaleźć pierwszej litery wzorca (lub pozycja jest pod sam koniec tekstu i nie ma już szans na znalezienie wzorca, algorytm już się zakończył). Dodatkowo, zarówno algorytm MP jak i algorytm Oszczędny-MP ma taką właściwość, że jeśli na pewnej pozycji tekstu było udane porównanie, to ta pozycja tekstu już nigdy nie będzie porównywana --- o niej ,,wiemy już wszystko. W związku z tym każde porównanie z szufladki $A$ wykonuje się na innej literze tekstu, czyli tych porównań jest co najwyżej $n$ .

Spójrzmy teraz, jak zmienia się wskaźnik, na jakiej pozycji szukamy teraz wzorca $x$ . Zauważmy, że prefikso-sufiks słowa $x[1\ldots s]$ dla $s>k$ jest długości co najwyżej $s-k-1$ --- litery $a$ tego prefikso-sufiksu muszą się zaczynać za literą $b$ na pozycji $k+1$ . W związku z tym w momencie nieudanego porównania, które wystąpiło gdy znaleziony już został niepusty prefiks słowa $x'$ , wskaźnik ,,gdzie teraz szukamy przesuwa się o conajmniej $k+1$ . Tak też jest, gdy znajdziemy całe słowo $x'$ --- przesuwamy się do prefikso-sufiksu słowa $x$ . Dodatkowo, każde nieudane porównanie litery $b$ z pozycji $k+1$ w słowie $x$ przesuwa wskaźnik o jeden.

W związku z tym:

Porównania z szufladki $B$ , podpunkt $1$ przesuwają wskaźnik o conajmniej $k+1\geq 2$ .

Po co najwyżej $k$ porównaniach z szufladki $B$ , podpunkt $2$ wskaźnik przesunie się o conajmniej $k+1$ . Dodatkowo, każde takie porównanie oznacza, że wcześniej na tym miejscu było nieudane porównanie litery $b$ . Wliczając przesunięcia pochodzące od tych porównań otrzymujemy, że wskaźnik przesunął się o conajmniej $k+1+L\geq 2L$ , gdzie $L$ to liczba takich porównań liter $a$ w jednej próbie znalezienia wzorca $x$ .

Czyli każde porównanie z szufladki $B$ przesuwa wskaźnik ,,gdzie teraz szukamy o conajmniej $2$ , czyli tych porównań jest nie więcej niż ${\frac {n}{2}}$ .

(Rozwiązanie opracował Marcin Pilipczuk)