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 zdefiniowany rekurencyjnie jako:

Gdzie symbol oznacza konkatenację.

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

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

, gdzie jest n-tą liczbą Fibonacciego.

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

Uwagi[edytuj | edytuj kod]

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 dwuznakowego.

Bibliografia[edytuj | edytuj kod]