Słowa Fibonacciego

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Słowa Fibonacciegociąg słów stosowany w informatyce teoretycznej między innymi do analizy złożoności algorytmów tekstowych.

Definicja słów Fibonacciego[edytuj | edytuj kod]

Słowa Fibonacciego są słowami nad alfabetem \left\{ a, b \right\} zdefiniowany rekurencyjnie jako:

 
  F_n:=
  \begin{cases}
    b             & \mbox{dla } n = 1; \\
    a             & \mbox{dla } n = 2; \\
    F_{n-1} \cdot  F_{n-2} & \mbox{dla } n > 2. \\
   \end{cases}

Gdzie symbol \cdot oznacza konkatenację.

Początkowe słowa Fibonacciego[edytuj | edytuj kod]

 F_1 = b
 F_2 = a
 F_3 = ab
 F_4 = aba
 F_5 = abaab
 F_6 = abaababa
 F_7 = abaababaabaab
 F_8 = abaababaabaababaababa
 F_9 = abaababaabaababaababaabaababaabaab

Własności słów Fibonacciego[edytuj | edytuj kod]

|F_n| = f_n, gdzie f_n jest n-tą liczbą Fibonacciego.

Niech \tilde w\, oznacza słowo w\, z ostatnimi dwoma literami zamienionymi kolejnością. Zachodzi:

 \tilde{F_n} = F_{n-2} \cdot F_{n-1}

Uwagi[edytuj | edytuj kod]

Nie ma jednej konwencji dotyczącej oznaczania początkowych słów Fibonacciego. W niektórych źródłach przyjmuje się F_0 = b, F_1 = a, w innych z kolei F_0 = a, F_1 = ab.

Alfabet \left\{ a, b \right\} nie jest konieczny (choć jest często używany). Można równie dobrze używać alfabetu \left\{ 0, 1 \right\} lub innego dwuliterowego.

Bibliografia[edytuj | edytuj kod]