Tekst źródłowy strony ASD Ćwiczenia 13

=='''Zadanie 1''' ==

Uzasadnić opoprawność algorytmu obliczającego długość najkrótszego słowa pokrywającego dany tekst.
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Rozwiązanie

<div class="mw-collapsible-content" style="display:none">
Niech <math>S[i]</math>
będzie rozmiarem minimalnego pokrywajćego słowa dla prefiksu <math>x[1..i]</math>. Poprawność wynika z następującego 
faktu: \ <math>S[i]=i \ \textrm{lub}\ S[i]=S[P[i]].</math> 
</div>
</div>

 

=='''Zadanie 2''' ==

Udowodnić, że w wersji on-line algorytmu KMP mamy <math> delay = O(log m)</math>

<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Rozwiązanie

<div class="mw-collapsible-content" style="display:none">
Wystarczy wykazać, że  

<math> P'[i]=j,\ P'[j]=k>0\ \Rightarrow \ i\ge k+j </math>

Fakt ten wynika z lematu o okresowości i z definicji tablicy P'.
 </div>
</div>


 

=='''Zadanie 3''' ==

Udowodnić, że w wersji on-line algorytmu KMP mamy <math> delay = \Omega(log m)</math>

<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Rozwiązanie

<div class="mw-collapsible-content" style="display:none">
Słowa Fibonacciego definiujemy następująco:
<center><math>F_0=a,\ F_1=ab,\ F_{n+1}\ =\ F_n\cdot F_{n-1}</math></center>

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>. 
 </div>
</div>


 

=='''Zadanie 4''' ==

Udowdnij poprawność algorytmu na cykliczną równoważność słów.

<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Rozwiązanie

<div class="mw-collapsible-content" style="display:none">

Zdefiniujmy:
<center>
<math>D(u)=\{k:1\leq k\leq n</math> oraz <math>u^{(k)}>w^{(j)}</math> dla pewnego <math>j\}</math>,<br>
<math>D(w)=\{k:1\leq k\leq n</math> oraz <math>w^{(k)}>u^{(j)}</math> dla pewnego <math>j\}</math>.
</center>

Skorzystamy z prostego faktu:
Jeśli <math>D(u)=[1.. n]</math> lub <math>D(w)=[1.. n]</math>, to <math>u,w</math> nie są równoważne. 
 Poprawność algorytmu wynika teraz z tego, że po każdej głównej iteracji zachodzi niezmiennik:
<center>
<math>D(w)\supseteq [1.. i]</math>\ oraz \ <math>D(u)\supseteq [1.. j]</math>.</center>

 </div>
</div>

 

===='''Zadanie 5''' ==

Dla jakich tekstów algorytm na cykliczną równoważność słów wykonuje maksymalną liczbę porównan symboli
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Rozwiązanie

<div class="mw-collapsible-content" style="display:none">
Dla tekstów postaci <math> 1^*201,\ 1^*20 </math> o tej samej długości.
 </div>
</div>

 

=='''Zadanie 6''' ==

Mamy zbiór słów, każde długości dwa, obliczyć długość minimalnego tekstu który zawiera wszystkie słowa.

<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Rozwiązanie

<div class="mw-collapsible-content" style="display:none">
Wezmy graf, węzłami są litery, słowa wejściowe odpowiadają krawędziom.
Wystarczy znalezć minimalną liczbę krawędzi które trzeba dołożyć do grafu by miał on
ścieżkę Eulera. 

'''Dygresja'''  Zadnie to było na Olimpiadzie Informatycznej pod nazwą ''pierowtek abstrakcyjny''.
Ciekawe jest to, że problem robi się NP-zupełny gdy wszytkie słowa wejściowe mają długość 3.
 </div>
</div>


 

=='''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.


{{lemat|[Lemat o okresowości]|lemat_o_okresowosci|
Jeśli x ma okresy p, q oraz <math>p+q \le |x|</math> to <math>nwd(p,q)</math> jest również okresem x. 
}}


<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Rozwiązanie

<div class="mw-collapsible-content" style="display:none">
Lemat ten wynika z poprawności algorytm Euklidesa z odejmowaniem, który liczy nwd(p,q). Zauważmy, żejeśli <math>p>q</math> są okresami to p-q też jest okresem. 
 </div>
</div>

 

=='''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]|silny_lemat_o_okresowosci|
Jeśli x ma okresy p, q oraz <math>p+q \le |x|+nwd(p,q)</math> to <math>nwd(p,q)</math> jest również okresem x. 
}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Rozwiązanie

<div class="mw-collapsible-content" style="display:none">
Indukcja ze względu na p+q.
 </div>
</div>