[niewinnosc]
Jeśli dział dla zaawansowanych, to:
Mamy taki o to zaawansowany problem <font color="darkblue">decyzyjny</span> o nazwie "problem odpowiedniości słów":
Dane wejściowe:
<font color="darkblue">alfabet</span> S
dwa równoliczne ciągi <font color="darkblue">słów nad alfabetem</span> S, X(x1,x2,...,xn) i Y(y1,y2,...,yn).
Wynik:
Tak - jeśli istnieje taki ciąg indeksów I(i1,i2,...,ik) taki, że xi1,xi2,...,xik=yi1,yi2,...,yik.
Nie - w przeciwnym wypadku.
Wprowadźmy kilka formalnych definicji:
problem decyzyjny - problem, którego wynikiem jest odpowiedź tak albo nie.
alfabet - niepusty i skończony zbiór symboli
słowo nad alfabetem - dowolny skończony ciąg liter tego alfabetu
przyjmijmy następującą konwencję zapisu:
słowo s=(s1,s2,...,sn) będziemy zapisywać po prostu jako s1s2...sn
np. słowo s=(b,c,c,a,b) będziemy zapisywać jako "bccab"
{uwaga - aby w takim zapisie słowo było jednoznacznie, musimy nałożyć na alfabet pewne dodatkowe ograniczenia, o których tu nie wspomnę, aby nie zaciemniać obrazu}
Przykład: Mamy trzyliterowy alfabet S={a,b,c}. Istnieje nieskończenie wiele słów nad alfabetem S, w tym: bccab, abc, a, aa, aaa, aaaa, ...
Ostatecznie powracając do samego problemu, oto dwa przykłady:
Przykład 1)
alfabet S = {a,b}
1 2 3 4
X a b aa ab
Y aa abaa b a
W powyżyszym przykładzie wynik to "tak", ponieważ np. ciąg indeksów (4,3,1,1) generuje w obydwu ciągach X i Y to samo słowo - abaaaa
Wystarczy jednak, że odrobinę zmienimy ciągi X i Y, np.
Przykład 2)
alfabet S = {a,b}
1 2 3 4
X aa b aa ab
Y a abaa b a
Odpowiedzią jest "nie", gdyż można wykazać że nie istnieje taki ciąg indeksów, który generuje to samo słowo w X i Y.
Jak zwykle, czekam na wszelkie obserwacje i szkice algorytmów.
Pozdrawiam.
[niewinnosc]
p.s. prawdopodobnie, temat ten znajdzie swój finał w artykule o złożoności obliczeniowej i klasach rozwiązywalności problemów.