Cesko.wiki Fibonacciho slovo
Author
Albert FloresFibonacciho slovo je posloupnost čísel, která vzniká podle pravidla nazvaného po italském matematikovi Leonardu z Pisy, známém také jako Fibonacci. Tato posloupnost začíná čísly 0 a 1, a každé další číslo je součtem dvou předchozích čísel. Fibonaccio slovo je pak posloupnost číslic, která se vytvoří nahrazením každého čísla ve Fibonacciho posloupnosti číslicí 0 nebo 1. Tato posloupnost má řadu zajímavých vlastností a je využívána v různých matematických úlohách a algoritmech. Fibonacciho slovo je základem pro mnoho dalších konstrukcí a je studováno v oblasti teorie čísel, teoretické informatiky a kryptografie.
Fibonacciho slovo je specifická posloupnost binárních číslic (nebo obecněji jakýchkoliv dvou symbolů). Fibonacciho slovo získáme podobně jako Fibonacciho číslo, pouze namísto sčítání použijeme zřetězení slov.
Definice
Nechť S0 = 0 a S1 = 01. Nyní můžeme definovat obecný člen posloupnosti Fibonacciho slov: Sn = Sn-1Sn-2 (pro n > 1). +more Slovně řečeno - n-tý prvek této posloupnosti získáme tak, že zřetězíme jeho předchozí dva prvky. Fibonacciho slov je nekonečně mnoho.
Nekonečné Fibonacciho slovo označujeme S∞.
Fibonacciho slova
Takže nyní máme takovouto posloupnost:
S0 = 0 S1 = 01 S2 = 010 S3 = 01001 S4 = 01001010 S5 = 0100101001001 …
Posloupnost několika prvních číslic z Fibonacciho slov by vypadala takto:
0100101001001010010100100101001001…
(.) Tato posloupnost zároveň tvoří slovo S∞.
Pravidla substituce
Jiné možnosti, jak definovat následující člen posloupnosti:
* Pokud známe slovo Sn a chceme získat slovo Sn+1, můžeme v Sn nahradit každý výskyt číslice 0 dvojicí 01 a každý výskyt číslice 1 nahradit číslicí 0. Příklad: máme S3 = 01001. +more Provedeme záměny 0→01 a 1→0 (musíme je provést zároveň, pokud bychom nejprve provedli první záměnu a na tento výsledek aplikovali druhou záměnu, získáme posloupnost samých nul. ).
0→01 1→0 0→01 0→01 1→0
Výsledek je 01001010. To odpovídá S4, které je spočítáno výše. +more * Fibonacciho slova můžeme přímo generovat pomoci posouváním kurzoru. Na začátku namíříme kurzor na první číslici slova. Pokud nyní kurzor míří na 0, přidáme na konec slova dvojici 01. Pokud kurzor míří na 1, přidáme na konec slova 0. Po přidání posuneme kurzor o jednu číslici doprava a opakujeme. Ve chvíli, kdy dojdeme na konec (původního) slova, proces končí a máme další člen posloupnosti. Mějme opět S3 = 01001. Celý postup by vypadal takto:.
01001 => (Inicializace, nalevo původní slovo, napravo nové slovo - zatím prázdné, kurzor mimo číslice.) ^
01001 => 01 ^
01001 => 010 ^
01001 => 01001 ^
01001 => 0100101 ^
01001 => 01001010 ^
Pokud bychom tento postup aplikovali na jednom slovu (kurzor by se pohyboval po stejném slovu, k jakému by se přidávaly číslice), vygenerovali bychom v nekonečnu S∞.
Další vlastnosti
Slovo Sn má délku Fn-2, kde F představuje Fibonacciho posloupnost. * S∞ nemá periodu. +more * Poslední dvě číslice v každém Fibonacciho slově (krom prvního) jsou buď 01, nebo 10. * Přidáním dvou posledních číslic ze slova Sn v opačném pořadí na začátek slova vytvoříme palindrom. Například: S3 = 01001 → 10 + 01001 = 1001001 a to je palindrom. * Odmazáním dvou posledních číslic také získáme palindrom. Příklad: S4 = 01001010 → 010010. * V S∞ platí, že (počet číslic)/(počet nul) = zlatý řez. * S∞ můžeme nazvat „vyrovnaným“ slovem. Pokud vezmeme dva libovolné podřetězce délky n, počet nul v těchto podřetězcích se bude lišit nejvýše o jedna. * V žádném slově nenalezneme podřetězce 11 nebo 000. * S∞ obsahuje k+1 různých podřetězců délky k. * S∞ je rekurentní slovo - každý podřetězec je v S∞ obsažen nekonečně krát. * Pokud je u podřetězec S∞, pak i obrácené slovo uR je podřetězec S∞.