...ematica se demonstreaza acum cu usurinta ca aceasta forma generala este corecta.5.3.2 Inductia constructivaInductia matematica este folosita de obicei ca tehnica de demonstrare a unei asertiuni deja enuntate. Vom vedea in aceasta sectiune ca inductia matematica poate fi utilizata cu succes si in descoperirea enuntului asertiunii. Aplicand aceasta tehnica, putem simultan sa demonstram o asertiune doar partial specificata si sa descoperim specificatiile care lipsesc si datorita carora asertiunea este corecta. Vom vedea ca aceasta tehnica a inductiei constructive este utila pentru rezolvarea anumitor recurente care apar in contextul analizei algoritmilor. Incepem cu un exemplu.Fie functia f N N, definita prin recurentaINCLUDEPICTURE td imagescap5cap5s16.gifSa presupunem pentru moment ca nu stim ca f n nn12 si sa cautam o astfel de formula. AvemINCLUDEPICTURE td imagescap5cap5s17.gifsi deci, f n I On2. Aceasta ne sugereaza sa formulam ipoteza inductiei specificate partial IISPn conform careia f este de forma f n an2bnc. Aceasta ipoteza este partiala, in sensul ca a, b si c nu sunt inca cunoscute. Tehnica inductiei constructive consta in a demonstra prin inductie matematica aceasta ipoteza incompleta si a determina in acelasi timp valorile constantelor necunoscute a, b si c.Presupunem ca IISPn-1 este adevarata pentru un anumit n 1. Atunci,f n an-12bn-1cn an21b-2ana-bcDaca dorim sa aratam ca IISPn este adevarata, trebuie sa aratam ca f n an2bnc. Prin identificarea coeficientilor puterilor lui n, obtinem ecuatiile 1b-2a b si a-bc c, cu solutia a b 12, c putand fi oarecare. Avem acum o ipoteza mai completa, pe care o numim tot IISPn f n n22n2c. Am aratat ca, daca IISPn-1 este adevarata pentru un anumit n 1, atunci este adevarata si IISPn. Ramane sa aratam ca este adevarata si IISP0. Trebuie sa aratam ca f 0 a0b0c c. Stim ca f 0 0, deci IISP0 este adevarata pentru c 0. In concluzie, am demonstrat ca f n n22n2 pentru orice n.5.3.3 Recurente liniare omogeneExista, din fericire, si tehnici care pot fi folosite aproape automat pentru a rezolva anumite clase de recurente. Vom incepe prin a considera ecuatii recurente liniare omogene, adica de formaa0tn a1tn-1 aktn-k 0 unde ti sunt valorile pe care le cautam, iar coeficientii ai sunt constante.Conform intuitiei, vom cauta solutii de formatn xnunde x este o constanta deocamdata necunoscuta. Incercam aceasta solutie in si obtinema0xn a1xn-1 ... akxn-k 0Solutiile acestei ecuatii sunt fie solutia triviala x 0, care nu ne intereseaza, fie solutiile ecuatieia0xk a1xk-1 ... ak 0care este ecuatia caracteristica a recurentei .Presupunand deocamdata ca cele k radacini r1, r2, ..., rk ale acestei ecuatii caracteristice sunt distincte, orice combinatie liniaraINCLUDEPICTURE td imagescap5cap5s18.gifeste o solutie a recurentei , unde constantele c1, c2, ..., ck sunt determinate de conditiile initiale. Este remarcabil ca are numai solutii de aceasta forma.Sa exemplificam prin recurenta care defineste sirul lui Fibonacci din Sectiunea 1.6.4tn tn-1 tn-2 n 2iar t0 0, t1 1. Putem sa rescriem aceasta recurenta sub formatn - tn-1 - tn-2 0care are ecuatia caracteristicax2 - x - 1 0cu radacinile r1,2 1INCLUDEPICTURE td imagescap5cap5s19.gif 2. Solutia generala are formaINCLUDEPICTURE td imagescap5cap5s20.gifImpunand conditiile initiale, obtinemc1 c2 0 n 0r1c1 r2c2 1 n 1de unde determinamc1,2 INCLUDEPICTURE td imagescap5cap5s21.gifDeci, INCLUDEPICTURE td imagescap5cap5s22.gif. Observam ca r1 f 1INCLUDEPICTURE td imagescap5cap5s23.gif2, r2 -f-1 si obtinemINCLUDEPICTURE td imagescap5cap5s24.giffn--f-ncare este cunoscuta relatie a lui de Moivre, descoperita la inceputul secolului XVI. Nu prezinta nici o dificultate sa aratam acum ca timpul pentru algoritmul fib1 din Sectiunea 1.6.4 este in Qfn.Ce facem insa atunci cand radacinile ecuatiei caracteristice nu sunt distincte Se poate arata ca, daca r este o radacina de multiplicitate m a ec...
Download