Zaawansowane algorytmy i struktury danych/Ćwiczenia 3: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
m Zastępowanie tekstu – „<math> ” na „<math>” |
||
| (Nie pokazano 2 wersji utworzonych przez 2 użytkowników) | |||
| Linia 1: | Linia 1: | ||
== Zadanie | |||
== Zadanie 1== | |||
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 14: | Linia 14: | ||
</div> | </div> | ||
== Zadanie | == 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 27: | Linia 27: | ||
==Zadanie | ==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:
Rozwiązanie
Zadanie 2
Udowodnij własność dowolnych palstarów:
Rozwiązanie
Zadanie 3
Udowodnij, że jeśli to dla pewnych <mtah> u,v \in PAL</math>, gdzie jest najdłuższym palindromem będącym prefiksem lub jest najdłuższym palindromem będącym sufiksem .
Rozwiązanie
