ASD Ćwiczenia 13: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 79: Linia 79:
 
   
 
   
  
==='''Zadanie 5''' ==
+
=='''Zadanie 5''' ==
  
 
Dla jakich tekstów algorytm na cykliczną równoważność słów wykonuje maksymalną liczbę porównan symboli
 
Dla jakich tekstów algorytm na cykliczną równoważność słów wykonuje maksymalną liczbę porównan symboli

Wersja z 11:39, 11 wrz 2006

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