Archívy autora: keptn

1

1

1

1

Fibonacciho postupnosA? a vA?elA� rodokmeA?

V spoloA?enstvA?ch vA?iel medonosnA?ch, mA?A?eme osadenstvo rozdeliA? na tri skupiny:

Jedna krA?A?ovnA? a�� kralovna
Robotnice a�� robotnica
TrA?dy a�� trud

RozmnoA?ovanie prebieha tak, A?e krA?A?ovnA? je oplodnenA? trA?dom a kladie oplodnenA� vajA�A?ka, z ktorA?ch sa neskA?r vyliahnu robotnice alebo novA? krA?A?ovnA?. ZA?roveA? kladie neoplodnenA� vajA�A?ka, z ktorA?ch sa vyliahnu trA?dy. Schematicky:

kralovna trud kralovna
krA?A?ovnA? + trA?d a�� robotnica alebo novA? krA?A?ovnA?
robotnica
/
kralovna
krA?A?ovnA? a�� trA?d
trud

Teda trA?d mA? jednA�ho rodiA?a a robotnica a krA?A?ovnA? dvoch rodiA?ov. KrA?A?ovnA? povA�A?A?inu svojho A?ivota rodA� robotnice a A?A�ri okolo seba feromA?ny, ktorA� zabraA?ujA? vA?voju novej krA?A?ovnej. Tieto vyprchajA?, keA? nadA�de A?as na novA? krA?A?ovnA?, naprA�klad vo vyA?A?om veku pA?vodnej.

PoA?me sa zameraA? na trA?dov rodokmeA?. MA?me

a��
kralovna
a��
trud
a��
kralovna
a��
kralovna
a��
trud
a��
kralovna
a��
trud
a��
trud
8
a��
kralovna
a��
trud
a��
kralovna
a��
kralovna
a��
trud
5
a��
kralovna
a��
trud
a��
kralovna
3
a��
kralovna
a��
trud
2
a��
kralovna
1
a��
trud
1

a keby sme pokraA?ovali, dostali by sme postupnosA?

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

OtA?zka, ktorA? si poloA?A�me znie: Za predpokladu, A?e sa krA?A?ovnA? nepA?ri s vlastnA?mi potomkami, koA?ko predkov mA? trA?d v rodokmeni v n-tej generA?ciA� dozadu?

Fibonacciho postupnosA?

UkA?A?ka z Liber Abbaci. PrvA?ch 13 Fibonacciho A?A�sel je vyA�sanA?ch v A?ervenom rA?miku vpravo v indicko-arabskom systA�me. (Zdroj: Wikipedia)

OznaA?me poA?et predkov v generA?ciA� n, F_n. PA�smeno F ako Fibonacci, alebo pre niekoho moA?no fA?ela… VA?imneme si, A?e pre poA?et predkov v n-tej generA?ciA� dozadu platA�

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

s tA?m, A?e v generA?ciA� nula je iba trA?d samotnA? F_0 = 1 a generA?ciA� jedna je iba krA?A?ovnA? F_1 = 1. TA?to postupnosA? nazA?vame Fibonacciho postupnosA?ou.

Leonardo Bonacci, prezA?vanA? Fibonacci, bol taliansky matematik pA?sobiaci v Pise na prelome dvanA?steho a trinA?steho storoA?ia. V publikA?ciA� Liber Abbaci (1209) sa zaoberal sa podobnou A?lohou ako my, ale na krA?likoch.

VzA?ah (1) mA?A?eme odvodiA? aj rigorA?zne. Nech K_n je poA?et krA?A?ovien a T_n je poA?et trA?dov v n-tej generA?ciA� dozadu. OznaA?me teda celkovA? poA?et predkov

    \[F_n=T_n + K_n.\]

PoA?et trA?dov zrA?tame ako poA?et otcov krA?A?ovnA?ch v generA?ciA� n-1, to jest T_n = K_{n-1} a na A?vod T_0 = 1. KrA?A?ovnA� zrA?tame ako poA?et mA?m vA?etkA?ch trA?dov a krA?A?ovien z generA?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 poA?iatoA?A?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*}

VzA?ah (1) nazA?vame rekurentnA? z francA?zskeho recourir – znovu beA?aA?. Ak nA?s zaujA�ma poA?et predkov v generA?ciA� 10 tak pomocou vzA?ahu vyrA?tame F_2 = F_1 + F_0 a znovu pomocou toho istA�ho vzA?ahu F_3 = F_2 + F_1 a takto ho nechA?me zopA?rkrA?t beA?at, aA? kA?m sa nedostaneme k A?A�slu F_{10}.

Teraz je vhodnA? doba zavolaA? na vA?pomoc PytA?na, programovacA� jazyk, ktorA? nA?m pomA?A?e toto vA?etko urobiA? za nA?s:

# kA?d sa dA? spustiA? naprA�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

CviA?enie: fib(n) ukladA? n prvkov do pamA�ti v zozname fib_cisla. SkA?ste ho prepA�saA? tak, aby pouA?A�val iba trojprvkovA? zoznam. RieA?enie na konci A?lA?nku.

UzavretA? tvar

PokiaA? sa A?itateA? neuspokojil s algoritmickA?m rieA?enA�m, pravdepodobne mu vA�ta v hlave, A?A� by sa dala Fibonacciho postupnosA? vyjadrA�t v uzavretom tvare. To jest pomocou nejakA�ho vzorca, ktorA? je nezA?vislA? od predchA?dzajA?cich hodnA?t F_{n-1}, F_{n-2}, ... ale iba od n samotnA�ho

    \[F_n = f(n)\]

pre nejakA? funkciu f. TakA?to prepis by bol veA?mi pohodlnA? z vA?poA?tovA�ho hA?adiska, lebo pre lubovoA?nA� n by funkcia vykonala iba konA?tantnA? poA?et operA?ciA�. V informatike oznaA?ujeme ako O(1). Algoritmus, ktorA? sme uviedli v predchA?dzajA?cej sekciA�, na druhej strane, potrebuje vykonaA? n razy konA?tantnA? poA?et operA?ciA�, A?o zodpovedA? zloA?itosti O(n).

PoA?me sa na to pozrieA?. Jeden z A?A?innA?ch nA?strojov na rieA?enie vzA?ahov podobnA?ch typu (1) je skA?siA? rieA?enie uhA?dnuA?. VyskA?A?ajme teda predpokladaA?, A?e F_n mA? tvar

    \[F_n = r^n\]

pre nejakA? konA?tantu r. DosadA�me do rekurentnA�ho prepisu Fibonacciho postupnosti \label{eq:1} a dostA?vame r^n = r^{n-1} + r^{n-2}. VydelA�me r^{n-2} a zostane nA?m

    \[r^2 = r + 1\]

Toto je dobre znA?ma kvadratickA? rovnica r^2 - r - 1 = 0 s diskriminantom D = (-1)^2 - (4.1.(-1)) = 5, A?o zodpovedA? dvom rieA?eniam

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

UA? sme skoro tam! VA?imnime si, A?e ak by sme poloA?ili F_n = r_1^n tak v rekurentnom prepise (1) sa A?avA? strana sa rovnA? pravej, dokonca F_0 = 1 ale bohuA?ial F_1 = r_1 \neq 1. To istA� platA� pre r_2. Ako sa vysporiadaA? s F_1 \neq 1?

VA?imnime si jednu dA?leA?itA? vlastnosA? Fibonacciho prepisu, ktorou je lineA?rnosA?. Ak je rieA?enA�m G_n = r_1^n aj H_n = r_2^n, tak A?A?vA? strana sa bude rovnaA? pravej aj pre

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

s A?ubovoA?nA?mi konA?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 tA?mto vA?eobecnA?m rieA?enA�m F_n sme ale vo veA?kej vA?hode, lebo si mA?A?eme vybraA? konA?tanty k,l tak aby platilo F_0 = 1 a F_1 = 1. DostA?vame sa k sA?stave

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

ktorej rieA?enA�m je

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

DosadA�me k,l,G_n,H_n do (2) a po upravenA� dostA?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 veA?mi zaujA�mavA? fakt a to, A?e hoc to tak nevyzerA?, keA? sa to vA?etko zrA?ta, dostaneme celA� A?A�slo 😯 .

PreverA�me v PytA?ne

# kA?d sa dA? spustiA? naprA�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

PripomeA?me si, A?e \sqrt{5} = 5^{1/2}.

Teraz mA?A?e pozornA? A?itateA? protestovaA?: „Ha! VeA? 89.00000000000003 nie je celA� A?A�slo!“. Zhruba ide o to, A?e vo vnA?tri poA?A�taA?a sA? desatinnA� A?A�sla pre numerickA� vA?poA?ty zapA�sanA� v dvojkovej sA?stave s koneA?nA?m rozvojom. TakA?e pri vA?poA?te dochA?dza k chybA?m na vyA?A?A�ch desatinnA?ch miestach, pokiaA? mA? medzivA?poA?et nekoneA?nA? dvojkovA? rozvoj.

RieA?enie cviA?enia

# kA?d sa dA? spustiA? naprA�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.
ObrA?zky vA?iel prevzatA� z: http://vcelamedonosnagc.blogspot.co.uk.

Ako otoA?iA? obrA?zok?

Asloha

