Archívy autora: keptn

Fibonacciho postupnosť a včelí rodokmeň

V spoločenstvách včiel medonosných, môžeme osadenstvo rozdeliť na tri skupiny:

Jedna kráľovná kralovna
Robotnice robotnica
Trúdy trud

Rozmnožovanie prebieha tak, že kráľovná je oplodnená trúdom a kladie oplodnené vajíčka, z ktorých sa neskôr vyliahnu robotnice alebo nová kráľovná. Zároveň kladie neoplodnené vajíčka, z ktorých sa vyliahnu trúdy. Schematicky:

kralovna trud kralovna
kráľovná + trúd → robotnica alebo nová kráľovná
robotnica
/
kralovna
kráľovná → trúd
trud

Teda trúd má jedného rodiča a robotnica a kráľovná dvoch rodičov. Kráľovná poväčšinu svojho života rodí robotnice a šíri okolo seba feromóny, ktoré zabraňujú vývoju novej kráľovnej. Tieto vyprchajú, keď nadíde čas na novú kráľovnú, napríklad vo vyššom veku pôvodnej.

Poďme sa zamerať na trúdov rodokmeň. Máme


kralovna

trud

kralovna

kralovna

trud

kralovna

trud

trud
8

kralovna

trud

kralovna

kralovna

trud
5

kralovna

trud

kralovna
3

kralovna

trud
2

kralovna
1

trud
1

a keby sme pokračovali, dostali by sme postupnosť

    \[1,1,2,3,5,8,13,21,34,55,89...\]

Otázka, ktorú si položíme znie: Za predpokladu, že sa kráľovná nepári s vlastnými potomkami, koľko predkov má trúd v rodokmeni v n-tej generácií dozadu?

Fibonacciho postupnosť

Ukážka z Liber Abbaci. Prvých 13 Fibonacciho čísel je vyísaných v červenom rámiku vpravo v indicko-arabskom systéme. (Zdroj: Wikipedia)

Označme počet predkov v generácií n, F_n. Písmeno F ako Fibonacci, alebo pre niekoho možno fčela… Všimneme si, že pre počet predkov v n-tej generácií dozadu platí

(1)   \begin{equation*} F_n = F_{n-1} + F_{n-2} \end{equation*}

s tým, že v generácií nula je iba trúd samotný F_0 = 1 a generácií jedna je iba kráľovná F_1 = 1. Túto postupnosť nazývame Fibonacciho postupnosťou.

Leonardo Bonacci, prezývaný Fibonacci, bol taliansky matematik pôsobiaci v Pise na prelome dvanásteho a trinásteho storočia. V publikácií Liber Abbaci (1209) sa zaoberal sa podobnou úlohou ako my, ale na králikoch.

Vzťah (1) môžeme odvodiť aj rigorózne. Nech K_n je počet kráľovien a T_n je počet trúdov v n-tej generácií dozadu. Označme teda celkový počet predkov

    \[F_n=T_n + K_n.\]

Počet trúdov zrátame ako počet otcov kráľovných v generácií n-1, to jest T_n = K_{n-1} a na úvod T_0 = 1. Kráľovné zrátame ako počet mám všetkých trúdov a kráľovien z generácie n-1, teda K_n = T_{n-1} + K_{n-1} s K_0 = 0.

Dostaneme

    \begin{align*} F_n &= T_n + K_n \\    &= K_{n-1} + T_{n-1} + K_{n-1}\\    &= F_{n-1} + K_{n-1}\\    &= F_{n-1} + T_{n-2} + K_{n-2}\\    &= F_{n-1} + F_{n-2}. \end{align*}

s počiatočými podmienkami

    \begin{align*} F_0 &= T_0 + K_0 \\     &= 1 \end{align*}

a

    \begin{align*} F_1 &= T_1 + K_1 \\     &= T_1 + T_0 + K_0\\     &= 1. \end{align*}

Vzťah (1) nazývame rekurentný z francúzskeho recourir – znovu bežať. Ak nás zaujíma počet predkov v generácií 10 tak pomocou vzťahu vyrátame F_2 = F_1 + F_0 a znovu pomocou toho istého vzťahu F_3 = F_2 + F_1 a takto ho necháme zopárkrát bežat, až kým sa nedostaneme k číslu F_{10}.

Teraz je vhodná doba zavolať na výpomoc Pytóna, programovací jazyk, ktorý nám pomôže toto všetko urobiť za nás:

# kód sa dá spustiť napríklad cez https://try.jupyter.org, New -> Python 3
def fib(n):
    fib_cisla = [1, 1]
   
    for i in range(2, n + 1):
      fib_cisla += [fib_cisla[i - 1] + fib_cisla[i - 2]]
  
    return fib_cisla[n]

