ASD Ćwiczenia 13

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zadanie 1

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

Rozwiązanie


Zadanie 2

Udowodnić, że w wersji on-line algorytmu KMP mamy

Rozwiązanie



Zadanie 3

Udowodnić, że w wersji on-line algorytmu KMP mamy

Rozwiązanie



Zadanie 4

Udowdnij poprawność algorytmu na cykliczną równoważność słów.

Rozwiązanie


Zadanie 5

Dla jakich tekstów algorytm na cykliczną równoważność słów wykonuje maksymalną liczbę porównan symboli

Rozwiązanie

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



Zadanie 7

Udowodnij następującą ciekawą własność kombinatoryczną okresowości w tekstach. Niech oznaczanajmnieszy 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 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 to jest również okresem x.

Rozwiązanie