OtoA?iA? obrA?zok o A?ubovoA?nA? uhol, naprA�klad 90 stupA?ov, proti smeru hodinovA?ch ruA?iA?iek okolo A?avA�ho dolnA�ho rohu.

Pred otoA?enA�m

Rendered by QuickLaTeX.com

Po otoA?enA�

Rendered by QuickLaTeX.com

RieA?enie

PosaA?me obrA?zok do sA?radnicovA�ho systA�mu. Na otoA?enie celA�ho obrA?zku je potrebnA� otoA?it kaA?dy jeden bod.

Rendered by QuickLaTeX.com

Zoberme si naprA�klad bod [1;3]. VypoA?A�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 sA?radnice otoA?enA�ho bodu [-3;1].

Rendered by QuickLaTeX.com

Po otoA?enA� vA?etkA?ch bodov rovnakA?m spA?sobom zA�skame

Rendered by QuickLaTeX.com

Teda vA?eobecne, ak oznaA?A�me sA?radnice bodu, ktorA? chceme otoA?A? proti smeru hodinovA?ch ruA?iA?iek okolo poA?iatku sA?radnA�ho systA�mu ako [x;y], tak sA?radnice otoA?enA�ho bodu [x’;y’] vypoA?A�tame ako

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

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

Ako to funguje

DanA? je vektor u = (x,y) a chceme zA�skaA? sA?radnice otoA?enA�ho vektora v = (x’,y’). Uhol alfa oznaA?uje v stupA?och veA?kosA? samotnA�ho otoA?enie okolo poA?iatku sA?radnA�ho systA�mu, proti smeru hodinovA?ch ruA?iA?iek.

Rendered by QuickLaTeX.com

Matematicky vzatA�, chceme nA?jsA? funkciu f ktorA? vezme ako parameter vektor u a vrA?ti otoA?enA? vektor v

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

Bez toho aby sme zatiaA? A?okoA?vek rA?tali si vA?imnime dve dA?leA?itA� vlastnosti otoA?enia f

PrvA? vlastnosA?

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

pre A?ubovoA?nA� dva vektory u1 a u2.

IntuitA�vny dA?kaz. VidA�me, A?e keA? najskA?r osobitne otoA?A�me vektory u1 a u2 a potom uA? otoA?enA� sA?A�tame dostaneme to istA�, akoby sme rovno otoA?ili u1 + u2.

Rendered by QuickLaTeX.com

sa rovnA?

Rendered by QuickLaTeX.com

DruhA? vlastnosA?

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

pre vA?etky skalA?ry c a vektory u.

IntuitA�vny dA?kaz pre c = 2. vidA�me, A?e keA? najskA?r otoA?A�me vektor u a potom uA? otoA?enA? vektor f(u) vynA?sobA�me dvomi dostaneme ten istA? vektor a keby sme otoA?ili vektor 2.u.

Rendered by QuickLaTeX.com

je to istA� ako

Rendered by QuickLaTeX.com

Funkciu, ktorA? spA?A?a obe vlastnosti nazA?vame lineA?rne zobrazenie. Teda otoA?enie f je lineA?rne zobrazenie.

S tA?mto dA?leA?itA?m poznatkom sa vrA?A?me k pA?vodnej A?lohe nA?jsA? f takA�, A?e

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

S vlastnostA� vektorov vyplA?va

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

Ak oznaA?A�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*}

KvA?li tomu, A?e f je lineA?rne zobrazenie, nA?m teda staA?A� nA?jsA? iba prepisy f(e1) a f(e2) na otoA?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

PouA?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*}

VA?sledok

DosadenA�m prepisov (2) a (3) do odvodenia (1) a oznaA?enA�m zloA?iek otoA?enA�ho vektora v=(x’,y) dostA?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 zloA?kA?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

VA?sledok (4) moA?no zapA�saA? pomocou matA�c. Odteraz budeme vektory oznaA?ovaA? v stA?pcovom tvare s hranatA?mi zA?tvorkami

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

Zadefinujme maticu 2×2 ako objekt so A?tyrmi A?islami

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

ktorA? nasledovne zA?ava-nA?sobA� 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] \]

VA?imnime si, A?e vA?sledok nA?sobenia je vektor 2×1. S touto definA�ciou mA?A?eme (4) zapA�saA? 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] \]

PrA�klady matA�c otoA?enia

o 30 stupA?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 stupA?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 stupA?ov

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

Jednou z vA?hod tejto notA?cie je, A?e otoA?enia mA?A?eme skladaA?. Ak chceme naprA�klad vektor u=(1,2) otoA?iA? o 165 stupA?ov vyrA?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 skutoA?nosti sa kaA?dA� lineA?rne zobrazenie dA? zapisaA? pomocou matA�c. Tak mA?A?eme skladaA? naprA�klad otoA?enia s natiahnutiami a reflexiami.