ASD Ćwiczenia 13

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zadanie 1

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

Rozwiązanie


Zadanie 2

Udowodnij, że w wersji on-line algorytmu KMP mamy

Rozwiązanie



Zadanie 3

Udowodnij, że w wersji on-line algorytmu KMP mamy

Rozwiązanie



Zadanie 4

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

Rozwiązanie



Zadanie 5

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


Lemat [Lemat o okresowości]

Jeśli x ma okresy p, q oraz , to jest również okresem x.


Rozwiązanie


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 , to jest również okresem x.

Rozwiązanie

Zadanie 7

Udowdnij poprawność algorytmu KMP realtime

Rozwiązanie

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)

Rozwiązanie

Zadanie 9

Słowa cykliczne (de Bruijna): Słowo binarne w długości dokładnie 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 :=  ; wynik := słowo puste;

3 while istnieje takie, że 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.

Rozwiązanie