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ć opoprawność algorytmu obliczającego długość najkrótszego słowa pokrywającego dany tekst.
+
Uzasadnić 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 7: Linia 7:
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
 
Niech <math>S[i]</math>
 
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  
+
będzie rozmiarem minimalnego pokrywającego 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>  
 
faktu: \ <math>S[i]=i \ \textrm{lub}\ S[i]=S[P[i]].</math>  
 
</div>
 
</div>
Linia 16: Linia 16:
 
=='''Zadanie 2''' ==
 
=='''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>
  
 
<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>
+
Udowodnić, ż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 55: Linia 55:
 
=='''Zadanie 4''' ==
 
=='''Zadanie 4''' ==
  
Udowdnij poprawność algorytmu na cykliczną równoważność słów.
+
Udowodnij poprawność algorytmu na cykliczną równoważność słów.
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Linia 81: Linia 81:
 
=='''Zadanie 5''' ==
 
=='''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?
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
Rozwiązanie
 
Rozwiązanie
Linia 98: Linia 98:
  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
Wezmy graf, węzłami są litery, 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.  
  
'''Dygresja'''  Zadnie to było na Olimpiadzie Informatycznej pod nazwą ''pierowtek 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>
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> oznaczanajmnieszy 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.
  
  
 
{{lemat|[Lemat o okresowości]|lemat_o_okresowosci|
 
{{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.  
+
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.  
 
}}
 
}}
  
Linia 123: Linia 123:
  
 
<div class="mw-collapsible-content" style="display:none">
 
<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.  
+
Lemat ten wynika z poprawności algorytmu Euklidesa z odejmowaniem, który oblicza nwd(p,q). Zauważmy, że jeśli <math>p>q</math> są okresami, to p-q też jest okresem.  
 
  </div>
 
  </div>
 
</div>
 
</div>
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|
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.  
+
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.  
 
}}
 
}}
  

Wersja z 15:09, 26 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