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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
WizualnieWikikod
Rytter (dyskusja | edycje)
830 edycji
Nie podano opisu zmian
 
m Zastępowanie tekstu – „<math> ” na „<math>”
 
(Nie pokazano 9 wersji utworzonych przez 3 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 x zawiera powtórzenie uu
wtedy i tylko wtedy gdy dla pewnego k zachodzi


</center>
== Zadanie 1==
<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 to <math> v_k </math> by nie występowało w faktoryzacji.
Udowodnij własność parzystych palstarów:
</div>
</div>
 
== Zadanie 2 ==


Oblicz faktoryzację LZ(x) w czasei liniowym.
<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">.


Skorzystaj z drzewa sufiksowego, z dodatkową informacja w węzłach.
Skorzystaj z kilku symetrii.
</div>
</div>
</div>
</div>


== Zadanie 3 ==
== Zadanie 2 ==
 
Udowdnij, ze algorytm Szukanie-Powtórzeń dził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
Udowodnij własność dowolnych palstarów:
<math> \sum_{k=1}^m\ |v_{k-1}v_k| \le 2n </math> </div>
</div>
 
== Zadanie 4 ==
 
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^* \ \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">.


Skorzystaj z kilku symetrii.
Skorzystaj z kilku symetrii</div>
</div>
</div>
</div>


== Zadanie 5 ==


Udowdnij,  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>


==Zadanie 3==
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>
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">.


Skorzystaj z kilku symetrii</div>
Skorzystaj z symetrii. </div>
</div>
</div>

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”