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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
Linia 1: Linia 1:
 
=='''Zadanie 1'''==
 
=='''Zadanie 1'''==
Dane sa teksty x, y, oblicz najdłuższy tekst z (który oznaczamy LCS(x,y) od ang. Longest Common Subword)
+
Dane sa teksty x, y, oblicz najdłuższy tekst <math>z</math> (oznaczany LCS(x,y) od ang. Longest Common Subword),
który jest jednocześnie podsłowem x, y.
+
który jest jednocześnie podsłowem x i y.
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Linia 7: Linia 7:
  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
Konstruujemy drzewo sufiksowe dla tekstu x#y$. nwpodsłowo(x,y) odpowiada węzłowi w drzewie, który  
+
Konstruujemy drzewo sufiksowe dla tekstu x#y$. LCS(x,y) odpowiada węzłowi w drzewie, który  
 
reprezentuje najdłuższe podsłowo, oraz z którego prowadzą ścieżki do liści reprezentujących numer sufiksu zaczynającego
 
reprezentuje najdłuższe podsłowo, oraz z którego prowadzą ścieżki do liści reprezentujących numer sufiksu zaczynającego
się w x, i numer sufiksu zaczynającego się w y. Drzewo trzeba odpowiednio ''przeprocessować'' bottom-up, żeby
+
się w x, i numer sufiksu zaczynającego się w y. Drzewo trzeba odpowiednio ''wstępnie przetworzyć'' bottom-up, żeby
można było potem łatwo wyliczyć odpowiedni węzeł. Podobnie rozwiazujemy dla wiely słów x,y ,.. .
+
można było potem łatwo wyliczyć odpowiedni węzeł. Podobnie rozwiązujemy problem dla wielu słów x,y ,.. .
 
  </div>
 
  </div>
 
</div>
 
</div>
Linia 17: Linia 17:
  
 
Niech <math>lcp</math> będzie tablicą najdłuższych wspólnych prefiksów dla słowa x oraz niech
 
Niech <math>lcp</math> będzie tablicą najdłuższych wspólnych prefiksów dla słowa x oraz niech
<math>SUMA(lcp)</math> będzie sumą elementów tablicy <math>lcp</math>. Uzasadnij dlaczego liczba  
+
<math>SUMA(lcp)</math> będzie sumą elementów tablicy <math>lcp</math>. Uzasadnij, dlaczego liczba  
 
wszystkich niepustych  podsłów x wynosi
 
wszystkich niepustych  podsłów x wynosi
  
Linia 26: Linia 26:
  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
Liczba ta jest równa sumie wag krawędzi drzewa sufiksowego. Wzór z zadania wynika to z konstrukcji drzewa  
+
Liczba ta jest równa sumie wag krawędzi drzewa sufiksowego. Wzór z zadania wynika z konstrukcji drzewa  
sufiksowego opiuerającej się na tablicy sufiksowej i tablicy <math>lcp</math>.  
+
sufiksowego opierającej się na tablicy sufiksowej i tablicy <math>lcp</math>.  
 
  </div>
 
  </div>
 
</div>
 
</div>
Linia 34: Linia 34:
 
=='''Zadanie 3'''==
 
=='''Zadanie 3'''==
  
Policz wzór na <math>|Subwords(F_n)|</math>
+
Wyprowadź wzór na <math>|Subwords(F_n)|</math>
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
Rozwiązanie
 
Rozwiązanie
  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
Oznaczmy <math> Sub(n)=|Subwords(F_n)|</math>, niech <math> \Phi_n</math> będzie n-tą liczba Fibonacciego.
+
Oznaczmy <math> Sub(n)=|Subwords(F_n)|</math> i niech <math> \Phi_n</math> będzie n-tą liczba Fibonacciego.
 
Wtedy
 
Wtedy
  
Linia 59: Linia 59:
  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
Wynika ze struktury tablicy lcp, oraz stąd że kolejno rozważane słow powstają z poprzednich
+
Wynika to ze struktury tablicy lcp oraz z tego, że kolejno rozważane słowa powstają z poprzednich
 
przez obcięcie pierwszej litery.
 
przez obcięcie pierwszej litery.
 
  </div>
 
  </div>
Linia 65: Linia 65:
  
 
=='''Zadanie 5'''==
 
=='''Zadanie 5'''==
Opisz liniowy  algorytm liczący tablicę ROT, zakładając, że mamy liniowy algorytm liczenia tablicy sufiksowej.
+
Opisz liniowy  algorytm obliczania tablicę ROT, przy założeniu, że mamy liniowy algorytm obliczania tablicy sufiksowej.
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
Rozwiązanie
 
Rozwiązanie
  
 
<div class="mw-collapsible-content" style="display:none">
 
<div class="mw-collapsible-content" style="display:none">
Zastosuj algorytm na liczenie tablicy sufiksowej do słowa xx
+
Zastosuj algorytm obliczania tablicy sufiksowej do słowa xx.
 
  </div>
 
  </div>
 
</div>
 
</div>
Linia 76: Linia 76:
 
=='''Zadanie 6'''==
 
=='''Zadanie 6'''==
  
Pokaż, że jeśli mamy tablicę sufiksową dla słowa compress(x) to można łatwo policzyć SUF[M] w czasie liniowym
+
Pokaż, że jeśli mamy tablicę sufiksową dla słowa compress(x), to można łatwo obliczyć SUF[M] w czasie liniowym.
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
Rozwiązanie
 
Rozwiązanie

Wersja z 15:32, 26 wrz 2006

Zadanie 1

Dane sa teksty x, y, oblicz najdłuższy tekst (oznaczany LCS(x,y) od ang. Longest Common Subword), który jest jednocześnie podsłowem x i y.

Rozwiązanie

Zadanie 2

Niech będzie tablicą najdłuższych wspólnych prefiksów dla słowa x oraz niech będzie sumą elementów tablicy . Uzasadnij, dlaczego liczba wszystkich niepustych podsłów x wynosi


Rozwiązanie


Zadanie 3

Wyprowadź wzór na

Rozwiązanie


Zadanie 4

Niech . Udowodnij, że

Rozwiązanie

Zadanie 5

Opisz liniowy algorytm obliczania tablicę ROT, przy założeniu, że mamy liniowy algorytm obliczania tablicy sufiksowej.

Rozwiązanie

Zadanie 6

Pokaż, że jeśli mamy tablicę sufiksową dla słowa compress(x), to można łatwo obliczyć SUF[M] w czasie liniowym.

Rozwiązanie