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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
Linia 1: Linia 1:
 
=='''Zadanie 1''' ==
 
=='''Zadanie 1''' ==
  
Uzasadnić poprawność algorytmu obliczającego długość najkrótszego słowa pokrywającego dany tekst.
+
Uzasadnij poprawność algorytmu obliczającego długość najkrótszego słowa pokrywającego dany tekst.
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
Rozwiązanie
 
Rozwiązanie
Linia 16: Linia 16:
 
=='''Zadanie 2''' ==
 
=='''Zadanie 2''' ==
  
Udowodnić, że w wersji on-line algorytmu KMP mamy <math> delay = O(\log m)</math>
+
Udowodnij, że w wersji on-line algorytmu KMP mamy <math> delay = O(\log m)</math>
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Linia 35: Linia 35:
 
=='''Zadanie 3''' ==
 
=='''Zadanie 3''' ==
  
Udowodnić, że w wersji on-line algorytmu KMP mamy <math> delay = \Omega(\log m)</math>
+
Udowodnij, że w wersji on-line algorytmu KMP mamy <math> delay = \Omega(\log m)</math>
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Linia 103: Linia 103:
  
 
'''Dygresja'''  Zadanie to było na Olimpiadzie Informatycznej pod nazwą ''pierwotek abstrakcyjny''.
 
'''Dygresja'''  Zadanie to było na Olimpiadzie Informatycznej pod nazwą ''pierwotek abstrakcyjny''.
Ciekawe jest to, że problem robi się NP-zupełny gdy wszytkie słowa wejściowe mają długość 3.
+
Ciekawe jest to, że problem robi się NP-zupełny, gdy wszytkie słowa wejściowe mają długość 3.
 
  </div>
 
  </div>
 
</div>
 
</div>
Linia 153: Linia 153:
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
 
Problem jaki musimy rozwiązać to właściwość algorytmu, którą nazwiemy
 
Problem jaki musimy rozwiązać to właściwość algorytmu, którą nazwiemy
''opóżnieniem'' polega ona na tym, że w danym kroku algorytm może wciąż
+
''opóżnieniem''. Polega ona na tym, że w danym kroku algorytm może wciąż
jeszcze rozważać właściwy prefiks aktualnego slowa i nie dotrzeć w ogóle
+
jeszcze rozważać właściwy prefiks aktualnego słowa i nie dotrzeć w ogóle
 
do rozważenia bieżącej litery. Pokażemy jednak, że w momencie, kiedy nastąpi
 
do rozważenia bieżącej litery. Pokażemy jednak, że w momencie, kiedy nastąpi
 
wystąpienie wzorca, kolejka zostanie opróżniona, co wystarczy do
 
wystąpienie wzorca, kolejka zostanie opróżniona, co wystarczy do
Linia 187: Linia 187:
  
 
Mogą nastąpić dwie instrukcje powiększające <math>j</math> o <math>1</math>.
 
Mogą nastąpić dwie instrukcje powiększające <math>j</math> o <math>1</math>.
Wówczas <math>|Kolejka|</math> maleje o <math>2</math>, <math>m-j</math> także maleje o <math>2</math>, zatem niezmien
+
Wówczas <math>|Kolejka|</math> maleje o <math>2</math>, <math>m-j</math> także maleje o <math>2</math>, zatem niezmiennik pozostaje zachowany.
nik pozostaje zachowany.
 
  
  

Wersja z 21:33, 3 gru 2006

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

Udowodnij 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 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 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

Zadanie 9

Udowdnij poprawność algorytmu KMP realtime

Rozwiązanie