Rekurzív sorozat

A Wikipédiából, a szabad lexikonból.

A rekurzív sorozat olyan sorozat, melynek elemeit a sorozatban a megelőző elemek ismeretében lehet kiszámítani. A pontos definíciót ld. lentebb.

Sokszor épp az okoz gondot, hogy csak a megelőző tagok ismeretében tudunk számolni; ezért ha pl. egy rekurzív sorozat 2004.-edik tagját akarjuk kiszámolni; mind a 2004 tagot végig kell számolni. Tehát a fogalomnak bizonyos mértékben ellenpárja az általánosan, képlettel megadott sorozat fogalma, mely utóbbi azt jelenti, hogy ha kíváncsiak vagyunk a sorozat valamely tagjára/elemére, azt az előző tagok ismerete nélkül is, explicite ki tudjuk számolni. Utóbbi fogalom kissé elmosódott és pragmatikus (azaz matematikailag nehezen lenne precízen értelmezhető, mivel gyakorlatilag minden függvény és sorozat, már a természetes számok 1,2,3,... sorozata is tkp. rekurzív); de a gyakorlatban fontos ez a megkülönböztetés.

Mind a rekurzív sorozat fogalma, mind a fenti probléma a matematika szinte minden ágában előfordul (de különösen a számítógéptudományban, a kombinatorikában, a numerikus analízisben, és az elemi matematikában), de az informatika számára is nagyon fontos, mivel az általános tagot számítgató emberrel ellentétben a gépek viszont a rekurzív sorozatokkal boldogulnak jobban.

Jelölések és előzetes megállapodások: Adott S halmazba képező, a szám (esetleg nemnegatív) természetes számok halmazán értelmezett $f: \mathbb{N} ^{+} \mapsto S$ függvényt az S feletti végtelen sorozatnak nevezünk; $i \in \mathbb{N}$ esetén pedig az $f (i) \in S$ elemet a sorozat i-edik tagjának nevezzük és $s i$ -vel jelöljük. Magát a sorozatot $\left\{ s_{i} \right\}$ -vel vagy $\left( s_{i} \right) _{ i \in \mathbb{N} }$ -nel vagy hasonló módon jelöljük.

[szerkesztés] Definíció

Egy S halmaz feletti $\left( s_{i} \right)_{i \in \mathbb{N} ^{+} } = \left( s_{1} , s_{2} , \cdots , s_{i} , ... \right)$ végtelen sorozatot m-edrendben rekurzívnak nevezünk, ha létezik olyan n-változós

$\varphi : S^{m} \mapsto S$ függvény,

mellyel tetszőleges nemnegatív egész $i$ indexre

$s_{i+m} = \varphi \left( s_{i} , s_{i+1}, ... , s_{i+m-1} \right)$ ;

tehát ha a sorozat bármely tagja a megelőző m db. tagból a fenti m-változós függvény segítségével számolható ki. A $\varphi$ függvény a rekurziós szabály (-előírás, -összefüggés , -kapcsolat, egyenlet stb.). Arról van szó tehát, hogy a sorozat bármely tagja az őt megelőző m db. tagból számítható ki valamilyen módon.

[szerkesztés] Rend

Egy sorozatot akkor nevezünk (minden további jelző nélkül) rekurzívnak, ha van olyan m természetes szám, amelyre nézve m-edrendben rekurzív. Ha van ilyen szám, akkor a természetes számok halmazának jólrendezettsége miatt – azaz amiatt, hogy természetes számok nem üres halmazában van egy legkisebb elem – van legkisebb ilyen szám is, melyet a sorozat minimális rekurziós rendjének nevezünk, és $o \left( f \right)$ -fel jelölünk (az o betű utalás a latin ordo = rend szóra). A minimális rekurziós rend egyértelmű, de ettől eltekintve egy sorozat ha m-rendben rekurzív, attól lehet más rendben is rekurzív: belátható, hogy ha a minimális rekurziós rend m, akkor minden ennél nagyobb n≥m számra is n-edrendben rekurzív a sorozat.

[szerkesztés] Példák

