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

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
← poprzednia edycja
WizualnieWikikod
m Zastępowanie tekstu – „ </math>” na „</math>”
m Zastępowanie tekstu – „<math> ” na „<math>”
 
Linia 6: Linia 6:
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 18: Linia 18:
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 28: Linia 28:


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

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”