Dubbio/Conferma risoluzione relazione di ricorrenza con il metodo di sostituzione
Ciao a tutti. A breve devo dare l'esame di Metodi Matematici per l'Informatica e mi sto esercitando sulle relazioni di ricorrenza. Un esercizio che mi ha fatto sorgere qualche dubbio è il seguente:
Data la seguente relazione di ricorrenza:
\(\displaystyle T(0)=1 \)
\(\displaystyle T(n)=2T(n-2) \qquad \text{per n pari} \)
Determinare con il metodo di sostituzione per quali valori della costante $c$ vale $T(n) \leq c2^n$
L'esercizio l'ho svolto nel seguente modo:
Passo base: $T(0) = 1 \leq c*2^0 = c$ vero per $c\geq 1$
Ipotesi ricorsiva: $T(n-2) \leq c*2^{n-2}$
Passo ricorsivo: $T(n)= 2T(n-2) \leq 2*c*2^{n-2} = c*2^{n-1} \leq c*2^n$
Devo risolvere $c*2^{n-1} \leq c*2^n$ al fine di ricavare il valore di c. Generalmente con tutti gli esercizi fatti finora mi è sempre stato possibile rimuovere la $n$ da tutti e due i membri. In questo caso non è possibile, ma siccome so che $c\geq 1$ e $n\geq 0$ la disequazione è sempre soddisfatta. Quindi la risposta finale è $c\geq 1$.
E' corretto in questo modo? Come potrei verificare io stesso che è corretto? Grazie in anticipo.
Data la seguente relazione di ricorrenza:
\(\displaystyle T(0)=1 \)
\(\displaystyle T(n)=2T(n-2) \qquad \text{per n pari} \)
Determinare con il metodo di sostituzione per quali valori della costante $c$ vale $T(n) \leq c2^n$
L'esercizio l'ho svolto nel seguente modo:
Passo base: $T(0) = 1 \leq c*2^0 = c$ vero per $c\geq 1$
Ipotesi ricorsiva: $T(n-2) \leq c*2^{n-2}$
Passo ricorsivo: $T(n)= 2T(n-2) \leq 2*c*2^{n-2} = c*2^{n-1} \leq c*2^n$
Devo risolvere $c*2^{n-1} \leq c*2^n$ al fine di ricavare il valore di c. Generalmente con tutti gli esercizi fatti finora mi è sempre stato possibile rimuovere la $n$ da tutti e due i membri. In questo caso non è possibile, ma siccome so che $c\geq 1$ e $n\geq 0$ la disequazione è sempre soddisfatta. Quindi la risposta finale è $c\geq 1$.
E' corretto in questo modo? Come potrei verificare io stesso che è corretto? Grazie in anticipo.
Risposte
Sul resto non saprei che dirti ma a me pare che sia $2^n/2^(n-1)=2$ quindi ...
"axpgn":
Sul resto non saprei che dirti ma a me pare che sia $2^n/2^(n-1)=2$ quindi ...
Si, avevo già provato
Mi sarebbe uscito $1\leq 2$ che è ovviamente vera, ma avendo tolto sia $c$ che $n$ da entrambi i membri un po' mi era sorto il dubbio se avessi svolto bene l'esercizio o no. Per questo sono andato per la spiegazione un po' più articolata nel post
Beh, qui mi pare che non serva a nulla complicarsi la vita, visto che puoi trovare la soluzione esplicita:
$T(n) = 2^(n/2)$.
Questo implica che $AA n in 2NN,\ T(n) <= c2^n$ non appena $c >= 1$.
$T(n) = 2^(n/2)$.
Questo implica che $AA n in 2NN,\ T(n) <= c2^n$ non appena $c >= 1$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo