Ćwiczenia

Zadanie 1

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

Zadanie 2

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

Zadanie 3

Udowodnij, że w wersji on-line algorytmu KMP mamy \( delay = \Omega(\log m) \)

Zadanie 4

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

Zadanie 5

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 \le |x| \), to \( nwd(p,q) \) jest również okresem x.

Zadanie 6

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 \le |x|+nwd(p,q) \), to \( nwd(p,q) \) jest również okresem x.

Zadanie 7

Udowdnij poprawność algorytmu KMP realtime

Zadanie 8

Przprowadź dokładny dowód tego, że algorytm Oszczędny KMP wykonuje co najwyżej 3/2 n porównań (schemat dowodu był już opisany w odpowiednim module)

Zadanie 9

Słowa cykliczne (de Bruijna): Słowo binarne w długości dokładnie \( 2^n \) nazwiemy cyklicznym (słowem de Bruijna, który to wymyślił) rzędu n gdy każde słowo binarne długości n jest podsłowem słowa ww.
Następujący algorytm generuje takie słowo, co więcej jest ono leksykograficznie pierwsze spośród wszystkich możliwych
Niech Cutfirst(x) oznacza obciecie x o pierwszy symbol, a Append(x,b) dopisanie litery b do słowa x na końcu.

Algorytm Słowa-Cykliczne
1 x := 1111..1 (n jedynek);
2 Z := \( \emptyset \) ; wynik := słowo puste;
3 while istnieje \( b \in \{0,1\} \) takie, że \( Append(Cutfirst(x),b)\notin Z \) do
4 wybierz minimalne takie b ;
5 Append(Cutfirst(x),b);
6 insert(x,Z) ;
7 Append(wynik,b);

Na przykład dla n=3 wynik = 00010111, a dla n=2 wynik = 0011

Udowodnij poprawność algorytmu.