Relacionet rekurente

Nga Wikipedia, enciklopedia e lirë
Jump to navigation Jump to search

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. [1]

Shembuj[Redakto | Redakto nëpërmjet kodit]

Vargu i Fibonaçit (Fibonacci Sequence)[Redakto | Redakto nëpërmjet kodit]

Ë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ë:

 : [2]

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[Redakto | Redakto nëpërmjet kodit]

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ë[Redakto | Redakto nëpërmjet kodit]

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[Redakto | Redakto nëpërmjet kodit]

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ë[Redakto | Redakto nëpërmjet kodit]

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.[3]

Shembull[Redakto | Redakto nëpërmjet kodit]

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[Redakto | Redakto nëpërmjet kodit]

Shkenca kompjuterike[Redakto | Redakto nëpërmjet kodit]

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

  1. ^ "Recurrence relation definition - Math Insight". mathinsight.org. Marrë më 2022-01-31. {{cite web}}: Mungon ose është bosh parametri |language= (Ndihmë!)
  2. ^ "The Fibonacci Sequence". www.imaginationstationtoledo.org (në anglisht). Marrë më 2022-01-31.
  3. ^ H.Rosen, Kenneth (2019). Discrete Mathematics and Its Applications (Eighth edition). New York: McGraw-Hill Education. {{cite book}}: Mungon ose është bosh parametri |language= (Ndihmë!)