Relacioni i përsëritjes

Relacion rekurent quajmë ekuacionin që shpreh termin e n-të të një sekuence në funksion të k termave paraardhës, për disa k të fiksuar (të pavarur nga n). Pasi jepen k termat fillestarë të një sekuence, relacioni rekurent lejon llogaritjen në mënyrë rekursive të të gjithë termave të sekuencës. 

Kushtet fillestare për një sekuencë të definuar në mënyrë rekursive specifikojnë termat që i paraprijnë termit n ku hyn në fuqi relacioni i rekurencës. Duke përdorur Induksionin Matematik ( një mënyrë vërtetimi në matematikë) mund të tregojmë se një relacion rekurent bashkë me kushtet fillestare të tij përcakton një zgjidhje unike. 

Shembuj
Vargu i Fibonaçit (Fibonacci Sequence)
Është emëruar pas matematikanit Italial Leonardo Fibonacci, i cili kishte lindur në shekullin e XII.

Vargu i Fibonaçit është seri e numrave ku secili numër është shuma e dy numrave paraardhës. Për shembull 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610...

Matematikisht e shkruajmë:

 : 

Këtë varg ( tash të famshëm ) për herë të parë Fibonaçi e prezantoi si zgjidhje për problemin e lepujve që thotë : Nëse një çift lepujsh i lëmë në një fushë (lepujt mund të riprodhohen pas 1 muaji, çdo lepur femër lindë një lepur mashkull dhe një femër dhe lepujt nuk ngordhin, kushte të pamundura biologjikisht), sa çifte lepujsh do të Kemi pas çdo muaji?

 Faktorieli 
Faktorieli funksion i rëndësishëm në matematikë (prodhim i të gjithë numrave natyrorë paraardhës të numrit të zgjedhur), gjithashtu mund të shprehet si relacion rekurent me kushte fillestare 0! = 1 dhe 1! = 1  ose më e kuptueshme nëse e shprehim faktorielin sikur një funksion () atëherë kemi:

.

 Koeficientët binomialë 
Një shembull i thjeshtë i një lidhjeje shumëdimensionale të përsëritjes jepet nga koeficientët binomialë , të cilët numërojnë numrin e mënyrave të zgjedhjes së elementeve nga një grup elementesh. 

Ato mund të llogariten nga relacioni i përsëritjes me rastet bazë . Përdorimi i kësaj formule për të llogaritur vlerat e të gjithë koeficientëve binomial gjeneron një grup të pafund të quajtur trekëndëshi i Paskalit. Të njëjtat vlera mund të llogariten gjithashtu drejtpërdrejt nga një formulë e ndryshme që nuk është një përsëritje, por përdor faktorialë, shumëzim dhe pjesëtim dhe jo vetëm mbledhje:

Koeficientët binomialë mund të llogariten gjithashtu edhe me një përsëritje njëdimensionale:

me vlerën fillestare  (Pjestimi nuk shfaqet si thyesë për të theksuar se duhet të llogaritet pas shumëzimit, për të mos futur numra thyesorë). Kjo përsëritje përdoret gjerësisht në kompjuterë sepse nuk kërkon të ndërtohet një tabelë siç bën përsëritja dydimensionale, dhe përfshin numra të plotë shumë të mëdhenj siç bën formula me faktorialë (nëse përdoret të gjithë numrat e plotë të përfshirë janë më të vegjël se rezultati përfundimtar).

 Zgjidhja e relacioneve rekurente lineare homogjene 

Releacionet rekurente mund të jetë vështirë të zgjidhen, por për relacionet rekurente homogjene mund të përdorim dy ide, e para këto relacione rekurente kanë zgjidhje të formës  ku r është konstante. Ndërsa ideja tjetër është se kombinimi linear i dy zgjidhjeve të relacioneve rekurente homogjene është gjithashtu një zgjidhje.

 Teoremë 
Le të jenë  dhe  numra real. Supozojmë se  ka dy rrënjë të ndryshme  dhe . Atëherë vargu {} është zgjidhje e relacionit rekurent  atëherë dhe vetëm atëherë kur  për n = 0, 1, 2, ..., ku 
dhe  janë konstante.

 Shembull 
Problemi: Cila është zgjidhja e relacionit rekurent  , me kushte fillestare  dhe  ?

Zgjidhje: Nga Teorema kemi:

 , ku r=2 dhe r= -1.

Pra, vargu {} është zgjidhje atëherë dhe vetëm atëherë kur:

, për disa konstante  dhe .

Prej kushteve fillestare formojmë sistemin:

Që pas zgjidhjes marrim   dhe .

Kështu që zgjidhja e relacionit rekurent homogjen  dhe kushteve fillestare të tij është vargu {} i shprehur:

 Aplikimet e relacioneve rekurente 

 Shkenca kompjuterike 
Relacionet rekurente kanë rëndësi të madhe në analizim të algoritmeve. Nëse një algoritëm është i dizajnuar që të ndajë një problem në probleme më të vogla, koha që kërkon ai algoritëm për ekzekutim është i shprehur me një relacion rekurent. 
Një shembull i thjeshtë është algoritmi për të gjetur një element specifik në një bashkësi elementesh, në rastin më të keq.
Një algoritëm naiv do të fillojë kërkimin prej anës së majtë në të djathtën, rasti më i keq është kur elementi gjendet në fund, pra numri i hapave është n.
Algoritëm më i mirë për këtë punë është algoritmi i kërkimit binarë (aplikohet vetëm në listë të rradhitur), ky algoritëm së pari shikon nëse vlera specifike gjendet në mes të listës, nëse jo, shikon nëse elementi që kërkojmë është më i vogël apo më i madh se elementi i mesit, në këtë pikë gjysma tjetër e listës mund të largohet dhe algoritmi rifillon ekzekutimin në gjysmën e mbetur.
Numri i hapave të këtij algoritmi mund të shprehet si relacion rekurent 

  me kusht fillestarë .

Kategoria:Algjebër