Zaawansowane algorytmy i struktury danych/Ćwiczenia 3: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
Dorota (dyskusja | edycje)
376 edycji
Nie podano opisu zmian
m Zastępowanie tekstu – „<math> ” na „<math>”
 
(Nie pokazano 3 wersji utworzonych przez 2 użytkowników)
Linia 1: Linia 1:
==Zadanie 1==
Udwodnij, że jeśli <math> LZ(x)\ =\ (v_{1},v_{2},\dots ,v_{m})</math>, to <math>x</math> zawiera powtórzenie <math>uu</math>
wtedy i tylko wtedy, gdy dla pewnego <math>k</math> zachodzi


<center>
<math> RightTest(v_1, v_2\ldots v_{k-2},\ v_{k-1}v_k lub Righttest(v_1, v_2\ldots v_{k-1},\ v_k) </math></center>
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  <div class="mw-collapsible-content" style="display:none">.
Jeśli środek powtórzenia byłby wcześniej, <math> v_k </math> nie występowałoby w faktoryzacji.
</div>
</div>
== Zadanie 2 ==
Oblicz faktoryzację LZ(x) w czasie liniowym.
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  <div class="mw-collapsible-content" style="display:none">.


Skorzystaj z drzewa sufiksowego z dodatkową informacją w węzłach.
</div>
</div>


== Zadanie 3 ==
== Zadanie 1==
 
Udowodnij, że algorytm Szukanie-Powtórzeń działa w czasie liniowym.
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  <div class="mw-collapsible-content" style="display:none">.
 
Złożoność liczenia alternatywy RightTest(u1,v1) lub RightTest(u2,v2) jest <math> O(|v_{k-1}v_k|)</math> oraz zachodzi
<math> \sum_{k=1}^m\ |v_{k-1}v_k| \le 2n </math> </div>
</div>
 
== Zadanie 4 ==


Udowodnij własność parzystych palstarów:  
Udowodnij własność parzystych palstarów:  


<math> x[i..n] \in PAL_0^* \ \Rightarrow\ parse_0(i)=first_0(i)</math>
<math>x[i..n] \in PAL_0^* \ \Rightarrow\ parse_0(i)=first_0(i)</math>


<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  <div class="mw-collapsible-content" style="display:none">.
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  <div class="mw-collapsible-content" style="display:none">.
Linia 43: Linia 14:
</div>
</div>


== Zadanie 5 ==
== Zadanie 2 ==


Udowodnij własność dowolnych palstarów:
Udowodnij własność dowolnych palstarów:


<math> x[i..n] \in PAL^* \ \Rightarrow\ parse(i)\in \{first(i),\ 2\cdot first(i)+1,\ 2\cdot first(i)-1\}</math>
<math>x[i..n] \in PAL^* \ \Rightarrow\ parse(i)\in \{first(i),\ 2\cdot first(i)+1,\ 2\cdot first(i)-1\}</math>


<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  <div class="mw-collapsible-content" style="display:none">.
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  <div class="mw-collapsible-content" style="display:none">.
Linia 56: Linia 27:




==Zadanie 6==
==Zadanie 3==
Udowodnij,  że jeśli <math> x \in PAL^2</math>  
Udowodnij,  że jeśli <math>x \in PAL^2</math>  
to <math>x=uv</math> dla pewnych <mtah> u,v \in PAL </math>, gdzie <math>u</math> jest najdłuższym palindromem będącym prefiksem <math>x</math> lub <math>v</math>  
to <math>x=uv</math> dla pewnych <mtah> u,v \in PAL</math>, gdzie <math>u</math> jest najdłuższym palindromem będącym prefiksem <math>x</math> lub <math>v</math>  
jest najdłuższym palindromem będącym sufiksem <math>x</math>.
jest najdłuższym palindromem będącym sufiksem <math>x</math>.
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  <div class="mw-collapsible-content" style="display:none">.
<div class="mw-collapsible mw-made=collapsible mw-collapsed">'''Rozwiązanie'''  <div class="mw-collapsible-content" style="display:none">.

Aktualna wersja na dzień 22:12, 11 wrz 2023


Zadanie 1

Udowodnij własność parzystych palstarów:

x[i..n]∈PAL0* ⇒ parse0(i)=first0(i)

Rozwiązanie

Zadanie 2

Udowodnij własność dowolnych palstarów:

x[i..n]∈PAL* ⇒ parse(i)∈{first(i), 2⋅first(i)+1, 2⋅first(i)−1}

Rozwiązanie


Zadanie 3

Udowodnij, że jeśli x∈PAL2 to x=uv dla pewnych <mtah> u,v \in PAL</math>, gdzie u jest najdłuższym palindromem będącym prefiksem x lub v jest najdłuższym palindromem będącym sufiksem x.

Rozwiązanie
Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=Zaawansowane_algorytmy_i_struktury_danych/Ćwiczenia_3&oldid=82474”