print(fib(10))
>>> 89

Cvičenie: fib(n) ukladá n prvkov do pamäti v zozname fib_cisla. Skúste ho prepísať tak, aby používal iba trojprvkový zoznam. Riešenie na konci článku.

Uzavretý tvar

Pokiaľ sa čitateľ neuspokojil s algoritmickým riešením, pravdepodobne mu vŕta v hlave, čí by sa dala Fibonacciho postupnosť vyjadrít v uzavretom tvare. To jest pomocou nejakého vzorca, ktorý je nezávislý od predchádzajúcich hodnôt F_{n-1}, F_{n-2}, ... ale iba od n samotného

    \[F_n = f(n)\]

pre nejakú funkciu f. Takýto prepis by bol veľmi pohodlný z výpočtového hľadiska, lebo pre lubovoľné n by funkcia vykonala iba konštantný počet operácií. V informatike označujeme ako O(1). Algoritmus, ktorý sme uviedli v predchádzajúcej sekcií, na druhej strane, potrebuje vykonať n razy konštantný počet operácií, čo zodpovedá zložitosti O(n).

Poďme sa na to pozrieť. Jeden z účinných nástrojov na riešenie vzťahov podobných typu (1) je skúsiť riešenie uhádnuť. Vyskúšajme teda predpokladať, že F_n má tvar

    \[F_n = r^n\]

pre nejakú konštantu r. Dosadíme do rekurentného prepisu Fibonacciho postupnosti \label{eq:1} a dostávame r^n = r^{n-1} + r^{n-2}. Vydelíme r^{n-2} a zostane nám

    \[r^2 = r + 1\]

Toto je dobre známa kvadratická rovnica r^2 - r - 1 = 0 s diskriminantom D = (-1)^2 - (4.1.(-1)) = 5, čo zodpovedá dvom riešeniam

    \begin{align*} r_1 = \frac{1 + \sqrt{5}}{2} \\ r_2 = \frac{1 - \sqrt{5}}{2}. \end{align*}

Už sme skoro tam! Všimnime si, že ak by sme položili F_n = r_1^n tak v rekurentnom prepise (1) sa ľavá strana sa rovná pravej, dokonca F_0 = 1 ale bohužial F_1 = r_1 \neq 1. To isté platí pre r_2. Ako sa vysporiadať s F_1 \neq 1?

Všimnime si jednu dôležitú vlastnosť Fibonacciho prepisu, ktorou je lineárnosť. Ak je riešením G_n = r_1^n aj H_n = r_2^n, tak ľává strana sa bude rovnať pravej aj pre

(2)   \begin{equation*} F_n = k . G_n + l . H_n \end{equation*}

s ľubovoľnými konštantami k, l:

    \begin{align*} F_n &= k . G_n + l . H_n \\ &= k . (G_{n-1} + G_{n-2}) + l . (H_{n-1} + H_{n-2}) \\ &= k . G_{n-1} + l H_{n-1} + k . G_{n-2} + l H_{n-2} \\ &= F_{n-1} + F_{n-2}. \end{align*}

S týmto všeobecným riešením F_n sme ale vo veľkej výhode, lebo si môžeme vybrať konštanty k,l tak aby platilo F_0 = 1 a F_1 = 1. Dostávame sa k sústave

    \begin{align*} k + l &= 1 \\ k . r_1 + l . r_2 &= 1 \end{align*}

ktorej riešením je

    \begin{align*} k &= \frac{1 + \sqrt{5}}{2\sqrt{5}} \\ l &= \frac{1 - \sqrt{5}}{2\sqrt{5}}. \end{align*}

Dosadíme k,l,G_n,H_n do (2) a po upravení dostávame

    \[\label{eq:3} F_{n}=\frac{1}{\sqrt{5}}\bigg[\bigg(\frac{1+\sqrt{5}}{2}\bigg)^{n+1}-\bigg(\frac{1-\sqrt{5}}{2}\bigg)^{n+1}\bigg].\]

Na tejto formule je jeden veľmi zaujímavý fakt a to, že hoc to tak nevyzerá, keď sa to všetko zráta, dostaneme celé číslo 😯 .

Preveríme v Pytóne

# kód sa dá spustiť napríklad cez https://try.jupyter.org, New -> Python 3
def fib(n):
    od5 = 5 ** 0.5
    return (((1 + od5) / 2) ** (n + 1) - ((1 - od5) / 2) ** (n + 1)) / od5

print(fib(10))
>>> 89.00000000000003

Pripomeňme si, že \sqrt{5} = 5^{1/2}.

