[Risolto] dubbio analisi compl. asintotica
Perdonate la banalità, ma sono le mie prime volte! 
Ho il seguente esercizio:
Segue la mia 'soluzione', qualche anima gentile mi dica se è giusta o meno.
Ho il seguente esercizio:
Dimostrare per esteso la verità o la falsità della seguente affermazione:
$ \log( f(n) ) = \theta ( g(n) ) $ implica $ f(n) = \theta(2^{g(n)}) $
Segue la mia 'soluzione', qualche anima gentile mi dica se è giusta o meno.
$ \log( f(n) ) = \theta ( g(n) ) \Rightarrow \exists c_1 > 0 \mbox{, } c_2 > 0 \mbox{, } n_0 > 0 : c_1 \cdot g(n) \leq \log( f(n) ) \leq c_2 \cdot c_2 g(n) $
che, usando la definizione di logaritmo e supponendo che questo sia binario, equivale a
$ 2^{c_1 \cdot g(n)} \leq f(n) \leq 2^{c_2 \cdot g(n)} $
ovvero
$ 2^{c_1} \cdot 2^{g(n)} \leq f(n) \leq 2^{c_2} \cdot 2^{g(n)} $ .
Ponendo $ c^{'}_1 = 2^{c_1} $ , $ c^{'}_2 = 2^{c_2} $ si ha
$ c^{'}_1 \cdot 2^{g(n)} \leq f(n) \leq c^{'}_2 \cdot 2^{g(n)} $
cioè $ f(n) = \theta( 2^{g(n)} ) $ , e pertanto l'affermazione è vera.
Risposte
Ciao,
emmm sicuro sicuro di questo passaggio?
mi pare che $2^(4*5) \ne 2^4 * 2^5$.
emmm sicuro sicuro di questo passaggio?
"Bonham":
$ 2^{c_1 \cdot g(n)} \leq f(n) \leq 2^{c_2 \cdot g(n)} $
ovvero
$ 2^{c_1} \cdot 2^{g(n)} \leq f(n) \leq 2^{c_2} \cdot 2^{g(n)} $ .
mi pare che $2^(4*5) \ne 2^4 * 2^5$.
Sì, hai ragione, che toppa!
Poi ci ripenso, al momento sono troppo stanco per ragionare.
Poi ci ripenso, al momento sono troppo stanco per ragionare.
C'ho ripensato adesso, ed ecco quanto m'è venuto. Spero di non aver scritto stupidaggini.
Che dite?
Ipotizzando vera la tesi (se fosse falsa, l'implicazione sarebbe banalmente vera per logica) abbiamo
$ \log( f(n) ) = \theta ( g(n) ) \Rightarrow \exists c_1 > 0 \mbox{, } c_2 > 0 \mbox{, } n_0 > 0 : c_1 \cdot g(n) \leq \log( f(n) ) \leq c_2 \cdot c_2 g(n), \forall n \geq n_0 $
che, usando la definizione di logaritmo e supponendo che questo sia binario, equivale a
$ 2^{c_1 \cdot g(n)} \leq f(n) \leq 2^{c_2 \cdot g(n)} $
ovvero
$(2^{c_1})^{g(n)} \leq f(n) \leq (2^{c_2})^{g(n)} $
$ c^{'}_1 \cdot g(n) = (2^{c_1})^{g(n)} \leq f(n) \leq (2^{c_2})^{g(n)} = c^{'}_2 \cdot g(n) $
$\Rightarrow c_1, c_2, c^{'}_1 , c^{'}_2 = 1, \forall n > 0$.
Ma
$(2^{c_1})^{g(n)} = c^{'}_1 \cdot 2^{g(n)} \rightarrow c^{'}_1 = \frac{(2^{c_1})^{g(n)}}{2^{g(n)}} = 2^{g(n) \cdot c_1 - g(n)}$
e analogamente succede per $c^{'}_2$.
Ciò significa che $c^{'}_1$ e $c^{'}_2$ dovrebbero dipendere da $g(n)$, e questo è impossibile in quanto sono costanti.
Dunque l'affermazione è falsa.
Che dite?
naa non mi convince per niente.
Da dove saltan fuori $c_1'$ in questa uguaglianza (forse itendi l'guaglianza con questo significato?):
\(\displaystyle {{\left({{2}}^{{{c}_{{1}}}}\right)}}^{{{g{{\left({n}\right)}}}}}={{c}}^{{'}}_{1}\cdot{{2}}^{{{g{{\left({n}\right)}}}}}\)
cioè chi è questa costante?
Fai così dimostra a pezzi:
Da dove saltan fuori $c_1'$ in questa uguaglianza (forse itendi l'guaglianza con questo significato?):
\(\displaystyle {{\left({{2}}^{{{c}_{{1}}}}\right)}}^{{{g{{\left({n}\right)}}}}}={{c}}^{{'}}_{1}\cdot{{2}}^{{{g{{\left({n}\right)}}}}}\)
cioè chi è questa costante?
Fai così dimostra a pezzi:
- [*:2rg5rgf8]$f(n)\ in^?\ O(2^{g(n)})$[/*:m:2rg5rgf8]
[*:2rg5rgf8]$f(n)\ in^?\ \Omega(2^{g(n)})$[/*:m:2rg5rgf8][/list:u:2rg5rgf8]
i passaggi sono due righe.
Quell'uguaglianza salta fuori dal fatto che il membro sinistro della diseguaglianza, per definizione, dev'essere una costante moltiplicata per una funzione. Perciò il pensiero era: dato che supponiamo vera $\log ( f(n) ) = \theta(g(n))$, esistono sicuramente due costanti $c_1$ e $c_2$, e possiamo usarle per ricavare altre costanti (possiamo anche ottenere $c^{'}_1 = c_1$, ad esempio).
Quando abbiamo
$ (2^{c_1})^{g(n)} \leq f(n) $
non è come se stessimo scrivendo
$ c^{'}_1 \cdot h(n) \leq f(n) $ ?
Così pensando, ho posto $h(n) = 2^{g(n)}$ ed ho considerato quell'uguaglianza.
Questo era per spiegare il ragionamento che feci.
Dimostrando a pezzi ottengo
$ c_1 \leq \frac{f(n)}{2^{g(n)}} \quad ( \mbox{per } f(n) = O(g(n)) ) $
$ c_2 \geq \frac{f(n)}{2^{g(n)}} \quad ( \mbox{per } f(n) = \Omega(g(n)) ) $
e poi? Ragiono sui limiti affermando che non esistono tali costanti per n, f(n), g(n), abbastanza grandi?
Quando abbiamo
$ (2^{c_1})^{g(n)} \leq f(n) $
non è come se stessimo scrivendo
$ c^{'}_1 \cdot h(n) \leq f(n) $ ?
Così pensando, ho posto $h(n) = 2^{g(n)}$ ed ho considerato quell'uguaglianza.
Questo era per spiegare il ragionamento che feci.
Dimostrando a pezzi ottengo
$ c_1 \leq \frac{f(n)}{2^{g(n)}} \quad ( \mbox{per } f(n) = O(g(n)) ) $
$ c_2 \geq \frac{f(n)}{2^{g(n)}} \quad ( \mbox{per } f(n) = \Omega(g(n)) ) $
e poi? Ragiono sui limiti affermando che non esistono tali costanti per n, f(n), g(n), abbastanza grandi?
Non funziona così.
Ricapitoliamo, devi dimostrare l'implicazione:
\[\log_2(f(n)) \in \Theta(g(n)) \Longrightarrow f(n) \in \Theta(2^{g(n)})\]
Ipotizziamo che \(\log_2(f(n)) \in \Theta(g(n))\) sia vera ((*))
Doppiamo dimostrare che l'implicazione (la tesi) è anchessa vera: \(f(n) \in \Theta(2^{g(n)})\)
Perciò: \[\exists\ c,d > 0 \wedge m \geq 0\ |\ c*2^{g(n)} \leq f(n) \leq d*2^{g(n))}\ ,\ \forall n \geq m\]
(per ipotesi)
\[k*g(n) \leq \log_2(f(n)) \leq j*g(n)\]
allora:
\[2^{k*g(n)} \leq 2^{\log_2(f(n))} \leq 2^{j*g(n)}\]
\[2^{k*g(n)} \leq f(n) \leq 2^{j*g(n)}\]
\[c*2^{g(n)} = 2^{k*g(n)} \leq f(n) \leq 2^{j*g(n)} = d*2^{g(n)} \]
\(\rightarrow c,d,k,j = 1\)
si può aggiungere: \(\forall n>0\) anche se si è in caso di funzioni generali.
salvo errori o svarioni questo è tutto
NOTA: è abbastanza facile notare, se non sbaglio, che $g(n) \in \Theta(log(n))$
(*) \(\exists\ k,j > 0 \wedge m \geq 0\ |\ k*g(n) \leq \log_2(f(n)) \leq j*g(n)\ ,\ \forall n \geq m\)
se fosse falsa l'ipotesi, ovviamente, l'implicazione sarebbe vera per logica.
Ricapitoliamo, devi dimostrare l'implicazione:
\[\log_2(f(n)) \in \Theta(g(n)) \Longrightarrow f(n) \in \Theta(2^{g(n)})\]
Ipotizziamo che \(\log_2(f(n)) \in \Theta(g(n))\) sia vera ((*))
Doppiamo dimostrare che l'implicazione (la tesi) è anchessa vera: \(f(n) \in \Theta(2^{g(n)})\)
Perciò: \[\exists\ c,d > 0 \wedge m \geq 0\ |\ c*2^{g(n)} \leq f(n) \leq d*2^{g(n))}\ ,\ \forall n \geq m\]
(per ipotesi)
\[k*g(n) \leq \log_2(f(n)) \leq j*g(n)\]
allora:
\[2^{k*g(n)} \leq 2^{\log_2(f(n))} \leq 2^{j*g(n)}\]
\[2^{k*g(n)} \leq f(n) \leq 2^{j*g(n)}\]
\[c*2^{g(n)} = 2^{k*g(n)} \leq f(n) \leq 2^{j*g(n)} = d*2^{g(n)} \]
\(\rightarrow c,d,k,j = 1\)
si può aggiungere: \(\forall n>0\) anche se si è in caso di funzioni generali.
salvo errori o svarioni questo è tutto
NOTA: è abbastanza facile notare, se non sbaglio, che $g(n) \in \Theta(log(n))$
(*) \(\exists\ k,j > 0 \wedge m \geq 0\ |\ k*g(n) \leq \log_2(f(n)) \leq j*g(n)\ ,\ \forall n \geq m\)
se fosse falsa l'ipotesi, ovviamente, l'implicazione sarebbe vera per logica.
@hamming_burst: Non sono molto convinto del tuo ultimo passaggio (ma sono di fretta e forse dirò una ca**ata..):
\[ c \, 2^g = 2^{k\,g} \implies 2^{g + \log\,c} = 2^{k\,g} \implies g + \log\,c = k\,g. \]
Non credo esistano costanti per cui questo sia valido per ogni \(n > 0\) e per ogni scelta della funzione \(g\). In particolare, se \(g \to \infty\) non sembra valere.
\[ c \, 2^g = 2^{k\,g} \implies 2^{g + \log\,c} = 2^{k\,g} \implies g + \log\,c = k\,g. \]
Non credo esistano costanti per cui questo sia valido per ogni \(n > 0\) e per ogni scelta della funzione \(g\). In particolare, se \(g \to \infty\) non sembra valere.
Ciao apatriarca
mmm però così facendo cerchi di dimostrare \(\Longleftarrow\) cioè dimostrare l'ipotesi tramite la tesi, sbaglio?
\(c*2^{g(n)}\) fa parte delle definizione di $\Theta(2^{g(n)})$ cioè ciò che si vuole dimostrare.
bhe basta che esista una costante maggiore di $0$ ed è $1$.
Su questo avevo un dubbio pure io, infatti l'unica scelta possibile dovrebbe essere $\Theta(logn)$.
Ma qua si parla solo di dimostrare l'implicazione non trovare la funzione per cui la renda vera (o falsa).
"apatriarca":
@hamming_burst: Non sono molto convinto del tuo ultimo passaggio (ma sono di fretta e forse dirò una ca**ata..):
\[ c \, 2^g = 2^{k\,g} \implies 2^{g + \log\,c} = 2^{k\,g} \implies g + \log\,c = k\,g. \]
mmm però così facendo cerchi di dimostrare \(\Longleftarrow\) cioè dimostrare l'ipotesi tramite la tesi, sbaglio?
\(c*2^{g(n)}\) fa parte delle definizione di $\Theta(2^{g(n)})$ cioè ciò che si vuole dimostrare.
Non credo esistano costanti per cui questo sia valido per ogni \(n > 0\)
bhe basta che esista una costante maggiore di $0$ ed è $1$.
e per ogni scelta della funzione \(g\). In particolare, se \(g \to \infty\) non sembra valere.
Su questo avevo un dubbio pure io, infatti l'unica scelta possibile dovrebbe essere $\Theta(logn)$.
Ma qua si parla solo di dimostrare l'implicazione non trovare la funzione per cui la renda vera (o falsa).
Stavo in realtà commentando il tuo ultimo passaggio in cui hai dato per scontata l'esistenza di una costante c con la proprietà che ho scritto.. Questo non è sempre possibile. Era questo il punto del mio ultimo post.
"apatriarca":
Stavo in realtà commentando il tuo ultimo passaggio in cui hai dato per scontata l'esistenza di una costante c con la proprietà che ho scritto.. Questo non è sempre possibile. Era questo il punto del mio ultimo post.
ah ok, ma su questo non ci sono dubbi.
Infatti sotto esplicito per quale costante $c$ è vera tale affermazione, per me \(\rightarrow\) sta a ssse.
Dicendo che l'ipotesi è vera, alla fine fissiamo un (il) $k$ qualunque. Perciò se $c=k=1$ anche nel tuo caso:
$log(1) + g(n) = 1*g(n)$
Credo di aver finalmente capito che cosa intendevi.. Pensavo stessi dicendo una cosa diversa.
"apatriarca":
Credo di aver finalmente capito che cosa intendevi.. Pensavo stessi dicendo una cosa diversa.
se hai avuto un dubbio te non immagino Bonham, se mi dici cosa ti turbava cambio formulazione nel post, così da evitare fuorviature.
Forse era l'ordine dell'uguaglianza in quel punto (per dimostrare $\Omega()$) la leggevi al contrario da sinistra a destra?
Non avevo visto la scritta \(\to c, d, k, j = 1\) alla fine e ci ho messo un po' a capire che cosa intendessi dopo averla vista. L'avrei probabilmente scritta in modo diverso, scrivendo le due relazioni separatamente. In particolare, avrei scritto che \( \exists \, c : c\,2^g \le 2^{k\,g} \) se e solo \(k \ge 1\)*. Si ottiene infatti facilmente la relazione \(g + \log\,c \le k\,g\), cioè \(\log\,c \le (k - 1)\,g\). Nel caso \(k < 1\), il secondo membro tende a \(-\infty\) e non esistono quindi valori di \(c\) accettabili. Se \(k \ge 1\), allora sicuramente \( (k - 1)\,g \ge 0 \) e quindi possiamo scegliere qualsiasi \( 0 \le c \le 1\). Lo stesso discorso lo possiamo fare per l'altro caso. Questa volta si avrà però che \( \exists \, d : d\,2^g \ge 2^{j\,g} \) se e solo se \( j \le 1 \). Infatti, si ha che \( \log\,d \ge (j - 1)\,g \) e \((j - 1)\,g \to \infty\) per \( n \to \infty \) se e solo se \( j > 1 \). Se \( j \le 1 \), qualsiasi \( d \ge 1 \) è accettabile. Valgono infine entrambe le relazione se e solo se \( j = k = 1 \) e \( 0 \le c \le 1 \le d \).
* Sto supponendo che \(g \to \infty\) per \(n \to \infty\). Il caso in cui \(g\) sia limitato è molto più semplice e in questo contesto poco interessante e il caso negativo è equivalente ma poco interessante in questo contesto.
* Sto supponendo che \(g \to \infty\) per \(n \to \infty\). Il caso in cui \(g\) sia limitato è molto più semplice e in questo contesto poco interessante e il caso negativo è equivalente ma poco interessante in questo contesto.
Sì in effetti si poteva considerare una disuguaglianza, dato che siamo nel mondo delle classi di complessità, la mia era un'uguaglianza induttiva. Avevo considerato $c2^{g(n)}$ come la conclusione, perciò la dimostrazione. Ma il tuo è più esplicativo 
Grazie ad entrambi, in effetti la mia seconda conclusione era simile a quella di hamming_burst, salvo poi che la mia scarsa abilità nella manipolazione algebrica mi ha condotto nell'esatto opposto, ma anche quella di apatriarca ha contribuito a darmi una giusta visione della cosa.
Ancora grazie!
Risolto.
Ancora grazie!
Risolto.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo