Rekurencat

Relacionet rekurente

Në matematikë, një relacion rekurent është një ekuacion që shpreh termin e n-të të një sekuence në funksion të k termave paraardhës, për një k të fiksuar (të pavarura nga n), që quhet rendi i relacionit. Pasi jepen k termat fillestarë të një sekuence, relacioni i rekurencës lejon llogaritjen e të gjithë termave të atij vargu. Shpesh termi rekursiv përdoret si sinonim i fjalës “i llogaritshëm” sepse thuhet se një funksion mund të përcaktohet në mënyrë rekursive vetëm nëse ai mund të llogaritet nga ndonjë progam. Në rastin e përgjithshëm, një relacion rekurrent definohet me:

$a_n=f(a_{n-1},a_{n-2},...,a_0)$

Ku f është një funksion i dhënë.

Relacioni rekurent quhet linear nëse termi i n-të mund të shprehet si funksion linear i termave paraardhës. Rekurenca lineare është homogjene nëse nuk përmban terma që nuk janë shumëfisha të kufizave paraardhëse $a_i$.

Kështu, rekurenca lineare homogjene e shkallës k ka formën:

$a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+...+c_k{a}_{n-k}$

ku $c_1,c_2,...,c_k$ janë numra realë, dhe $c_k$ është i ndryshëm nga zero. Ndërsa relacioni rekurent quhet johomogjen nëse ka formën:

$a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+...+c_k{a}_{n-k}+F(n)$

ku $c_1,c_2,...,c_k$ janë numra realë dhe $F(n)$ është funksion jo-zero i cili varet vetëm nga n.

Shembuj

Vargu i Fibonaçit

Rekurenca e rendit të dytë e fituar nga numrat e Fibonaçit është shembull i një relacioni rekurent homogjen. Vargu i Fibonaçit është i definuar me ekuacionin

$F_n=F_{n-1}+F_{n-2},n\ge 2$

dhe kushtet fillestare

$F_0=0$

Trekëndëshi i Paskalit

$F_1=1$

Në mënyrë të qartë, sekuenca jep ekuacionet

Golden Ration- Vargu i Fibonaçit

$F_2=F_1+F_0,$

$F_3=F_2+F_1,$

$F_4=F_3+F_2,$$...$

Kështu fitojmë vargun me kufizat fillestare $0,1,1,2,3,5,8,13,21,34,...$

Këto kufiza formojnë edhe Relacionin e "Artë" .

Rekurenca mund të zgjidhet me formulën e Binetit, e cila përfshin fuqitë e dy rrënjëve të polinomit karakteristik $t^2=t+1$ dhe fitohet ekuacioni:

$F_n=\frac{1}{\surd 5}(\frac{1+\surd 5}{2}{)}^n-\frac{1}{\surd 5}(\frac{1-\surd 5}{2}{)}^n$ ,

ndërsa funksioni gjenerues i sekuencës është funksioni racional $\frac{t}{1-t-t^2}$ .

Kullat e Hanoit

Kullat e Hanoit 1

Kulla e Hanoit është një enigmë popullore e fundit të shekullit të nëntëmbëdhjetë e shpikur nga matematikani francez Édouard Lucas. Kjo enigmë përbëhet nga tre kunja të montuara në një tabelë së bashku me disqe të madhësive të ndryshme. Fillimisht këto disqe vendosen në kunjin e parë sipas madhësisë, me më të madhin në fund. Rregullat e enigmës lejojnë që disqet të zhvendosen një nga një nga një kunj në tjetrin për sa kohë që një disk nuk është kurrë i vendosur mbi një disk më të vogël. Qëllimi i enigmës është që të gjitha disqet të jenë në kunjin e dytësipas madhësisë, me më të madhin në fund.

Le të jetë $H_n$ numri i lëvizjeve të nevojshme për të zgjidhur enigmën e Kullës së Hanoit me n disqe. Gjejmë një relacion rekurent për sekuencën $H_n$.

Fillojmë me $n$ disqe në kunjën e parë. Ne mund t'i transferojmë $n-1$ disqet e sipërme në kunjën e tretë, duke ndjekur rregullat e enigmës, me $H_{n-1}$ lëvizje. Diskun më të madh e mbajmë të fiksuar gjatë këtyre lëvizjeve. Pastaj, e përdorim një lëvizje për të transferuar diskun më të madh në kunjin e dytë. Së fundmi, i transferojmë $n-1$ disqet tjera nga kunji 3 në kunjin 2 duke përdorur $H_{n-1}$ lëvizje përsëri. Kjo tregon se enigmën e Kullave të Hanoit me $n$ disqe mund t'a përfundojmë duke përdorur $2H_{n-1}+1$ lëvizje.

Kullat e Hanoit 2

Pra relacioni rekurent i formuar është:

$H_1=1$

$H_n=2H_{n-1}+1,n\ge 2$

me zgjidhjen e tij fitojmë ekuacionin: $H_n=2^n-1$

Vargu aritmetik dhe vargu gjeometrik

Vargu aritmetik është vargu i formës $a,a+d,a+2d,...$, pra, i cili fillon me një term a dhe secili term i rradhës fitohet duke ia shtuar termit paraardhës numrin d. Kështu vërejmë se vargu aritmetik mund të definohet në mënyre rekurente me

$a_1=a$ dhe

$a_{k+1}=a_k+d,k\ge 1$

Zgjidhja e kësaj rekurence jep ekuacionin:

$a_n=a+(n-1)d$

Ndërsa vargu gjeometrik i cili ka formën $a,ar,a{r}^2,a{r}^3,...$ mund të definohet në formë rekursive si:

$a_1=a$ dhe

$a_{k+1}=r{a}_k,k\ge 1$

Zgjidhja e të cilit do të ishte: $a_{n+1}=a{r}^n$

Koeficientët binomialë

Koeficientët binomialë $(\genfrac{}{}{0ex}{}{n}{k})$ , të cilët numërojnë në sa mënyra mund të zgjedhen k elemente nga bashkësia me n elemente janë shembull i relacioneve rekurente shumëdimensionale. Për t'i shprehur këta koeficientë në formë rekursive përdoret Identiteti i Paskalit

$(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n-1}{k})+(\genfrac{}{}{0ex}{}{n-1}{k-1})$

me kushtet fillestare:

$(\genfrac{}{}{0ex}{}{n}{0})=(\genfrac{}{}{0ex}{}{n}{n})=1$

Me këto formula gjenerohet vargu i pafundëm i njohur si Trekëndëshi i Paskalit. Këta terma gjenden edhe me formulën:

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{k!(n-k)!}$

Zgjidhja e relacioneve rekurente homogjene

Jo të gjitha relacionet rekurente mund të zgjidhen, por në vijim po shqyrtojmë rastet që mund të zgjidhen me metodën e zevendësimit dhe metodën e koeficientëve konstantë - ekuacionit karakteristik.

Zgjidhja me metodën e zëvendësimit

Metoda më e thjeshtë e zgjidhjes së relacioneve rekurente është metoda e zëvendësimit. Fillimihst e zëvendësojmë vlerën e $a_{n-1}$ në ekuacionin e dhënë, pastaj vlerën e $a_{n-2}$, $a_{n-3}$, etj. Dhe kështu, tek relacionet rekurente të rendit të parë do të mund të vërejmë një ekuacion i cili më pas duhet të vërtetohet, p.sh. me anë të iduksionit matematik.

Kjo metodë funksionon mirë vetëm për relacionet e rendit të parë, dhe për disa relacione të rendit të dytë.

Zgjidhja me anë të ekuacionit karakteristik kur rrënjët janë të ndryshme

Le të jenë $c_1,c_2,...,c_k$ numra realë. Supozojmë se ekuacioni karakteristik

$r^k-c_1{r}^{k-1}=...-c^k=0$

ka $k$ rrenje $r_1,r_2,...,r_k$. Atëherë vargu $\{a_n\}$ është zgjidhje e relacionit rekurent

$a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+...+c_k{a}_{n-k}$

atëherë dhe vetëm atëherë kur

$a_n={\alpha }_1{r}_1^n+{\alpha }_2{r}_2^n+...+{\alpha }_k{r}_k^n$

për $n=1,2,...$ ku ${\alpha }_1,{\alpha }_2,...,{\alpha }_k$ janë konstante.

Zgjidhja me anë të ekuacionit karakteristik kur rrënjët mund të mos jenë të gjitha të ndryshme

Le të jenë $c_1,c_2,c_3,...,c_k$ numra realë. Supozoni se ekuacioni karakteristik

$r^k-c_1{r}^{k-1}-...-c_k=0$

ka $t$ rrënjë të ndryshme $r_1,r_2,...,r_t$ me shumëfisha $m_1,m_2,...,m_t$, përkatësisht, pra që $m_1\ge 1$ për $i=1,2,...,t$ dhe $m_1+m_2+...+m_t=k$. Atëherë një varg $\{a_n\}$ është një zgjidhje e relacionit rekurent

$a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+...+c_k{a}_{n-k}$

nëse dhe vetëm nëse

$a_n=({\alpha }_{1,0}+{\alpha }_{1,1}n+...+{\alpha }_{1,m_1-1}{n}^{m_1-1})r_1^n$

$+({\alpha }_{2,0}+{\alpha }_{2,1}n+...+{\alpha }_{2,m_2-1}{n}^{m_2-1})r_2^n$

$+...+({\alpha }_{t,0}+{\alpha }_{t,1}n+...+{\alpha }_{t,m_t-1}{n}^{m_t-1})r_t^n$

për $n=0,1,2,...,$ ku ${\alpha }_{i,j}$ janë konstante për $1\le i\le t$ dhe $1\le j\le m_i-1$.

Zgjidhja e relacioneve rekurente johomogjene

Rikujtojmë se relacioni rekurent johomogjen kishte formën:

$a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+...+c_k{a}_{n-k}+F(n)$

ku $c_1,c_2,...,c_k$ janë numra realë dhe $F(n)$ është funksion jo-zero i cili varet vetëm nga n.

Shënojmë $a_n^{(h)}=c_1{a}_{n-1}+c_2{a}_{n-2}+...+c_k{a}_{n-k}$ pjesën homogjene të relacionit dhe $a_n^{(p)}=F(n)$ pjesën partikulare. Atëherë çdo zgjidhje e rekurencës do të jetë e formës $a_n^{(h)}+a_n^{(p)}$.

Nëse $F(n)$ mund t'a shënojmë në formën:

$F(n)=(b_t{n}^t+b_{t-1}{n}^{n-1}+...+b_{1}n+b_0)s^n$

ku $b_0,b_1,...,b_n,s$ janë numra realë dallojmë dy raste:

• Nëse $s$ nuk është zgjidhje e ekuacionit karakteristik të pjesës homogjene atëherë një zgjidhje partikulare merret:

$a_n^{(p)}=(p_t{n}^t+p_{t-1}{n}^{t-1}+...+p_{1}t+p_0)s^n$.

• Nëse $s$ është zgjidhje e $m$-fishtë e ekuacionit karakteristik të pjesës homogjene, atëherë një zgjidhje partikulare merret:

$n^m{a}_n^{(p)}=(p_t{n}^t+p_{t-1}{n}^{t-1}+...+p_{1}t+p_0)s^n$.

Aplikimi

Biologji

Shtimi i popullatës së lepujve sipas vargut të Fibonaçit

Algoritmi i kërkimit binar

Disa nga relacionet më të njohura të rekuerencës e kanë origjinën në përpjekjet për të modeluar dinamikën erritjes së popullsisë. Për shembull, numrat e Fibonaçit dikur u përdorën si model për rritjen e një popullate lepujsh.Madje, relacionet rekurente shpesh përdoren për të modeluar ndërveprimin e dy ose më shumë popullatave. Për shembull, modeli Nicholson-Bailey për një ndërveprim organizëm-parazit jepet nga

$N_{t+1}=\lambda N_t{e}^{-a{P}_t}$

$P_{t+1}=N+t(1-e^{-1P_t})$

ku $N_t$ përfaqëson organizmat e infektuar, dhe $P_t$ parazitët, në kohën $t$ .

Shkenca kompjuterike

Relacionet rekurente janë gjithashtu të një rëndësie themelore në analizën e algoritmeve. Nëse një algoritëm është projektuar në mënyrë që të ndajë një problem në nënprobleme më të vogla (përçaj dhe sundo), koha e ekzekutimit të tij përshkruhet nga një relacion rekurent.

Një shembull i thjeshtë është koha që i duhet një algoritmi për të gjetur një element në një varg të renditur me $n$ elementë, në rastin më të keq.

Një algoritëm naiv do të kërkojë nga e majta në të djathtë, një element në të njëjtën kohë. Skenari më i keq i mundshëm është kur elementi i kërkuar është i fundit, kështu që numri i krahasimeve është $n$ .

Një algoritëm më i mirë është algoritmi i kërkimit binar. Megjithatë, ai kërkon një varg të renditur. Së pari do të kontrollojë nëse elementi është në mes të vargut. Nëse jo, atëherë do të kontrollojë nëse elementi i mesëm është më i madh apo më i vogël se elementi i kërkuar. Në këtë pikë, gjysma e vargut mund të hidhet poshtë dhe algoritmi mund të ekzekutohet përsëri në gjysmën tjetër. Numri i krahasimeve do të jepet nga relacioni rekurent

$c_1=1$

$c_n=1+c_{n/2},n\ge 2$

kompleksiteti kohor i të cilit do të jetë $O(lo{g}_2(n))$ .