Simboli di Landau
Aprirò probabilmente l'ennesimo thread sull'argomento, ma non ho trovato nulla che risponda alla mia domanda. C'è un po di confusione sui simboli di Landau. Per ogni simbolo c'è una definizione che fa uso del limite (alla quale mi sono affezionato) e un'altra che fa uso di una diseguaglianza, che non mi sembra avere lo stesso effetto, mi sembra un po "debole". C'è chi dice che sono equivalenti, c'è chi afferma il contrario, chi dice che la definzione standard è quella col limite, c'è chi dice che è più appropriata l'altra. Leggend molti post non ho fatto altro che aumentare la mia confusione, su un argomento che ancora non avevo studiato. Potreste per favore chiarimi come stanno le cose. Avendo iniziato a studiare l'argomento su ****, che mi sembra sia ben documentato, ho visto una serie di proprietà come per esempio $f(x)*O(g(x)) = O(f(x)*g(x))$ oppure
$O(g_1(x))+O(g_2(x)) = O(|g_1(x)| + |g_2(x)|)$.
Ptreste spiegarmi per favore come andrebbero dimostrate queste e altre proprietà? Io ho tentato di utlizzare la definzione del limite, ma senza riusciurci.
$O(g_1(x))+O(g_2(x)) = O(|g_1(x)| + |g_2(x)|)$.
Ptreste spiegarmi per favore come andrebbero dimostrate queste e altre proprietà? Io ho tentato di utlizzare la definzione del limite, ma senza riusciurci.
Risposte
Ciao ZfreS,
Magari l'hai già fatto, ma nel dubbio... Hai già dato un'occhiata a questo tutorial, che al momento si trova giusto sopra il tuo post?
Magari l'hai già fatto, ma nel dubbio... Hai già dato un'occhiata a questo tutorial, che al momento si trova giusto sopra il tuo post?
**** ben documentato? 
Ad ogni buon conto, se continui ad usare un limite con $"O"$ non vai da nessuna parte...
Ad ogni buon conto, se continui ad usare un limite con $"O"$ non vai da nessuna parte...
Grazie pilloeffe! Ma non capisco perchè su molti libri/dispense/siti viene fornita la definzione col limite se la condizione di esistenza del limite non è necessaria. **** mi è sembrato sempre un sito serio.
Riprendo l'argomento perchè sono troppo confuso sui simboli di Landau. Il problema è che li sto affrontando studiando la complessità computazionale degli algoritmi. Li ho sfiorati quando studiai la serie e il polinomio di Taylor, in cui i termini meno significativi venivano indicati con o-piccolo. Stando alla definizione che da gugo, per dimostrare che una funzione $f(n) in Theta(g(n))$ (lo stesso vale per O-grande e per gli altri) bisogna ricorre alla definzione per cui trovare $c_1, c_2, n_0$ positivi, tali che $0<=c_1g(n)<=f(n)<=c_2g(n)$, oppure stando alle definzioni che fanno uso del limite, dimostrare ciò calcolando il limite? Il libro da cui studio algoritmi sceglie la prima strada e a detta di gugo il caso con il limite è un caso particolare, tuttavia c'è una grossa discordanza in quanto molti libri autorevoli (quindi non solo ****) riportano. Sinceramente non capisco perchè si usa o l'una o l'altra pur non essendo equivalenti, oppure per qualcuno lo sono e per qualcuno no?
"ZfreS":
Ma non capisco perchè su molti libri/dispense/siti viene fornita la definzione col limite se la condizione di esistenza del limite non è necessaria.
Semplicemente, chi le propone “canta la mezza messa” perché per gli usi che ne deve fare e per le funzioni che incontra non è necessario lavorare di fino.
"ZfreS":
**** mi è sembrato sempre un sito serio.
Perché non hai mai visto gli amministratori venirsi a lamentare del fatto che loro utenti chiedessero su queste pagine chiarimenti su quanto riportato nelle loro “dispense”…
Capisco..., quindi la definizione più fine trova applicazione nell'analisi della complessità computazionale, invece la'ltra definzione serve solo per fare calcoli e cercare di trasmettere un'idea intuitiva di cioò che succede. Stando alla mia domanda, per dimostrare che una funzione appartiene a $Theta(g(n))$ piuttosto che $O(g(n))$, devo ricorrere per forza alla definzione come ho visto fare fino adesso (anche se non c'è una procedura del tutto chiara), oppure esiste un altro metodo?
Beh, dipende.
In generale per $f in Theta(g)$ ti basta che $f in text(O)(g) ^^ g in text(O)(f)$; se $g != 0$ affinché ciò sia vero basta che $|f/g|$ sia limitata e per quest’ultima ti basta che esista finito e non nullo il $lim |f/g|$.
Mentre per $f in text(O)(g)$ ti serve mostrare che, se $ g != 0$, il rapporto $|f/g|$ è definitivamente limitato superiormente, cioè che $text(maxlim) |f/g|$ esiste finito.
In generale per $f in Theta(g)$ ti basta che $f in text(O)(g) ^^ g in text(O)(f)$; se $g != 0$ affinché ciò sia vero basta che $|f/g|$ sia limitata e per quest’ultima ti basta che esista finito e non nullo il $lim |f/g|$.
Mentre per $f in text(O)(g)$ ti serve mostrare che, se $ g != 0$, il rapporto $|f/g|$ è definitivamente limitato superiormente, cioè che $text(maxlim) |f/g|$ esiste finito.
Mi sarebbe più utile capire con un esempio. Se devo dimostrare che $((n), (k)) in Theta(n^k)$, in che modo devo verificare ciò che hai scritto?
"gugo82":
basta che esista finito e non nullo il $lim |f/g|$.
Scusami gugo, ma il limite di chi tendente a cosa? Quale dovrebbe essere il punto di accumulazione?
devi verificare che
$ lim_(n -> +infty) (( (n), (k) ))/n^k $
sia finito e non nullo
$ lim_(n -> +infty) (( (n), (k) ))/n^k $
sia finito e non nullo
"ZfreS":
Scusami gugo, ma il limite di chi tendente a cosa? Quale dovrebbe essere il punto di accumulazione?
Per quanto riguarda chi sia $f$ e chi sia $g$ basta leggere con attenzione i post precedenti ed attarseli alla situazione che si analizza.
Per il p.d.a... A cosa vuoi che tenda $n$?
@ l'abatefarina: Grazie.
Perfetto, il mio dubbio era se n tendesse a nfinito o a zero. Ma è chiaro che visto che voglio un comportamento asintotico, deve per forzatendere a + infinito. Domanda illegittima. Grazie ancora per l'aiuto!
Ciao, per dimostrare la proprietà di o-piccolo che ho visto nel tutorial di Gugo
\[
o(o(f(x)))=o(f(x)), x\rightarrow x_0
\]
posso procedere in questo modo? Prendo la funzione $g(x)$
\[
g(x)=o(f(x))
\]
applico la definizione di o-piccolo e sostituisco $o(f(x))$ con $g(x)$
\[
o(o(f(x)))=o(f(x)), x\rightarrow x_0 \Leftrightarrow \lim_{x\rightarrow x_0}{\frac{o(o(f(x))}{o(f(x))}}=\lim_{x\rightarrow x_0}{\frac{o(g(x))}{g(x)}}=0
\]
È corretto?
Nei primi messaggi di questa discussione si parlava di libri e dispense, sapreste consigliarmi un libro di testo che metta molta "enfasi" su tutti i simboli di Landau? Possiedo i seguenti testi
- "Calcolo", Marcellini/Sbordone. Poco utilizzati, solo nel capitolo 16 riguardante la formula di Taylor viene data la definizione di o-piccolo.
- "Analisi 1. Teora ed esercizi", Canuto/Tabacco. Introduce O-grande, o-piccolo, asintotico ed "equigrande", ma molto sbrigativamente.
- "Lezioni di Analisi 1", S. Lancelotti. Solo simbolo o-piccolo e asintotico. Molto completo (ben 25 pagine, li utilizza nelle definizioni degli asintoti obliqui), peccato manchino gli altri simboli (l'autore esplicitamente dichiara "Ve ne sono altri ma noi non li introduciamo"...)
\[
o(o(f(x)))=o(f(x)), x\rightarrow x_0
\]
posso procedere in questo modo? Prendo la funzione $g(x)$
\[
g(x)=o(f(x))
\]
applico la definizione di o-piccolo e sostituisco $o(f(x))$ con $g(x)$
\[
o(o(f(x)))=o(f(x)), x\rightarrow x_0 \Leftrightarrow \lim_{x\rightarrow x_0}{\frac{o(o(f(x))}{o(f(x))}}=\lim_{x\rightarrow x_0}{\frac{o(g(x))}{g(x)}}=0
\]
È corretto?
Nei primi messaggi di questa discussione si parlava di libri e dispense, sapreste consigliarmi un libro di testo che metta molta "enfasi" su tutti i simboli di Landau? Possiedo i seguenti testi
- "Calcolo", Marcellini/Sbordone. Poco utilizzati, solo nel capitolo 16 riguardante la formula di Taylor viene data la definizione di o-piccolo.
- "Analisi 1. Teora ed esercizi", Canuto/Tabacco. Introduce O-grande, o-piccolo, asintotico ed "equigrande", ma molto sbrigativamente.
- "Lezioni di Analisi 1", S. Lancelotti. Solo simbolo o-piccolo e asintotico. Molto completo (ben 25 pagine, li utilizza nelle definizioni degli asintoti obliqui), peccato manchino gli altri simboli (l'autore esplicitamente dichiara "Ve ne sono altri ma noi non li introduciamo"...)
No.
Allora procederei così, sempre con la sostituzione $g(x)=o(f(x))$
\[
o(o(f(x)))=o(f(x)), x\rightarrow x_0 \Leftrightarrow \lim_{x\rightarrow x_0}{\frac{o(o(f(x))}{f(x)}}=\lim_{x\rightarrow x_0}{\frac{o(g(x))}{f(x)}\cdot\frac{g(x)}{g(x)}}=\\
=\lim_{x\rightarrow x_0}{\frac{o(g(x))}{g(x)}\cdot\frac{g(x)}{f(x)}}=0
\]
perché entrambi i fattori tendono a zero.
\[
o(o(f(x)))=o(f(x)), x\rightarrow x_0 \Leftrightarrow \lim_{x\rightarrow x_0}{\frac{o(o(f(x))}{f(x)}}=\lim_{x\rightarrow x_0}{\frac{o(g(x))}{f(x)}\cdot\frac{g(x)}{g(x)}}=\\
=\lim_{x\rightarrow x_0}{\frac{o(g(x))}{g(x)}\cdot\frac{g(x)}{f(x)}}=0
\]
perché entrambi i fattori tendono a zero.
No.
Il problema è che non stai applicando la definizione.
Il problema è che non stai applicando la definizione.
Una cosa è vera. Nelle dispense gugo scrive di non essere completo, il bello è che è più completo della maggior parte dei libri di analisi 1 che ho consultato che spendono due righe sui simboli di landau. Non so in che libri vengano trattati come li ha spiegati gugo.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo