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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
m (Zastępowanie tekstu - "\ =\" na "=")
 
(Nie pokazano 9 wersji utworzonych przez 3 użytkowników)
Linia 1: Linia 1:
 
=='''Zadanie 1'''==
 
=='''Zadanie 1'''==
Dane sa teksty x, y, oblicz najdłuższy tekst <math>z</math> (oznaczany LCS(x,y) od ang. Longest Common Subword),
+
Dane 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 i y.
 
który jest jednocześnie podsłowem x i y.
  
Linia 18: Linia 18:
 
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 42: Linia 42:
 
Wtedy
 
Wtedy
  
<center><math>Sub(n+1)\ =\ Sub(n) + \Phi_{n-3}\cdot \Phi_{n-1} + \Phi_{n-2}\cdot (\Phi_{n-1}+2)
+
<center><math>Sub(n+1) = Sub(n) + \Phi_{n-3}\cdot \Phi_{n-1} + \Phi_{n-2}\cdot(\Phi_{n-1}+2)
 
</math></center>
 
</math></center>
  
<center><math>{Sub(n)\ =\
+
<center><math>Sub(n) = \Phi_{n-1} \Phi_{n-2}+2\cdot \Phi_{n-1}-1</math></center>
\Phi_{n-1}\Phi_{n-2}+2\cdot \Phi_{n-1}-1</math></center>
 
 
  </div>
 
  </div>
 
</div>
 
</div>
 
  
 
=='''Zadanie 4'''==
 
=='''Zadanie 4'''==
  
Niech  <math>lcp'[k]\ =\ lcp[rank[k]-1]</math>.
+
Niech  <math>lcp'[k]= lcp[rank[k]-1]</math>.
 
Udowodnij, że <math>lcp'[k]\ge lcp'[k-1]-1</math>
 
Udowodnij, że <math>lcp'[k]\ge lcp'[k-1]-1</math>
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
Linia 83: Linia 81:
 
Tablica  sufiksowa dla słowa compress(x) składa się z dwóch ''połówek'', kodują one słowa zaczynające się na pozycjach  
 
Tablica  sufiksowa dla słowa compress(x) składa się z dwóch ''połówek'', kodują one słowa zaczynające się na pozycjach  
 
odpowiedni i mod 3 =1, oraz i mod 3 =2.  
 
odpowiedni i mod 3 =1, oraz i mod 3 =2.  
 +
</div>
 +
</div>
 +
 +
 +
=='''Zadanie 7''' ==
 +
 +
''(Teksty-> Grafy)'' Dany jet zbiór tekstów długości dwa. Wyznaczyć długość minimalnego tekstu, zawierającego teksty wejściowe.
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
Rozwiązanie
 +
 +
<div class="mw-collapsible-content" style="display:none">
 +
<br>
 +
 +
Zadanie sprowadza się do policzenia minimalnego ( w sensie liczności) zbioru rozłącznych ścieżek w grafie
 +
skierowanym, które zawierają wszystkie krawędzie. Krawędzie odpowiadają słowom wejściowym,
 +
wierzchołki grafu odpowiadają literom.
 +
<br>
 +
 +
Zadanie było na olimpiadzie informatycznej pod nazwą ''Pierwotek abstrakcyjny'', miało rozwiązanie w czasie liniowym.
 +
</div>
 +
</div>
 +
 +
 +
=='''Zadanie 8''' ==
 +
 +
Dany jest zbiór X tekstów binarnych. Sprawdzić czy istnieje nieskończenie wiele słów  binarnych nie
 +
zawierających żadnego elementu z X jako podsłowo.
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
Rozwiązanie
 +
 +
<div class="mw-collapsible-content" style="display:none">
 +
<br>
 +
 +
Opiszemy operacje redukcji tekstu. Jeśli w zbiorze X są teksty ua, vb, gdzie a,b są różnymi cyframi binarnymi
 +
oraz u jest sufiksem v (np. gdy <math> u=v</math>) , to zastępujemy w X słowo vb przez słowo v. Inaczej mówiąc wykonujemy operację:
 +
<br>
 +
 +
''redukcja'': vb -> v
 +
<br>
 +
 +
Algorytm wykonuje wszelkie redukcje póki się da (w dowolnym porządku). Jeśli otrzymamy słowo puste
 +
to odpowiedź jest ''NIE'', w przeciwym wypadku ''TAK''.
 +
<br>
 +
 +
Zadanie było na olimpiadzie informatycznej pod nazwą ''Wirusy'', miało rozwiązanie w czasie liniowym.
 +
</div>
 +
</div>
 +
 +
 +
 +
=='''Zadanie 9''' ==
 +
 +
Udowdnij, że dla słów Fibonacciego kończących się na literę 'a'
 +
tablica sufksowa jest postępem arytmetycznym modulo długość słowa.
 +
<div class="mw-collapsible mw-made=collapsible mw-collapsed">
 +
Rozwiązanie
 +
 +
<div class="mw-collapsible-content" style="display:none">
 +
<br>
 +
Zobacz jakie są zależności między słowami Fibonacciego i zapisem kolejnych liczb
 +
naturalnych w systemie liczbowym Fibonacciego.
 
</div>
 
</div>
 
</div>
 
</div>

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

Zadanie 1

Dane są 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


Zadanie 7

(Teksty-> Grafy) Dany jet zbiór tekstów długości dwa. Wyznaczyć długość minimalnego tekstu, zawierającego teksty wejściowe.

Rozwiązanie


Zadanie 8

Dany jest zbiór X tekstów binarnych. Sprawdzić czy istnieje nieskończenie wiele słów binarnych nie zawierających żadnego elementu z X jako podsłowo.

Rozwiązanie


Zadanie 9

Udowdnij, że dla słów Fibonacciego kończących się na literę 'a' tablica sufksowa jest postępem arytmetycznym modulo długość słowa.

Rozwiązanie