Rekurzív sorozat

A Wikipédiából, a szabad enciklopédiából

A matematikában a rekurzív sorozat egy olyan sorozat, ami definiálható egy rekurziós összefüggés segítségével. Utóbbi olyan képlet, összefüggés, ami a sorozat bármely elemét a megelőző néhány tag ismeretében adja meg (a pontos definíciót lásd lentebb).

Rekurzív vs. explicit képlet[szerkesztés | forrásszöveg szerkesztése]

Például az an+1=an+n; a1=0 rekurzív képlettel definiált sorozat tagjai rendre: 0, 1, 3, 6, 10, 15, ... (magyarul: bármely tagot úgy számolj ki, hogy az előző taghoz hozzáadod a sorszámát). Az a7=a6+6=21 tagot csak akkor tudjuk kiszámolni, ha előbb a hatodik tagot már kiszámoltuk. E sorozatra azonban explicit (a megelőző tagok ismeretét nem kívánó) képlet is adható: an= (n-1)·n/2. Sokszor épp az okoz gondot, hogy csak a megelőző tagok ismeretében tudunk számolni (ha az explicit képletet nehezebb megtalálni); ezért ha például egy számszerűen ismeretlen rekurzív sorozat 10000. tagját kívánjuk ismerni, akkor előtte mind a 9999 megelőző tagot végig kell számolni.

Tehát a fogalomnak bizonyos értelemben 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. Azonban, mint a fenti példából látható, a félrevezető név ellenére egy sorozat rekurzivitása nem az egyes sorozatok egy immanens tulajdonsága, hanem pusztán egy megadási mód (egy lehetséges a sok közül).

A két fogalom (rekurzív-explicit) szembeállítása 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. Bizonyos esetekben a rekurzív sorozat elemei kiszámíthatók zárt alakos kifejezéssel is (az előző tagok ismerete nélkül), ilyenek például a lineáris rekurzióval definiált sorozatok, mint amilyen a Fibonacci-számok sorozata is.

Alkalmazások[szerkesztés | forrásszöveg szerkesztése]

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 természetes számok (esetleg a pozitív egész számok) halmazán értelmezett f: \mathbb{N} \to 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.

Definíció[szerkesztés | forrásszöveg szerkesztése]

  • Egy S halmaz feletti (s_i)_{i \in \mathbb{N}} = (s_0, s_1, s_2, \ldots, s_i, \ldots) végtelen sorozatot m-edrendben rekurzívnak nevezünk, ha létezik olyan m-változós
\varphi\! : S^{m} \to S függvény,

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

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

tehát ha a sorozat bármely tagja a megelőző m darab 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 darab tagból számítható ki valamilyen módon.

Rend[szerkesztés | forrásszöveg szerkesztése]

Egy sorozatot akkor nevezünk (minden további jelző nélkül) rekurzívnak, ha van olyan m pozitív természetes szám, amelyre nézve m-edrendben rekurzív. Ha van ilyen pozitív szám, akkor a (pozitív) természetes számok halmazának jólrendezettsége miatt – azaz amiatt, hogy a pozitív természetes számok nem üres halmazában van egy legkisebb elem – van legkisebb ilyen pozitív 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 nm számra is n-edrendben rekurzív a sorozat.

Példák[szerkesztés | forrásszöveg szerkesztése]

  1. Legyen S = ℕ a természetes számok halmaza, ekkor az  \phi _{1} (n): \mathbb{N} \to \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.
  2. Legyen S = ℕ, és j∈ℕ rögzített természetes szám; a  \phi _{j} (n): \mathbb{N} \to \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.
  3. Legyen S = ℕ, és  \Phi (n,m): \mathbb{N} ^{2} \to \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 , … sn, sn+1 , sn+sn+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 rekurzió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 s2 = f(1) = 1 és 2 = s3 = f(s2) = 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.
  4. 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  \psi (a,b,c): \mathbb{N} ^{3} \to \mathbb{N} ; \psi (a,b,c) := a-b+c 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 s4 = a-b+c, az ötödik pedig s5 = b-c+(a-b+c) = a , a hatodik s6 = c-(a-b+c)+(a) = c-a+b-c+a = b , a hetedik s7 = (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 s2 = g(s1) = g(0) = 0 és s3 = g(s2) = 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ó.

A rekurzív sorozat állapotai[szerkesztés | forrásszöveg szerkesztése]

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

Periodikus és rekurzív sorozatok[szerkesztés | forrásszöveg szerkesztése]

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

 p \le p+k \le \left| S \right| ^{o(f)} = N ^{o(f)}

Külső hivatkozások[szerkesztés | forrásszöveg szerkesztése]