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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Linia 1: Linia 1:
<font color=darkred>
+
=='''Zadanie 1''' ==
'''Zadanie 1''' </font>
 
  
 
Uzasadnić opoprawność algorytmu obliczającego długość najkrótszego słowa pokrywającego dany tekst.
 
Uzasadnić opoprawność algorytmu obliczającego długość najkrótszego słowa pokrywającego dany tekst.
Linia 13: Linia 12:
 
</div>
 
</div>
  
<font color=darkred> ----------------------------------------------------------------------
+
  
'''Zadanie 2''' </font>
+
=='''Zadanie 2''' ==
  
 
Udowodnić, że w wersji on-line algorytmu KMP mamy <math> delay = O(log m)</math>
 
Udowodnić, że w wersji on-line algorytmu KMP mamy <math> delay = O(log m)</math>
Linia 32: Linia 31:
  
  
<font color=darkred> ----------------------------------------------------------------------
+
  
'''Zadanie 3''' </font>
+
=='''Zadanie 3''' ==
  
 
Udowodnić, że w wersji on-line algorytmu KMP mamy <math> delay = \Omega(log m)</math>
 
Udowodnić, że w wersji on-line algorytmu KMP mamy <math> delay = \Omega(log m)</math>
Linia 52: Linia 51:
  
  
<font color=darkred> ----------------------------------------------------------------------
+
  
'''Zadanie 4''' </font>
+
=='''Zadanie 4''' ==
  
 
Udowdnij poprawność algorytmu na cykliczną równoważność słów.
 
Udowdnij poprawność algorytmu na cykliczną równoważność słów.
Linia 78: Linia 77:
 
</div>
 
</div>
  
<font color=darkred> ----------------------------------------------------------------------
+
  
'''Zadanie 5''' </font>
+
===='''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
Linia 91: Linia 90:
 
</div>
 
</div>
  
<font color=darkred> ----------------------------------------------------------------------
+
  
'''Zadanie 6''' </font>
+
=='''Zadanie 6''' ==
  
 
Mamy zbiór słów, każde długości dwa, obliczyć długość minimalnego tekstu który zawiera wszystkie słowa.
 
Mamy zbiór słów, każde długości dwa, obliczyć długość minimalnego tekstu który zawiera wszystkie słowa.
Linia 111: Linia 110:
  
  
<font color=darkred> ----------------------------------------------------------------------
+
  
'''Zadanie 7''' </font>
+
=='''Zadanie 7''' ==
 
Udowodnij  następującą  ciekawą własność kombinatoryczną okresowości w tekstach. Niech <math>nwd(p,q)</math> oznaczanajmnieszy wspólny dzielnik p,q.
 
Udowodnij  następującą  ciekawą własność kombinatoryczną okresowości w tekstach. Niech <math>nwd(p,q)</math> oznaczanajmnieszy wspólny dzielnik p,q.
  
Linia 130: Linia 129:
 
</div>
 
</div>
  
<font color=darkred> ----------------------------------------------------------------------
+
  
'''Zadanie 8''' </font>
+
=='''Zadanie 8''' ==
  
 
Lemat o okresowości  można wzmocnić osłabiając założenia. Udowodnij następujący lemat.
 
Lemat o okresowości  można wzmocnić osłabiając założenia. Udowodnij następujący lemat.

Wersja z 11:38, 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