Am vazut in exemplul precedent cat de puternica si, in acelasi timp, cat de eleganta este recursivitatea in elaborarea unui algoritm.
Nu vom face o introducere in recursivitate si nici o prezentare a metodelor de eliminare a ei. Cel mai important castig al exprimarii recursive este faptul ca ea este naturala si compacta, fara sa ascunda esenta algoritmului prin detaliile de implementare. Pe de alta parte, apelurile recursive trebuie folosite cu discernamant, deoarece solicita si ele resursele calculatorului (timp si memorie). Analiza unui algoritm recursiv implica rezolvarea unui sistem de recurente. Vom vedea in continuare cum pot fi rezolvate astfel de recurente. Incepem cu tehnica cea mai banala.
Cu putina experienta si intuitie, putem rezolva de multe ori astfel de recurente prin metoda iteratiei: se executa primii pasi, se intuieste forma generala, iar apoi se demonstreaza prin inductie matematica ca forma este corecta.
Sa consideram de exemplu recurenta problemei turnurilor din Hanoi.
Pentru un anumit n > 1 obtinem succesiv Rezulta t (n) = 2n?1. Prin inductie matematica se demonstreaza acum cu usurinta ca aceasta forma generala este corecta.
Inductia 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.
si deci, f (n) ? O (n2). Aceasta ne sugereaza sa formulam ipoteza inductiei specificate partial IISP (n) conform careia f este de forma f (n) = an2?bn?c. 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 IISP (n?1) este adevarata pentru un anumit n ? 1. Atunci, f (n) = a (n?1) 2?b (n?1) ?c?n = an2? (1?b?2a) n?
(a?b?c) Daca dorim sa aratam ca IISP (n) este adevarata, trebuie sa aratam ca f (n) = an2?bn?c. Prin identificarea coeficientilor puterilor lui n, obtinem ecuatiile 1?b?2a = b si a?b?c = c, cu solutia a = b = 1/2, c putand fi oarecare. Avem acum o ipoteza mai completa, pe care o numim tot IISP (n): f (n) = n2/2?n/2?c. Am aratat ca, daca IISP (n?1) este adevarata pentru un anumit n ? 1, atunci este adevarata si IISP (n). Ramane sa aratam ca este adevarata si IISP (0). Trebuie sa aratam ca f (0) = a?0?b?0?c = c.
Stim ca f (0) = 0, deci IISP (0) este adevarata pentru c = 0. In concluzie, am demonstrat ca f (n) = n2/2?n/2 pentru orice n.
5. 3. 3 Recurente liniare omogene Exista, din fericire, si tehnici care ...
Pentru a descărca acest document,
trebuie să te autentifici in contul tău.
