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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
Linia 46: Linia 46:
 
Na przykład: <math>F_3=abaab,\ F_4=abaababa,\ F_5=abaababaabaab.</math>
 
Na przykład: <math>F_3=abaab,\ F_4=abaababa,\ F_5=abaababaabaab.</math>
  
Niech <math>F'_n</math> oznacza słowo Fibonacciego z obciętymi ostatnimi dwoma symbolami. Jeśli jako wzorzec weżmiemy słowo Fibonacciego <math>F_n</math>, a jako tekst słowo <math>F'_ncc</math> to przy wczytywaniu <math>|F_n-1|</math>-ego symbolu algorytm ma opóżnienie logarytmiczne, iterujemy <math>\Omega(\log n)</math> razy operację: <math>j:=P'[j]</math>.  
+
Niech <math>F'_n</math> oznacza słowo Fibonacciego z obciętymi ostatnimi dwoma symbolami. Jeśli jako wzorzec weźmiemy słowo Fibonacciego <math>F_n</math>, a jako tekst słowo <math>F'_ncc</math> to przy wczytywaniu <math>|F_n-1|</math>-ego symbolu algorytm ma opóżnienie logarytmiczne, iterujemy <math>\Omega(\log n)</math> razy operację: <math>j:=P'[j]</math>.  
 
  </div>
 
  </div>
 
</div>
 
</div>
Linia 99: Linia 99:
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
 
Weźmy graf, którego węzłami są litery, a słowa wejściowe odpowiadają krawędziom.
 
Weźmy graf, którego węzłami są litery, a słowa wejściowe odpowiadają krawędziom.
Wystarczy znalezć minimalną liczbę krawędzi które trzeba dołożyć do grafu by miał on
+
Wystarczy znalezć minimalną liczbę krawędzi, które trzeba dołożyć do grafu, by miał on
 
ścieżkę Eulera.  
 
ścieżkę Eulera.  
  
Linia 111: Linia 111:
  
 
=='''Zadanie 7''' ==
 
=='''Zadanie 7''' ==
Udowodnij następującą ciekawą własność kombinatoryczną okresowości w tekstach. Niech <math>nwd(p,q)</math> oznacza najmniejszy wspólny dzielnik p,q.
+
Udowodnij następującą ciekawą własność kombinatoryczną okresowości w tekstach. Niech <math>nwd(p,q)</math> oznacza najmniejszy wspólny dzielnik p,q.
  
  
Linia 131: Linia 131:
 
=='''Zadanie 8''' ==
 
=='''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.
  
 
{{lemat|[Silny lemat o okresowości]|silny_lemat_o_okresowosci|
 
{{lemat|[Silny lemat o okresowości]|silny_lemat_o_okresowosci|

Wersja z 13:47, 30 wrz 2006

Zadanie 1

Uzasadnić poprawność 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

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