[Algoritmi] Ricorrenze e notazione asintotiche
Ciao a tutti volevo sapere se questo esercizio è corretto o sbagliato.
Siano f(n) e g(n) funzioni positive. Analizzare la seguente relazione $4f(n) + g(n)/9 = \theta(f(n)+g(n))$. Dire se è vera o falsa, motivando e provando le proprie affermazioni.
ho provato per un qualche $c_1$ e $c_2$
$c_1=2$ ottengo:
$c_1(f(n)+g(n)) <= 4f(n)+g(n)/9 <= c_2(f(n)+g(n))$
$2f(n)+2g(n) <= 4f(n)+g(n)/9$ $=>$ $2g(n)<=2f(n)+g(n)/9$
$c_2=6$
$4f(n)+g(n)/9 <= 6f(n)+6g(n)$ $=>$ $g(n)/9 <= 2f(n)+6g(n)$
per cui è vera per $c_1=2$ e $c_2=6$
è corretta?
Siano f(n) e g(n) funzioni positive. Analizzare la seguente relazione $4f(n) + g(n)/9 = \theta(f(n)+g(n))$. Dire se è vera o falsa, motivando e provando le proprie affermazioni.
ho provato per un qualche $c_1$ e $c_2$
$c_1=2$ ottengo:
$c_1(f(n)+g(n)) <= 4f(n)+g(n)/9 <= c_2(f(n)+g(n))$
$2f(n)+2g(n) <= 4f(n)+g(n)/9$ $=>$ $2g(n)<=2f(n)+g(n)/9$
$c_2=6$
$4f(n)+g(n)/9 <= 6f(n)+6g(n)$ $=>$ $g(n)/9 <= 2f(n)+6g(n)$
per cui è vera per $c_1=2$ e $c_2=6$
è corretta?
Risposte
Ciao,
Non funziona così una dimostrazione per induzione, e soprattutto in algoritmica non dobbiamo dimenticarci i passaggi formali (ci si può rilassare in alcuni punti, ma non troppo).
Ti consiglio di dare prima una letta, a questa semplice spiegazione scritta da apatriarca.
Per questo caso la definizione di $Theta()$ è questa:
\[\exists c,d > 0,\ m \geq 0\ \ |\ \ 0 \leq cg(x) \leq f(x) \leq dg(x)\ ,\ \forall n \geq m \]
Non puoi prendere così a caso due costanti e fissarle, deve esserci un legame ed un filo logico nella dimostrazione. Perchè $2$ o $6$ sono plausibili?
Leggi il post che ti ho linkato e ne riparliamo.
Non funziona così una dimostrazione per induzione, e soprattutto in algoritmica non dobbiamo dimenticarci i passaggi formali (ci si può rilassare in alcuni punti, ma non troppo).
Ti consiglio di dare prima una letta, a questa semplice spiegazione scritta da apatriarca.
Per questo caso la definizione di $Theta()$ è questa:
\[\exists c,d > 0,\ m \geq 0\ \ |\ \ 0 \leq cg(x) \leq f(x) \leq dg(x)\ ,\ \forall n \geq m \]
Non puoi prendere così a caso due costanti e fissarle, deve esserci un legame ed un filo logico nella dimostrazione. Perchè $2$ o $6$ sono plausibili?
Leggi il post che ti ho linkato e ne riparliamo.
Non sono sicuro che in questo caso valga la pena di scomodare l'induzione, anche perché si può prendere \(m = 0\) e definire \(c\) e \(d\) in modo del tutto indipendente dalle funzioni \(f\) e \(g\). Ma le costanti scelte sono certamente sbagliate. Prendendo infatti ad esempio \(g(n) = n!\) e \(f(n) = n\) si avrebbe che \( 2\,g(n) = 2\,n! > 2\,n + n!/9 = 2\,f(n) + g(n)/9 \) per \(n\) sufficientemente grande. L'altra costante è invece valida, ma rimane il fatto che una dimostrazione di questo tipo non andrebbe fatta a caso.
vorrei ringraziare hamming_burst per la risposta, ho letto il post, io e alcuni miei amici abbiamo preso spunto da una slide di un prof. che dice:
Date $f : n ∈ N → f (n) ∈ R+ , g : n ∈ N → g(n) ∈ R+$
scriveremo
$f(n) = Θ(g(n))$ $⇔$ $∃n0 , c1 , c2 > 0 : c1 g(n) ≤ f(n) ≤ c2 g(n), ∀n ≥ n0$
Equivalentemente
$f(n) = Θ(g(n)) ⇔ f(n) = O(g(n)) e f(n) = Ω(g(n))$
il problema che delle notazione asintotiche non abbiamo capito molto, ma non c'è passato proprio per la testa di utilizzare l'induzione matematica, anche perchè qualche esercizio che c'è stato mostrano non trattava l'induzione.
voi che ne dite.
p.s. ho letto sul libro "Introduzione agli algoritmi e strutture dati" questo:
$theta(g(n)) = f(n)$ : esistono delle costanti positive $c_1, c_2, n_0$ tali che $0<=c_1g(n)<=f(n)<=c_2g(n)$ per ogni $n>=n_0.$
Una funzione $f(n)$ appartiene all'insieme $theta(g(n))$ se esistono constanti positive $c_1, c_2$ tali che possa essere compresa fra $c_1g(n)$ e $c_2g(n)$, per un valore sufficientemente grande di n.
Date $f : n ∈ N → f (n) ∈ R+ , g : n ∈ N → g(n) ∈ R+$
scriveremo
$f(n) = Θ(g(n))$ $⇔$ $∃n0 , c1 , c2 > 0 : c1 g(n) ≤ f(n) ≤ c2 g(n), ∀n ≥ n0$
Equivalentemente
$f(n) = Θ(g(n)) ⇔ f(n) = O(g(n)) e f(n) = Ω(g(n))$
il problema che delle notazione asintotiche non abbiamo capito molto, ma non c'è passato proprio per la testa di utilizzare l'induzione matematica, anche perchè qualche esercizio che c'è stato mostrano non trattava l'induzione.
voi che ne dite.
p.s. ho letto sul libro "Introduzione agli algoritmi e strutture dati" questo:
$theta(g(n)) = f(n)$ : esistono delle costanti positive $c_1, c_2, n_0$ tali che $0<=c_1g(n)<=f(n)<=c_2g(n)$ per ogni $n>=n_0.$
Una funzione $f(n)$ appartiene all'insieme $theta(g(n))$ se esistono constanti positive $c_1, c_2$ tali che possa essere compresa fra $c_1g(n)$ e $c_2g(n)$, per un valore sufficientemente grande di n.
Come ti ho detto non hai bisogno a mio parere dell'induzione, è sufficiente utilizzare i seguenti fatti:
1. \(f(n) \ge 0 \quad \forall n\),
2. \(g(n) \ge 0 \quad \forall n\),
3. \(\alpha\,x \ge \beta\,x \Leftrightarrow \alpha \ge \beta, \quad \forall \alpha, \beta, x \in \mathbb R^+\),
4. \(x + y \ge x + z \Leftrightarrow y \ge z, \quad \forall x, y, z \in \mathbb R^+\).
1. \(f(n) \ge 0 \quad \forall n\),
2. \(g(n) \ge 0 \quad \forall n\),
3. \(\alpha\,x \ge \beta\,x \Leftrightarrow \alpha \ge \beta, \quad \forall \alpha, \beta, x \in \mathbb R^+\),
4. \(x + y \ge x + z \Leftrightarrow y \ge z, \quad \forall x, y, z \in \mathbb R^+\).
in pratica i passi utilizzati per svolgere l'esercizio postato sono giusti, il problema è come scegliere le costanti $c_1 e c_2$?
o sbaglio?
o sbaglio?
In pratica, sì.
"Sentenza84":
in pratica i passi utilizzati per svolgere l'esercizio postato sono giusti, il problema è come scegliere le costanti $c_1 e c_2$?
o sbaglio?
Sì, il mio era più un int per far capire che le cose non si stabiliscono a caso, come hai fatto te, infatti l'induzione ha passaggi ben delineati.
In questa dimostrazione molto semplice, come ha fatto già notare apatriarca, siamo in un caso generale e non si può dire molto sulle funzioni in gioco, e in questo caso l'induzione forse è sprecata.
L'unico passaggio "difficile" è stabilire le costanti, fine.
proviamo che $4f(n) + 1/9f(n) in Theta(f(n)+g(n))$
Per semplificare questo puoi dividere il tutto nella dimostrazione con la definizione di $O()$ e $Omega()$.
utilizziamo la definizione di $O()$
\[4f(n) + 1/9g(n) \leq d(f(n)+g(n))\]
\[4f(n) + 1/9g(n) \leq d'f(n)+ d''g(n)\]
questo è vero per \(d'\geq 4 \wedge d''\geq1/9\) con un $m >= 0$ qualunque (non sappiamo nulla delle funzioni).
il resto lo lascio a te.
Come detto si può smussare le cose inutili, nessuno lo vieta, basta stare attenti, come l'induzione insegna
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo