Relazione di ricorrenza: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
m →Collegamenti esterni: Bot: +controllo di autorità |
m Bot: fix citazione web (v. discussione) |
||
Riga 3:
:<math>f(x_n,x_{n+1},\dots,x_{n+k})=0</math>
Il numero <math>k</math> viene detto ''ordine della relazione''.
Vi sono anche relazioni di ricorrenza che riguardano più successioni, matrici infinite e successioni con tre o più indici. In genere le relazioni di ricorrenza sono accompagnate da condizioni iniziali tali da rendere possibile, almeno in linea di principio, la valutazione dei componenti della successione.
Riga 10:
Il [[fattoriale]] del numero naturale ''n'', ''n''!, viene definito da:
:<math> 0! := 1 ~; \quad n! := n\cdot(n-1)! ~~~\mathrm{per}~~ n=1, 2, 3, \dots </math>
e per i primi fattoriali si trovano i valori: 1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800 ...
Riga 37:
:<math>c_nx_n + c_{n+1}x_{n+1}+ ... c_{n+k}x_{n+k} + c_0 \,=\, 0</math>
con i coefficienti <math>\,c_m</math> costanti, non dipendenti dagli <math>\,x_n</math>. Si parla di ''relazione di ricorrenza lineare omogenea'' nel caso sia <math> c_0 \,=\,0</math>. Le relazioni di ricorrenza lineari come le precedenti devono essere accompagnate da <math>k</math> condizioni iniziali; infatti, se si assegnano i primi <math>k</math> termini, seguendo qualsivoglia criterio, la stessa ricorrenza riscritta come assegnazione di un valore a <math>\,x_{n+k}</math> implica la determinazione univoca dei successivi termini della successione.
Le relazioni di ricorrenza lineari possono essere risolte con procedimenti sistematici, spesso utilizzando le [[funzione generatrice|funzioni generatrici]] (ovvero le [[serie formale di potenze|serie formali di potenze]]), oppure osservando che <math>\,r^n</math> è una soluzione per particolari valori di <math>r</math>.
Riga 82:
== Analisi di procedure ricorsive ==
{{vedi anche|funzione generatrice}}
Molti classici [[algoritmo|algoritmi]] possono essere descritti tramite procedure ricorsive. Di conseguenza l'analisi dei relativi tempi di calcolo è ridotta alla soluzione di una o più equazioni di ricorrenza nelle quali si esprime il termine n-esimo di una sequenza in funzione dei precedenti.
Se si vuole analizzare la complessità di un algoritmo mediante un insieme di procedure P1,P2,P3,...Pm che si richiamano tra di loro si sfrutta la funzione <math>T_i(n)</math> che rappresenta il tempo di calcolo impiegato dall'i-ma procedura su dati di dimensione n. Se la procedura richiama sé stessa diminuendo l'ordine dei dati la si può descrivere come <math>T_i(k)</math>, dove <math>k</math> è un valore minore di <math>n</math>.
Analizzando una sola procedura che richiama sé stessa si può impostare la seguente relazione di ricorrenza:
:<math>T(n)\leq f_n(T(n-1),\dots,(2),T(1),T(0))</math>
In questo modo si fissa che con numero 0 di input si ha una sola funzione <math>T(n)</math> che la soddisfa. L'analisi di un algoritmo ricorsivo prevede quindi due fasi:
* Deduzione di relazioni di ricorrenza contenenti come incognita la funzione <math>T(n)</math> da stimare
Riga 186:
* {{springerEOM|titolo=Recurrence relation|autore= S.N. Artemov}}
* {{MathWorld|RecurrenceEquation|Recurrence Equation}}
* {{
{{Controllo di autorità}}
[[Categoria:Algoritmi]]
[[Categoria:
[[Categoria:Ricorsione]]
| |||