Teraz môže pozorný čitateľ protestovať: „Ha! Veď 89.00000000000003 nie je celé číslo!“. Zhruba ide o to, že vo vnútri počítača sú desatinné čísla pre numerické výpočty zapísané v dvojkovej sústave s konečným rozvojom. Takže pri výpočte dochádza k chybám na vyšších desatinných miestach, pokiaľ má medzivýpočet nekonečný dvojkový rozvoj.

Riešenie cvičenia

# kód sa dá spustiť napríklad cez https://try.jupyter.org, New -> Python 3
def fib(n):
    fib_cisla = [1, 1, 0]
    for i in range(2, n + 1):
        fib_cisla[i % 3] = fib_cisla[(i + 1) % 3] + fib_cisla[(i + 2) % 3]
    
    return fib_cisla[n % 3]

print(fib(10))
>>> 89

Zdroje

Basin SL. The Fibonacci sequence as it appears in nature. Fibonacci Quarterly. 1963 Feb;1(1):53-6.
King, F. Probability, Part IA Lecture Notes. 1st ed. Cambridge University, 2003. Web. 7 Feb. 2016.
Knott, R. „Who was Fibonacci?“. Maths.surrey.ac.uk. Retrieved 2010-08-02.
Knott, R. „Fibonacci Numbers and Nature“. Maths.surrey.ac.uk. Retrieved 2016-02-07.
Obrázky včiel prevzaté z: http://vcelamedonosnagc.blogspot.co.uk.

Ako otočiť obrázok?

Úloha

Otočiť obrázok o ľubovoľný uhol, napríklad 90 stupňov, proti smeru hodinových ručičiek okolo ľavého dolného rohu.

Pred otočením

Rendered by QuickLaTeX.com

Po otočení

Rendered by QuickLaTeX.com

Riešenie

Posaďme obrázok do súradnicového systému. Na otočenie celého obrázku je potrebné otočit každy jeden bod.

Rendered by QuickLaTeX.com

Zoberme si napríklad bod [1;3]. Vypočítame

    \[\cos(90^{\circ}) \cdot 1 - \sin(90^{\circ}) \cdot 3 = -3\]

    \[\sin(90^{\circ}) \cdot 1 + \cos(90^{\circ}) \cdot 3 = 1\]

a dostaneme súradnice otočeného bodu [-3;1].

Rendered by QuickLaTeX.com

Po otočení všetkých bodov rovnakým spôsobom získame

Rendered by QuickLaTeX.com

