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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
Linia 204: Linia 204:
  
 
''(Rozwiązanie opracował Jakub Radoszewski)''
 
''(Rozwiązanie opracował Jakub Radoszewski)''
 +
</div>
 +
</div>
 +
 +
=='''Zadanie 9''' ==
 +
 +
Udowdnij że algorytm Oszczędny KMP wykonuje co najwyżej 3/2 n porównań
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
Rozwiązanie
 +
 +
<div class="mw-collapsible-content" style="display:none">
 +
 +
By wykazać, że algorytm Oszczędny-MP wykonuje co najwyżej <math> \frac{3}{2}n</math> 
 +
porównań, pogrupujemy te porównania w dwie szufladki: <math> A</math>  i <math> B</math> . Pokażemy, że
 +
w szufladce <math> A</math>  będzie co najwyżej <math> n</math>  porównań, a w szufladce <math> B</math>  co najwyżej
 +
<math> \frac{n}{2}</math>  porównań.
 +
 +
Do szufladki <math> A</math>  wrzucamy:
 +
 +
<br>
 +
Wszystkie udane porównania dokonane w trakcie szukania wzorca <math> x'</math> .
 +
 +
<br>
 +
Wszystkie nieudane porównania pierwszej litery wzorca <math> x'</math>  (czyli litery
 +
<math> b</math> ), dokonane w trakcie szukania wzorca <math> x'</math> .
 +
 +
<br> Wszystkie porównania początkowych liter <math> a</math> , za wyjątkiem porównań
 +
na tych pozycjach, gdzie wcześniej szukaliśmy litery <math> b</math>  --- pierwszej litery
 +
wzorca <math> x'</math>  --- i nie znaleźliśmy jej.
 +
<br><br>
 +
 +
Do szufladki <math> B</math>  wrzucamy wszystkie pozostałe porównania, czyli:
 +
 +
 +
<br>
 +
Wszystkie nieudane porównania dokonane w trakcie szukania wzorca <math> x'</math> ,
 +
za wyjątkiem nieudanych porównań pierwszej litery; są to nieudane porównania
 +
dokonywane w momencie, gdy znaleźliśmy już jakiś niepusty prefiks <math> x'</math> .
 +
 +
 +
<br> Porównania początkowych liter <math> a</math>  na tych pozycjach, gdzie wcześniej
 +
szukaliśmy litery <math> b</math>  i nie znaleźliśmy jej.
 +
<br><br>
 +
 +
 +
Zauważmy, że w algorytmie MP pozycje tekstu, na których nigdy nie było
 +
żadnego udanego porównania to dokładnie te pozycje, na których nie udało
 +
się znaleźć pierwszej litery wzorca (lub pozycja jest pod sam koniec tekstu
 +
i nie ma już szans na znalezienie wzorca, algorytm już się zakończył).
 +
Dodatkowo, zarówno algorytm MP jak i algorytm Oszczędny-MP ma taką właściwość,
 +
że jeśli na pewnej pozycji tekstu było udane porównanie, to ta pozycja
 +
tekstu już nigdy nie będzie porównywana --- o niej ,,wiemy już wszystko''.
 +
W związku z tym każde porównanie z szufladki <math> A</math>  wykonuje się na innej
 +
literze tekstu, czyli tych porównań jest co najwyżej <math> n</math> .
 +
 +
Spójrzmy teraz, jak zmienia się wskaźnik, na jakiej pozycji szukamy teraz
 +
wzorca <math> x</math> . Zauważmy, że prefikso-sufiks słowa <math> x[1\ldots s]</math>  dla <math> s > k</math>
 +
jest długości co najwyżej <math> s - k - 1</math>  --- litery <math> a</math>  tego prefikso-sufiksu
 +
muszą się zaczynać za literą <math> b</math>  na pozycji <math> k+1</math> . W związku z tym
 +
w momencie nieudanego porównania, które wystąpiło
 +
gdy znaleziony już został niepusty prefiks słowa <math> x'</math> , wskaźnik ,,gdzie
 +
teraz szukamy'' przesuwa się o conajmniej <math> k+1</math> . Tak też jest,
 +
gdy znajdziemy całe słowo <math> x'</math>  --- przesuwamy się do prefikso-sufiksu
 +
słowa <math> x</math> . Dodatkowo, każde nieudane porównanie litery <math> b</math>  z pozycji
 +
<math> k+1</math>  w słowie <math> x</math>  przesuwa wskaźnik o jeden.
 +
 +
W związku z tym:
 +
 +
 +
<br>
 +
Porównania z szufladki <math> B</math> , podpunkt <math> 1</math>  przesuwają wskaźnik o conajmniej
 +
<math> k+1 \geq 2</math> .
 +
 +
 +
<br>
 +
Po co najwyżej <math> k</math>  porównaniach z szufladki <math> B</math> , podpunkt <math> 2</math>  wskaźnik
 +
przesunie się o conajmniej <math> k+1</math> . Dodatkowo, każde takie porównanie oznacza,
 +
że wcześniej na tym miejscu było nieudane porównanie litery <math> b</math> . Wliczając
 +
przesunięcia pochodzące od tych porównań otrzymujemy, że
 +
wskaźnik przesunął się o conajmniej <math> k+1+L \geq 2L</math> , gdzie <math> L</math>  to liczba
 +
takich porównań liter <math> a</math>  w jednej próbie znalezienia wzorca <math> x</math> .
 +
<br><br>
 +
 +
 +
Czyli każde porównanie z szufladki <math> B</math>  przesuwa wskaźnik ,,gdzie teraz
 +
szukamy'' o conajmniej <math> 2</math> , czyli tych porównań jest nie więcej niż
 +
<math> \frac{n}{2}</math> .
 +
 +
 +
 +
''(Rozwiązanie opracował Marcin Pilipczuk)''
 
</div>
 
</div>
 
</div>
 
</div>

Wersja z 17:29, 18 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

Zadanie 9

Udowdnij że algorytm Oszczędny KMP wykonuje co najwyżej 3/2 n porównań

Rozwiązanie