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]

Słowa Fibonacciego są słowami nad alfabetem zdefiniowany rekurencyjnie jako:

Gdzie symbol oznacza konkatenację.

Początkowe słowa Fibonacciego[edytuj]

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

, gdzie jest n-tą liczbą Fibonacciego.

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

Uwagi[edytuj]

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

Alfabet nie jest konieczny (choć jest często używany). Można równie dobrze używać alfabetu lub innego dwuliterowego.

Bibliografia[edytuj]