Legyen S = ℕ a természetes számok halmaza, ekkor az $\phi _{1} (n): \mathbb{N} \mapsto \mathbb{N} ; \phi _{1} (n) := n+1$ függvényt véve, $s 1 : = 0$ esetén a következő elsőrendben rekurzív sorozatot kapjuk: 0, 1, 2, 3, 4, ... ; ennek értékkészlete a természetes számok halmaza.
Legyen S = ℕ, és j∈ℕ rögzített természetes szám; a $\phi _{j} (n): \mathbb{N} \mapsto \mathbb{N} ; \phi _{j} (n) := n+j$ függvényt véve, a $s 1 : = 0$ megállapodással a 0, 0+j = j, j+j = 2j, 2j+j = 3j , ... egyszóval a 0, j, 2j, 3j , ... sorozatot kapjuk, vagyis a j-vel osztható számok sorozatát.
Legyen S = ℕ, és $\Phi (n,m): \mathbb{N} ^{2} \mapsto \mathbb{N} ; \Phi (n,m) := n+m$ . Ekkor a $s 1 : = 1, s 2 : = 1$ megállapodással a következő másodrendben rekurzív sorozatot kapjuk: 1, 1, 1+1 = 2 , 1+2 = 3 , 2+3 = 5, 3+5 = 8 , ... s_n, s_n+1 , s_n+s_n+1 , ... sorozatot kapjuk; minden elem a két megelőző elem összege. ez a híres Fibonacci-sorozat (1, 1, 2, 3, 5, 8, 13, 21, 34 , ...), amely másodrendben rekurzív. Minimális rekurzós rendje is 2, ugyanis nem állítható elő egyváltozós f(n) függvény segítségével rekurzív módon; mivel s₂ = f(1) = 1 és 2 = s₃ = f(s₂) = f(1) miatt f(n) az n = 1 helyen az 1 és 2 értéket is fel kellene hogy vegye, így nem (lenne) függvény.
Adott rekurzióval számított sorozatok esetén a kezdőelemek (a kezdőállapot) megválasztása hatással lehet a minimális rekurziós rendre. Legyen most S = ℤ, és tekintsük a rekurziót.
1. Ha például a $s 1 : = 0, s 2 : = 0, s 3 : = 0$ megállapodással indítunk, akkor a sorozat összes értéke 0 lesz: 0,0,0, 0-0+0 = 0, 0-0+0 = 0, ... , tehát a csupa 0-ból álló sorozatot kapjuk. Ez viszont már elsőrendben is rekurzív.
2. Ha meg például az $s 1 : = 0, s 2 : = 0, s 3 : = 1$ megállapodással indítunk, akkor a sorozat periodikus lesz : 0,0,1, 0-0+1 = 1, 0-1+1 = 0, 1-1+0 = 0, 1-0+0 = 1, 0-0+1 = 1 , ...; tehát a 0,0,1,1,0,0,1,1, ... sorozatot kapjuk. Ez nem meglepő, hisz a sorozat első három a,b,c tagját bárhogy is megválasztva a negyedik tag s₄ = a-b+c, az ötödik pedig s₅ = b-c+(a-b+c) = a , a hatodik s₆ = c-(a-b+c)+(a) = c-a+b-c+a = b , a hetedik s₇ = (a-b+c)-(a)+b = c, tehát a sorozat így néz ki: a,b,c,a-b+c, a,b,c,a-b+c ... Másrészt ez a sorozat már 2-rendben is rekurzív, ugyanis a kétváltozós f(x,y)=1-x függvény is generálja (ez csak egy változótól függ igazán, de két változós). A sorozat minimális rekurziós rendje pedig 2, mert egyváltozós g(x) függvény nem generálja: ugyanis s₂ = g(s₁) = g(0) = 0 és s₃ = g(s₂) = g(0) = 1 is teljesülne, azaz g(0) = 0 = 1, márpedig nem igaz, hogy 0 = 1 .
3. Belátható azonban, hogy bármilyen kezdőelemekből is induljunk ki, a fenti rekurzióval adott sorozatok mindig már másodrendben is rekurzívak lesznek, bármilyen, az f(a,b) = c; f(b,c) = a-b+c; f(c, a-b+c) = a , f(a-b+c,a) = b előírással értelmezett függvénnyel. Némi számolással ellenőrizhető, hogy ilyen függvény létezik (ha (x,y)=(x',y'), akkor f(x,y)=f(x',y') teljesül, amennyiben (x,y) a fent megnevezett rendezett párok közül kerülnek ki), egy konkrét példánya pedig valamilyen interpolációs eljárással kereshető (utóbbi esetben a függvény egy polinom lesz); vagy akár a megnevezett rendezett párok kivételével akár mindenütt máshol 1-nek is definiálható.

[szerkesztés] A rekurzív sorozat állapotai

E szakasz szerint egy m-edrendű rekurzív sorozatot (ahogy az sejthető) az első m eleme tökéletesen meghatározza.

Az $s^{i} := \left( s_{i} , s_{i+1} , ... , s_{i+m-1} \right)$ elem-m-est a sorozat i-edik állapotának nevezzük, $s^{0} := \left( s_{0} , s_{1} , ... , s_{m-1} \right)$ -et, tehát az első m db. elemét (az első állapotot) kezdőállapotnak. Belátható, hogy a kezdőállapot egyértelműen meghatározza a rekurzív sorozat bármelyik elemét, tehát az egész sorozatot; a k-adik állapot pedig a sorozat bármely, k-nál nagyobb (ti. nem kisebb) indexű elemét.

Előbbi, kezdőállapotra vonatkozó tétel teljes indukcióval látható be (az azt követő állítás is, hasonlóan): adottak az $s^{1} := \left( s_{1} , s_{2} ... , s_{m-1} , s_{m} \right)$ elemek, ezek tehát meghatározottak, továbbá ekkor $s_{m+1} = \varphi \left( s_{1} , s_{2} , ... , s_{m} \right)$ is egyértelműen kiszámolható a $\varphi$ függvény segítségével, ugyanígy az $s^{2} := \left( s_{2} , s_{3} , ... , s_{m+1} \right)$ elemekből $s_{m+2} = \varphi \left( s_{2} , s_{3} , ... , s_{m+1} \right)$ , ... és ha már valamilyen k-ra (k ≥ m) ismerjük a sorozat összes elemét, akkor az utolsó, k-adik elemtől visszafelé számolva, az utolsó m db. elemből: $s^{k-m+1} := \left( s_{k-(m-1)} , ... , s_{k-1} , s_{k} \right) = \left( s_{k-m+1} , s_{k-m+2} , ... , s_{k-m+m} \right)$ állapotból a következő, k+1-edik elem is kiszámolható: $s_{k+1} := \varphi \left( s_{k-m+1} , s_{k-m+2} , ... , s_{k} \right)$ .

[szerkesztés] Periodikus és rekurzív sorozatok

Belátható, hogy ha egy S-sorozat a k küszöbindextől kezdve periodikus a p (minimális) periódussal, akkor rekurzív, és rendje legfeljebb a küszöbindex és a periódus összege:

$o(f) \le p+k$

Érdekes, hogy ha S véges halmaz (elemeinek száma N), akkor tkp. fordítva is igaz: ha $f$ rekurzív, akkor periodikus is, és minimális p periódusára érvényes