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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
m (Zastępowanie tekstu - "\ =\" na "=")
 
(Nie pokazano 15 wersji utworzonych przez 2 użytkowników)
Linia 8: Linia 8:
 
Niech <math>S[i]</math>
 
Niech <math>S[i]</math>
 
będzie rozmiarem minimalnego pokrywającego 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 \ \text{lub}\ S[i]=S[P[i]].</math>  
 
</div>
 
</div>
 
</div>
 
</div>
Linia 25: Linia 25:
  
 
<math> P'[i]=j,\ P'[j]=k>0\ \Rightarrow \ i\ge k+j </math>
 
<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'.
 
Fakt ten wynika z lematu o okresowości i z definicji tablicy P'.
 
  </div>
 
  </div>
Linia 42: Linia 41:
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
 
Słowa Fibonacciego definiujemy następująco:
 
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>
+
<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>
 
Na przykład: <math>F_3=abaab,\ F_4=abaababa,\ F_5=abaababaabaab.</math>
Linia 51: Linia 50:
  
  
+
 
  
 
=='''Zadanie 4''' ==
 
=='''Zadanie 4''' ==
 
Udowodnij 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.
 
Mamy zbiór słów, każde długości dwa, obliczyć długość minimalnego tekstu który zawiera wszystkie słowa.
Linia 110: Linia 72:
 
   
 
   
  
=='''Zadanie 7''' ==
+
=='''Zadanie 5''' ==
 
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 129: Linia 91:
 
   
 
   
  
=='''Zadanie 8''' ==
+
=='''Zadanie 6''' ==
  
 
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.
Linia 145: Linia 107:
 
</div>
 
</div>
  
=='''Zadanie 9''' ==
+
=='''Zadanie 7''' ==
  
 
Udowdnij poprawność  algorytmu KMP realtime
 
Udowdnij poprawność  algorytmu KMP realtime
Linia 204: Linia 166:
  
 
''(Rozwiązanie opracował Jakub Radoszewski)''
 
''(Rozwiązanie opracował Jakub Radoszewski)''
 +
</div>
 +
</div>
 +
 +
=='''Zadanie 8''' ==
 +
 +
Przprowadź dokładny dowód tego, że algorytm Oszczędny KMP wykonuje co najwyżej 3/2 n porównań
 +
(schemat dowodu był już opisany w odpowiednim module)
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
Rozwiązanie
 +
 +
<div class="mw-collapsible-content" style="display:none">
 +
<br>
 +
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>
 +
 +
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>
 +
 +
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>
 +
 +
Czyli każde porównanie z szufladki <math> B</math>  przesuwa aktualny 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>
 +
 +
=='''Zadanie 9''' ==
 +
 +
Słowa cykliczne (de Bruijna):
 +
Słowo binarne w długości dokładnie <math> 2^n </math> nazwiemy cyklicznym (słowem de Bruijna, który to wymyślił) rzędu n gdy każde słowo binarne długości n jest podsłowem słowa ww.
 +
 +
Następujący algorytm generuje takie słowo, co więcej jest ono leksykograficznie pierwsze spośród wszystkich możliwych
 +
 +
Niech Cutfirst(x) oznacza obciecie x o pierwszy symbol, a Append(x,b) dopisanie litery b do słowa x na końcu.
 +
 +
 +
Algorytm Słowa-Cykliczne
 +
 +
1  x := 1111..1 (n jedynek);
 +
 +
2  Z := <math>\emptyset</math> ; wynik :=  słowo puste;
 +
 +
3  while istnieje <math>b \in \{0,1\}</math> takie, że <math>Append(Cutfirst(x),b)\notin  Z</math>  do
 +
 +
4    wybierz minimalne takie b ;
 +
 +
5    Append(Cutfirst(x),b); 
 +
 +
6    insert(x,Z) ; 
 +
 +
7    Append(wynik,b);
 +
 +
 +
Na przykład dla n=3 wynik = 00010111, a dla n=2 wynik = 0011
 +
 +
 +
Udowodnij poprawność algorytmu.
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
Rozwiązanie
 +
 +
<div class="mw-collapsible-content" style="display:none">
 +
Zadanie ma to związek z pewną metodą konstrukcji cyklu Eulera, chociaż zadanie pozornie wydaje się nie mieć nic wspólnego z grafami.
 +
Mamy tu do czynienia z grafem ktorego węzłami są wszystkie słowa binarne długości n-1.
 +
 +
Istnieje krawędż u \rightarrow v o etykieci a, gdy Append(Cutfirst(u),a)=v.
 +
 +
Ciąg operacji w algorytmie Słowa-Cykliczne odpowiada zachłannej ścieżce Eulera która startuje z węzła <math>1^{n-1}</math>. patrz zadania w module Algorytmy grafowe.
 +
 
</div>
 
</div>
 
</div>
 
</div>

Aktualna wersja na dzień 12:51, 9 cze 2020

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

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 5

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 6

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 7

Udowdnij poprawność algorytmu KMP realtime

Rozwiązanie

Zadanie 8

Przprowadź dokładny dowód tego, że algorytm Oszczędny KMP wykonuje co najwyżej 3/2 n porównań (schemat dowodu był już opisany w odpowiednim module)

Rozwiązanie

Zadanie 9

Słowa cykliczne (de Bruijna): Słowo binarne w długości dokładnie nazwiemy cyklicznym (słowem de Bruijna, który to wymyślił) rzędu n gdy każde słowo binarne długości n jest podsłowem słowa ww.

Następujący algorytm generuje takie słowo, co więcej jest ono leksykograficznie pierwsze spośród wszystkich możliwych

Niech Cutfirst(x) oznacza obciecie x o pierwszy symbol, a Append(x,b) dopisanie litery b do słowa x na końcu.


Algorytm Słowa-Cykliczne

1 x := 1111..1 (n jedynek);

2 Z :=  ; wynik := słowo puste;

3 while istnieje takie, że do

4 wybierz minimalne takie b ;

5 Append(Cutfirst(x),b);

6 insert(x,Z) ;

7 Append(wynik,b);


Na przykład dla n=3 wynik = 00010111, a dla n=2 wynik = 0011


Udowodnij poprawność algorytmu.

Rozwiązanie