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:

${\displaystyle 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:

${\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+...+c_{k}a_{n-k}}$

ku ${\displaystyle c_{1},c_{2},...,c_{k}}$ janë numra realë, dhe ${\displaystyle c_{k}}$ është i ndryshëm nga zero. Ndërsa relacioni rekurent quhet johomogjen nëse ka formën:

${\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+...+c_{k}a_{n-k}+F(n)}$

ku ${\displaystyle c_{1},c_{2},...,c_{k}}$ janë numra realë dhe ${\displaystyle 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

${\displaystyle F_{n}=F_{n-1}+F_{n-2},n\geq 2}$

dhe kushtet fillestare

${\displaystyle F_{0}=0}$

Trekëndëshi i Paskalit

${\displaystyle F_{1}=1}$

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

Golden Ration- Vargu i Fibonaçit

${\displaystyle F_{2}=F_{1}+F_{0}},$

${\displaystyle F_{3}=F_{2}+F_{1}},$

${\displaystyle F_{4}=F_{3}+F_{2}},$$...$

Kështu fitojmë vargun me kufizat fillestare ${\displaystyle 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 ${\displaystyle t^{2}=t+1}$ dhe fitohet ekuacioni:

${\displaystyle 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 ${\displaystyle {\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ë ${\displaystyle 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 ${\displaystyle H_{n}}$.

Fillojmë me ${\displaystyle n}$ disqe në kunjën e parë. Ne mund t'i transferojmë ${\displaystyle n-1}$ disqet e sipërme në kunjën e tretë, duke ndjekur rregullat e enigmës, me ${\displaystyle 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ë ${\displaystyle n-1}$ disqet tjera nga kunji 3 në kunjin 2 duke përdorur ${\displaystyle H_{n-1}}$ lëvizje përsëri. Kjo tregon se enigmën e Kullave të Hanoit me ${\displaystyle n}$ disqe mund t'a përfundojmë duke përdorur ${\displaystyle 2H_{n-1}+1}$ lëvizje.

Kullat e Hanoit 2

Pra relacioni rekurent i formuar është:

${\displaystyle H_{1}=1}$

${\displaystyle H_{n}=2H_{n-1}+1,n\geq 2}$

me zgjidhjen e tij fitojmë ekuacionin: ${\displaystyle H_{n}=2^{n}-1}$

Vargu aritmetik dhe vargu gjeometrik

Vargu aritmetik është vargu i formës ${\displaystyle 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

${\displaystyle a_{1}=a}$ dhe

${\displaystyle a_{k+1}=a_{k}+d,k\geq 1}$

Zgjidhja e kësaj rekurence jep ekuacionin:

${\displaystyle a_{n}=a+(n-1)d}$

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

${\displaystyle a_{1}=a}$ dhe

${\displaystyle a_{k+1}=ra_{k},k\geq 1}$

Zgjidhja e të cilit do të ishte: ${\displaystyle a_{n+1}=ar^{n}}$

Koeficientët binomialë

Koeficientët binomialë ${\tbinom {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

${\binom {n}{k}}={\binom {n-1}{k}}+{\binom {n-1}{k-1}}$

me kushtet fillestare:

${\binom {n}{0}}={\binom {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:

${\binom {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 ${\displaystyle a_{n-1}}$ në ekuacionin e dhënë, pastaj vlerën e ${\displaystyle a_{n-2}}$, ${\displaystyle 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

${\displaystyle r^{k}-c_{1}r^{k-1}=...-c^{k}=0}$

ka $k$ rrenje ${\displaystyle r_{1},r_{2},...,r_{k}}$. Atëherë vargu $\{a_{n}\}$ është zgjidhje e relacionit rekurent

${\displaystyle 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

${\displaystyle 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ë ${\displaystyle c_{1},c_{2},c_{3},...,c_{k}}$ numra realë. Supozoni se ekuacioni karakteristik

${\displaystyle r^{k}-c_{1}r^{k-1}-...-c_{k}=0}$

ka ${\displaystyle t}$ rrënjë të ndryshme ${\displaystyle r_{1},r_{2},...,r_{t}}$ me shumëfisha ${\displaystyle m_{1},m_{2},...,m_{t}}$, përkatësisht, pra që ${\displaystyle m_{1}\geq 1}$ për ${\displaystyle i=1,2,...,t}$ dhe ${\displaystyle m_{1}+m_{2}+...+m_{t}=k}$. Atëherë një varg $\{a_{n}\}$ është një zgjidhje e relacionit rekurent

${\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+...+c_{k}a_{n-k}}$

nëse dhe vetëm nëse

${\displaystyle a_{n}=(\alpha _{1,0}+\alpha _{1,1}n+...+\alpha _{1,m_{1}-1}n^{m_{1}-1})r_{1}^{n}}$

${\displaystyle +(\alpha _{2,0}+\alpha _{2,1}n+...+\alpha _{2,m_{2}-1}n^{m_{2}-1})r_{2}^{n}}$

${\displaystyle +...+(\alpha _{t,0}+\alpha _{t,1}n+...+\alpha _{t,m_{t}-1}n^{m_{t}-1})r_{t}^{n}}$

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

Zgjidhja e relacioneve rekurente johomogjene

Rikujtojmë se relacioni rekurent johomogjen kishte formën:

${\displaystyle a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+...+c_{k}a_{n-k}+F(n)}$

ku ${\displaystyle c_{1},c_{2},...,c_{k}}$ janë numra realë dhe ${\displaystyle F(n)}$ është funksion jo-zero i cili varet vetëm nga n.

Shënojmë ${\displaystyle a_{n}^{(h)}=c_{1}a_{n-1}+c_{2}a_{n-2}+...+c_{k}a_{n-k}}$ pjesën homogjene të relacionit dhe ${\displaystyle a_{n}^{(p)}=F(n)}$ pjesën partikulare. Atëherë çdo zgjidhje e rekurencës do të jetë e formës ${\displaystyle a_{n}^{(h)}+a_{n}^{(p)}}$.

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

${\displaystyle F(n)=(b_{t}n^{t}+b_{t-1}n^{n-1}+...+b_{1}n+b_{0})s^{n}}$

ku ${\displaystyle b_{0},b_{1},...,b_{n},s}$ janë numra realë dallojmë dy raste:

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

${\displaystyle a_{n}^{(p)}=(p_{t}n^{t}+p_{t-1}n^{t-1}+...+p_{1}t+p_{0})s^{n}}$.

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

${\displaystyle 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

${\displaystyle N_{t+1}=\lambda N_{t}e^{-aP_{t}}}$

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

ku ${\displaystyle N_{t}}$ përfaqëson organizmat e infektuar, dhe ${\displaystyle P_{t}}$ parazitët, në kohën ${\displaystyle 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 ${\displaystyle 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ë ${\displaystyle 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

${\displaystyle c_{1}=1}$

${\displaystyle c_{n}=1+c_{n/2},n\geq 2}$

kompleksiteti kohor i të cilit do të jetë ${\displaystyle O(log_{2}(n))}$ .