Teda všeobecne, ak označíme súradnice bodu, ktorý chceme otočť proti smeru hodinových ručičiek okolo počiatku súradného systému ako [x;y], tak súradnice otočeného bodu [x’;y’] vypočítame ako

    \[x'=\cos(\alpha) \cdot x - \sin(\alpha) \cdot y\]

    \[y'=\sin(\alpha) \cdot x + \cos(\alpha) \cdot y\]

Ako to funguje

Daný je vektor u = (x,y) a chceme získať súradnice otočeného vektora v = (x’,y’). Uhol alfa označuje v stupňoch veľkosť samotného otočenie okolo počiatku súradného systému, proti smeru hodinových ručičiek.

Rendered by QuickLaTeX.com

Matematicky vzaté, chceme nájsť funkciu f ktorá vezme ako parameter vektor u a vráti otočený vektor v

    \[\vec{v} = f(\vec{u})\]

Bez toho aby sme zatiaľ čokoľvek rátali si všimnime dve dôležité vlastnosti otočenia f

Prvá vlastnosť

    \[f(\vec{u_{1}} + \vec{u_{2}}) = f(\vec{u_{1}}) + f(\vec{u_{2}}),\]

pre ľubovoľné dva vektory u1 a u2.

Intuitívny dôkaz. Vidíme, že keď najskôr osobitne otočíme vektory u1 a u2 a potom už otočené sčítame dostaneme to isté, akoby sme rovno otočili u1 + u2.

Rendered by QuickLaTeX.com

sa rovná

Rendered by QuickLaTeX.com

Druhá vlastnosť

    \[f(c\cdot\vec{u})=c\cdot f(\vec{u}),\]

pre všetky skaláry c a vektory u.

Intuitívny dôkaz pre c = 2. vidíme, že keď najskôr otočíme vektor u a potom už otočený vektor f(u) vynásobíme dvomi dostaneme ten istý vektor a keby sme otočili vektor 2.u.

Rendered by QuickLaTeX.com

je to isté ako

Rendered by QuickLaTeX.com

Funkciu, ktorá spĺňa obe vlastnosti nazývame lineárne zobrazenie. Teda otočenie f je lineárne zobrazenie.

S týmto dôležitým poznatkom sa vráťme k pôvodnej úlohe nájsť f také, že

    \[\vec{v}=f(\vec{u})\]

S vlastností vektorov vyplýva

    \[\vec{u}=(x,y)=x\cdot (1,0) + y\cdot (0,1)\]

Ak označíme vektory e1 = (1,0) a e2 = (0,1)

(1)   \begin{align*} f(\vec{u}) & =f(x\cdot \vec{e_{1}} + y\cdot \vec{e_{2}}) \\  & =f(x\cdot \vec{e_{1}}) + f(y\cdot \vec{e_{2}})\quad\text{podla prvej vlastnosti} \\  & = x\cdot f(\vec{e_{1}}) + y\cdot f(\vec{e_{2}})\quad\text{podla druhej vlastnosti} \end{align*}

Kvôli tomu, že f je lineárne zobrazenie, nám teda stačí nájsť iba prepisy f(e1) a f(e2) na otočenie vektorov e1 a e2.

Prepis f(\vec{e_{1}})

Rendered by QuickLaTeX.com

Teda

(2)   \begin{equation*} f(\vec{e_{1}})=(\cos(\alpha),\sin(\alpha)) \end{equation*}

Prepis f(\vec{e_{2}})

Rendered by QuickLaTeX.com

Použili sme

    \begin{align*} \sin(\pi/2 + \alpha) &=\cos(\alpha) \\ \cos(\pi/2 + \alpha) &=-\sin(\alpha) \end{align*}

Teda

(3)   \begin{equation*} f(\vec{e_{2}})=(-\sin(\alpha),\cos(\alpha)) \end{equation*}

Výsledok

Dosadením prepisov (2) a (3) do odvodenia (1) a označením zložiek otočeného vektora v=(x’,y) dostávame

    \begin{align*} (x',y') &= f(\vec{u}) \\ &= x \cdot (\cos(\alpha),\sin(\alpha)) + y\cdot(-\sin(\alpha),\cos(\alpha)) \\ &= (x \cdot \cos(\alpha) - y \cdot \sin(\alpha), x \cdot \sin(\alpha) + y\cdot \cos(\alpha) ) \end{align*}

po zložkách

(4)   \begin{align*} x' &= x\cdot\cos(\alpha) - y\cdot\sin(\alpha)\\ y' &= x\cdot\sin(\alpha) + y\cdot\cos(\alpha)\\ \end{align*}

Bonus

Výsledok (4) možno zapísať pomocou matíc. Odteraz budeme vektory označovať v stĺpcovom tvare s hranatými zátvorkami

    \[\left[\begin{array}{c} x\\ y \end{array}\right] = (x,y)\]

Zadefinujme maticu 2×2 ako objekt so štyrmi čislami

    \[\left[\begin{array}{cc} a & b\\ c & d \end{array}\right]\]

ktorý nasledovne zľava-násobí vektory 2×1

    \[ \left[\begin{array}{cc} a & b\\ c & d \end{array}\right]\left[\begin{array}{c} x\\ y \end{array}\right]=x\cdot\left[\begin{array}{c} a\\ c \end{array}\right]+y\cdot\left[\begin{array}{c} b\\ d \end{array}\right] \]

Všimnime si, že výsledok násobenia je vektor 2×1. S touto definíciou môžeme (4) zapísať ako

    \[ \left[\begin{array}{c} x'\\ y' \end{array}\right]=\left[\begin{array}{cc} \cos(\alpha) & -\sin(\alpha)\\ \sin(\alpha) & \cos(\alpha) \end{array}\right]\left[\begin{array}{c} x\\ y \end{array}\right] \]

Príklady matíc otočenia

o 30 stupňov

    \[A=\left[\begin{array}{cc} \frac{\sqrt{3}}{2} & -\frac{1}{2}\\ \frac{1}{2} & \frac{\sqrt{3}}{2} \end{array}\right]\]

o 45 stupňov

    \[B=\left[\begin{array}{cc} \frac{\sqrt{2}}{2} & -\frac{\sqrt{2}}{2}\\ \frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} \end{array}\right]\]

o 90 stupňov

    \[C=\left[\begin{array}{cc} 0 & -1\\ 1 & 0 \end{array}\right]\]

Jednou z výhod tejto notácie je, že otočenia môžeme skladať. Ak chceme napríklad vektor u=(1,2) otočiť o 165 stupňov vyrátame

    \[A(B(C\vec{u}))) = \left[\begin{array}{c} -\frac{-1+\sqrt{3}}{\sqrt{2}}-\frac{1+\sqrt{3}}{2\sqrt{2}}\\ \frac{-1+\sqrt{3}}{2\sqrt{2}}-\frac{1+\sqrt{3}}{\sqrt{2}} \end{array}\right] \approx \left[\begin{array}{c} -1.484\\ -1.673 \end{array}\right]\]

V skutočnosti sa každé lineárne zobrazenie dá zapisať pomocou matíc. Tak môžeme skladať napríklad otočenia s natiahnutiami a reflexiami.