Ricorrenze e notazioni asintotiche
(a)Siano f(n) e g(n) funzioni positive. Analizzare la seguente relazione 5f(n)+ g(n)/7 = Θ(f(n)+ g(n)). Dire se e vera o falsa, motivando e provando le proprie affermazioni.
(b) Risolvere la seguente relazione di ricorrenza: T(n)= T (n/5) + T (4n/5) + n con T (n)= O(1) per n ≤ 5.
Sperando che questo sia il luogo giusto, qualcuno mi potrebbe risolvere questi esercizi, ovviamente spiegandomi come procedere
(b) Risolvere la seguente relazione di ricorrenza: T(n)= T (n/5) + T (4n/5) + n con T (n)= O(1) per n ≤ 5.
Sperando che questo sia il luogo giusto, qualcuno mi potrebbe risolvere questi esercizi, ovviamente spiegandomi come procedere
Risposte
Ciao benvenuto,
vediamo...
bhe vedila in questo modo:
\[5f(n)+ \frac{1}7g(n) \in \Theta(f(n)+ g(n))\]
essendo $5$ e $1/7$ due cosanti mi sempra palese la risposta. Per "dimostrarla" puoi farla anche ad occhio conoscendo la definizione di $\Theta()$.
meglio scritta così:
$T(n) = {(O(1) if n<=5),(T(n/5) + T(4n/5) + n \ other):}$
con doppio punto di ricorsione il discorso si complica in questo genere di ricorrenze.
Io ti propongo di risolvere questa riscritta (che diventa una limitazione superiore all'originale):
$T(n) = {(O(1) if n<=5),(2T(4n/5) + n \ other):}$
le motivazioni di questo passaggio te le rinvio a qui, qui o anche qui
In generali quei tre post ti spiegano come affrontare questo genere di ricorrenze, ho utilizzato il metodo dell'albero per risolverle, ma se vede l'intero topic (non solo il post che ti ho linkato) vedrai altri metodi di risoluzione (iterazione, sostituzione o induzione).
Cerca di applicare quei metodi, penso che almeno uno lo devi conoscere se proponi e sai cosa sia un'equazione di ricorrenza. Mostra qui i tuoi passaggi, così vediamo se è corretto e casomai ti aiutiamo a svogerli.
Sarebbe più un argomento di algoritmica, perciò sezione Informatica.
Di solito, in generale (e per il futuro) ,in questo forum si propone uno svolgimento oppure un punto in cui si è bloccati (teorico o pratico), non si chiede l'intero svolgimento di un esercizio.
vediamo...
"pippopelo":
(a)Siano f(n) e g(n) funzioni positive. Analizzare la seguente relazione 5f(n)+ g(n)/7 = Θ(f(n)+ g(n)). Dire se e vera o falsa, motivando e provando le proprie affermazioni.
bhe vedila in questo modo:
\[5f(n)+ \frac{1}7g(n) \in \Theta(f(n)+ g(n))\]
essendo $5$ e $1/7$ due cosanti mi sempra palese la risposta. Per "dimostrarla" puoi farla anche ad occhio conoscendo la definizione di $\Theta()$.
(b) Risolvere la seguente relazione di ricorrenza: T(n)= T (n/5) + T (4n/5) + n con T (n)= O(1) per n ≤ 5.
meglio scritta così:
$T(n) = {(O(1) if n<=5),(T(n/5) + T(4n/5) + n \ other):}$
con doppio punto di ricorsione il discorso si complica in questo genere di ricorrenze.
Io ti propongo di risolvere questa riscritta (che diventa una limitazione superiore all'originale):
$T(n) = {(O(1) if n<=5),(2T(4n/5) + n \ other):}$
le motivazioni di questo passaggio te le rinvio a qui, qui o anche qui
In generali quei tre post ti spiegano come affrontare questo genere di ricorrenze, ho utilizzato il metodo dell'albero per risolverle, ma se vede l'intero topic (non solo il post che ti ho linkato) vedrai altri metodi di risoluzione (iterazione, sostituzione o induzione).
Cerca di applicare quei metodi, penso che almeno uno lo devi conoscere se proponi e sai cosa sia un'equazione di ricorrenza. Mostra qui i tuoi passaggi, così vediamo se è corretto e casomai ti aiutiamo a svogerli.
Sperando che questo sia il luogo giusto, qualcuno mi potrebbe risolvere questi esercizi, ovviamente spiegandomi come procedere
Sarebbe più un argomento di algoritmica, perciò sezione Informatica.
Di solito, in generale (e per il futuro) ,in questo forum si propone uno svolgimento oppure un punto in cui si è bloccati (teorico o pratico), non si chiede l'intero svolgimento di un esercizio.
"hamming_burst":
Ciao benvenuto,
vediamo...
[quote="pippopelo"](a)Siano f(n) e g(n) funzioni positive. Analizzare la seguente relazione 5f(n)+ g(n)/7 = Θ(f(n)+ g(n)). Dire se e vera o falsa, motivando e provando le proprie affermazioni.
bhe vedila in questo modo:
\[5f(n)+ \frac{1}7g(n) \in \Theta(f(n)+ g(n))\]
essendo $5$ e $1/7$ due costanti mi sempra palese la risposta. Per "dimostrarla" puoi farla anche ad occhio conoscendo la definizione di $\Theta()$. [/quote]
Allora ci provo purtroppo il materiale su cui lavoro è questo http://www.dia.unisa.it/~ads/ads/Algori ... s/Cap2.pdf e sto cercando di capirci qualcosa (se puoi dare un'occhiata anche tu che hai occhio più allenato di me forse riesci a trovare la soluzione) comunque:
Si definisce $\Theta(f(n)+g(n))$se f(n)+ g(n) è sia $\O(f(n)+ g(n))$ sia $\Ω(f(n)+ g(n))$. Quindi dovrei dimostrare che $\f(n)+ g(n)$ $\in\$ $\ O(f(n)+ g(n))$ e $\f(n)+ g(n)$ $\in\$ $\ Ω(f(n)+ g(n))$ Poi affermo che essendo vero l'uno e l'altro allora $\f(n)+ g(n)$ $\in\$ $\Theta(f(n)+g(n))$ potendo tralasciare le costanti che non hanno peso.
Per dimostrare che $\f(n)+ g(n)$ $\in\$ $\O(f(n)+ g(n))$ come faccio? O posso utilizzare direttamente la Notazione $\Theta()$ contenuta nella diapositiva 7 (però poi chi sarebbero n,n0, c )?
(b) Risolvere la seguente relazione di ricorrenza: T(n)= T (n/5) + T (4n/5) + n con T (n)= O(1) per n ≤ 5.
meglio scritta così:
$T(n) = {(O(1) if n<=5),(T(n/5) + T(4n/5) + n \ other):}$
con doppio punto di ricorsione il discorso si complica in questo genere di ricorrenze.
Io ti propongo di risolvere questa riscritta (che diventa una limitazione superiore all'originale):
$T(n) = {(O(1) if n<=5),(2T(4n/5) + n \ other):}$
le motivazioni di questo passaggio te le rinvio a qui, qui o anche qui
In generali quei tre post ti spiegano come affrontare questo genere di ricorrenze, ho utilizzato il metodo dell'albero per risolverle, ma se vede l'intero topic (non solo il post che ti ho linkato) vedrai altri metodi di risoluzione (iterazione, sostituzione o induzione).
Cerca di applicare quei metodi, penso che almeno uno lo devi conoscere se proponi e sai cosa sia un'equazione di ricorrenza. Mostra qui i tuoi passaggi, così vediamo se è corretto e casomai ti aiutiamo a svogerli.
L'amara verità è che su queste cose non so granchè....Il metodo master non è stato spiegato....Il prof a lezione diceva: proviamo per una costante qualsiasi e poi la sostituiva nella definizione...L'albero l'abbiamo trattato solo un pò più avanti e allora ho provato a fare questo...Il problema è che mi blocco subito poichè volendo svolgere $T(n) = {(O(1) if n<=5),(2T(4n/5) + n \ other):}$ mettendo come padre n e poi come figli $(4n/5)$ e $(4n/5)$ la loro somma mi darebbe $(8n/5)$ che è assolutamente assurdo (credo)...Quindi se hai un pò di pazienza mi spieghi come si fa?
Sarebbe più un argomento di algoritmica, perciò sezione Informatica.
Di solito, in generale (e per il futuro) ,in questo forum si propone uno svolgimento oppure un punto in cui si è bloccati (teorico o pratico), non si chiede l'intero svolgimento di un esercizio.
In effetti studio Informatica. Se c'è necessità di cambiare sezione e posso farlo io non c'è problema...
Domani provo a sbattere la testa ancora ora sono le 3.10 e se nell'arco della giornata non sono riuscito a ricavarne niente non penso ne trarrò qualcosa ora...notte
L'amara verità è che su queste cose non so granchè....Il metodo master non è stato spiegato....
il Master Theorem è più una tecnica per risolvere ad occhio una ricorrenza; approssimandola in qualche modo per avere l'idea dell'andamento asintotico. Se si vogliono avere limitazioni più strette si usano altre tecniche di calcolo. Ma è utile conoscere tale teorema; è parecchio usato per molti algoritmi di natura ricorsiva.
Il prof a lezione diceva: proviamo per una costante qualsiasi e poi la sostituiva nella definizione...
dovrebbe essere o il metodo dell'iterazione (il più algebrico) che ti da il valore preciso della limitazione asintotica oppure il metodo della sostituazione (o per tentativi) dove ipotizzi una limitazione e lo dimostri per induzione se è corretta.
L'albero l'abbiamo trattato solo un pò più avanti e allora ho provato a fare questo...Il problema è che mi blocco subito poichè volendo svolgere $T(n) = {(O(1) if n<=5),(2T(4n/5) + n \ other):}$ mettendo come padre n e poi come figli $(4n/5)$ e $(4n/5)$ la loro somma mi darebbe $(8n/5)$ che è assolutamente assurdo (credo)...Quindi se hai un pò di pazienza mi spieghi come si fa?
visto che lo conosci usiamo l'albero, è equivalente al metodo algebrico o per iterazione (è una sua sottocategoria)
la nostra ricorrenza "semplificata" è: $T(n) = 2T(4n/5) + n$
partiamo con la radice e sostituiamo successivamente sulla funzione di costo (il valore libero) e sommiamo infine i vari livelli:
n
|$\ \ $\
$4n/5$ $4n/5$ $= 2*4n/5 = 2^1((4^1)/(5^1))n$
|$\ \ \ $\
$4*4n/5*5\ \ \ \ 4*4n/5*5$ ... $=2^2((4^2)/(5^2))n$
...
$4^i\n/5^i$ $4^i\n/5^i$ ... $ = 2^i((4^i)/(5^i))n$
...
qua si arriva fino a quando $n$ raggiunge il valore $n=6$ per via della definizione di $T(n)$ della ricorrenza.
Prima di tutto cerchiamo di capire come si comportano le proprietà degli alberi nel caso dell'albero completo, cioè fino a profondità di $n=1$ (se le conosci ad esempio la profondità di un albero binario è dipendente dal numero di nodi perciò: $log_2(n)$) la profondità massima di questo albero è quando $(4^i)/(5^i)n = 1$, calcoliamolo (utilizzo qualche proprietà delle potenze e cose simili):
$(4^i)/(5^i)n = (4/5)^i\n$
allora:
$(4/5)^i\n = 1$ quando $i=log_(5/4)n$. Perciò l'albero ha profondità massima $log_(5/4)n$
Noi dobbiamo fermarci a $n=6$ per il calcolo dei nodi interni, poi calcoliamo il caso $n<=5$ dove consideriamo $5$ livelli di foglie distinte per semplificarci la vita, cioè sommiamo semplicemente delle foglie con la sommatoria generale che mostro ora.
Prima cosa calcoliamo i nodi interni, sommando i vari livelli dell'albero a livello $i-$esimo dalla radice a $n=6$ cioè a profondità $log_(5/4)(n)-5$
$\sum_{i=0}^{log_(5/4)(n)-5} 2^i((4^i)/(5^i))n =$ semplifichiamo un po' di cose:
$2^i((4^i)/(5^i)) = 2^i*2^(2i)/5^i = 2^(3i)/5^i = (8/5)^i$
$= \sum_{i=0}^{log_(5/4)(n)-5} (8/5)^i \n= n * \sum_{i=0}^{log_(5/4)(n)-5} (8/5)^i$ è una serie geometrica finita (ha una simpatica formula chiusa):
$n*((8/5)^((log_(5/4)(n)-5)+1) - 1)/((8/5)-1) =$ utilizzo qualche proprietà delle potenze e l'uguaglianza $a^{log_b(n)} = n^{log_b(a)}$
$= n*((n^{log_(5/4)(8/5)}/(8/5)^4) - 1) / (3/5) = 5/3n * (n^{log_(5/4)(8/5)}/((8/5)^4) - 1) = 4096/375n^{log_(5/4)(8/5)+1} - 5/3n$
Ora calcoliamo i cinque livelli di foglie di costo singolarmente $O(1)$:
$\sum_{i=0}^{4}2^{log_{5/4}(n)-i}*O(1) = \sum_{i=0}^{4}n^{log_{5/4}(2)}/2^i*O(1) =$
$= n^{log_{5/4}(2)}\sum_{i=0}^{4}(1/2)^i = n^{log_{5/4}(2)}((1 - (1/2)^5) / (1 - 1/2) ) = 31/16n^{log_{5/4}(2)} in O(n^3.1)$
Perciò ci sono $O(n^3.1)$ foglie.
ora sommiamo il tutto (nodi interni + foglie):
$4096/375n^{log_(5/4)(8/5)+1} - 5/3n + O(n^3.1) ~~ n^{3.1} - n + O(n^(3.1)) \in O(n^3.1)$
In conclusione la complessità dell'equazione di ricorrenza $T(n) \in O(n^3.1)$.
Il conteggio delle foglie non ricordo se è lecito farlo così perchè semplifico alcune cose secondarie, ma comunque ritornano i conti perciò dovrebbe essere ok.
Ti consiglio, come esercizio, di dimostrare per induzione che la complessità trovata è vera, cosa che sarebbe da fare SEMPRE (trovi una complessità e la dimostri per induzione).
Oppure prova a calcolarla con il Master Therorem così vedrai se abbiamo fatto le cose correttamente o meno.
Come vedi in questo metodo si utilizzano molto le proprietà delle serie, sommatorie, potenze ed alberi. Ti ho mostrato ed ho utilizzato questo metodo, anche perchè per un informatico è d'obbligo essere pratici con questi argomenti e le equazioni di ricorrenza danno la possibilità di maneggiare tanti argomenti insieme; se già sei pratico di tutto ciò meglio così
Rivedi tutto il procedemento, quello che non hai chiaro basta dirlo.
In effetti studio Informatica. Se c'è necessità di cambiare sezione e posso farlo io non c'è problema...
Non puoi farlo te, dovrebbe essere un mod a spostarla.
Per la 1. è ok come hai proceduto, basta usare semplicemente la definizione (se vuoi essere più formale dovrei usare l'induzione e trovare le $c$ e $d$ per qualche $n_0$) vedi te.
La definzione della Slide per $Theta()$ non è quella formale, ma è un metodo veloce per confrontare due funzioni al limite come puoi vedere non ti da le costanti di validità.
Penso che il modo migliore per verificare quanto ho capito è prendere un esercizio e risolverlo. beh ci provo con questo.
$T(n) = {(O(1) if n<=4),(T(n)=T(n/4)+T(3n/4) + n \ other):}$
la nostra ricorrenza "semplificata" è: $T(n) = 2T(3n/4) + n$
partiamo con la radice e sostituiamo successivamente sulla funzione di costo (il valore libero) e sommiamo infine i vari livelli:
n
|$\ \ $\
$3n/4$ $3n/4$ $= 2*3n/4 = 2^1((3^1)/(4^1))n$
|$\ \ \ \$\
$3*3n/4*4\ \ \ \ 3*3n/4*4$ ... $=2^2((3^2)/(4^2))n$
...
$3^i\n/4^i$ $3^i\n/4^i$ ... $ = 2^i((3^i)/(4^i))n$
...
qua si arriva fino a quando $n$ raggiunge il valore $n=5$ per via della definizione di $T(n)$ della ricorrenza.
Prima di tutto cerchiamo di capire come si comportano le proprietà degli alberi nel caso dell'albero completo, cioè fino a profondità di $n=1$, la profondità massima di questo albero è quando $(3^i)/(4^i)n = 1$, calcoliamolo
$(3^i)/(4^i)n = (3/4)^i\n$
allora:
$(3/4)^i\n = 1$ quando $i=log_(4/3)n$. Perciò l'albero ha profondità massima $log_(4/3)n$
Noi dobbiamo fermarci a $n=5$ per il calcolo dei nodi interni, poi calcoliamo il caso $n<=4$ dove consideriamo $4$ livelli di foglie distinte per semplificarci la vita, cioè sommiamo semplicemente delle foglie con la sommatoria generale che mostro ora.
Prima cosa calcoliamo i nodi interni, sommando i vari livelli dell'albero a livello $i-$esimo dalla radice a $n=5$ cioè a profondità $log_(4/3)(n)-4$
$\sum_{i=0}^{log_(4/3)(n)-4} 2^i((3^i)/(4^i))n =$ semplifichiamo un po' di cose:
$2^i((3^i)/(4^i)) = 2^i*3^(i)/2^(2i) = 3^i/2^i = (3/2)^i$
$= \sum_{i=0}^{log_(4/3)(n)-4} (3/2)^i \n= n * \sum_{i=0}^{log_(4/3)(n)-4} (3/2)^i$ è una serie geometrica finita:
$n*((3/2)^((log_(4/3)(n)-4)+1) - 1)/((3/2)-1) =$ utilizzo qualche proprietà delle potenze e l'uguaglianza $a^{log_b(n)} = n^{log_b(a)}$
$= n*((n^{log_(4/3)(3/2)}/(3/2)^4) - 1) / (1/2) = 2n * (n^{log_(4/3)(3/2)}/((3/2)^4) - 1) = 27/4n^{log_(4/3)(3/2)+1} - 2n$
Ora calcoliamo i cinque livelli di foglie di costo singolarmente $O(1)$: Questo passaggio non l'ho capito....
Poi come faccio ad eseguire il $log_(4/3)$ del risultato che uscirà
Alla fine otterrò il risultato
poi sommo il tutto (nodi interni + foglie):
$27/4n^{log_(4/3)(3/2)+1} - 2n + x$(risultato II passaggio)
Prima vorrei avere ulteriori delucidazioni sul II passaggio e se ho svolto correttamente il I passaggio (alla fine mi è bastato sostituire i numeri e fare un pò di conti a dire il vero) (penso lo abbia notato)
Non capisco come questo esercizio sia valutato dal mio prof solo 6/100. Ad ogni modo l'induzione la farò per un mio tornaconto personale ma non penso di farlo sul compito poichè perderei troppo tempo (ho solo 2 h e ci sono algoritmi di Dijkstra,Bellman-Ford, e altri soliti problemi di algoritmica) quindi non ho molto fretta di impararla...
Si definisce $\Theta(f(n)+g(n))$se f(n)+ g(n) è sia $\O(f(n)+ g(n))$ sia $\Ω(f(n)+ g(n))$. Quindi dovrei dimostrare che $\f(n)+ g(n)$ $\in\$ $\ O(f(n)+ g(n))$ e $\f(n)+ g(n)$ $\in\$ $\ Ω(f(n)+ g(n))$ Poi affermo che essendo vero l'uno e l'altro allora $\f(n)+ g(n)$ $\in\$ $\Theta(f(n)+g(n))$
$\f(n)+ g(n)$ $\in\$ $\O(f(n)+ g(n))$ se esistono costanti $c,d > 0$ e $n_0 ≥ 0$ tali che per tutti $n ≥ n_0$ si ha $\f(n)+ g(n)≤ (c+d) · (f(n)+g(n))$.
Essendo $c=5$ e $d=1/7$ allora scrivo $\f(n)+ g(n)≤ (5+1/7) · (f(n)+g(n))$ ovvero
$\f(n)+ g(n)≤ 36/7 · (f(n)+g(n))$ ma $\f(n)+ g(n)$ è sicuramente $≤ 36/7 · (f(n)+g(n))$ C.V.D.
Analogamente procedo con $Ω()$ però con $≥$.
E' corretto il mio pensiero? Se non è cosi potresti aiutarmi l'esame è domani!!
$T(n) = {(O(1) if n<=4),(T(n)=T(n/4)+T(3n/4) + n \ other):}$
la nostra ricorrenza "semplificata" è: $T(n) = 2T(3n/4) + n$
partiamo con la radice e sostituiamo successivamente sulla funzione di costo (il valore libero) e sommiamo infine i vari livelli:
n
|$\ \ $\
$3n/4$ $3n/4$ $= 2*3n/4 = 2^1((3^1)/(4^1))n$
|$\ \ \ \$\
$3*3n/4*4\ \ \ \ 3*3n/4*4$ ... $=2^2((3^2)/(4^2))n$
...
$3^i\n/4^i$ $3^i\n/4^i$ ... $ = 2^i((3^i)/(4^i))n$
...
qua si arriva fino a quando $n$ raggiunge il valore $n=5$ per via della definizione di $T(n)$ della ricorrenza.
Prima di tutto cerchiamo di capire come si comportano le proprietà degli alberi nel caso dell'albero completo, cioè fino a profondità di $n=1$, la profondità massima di questo albero è quando $(3^i)/(4^i)n = 1$, calcoliamolo
$(3^i)/(4^i)n = (3/4)^i\n$
allora:
$(3/4)^i\n = 1$ quando $i=log_(4/3)n$. Perciò l'albero ha profondità massima $log_(4/3)n$
Noi dobbiamo fermarci a $n=5$ per il calcolo dei nodi interni, poi calcoliamo il caso $n<=4$ dove consideriamo $4$ livelli di foglie distinte per semplificarci la vita, cioè sommiamo semplicemente delle foglie con la sommatoria generale che mostro ora.
Prima cosa calcoliamo i nodi interni, sommando i vari livelli dell'albero a livello $i-$esimo dalla radice a $n=5$ cioè a profondità $log_(4/3)(n)-4$
$\sum_{i=0}^{log_(4/3)(n)-4} 2^i((3^i)/(4^i))n =$ semplifichiamo un po' di cose:
$2^i((3^i)/(4^i)) = 2^i*3^(i)/2^(2i) = 3^i/2^i = (3/2)^i$
$= \sum_{i=0}^{log_(4/3)(n)-4} (3/2)^i \n= n * \sum_{i=0}^{log_(4/3)(n)-4} (3/2)^i$ è una serie geometrica finita:
$n*((3/2)^((log_(4/3)(n)-4)+1) - 1)/((3/2)-1) =$ utilizzo qualche proprietà delle potenze e l'uguaglianza $a^{log_b(n)} = n^{log_b(a)}$
$= n*((n^{log_(4/3)(3/2)}/(3/2)^4) - 1) / (1/2) = 2n * (n^{log_(4/3)(3/2)}/((3/2)^4) - 1) = 27/4n^{log_(4/3)(3/2)+1} - 2n$
Ora calcoliamo i cinque livelli di foglie di costo singolarmente $O(1)$: Questo passaggio non l'ho capito....
Poi come faccio ad eseguire il $log_(4/3)$ del risultato che uscirà
Alla fine otterrò il risultato
poi sommo il tutto (nodi interni + foglie):
$27/4n^{log_(4/3)(3/2)+1} - 2n + x$(risultato II passaggio)
Ti consiglio, come esercizio, di dimostrare per induzione che la complessità trovata è vera, cosa che sarebbe da fare SEMPRE (trovi una complessità e la dimostri per induzione).
Oppure prova a calcolarla con il Master Therorem così vedrai se abbiamo fatto le cose correttamente o meno.
Prima vorrei avere ulteriori delucidazioni sul II passaggio e se ho svolto correttamente il I passaggio (alla fine mi è bastato sostituire i numeri e fare un pò di conti a dire il vero) (penso lo abbia notato)
Non capisco come questo esercizio sia valutato dal mio prof solo 6/100. Ad ogni modo l'induzione la farò per un mio tornaconto personale ma non penso di farlo sul compito poichè perderei troppo tempo (ho solo 2 h e ci sono algoritmi di Dijkstra,Bellman-Ford, e altri soliti problemi di algoritmica) quindi non ho molto fretta di impararla...
II esercizio
Si definisce $\Theta(f(n)+g(n))$se f(n)+ g(n) è sia $\O(f(n)+ g(n))$ sia $\Ω(f(n)+ g(n))$. Quindi dovrei dimostrare che $\f(n)+ g(n)$ $\in\$ $\ O(f(n)+ g(n))$ e $\f(n)+ g(n)$ $\in\$ $\ Ω(f(n)+ g(n))$ Poi affermo che essendo vero l'uno e l'altro allora $\f(n)+ g(n)$ $\in\$ $\Theta(f(n)+g(n))$
$\f(n)+ g(n)$ $\in\$ $\O(f(n)+ g(n))$ se esistono costanti $c,d > 0$ e $n_0 ≥ 0$ tali che per tutti $n ≥ n_0$ si ha $\f(n)+ g(n)≤ (c+d) · (f(n)+g(n))$.
Essendo $c=5$ e $d=1/7$ allora scrivo $\f(n)+ g(n)≤ (5+1/7) · (f(n)+g(n))$ ovvero
$\f(n)+ g(n)≤ 36/7 · (f(n)+g(n))$ ma $\f(n)+ g(n)$ è sicuramente $≤ 36/7 · (f(n)+g(n))$ C.V.D.
Analogamente procedo con $Ω()$ però con $≥$.
E' corretto il mio pensiero? Se non è cosi potresti aiutarmi l'esame è domani!!
vediamo...
spero tu abbia capito il perchè di questa trasformazione di T(n) e della sua validità (rivedi i post che ti ho linkato in caso).
vedila così:
$T(n/4)+T(3n/4) + n <= 2T(3n/4) + n$
cerchi una limitazione superiore stretta sulla ricorrenza originale, per essere pignoli trovi un o-piccolo su $T(n)$.
Ma sono cose secondarie.
(*) hai capito perchè il logaritmo a base invertita rispetto alla base dell'esponenziale? E' un punto abbastanza importante del metodo dell'albero, ed in questo caso mostra il suo funzionamento alla base (con n=1).
sai cosa sono i nodi interni?
Nel caso delle ricorrenze deve esserci distinzione tra il calcolo dei nodi interni (con costo variabile dettato dalla funzione libera e dai rami di T(n)) e le foglie (con costo costante o prestabilito).
piccola svista penso (cose secondarie):
$(3/2)^((log_(4/3)(n)-4)+1) = (3/2)^(log_(4/3)(n)-3) = n^(log_(4/3)(3/2))/(3/2)^3$
vedila in questo modo.
Negli alberi completi (es. binari) c'è solo un livello di foglie, l'ultimo di profondità massima.
In questi alberi le foglie rappresentano i costi costanti alla base di un algoritmo, quando $n=1$ siamo nel caso di un albero qualunque e le regole che hai imparato sono valide.
Ma nel caso che la base costante sia per più valori di $n$, l'albero non avrà più un solo livello di foglie ma tanti separati e distinti, cioè astrattamente collegati ai nodi interni.
Un disegno è più chiarificatore di mille parole:
le FOGLIE sono tanti livelli separati o collegati astrattamente ai nodi. Ma tieni in considerazione che le foglie con $n=1$ saranno sempre maggiori di quelle a $n=5$ perciò il limite superiore delle foglie sarà sempre lo stesso cambiano le costanti.
In calcoli, sommi le foglie ad ogni livello e poi sommi il tutto.
Nel caso $n=1$ risulta essere:
$2^(log_(4/3)(n))*(3/2)^(log_(4/3)(n))$ per via dell'uguaglianze scritta sopra (*)
$(3/2)^(log_(4/3)(n))n = 1$ perciò la condizione $O(1)$ quando $n=1$ è rispettata e si calcola (o sostituisce):
$2^(log_(4/3)(n))*O(1) =$ ...
il resto sono solo sommme.
bhè questo è un semplice calcolo di un logaritmo, utilizza la classica formula per calcolare un logaritmo in una base che più ti piace, tipo in base $10$ risulterà:
$log_(4/3)(a) = (log_(10)(a))/(log_(10)(4/3))$
un po' lo ho notato
ma attento a non sostituire senza capire cosa ci sta sotto, alla fine sono solo qualche sommatoria e potenze.
Prova a calcolare una di tipo diverso, considerando semplicemente un caso base O(1) quando $n=1$ così ti semplifichi la vita:
$T(n) = {(O(1) if n=1),(3T(n/2) + n^2 \ other):}$
il metodo dell'albero è una sottocategoria del metodo algebrico, cioè il metodo che calcola effettivaemente una ricorrenza e ti da la vera complessità. Altre tecniche sono più veloci, ma danno solo una approssimazione di una limitazione.
Il tuo docente forse pretende solo una limitazione corretta non quella esatta. Attento però che l'induzione è effettivamente una tecnica di risoluzione...
Questi metodi servono più a capire come funzionano le limitazioni asintotiche e cosa ci sta sotto a livello algoritmico.
Di solito si va di induzione ipotizzando una limitazione, ma alle volte non è possibile fare ciò (ci vuole esperienza o si utilizza il master per alcune ricorrenze) per questo esistono metodi più algebrici ed intuitivi (come l'albero).
"pippopelo":
Penso che il modo migliore per verificare quanto ho capito è prendere un esercizio e risolverlo. beh ci provo con questo.
$T(n) = {(O(1) if n<=4),(T(n)=T(n/4)+T(3n/4) + n \ other):}$
la nostra ricorrenza "semplificata" è: $T(n) = 2T(3n/4) + n$
spero tu abbia capito il perchè di questa trasformazione di T(n) e della sua validità (rivedi i post che ti ho linkato in caso).
vedila così:
$T(n/4)+T(3n/4) + n <= 2T(3n/4) + n$
cerchi una limitazione superiore stretta sulla ricorrenza originale, per essere pignoli trovi un o-piccolo su $T(n)$.
Ma sono cose secondarie.
$(3/4)^i\n = 1$ quando $i=log_(4/3)n$. Perciò l'albero ha profondità massima $log_(4/3)n$
(*) hai capito perchè il logaritmo a base invertita rispetto alla base dell'esponenziale? E' un punto abbastanza importante del metodo dell'albero, ed in questo caso mostra il suo funzionamento alla base (con n=1).
Noi dobbiamo fermarci a $n=5$ per il calcolo dei nodi interni, poi calcoliamo il caso $n<=4$ dove consideriamo $4$ livelli di foglie distinte per semplificarci la vita, cioè sommiamo semplicemente delle foglie con la sommatoria generale che mostro ora.
Prima cosa calcoliamo i nodi interni, sommando i vari livelli dell'albero a livello $i-$esimo dalla radice a $n=5$ cioè a profondità $log_(4/3)(n)-4$
sai cosa sono i nodi interni?
Nel caso delle ricorrenze deve esserci distinzione tra il calcolo dei nodi interni (con costo variabile dettato dalla funzione libera e dai rami di T(n)) e le foglie (con costo costante o prestabilito).
$n*((3/2)^((log_(4/3)(n)-4)+1) - 1)/((3/2)-1) =$ utilizzo qualche proprietà delle potenze e l'uguaglianza $a^{log_b(n)} = n^{log_b(a)}$
$= n*((n^{log_(4/3)(3/2)}/(3/2)^4) - 1) / (1/2) = 2n * (n^{log_(4/3)(3/2)}/((3/2)^4) - 1) = 27/4n^{log_(4/3)(3/2)+1} - 2n$
piccola svista penso (cose secondarie):
$(3/2)^((log_(4/3)(n)-4)+1) = (3/2)^(log_(4/3)(n)-3) = n^(log_(4/3)(3/2))/(3/2)^3$
Ora calcoliamo i cinque livelli di foglie di costo singolarmente $O(1)$: Questo passaggio non l'ho capito....
vedila in questo modo.
Negli alberi completi (es. binari) c'è solo un livello di foglie, l'ultimo di profondità massima.
In questi alberi le foglie rappresentano i costi costanti alla base di un algoritmo, quando $n=1$ siamo nel caso di un albero qualunque e le regole che hai imparato sono valide.
Ma nel caso che la base costante sia per più valori di $n$, l'albero non avrà più un solo livello di foglie ma tanti separati e distinti, cioè astrattamente collegati ai nodi interni.
Un disegno è più chiarificatore di mille parole:
le FOGLIE sono tanti livelli separati o collegati astrattamente ai nodi. Ma tieni in considerazione che le foglie con $n=1$ saranno sempre maggiori di quelle a $n=5$ perciò il limite superiore delle foglie sarà sempre lo stesso cambiano le costanti.
In calcoli, sommi le foglie ad ogni livello e poi sommi il tutto.
Nel caso $n=1$ risulta essere:
$2^(log_(4/3)(n))*(3/2)^(log_(4/3)(n))$ per via dell'uguaglianze scritta sopra (*)
$(3/2)^(log_(4/3)(n))n = 1$ perciò la condizione $O(1)$ quando $n=1$ è rispettata e si calcola (o sostituisce):
$2^(log_(4/3)(n))*O(1) =$ ...
il resto sono solo sommme.
Poi come faccio ad eseguire il $log_(4/3)$ del risultato che uscirà
bhè questo è un semplice calcolo di un logaritmo, utilizza la classica formula per calcolare un logaritmo in una base che più ti piace, tipo in base $10$ risulterà:
$log_(4/3)(a) = (log_(10)(a))/(log_(10)(4/3))$
(alla fine mi è bastato sostituire i numeri e fare un pò di conti a dire il vero) (penso lo abbia notato)
un po' lo ho notato
ma attento a non sostituire senza capire cosa ci sta sotto, alla fine sono solo qualche sommatoria e potenze.
Prova a calcolare una di tipo diverso, considerando semplicemente un caso base O(1) quando $n=1$ così ti semplifichi la vita:
$T(n) = {(O(1) if n=1),(3T(n/2) + n^2 \ other):}$
Non capisco come questo esercizio sia valutato dal mio prof solo 6/100. Ad ogni modo l'induzione la farò per un mio tornaconto personale ma non penso di farlo sul compito poichè perderei troppo tempo (ho solo 2 h e ci sono algoritmi di Dijkstra,Bellman-Ford, e altri soliti problemi di algoritmica) quindi non ho molto fretta di impararla...
il metodo dell'albero è una sottocategoria del metodo algebrico, cioè il metodo che calcola effettivaemente una ricorrenza e ti da la vera complessità. Altre tecniche sono più veloci, ma danno solo una approssimazione di una limitazione.
Il tuo docente forse pretende solo una limitazione corretta non quella esatta. Attento però che l'induzione è effettivamente una tecnica di risoluzione...
Questi metodi servono più a capire come funzionano le limitazioni asintotiche e cosa ci sta sotto a livello algoritmico.
Di solito si va di induzione ipotizzando una limitazione, ma alle volte non è possibile fare ciò (ci vuole esperienza o si utilizza il master per alcune ricorrenze) per questo esistono metodi più algebrici ed intuitivi (come l'albero).
...
Essendo $c=5$ e $d=1/7$ allora scrivo $\f(n)+ g(n)≤ (5+1/7) · (f(n)+g(n))$ ovvero
$\f(n)+ g(n)≤ 36/7 · (f(n)+g(n))$ ma $\f(n)+ g(n)$ è sicuramente $≤ 36/7 · (f(n)+g(n))$ C.V.D.
mi pare ok. Nelle forme generali non si può dire molto. Attento che:
$5f(n)+ 1/7g(n) <= e*(f(n)+g(n))$
$(36/7)(f(n)+g(n)) <= e*(f(n)+g(n))$
per $e>=36/7$ ed un $n_0$ qualunque (perchè non sappiamo nulla sulle funzioni in gioco)
un po' la stessa cosa circa, ma attenzione. Potresti anche scrivere che non sapendo che funzioni siano (cioè non sono algrbricamente "compatibili"), non potresti fare mcm come hai fatto, ma poresti trovare due costanti $c>=5$ e $d>=1/7$ che verifichino l'ipotesi.
Analogamente procedo con $Ω()$ però con $≥$.
esatto. Basta seguire la definzione pari pari essendo $f(n)$ e $g(n)$ due funzioni qualunque.
Se non è cosi potresti aiutarmi l'esame è domani!!
mmm brutta storia. Dovevi segnalarlo prima, non mi sarei messo a mostrati il metodo dell'albero ma una tecnica più veloce e pratica. Anche se penso tu sappia che per un esame non si imparano tecniche o qualunque cosa il giorno prima...ma tant'è.
L'esame l'ho fatto...ha dato la stessa ricorrenza che mi hai risolto tu...poi ti farò sapere come è andata...comunque successivamente tornerò sull'argomento in modo da approfondire per conto mio.
Grazie.
Grazie.
"pippopelo":
L'esame l'ho fatto...ha dato la stessa ricorrenza che mi hai risolto tu...poi ti farò sapere come è andata...comunque successivamente tornerò sull'argomento in modo da approfondire per conto mio.
Grazie.
sei stato fortunato a ritrovartela
comuque, quando avrai dubbi, basta scrivere nella sezione Informatica, ti si darà na mano.
Sono andato a vedere il compito, la risposta alla ricorrenza è O(nlogn) e che l'albero di ricorrenza va costruito secondo la traccia senza poter applicare la limitazione superiore. A tal proposito non serve nemmeno la sommatoria dopo. Possiamo provare a risolvere la ricorrenza come data dal prof, per piacere..
Io cerco di girovagare in rete e risolverla prima da me poi domani ti posto i miei risultati. Provo un pò a sbatterci la testa.
Bye
Io cerco di girovagare in rete e risolverla prima da me poi domani ti posto i miei risultati. Provo un pò a sbatterci la testa.
Bye
"pippopelo":
Sono andato a vedere il compito, la risposta alla ricorrenza è O(nlogn) e che l'albero di ricorrenza va costruito secondo la traccia senza poter applicare la limitazione superiore.
ok ho capito, mi dispiace.
Ma forse sono stato io ha non spiagartela bene, anche perchè secondo me non hai compreso fino in fondo ciò che la riscrittura comporta e come la si utilizza in modo adeguato.
Devo dire che solo ora mi sono accorto della semplicità di queste ricorrenze e che la riscrittura non serviva (ecco del perchè di 6/100 punti), io ho riscritto poi dimenticandomi completamente dell'orginale
Cerco di spiegare meglio come approcciarsi alle ricorrenze con più rami di ricorsione e dove la tecnica di riscrittura è un buon metodo di risoluzione e dove fallisce (cioè si può utilzzare la ricorrenza originale trovando la limitazione senza fatica algebrica).
Utilizzo queste due ricorrenze:
$T_1(n) = T(n/5) + T(4n/5) + n$
$T_2(n) = T(n/4) + T(3n/5) + n$
tutte con costo $O(1)$ quando $n=1$.
Con più rami di ricorsione tutto si complica, ma a seconda della suddivisione dei rami, se equilibrata, la complicazione si annulla.
Vediamo $T_1(n)$ con il metodo dell'albero direttamente.
$n$
$1/5n\ \ 4n/5 = (1/5 + 4/5)n = n$
$1/25n\ \ 4/25n\ \ 4/25n\ \ 16/25\ = (1/25 + 4/25 + 4/25 + 16/25)n = n$
...
andando avanti si scopre che tutti i livelli si distribuiscono i costi in modo equilibrato, rendendo il costo di livello sempre uguale a $O(1)*n$.
calcoliamo allora la profondità massima che può raggiungere questo albero:
$(4n/5)^i\n = 1$ quando $i=log_{5/4}(n)$
Da tenere in considerezione che questo albero è pieno di puchi e in pendenza, non è completo ed il calcolo delle foglie è quasi inutile, dato che ad ogni livello sono sempre in meno del livello $i$.
perciò alla fine ci si riduce ad una somma dei livelli linearmente fino a profondità massima (non cambia se a profondità minore):
$sum_{i=0}^{log_{5/4}(n)} n = n*(log_{5/4}(n) + 1) in O(nlog_{5/4}(n))$
come si vede si è trovata una limitazione molto più stretta di quella calcolata precedentemente ($o(n^3.1)$).
Vediamo $T_2(n)$ con il metodo dell'albero direttamente.
In questa ricorrenza i costi NON sono equilibrati; vediamo perchè applicando direttamente l'albero:
$n$
$n/4 \ 3/5n = (1/4 + 3/5)n = 17/20n$
$n/16 \ 3/20n \ 3/20n \ 9/25n = ...$
$...$
già al secondo livello si può vedere che i costi sono talmente discordanti che andando avanti, i costi del cammino dell'albero tramite $3/5n$ spadroneggerà su tutti. L'albero avrà molti più buchi di $T_1(n)$ e sarebbe inutile calcolare precisamente questi costi e dove davvero saltano fuori. Per evitare tutto questo (inutile) calcolo, si preferisce limitare superiormente (e inferiormente) questa ricorrenza riscrivendola con il ramo che spadroneggia sui costi totali. Perciò:
$2T(n/4) + n < T(n/4) + T(3n/5) + n < 2T(3n/5) + n $
calcolando le limitazioni avremo:
$omega(f(n)) < T(n/4) + T(3n/5) + n < o(g(n))$
facendo questo si circonda la ricorrenza originale con due limitazioni (che possiamo calcolare anche con altre tecniche se è possibile); perciò rendendo chiaro l'andamento possiamo ipotizzare una complessità più stretta nei limiti trovati (tra $omega(f(n))$ e $o(g(n))$).
Come vedi utilizzare una o l'altra tecnica dipende dai valori della ricorrenza:
- $T_1$ è equilibrata perciò è fattibile utilizzare l'albero direttamente
- $T_2$ è più complicata ed è in questo caso si utilizza la riscrittura. Cosa che purtroppo ti ho proposto di fare da subito, non ho valutato i valori.
Da sottolineare che l'albero da sempre limitazioni superiori, precise o meno, per averne di più strette si ipotizza diminuendo l'ordine di grandezza della complessità con altre tecniche (v. es. questa dove abbiamo utilizzato 3 tecniche e con una di esse, ne abbiamo trovata una più stretta).
se hai domande chiedi pure
Onestamente come già detto il costo dei nodi interni era difficile ma il resto l'ho capito. il prof non vuole cose da lui non spiegate ma ha lasciato passare limitazione ed altre cose tanto più che alla fine me l'ha valutato 4/6 che tutto sommato non è male.
L'esercizio in questo modo è molto semplice, l'albero l'ho capito (ho trovato materiale interessante 10 min fa) e lo stavo vedendo proprio ora. Tutti i passaggi mi sono chiari, ora è davvero esaustivo ( e molto semplice). Ti ringrazio x la disponibilità e per il tempo perso a spiegarmi queste cose.
Si può anche chiudere.
L'esercizio in questo modo è molto semplice, l'albero l'ho capito (ho trovato materiale interessante 10 min fa) e lo stavo vedendo proprio ora. Tutti i passaggi mi sono chiari, ora è davvero esaustivo ( e molto semplice). Ti ringrazio x la disponibilità e per il tempo perso a spiegarmi queste cose.
Si può anche chiudere.
di nulla
Tutto questo va ben oltre un semplice esercizio di un esame; son stato molto più ampio per farti capire (almeno ho provato) diversi modi di vedere la stessa tecnica, e che insidie ci possono essere (come è accaduto sottovalutando la filosofia KISS).
Se avrai altri dubbi basterà postare, alla prossima.
Tutto questo va ben oltre un semplice esercizio di un esame; son stato molto più ampio per farti capire (almeno ho provato) diversi modi di vedere la stessa tecnica, e che insidie ci possono essere (come è accaduto sottovalutando la filosofia KISS).
Se avrai altri dubbi basterà postare, alla prossima.
"hamming_burst":
(almeno ho provato)
Ci sei riuscito molto bene, considerando che siamo entrambi dietro al pc e non possiamo avere un confronto diretto. Very good. Alla prossima
Salve ragazzi, rispondo in questo thread dato che anch'io sto preparando l'esame di Algoritmi e gli esercizi d'esame postati qui sono identici ai miei (probabilmente io e pippopelo seguiamo con lo stesso Prof!).
Ho un dubbio sullo svolgimento della parte a) dell'esercizio, quello relativo alle notazioni asintotiche.
Secondo definizione, per verificare se $ 5f(n)+1/7g(n)inTheta(f(n)+g(n)) $ devo trovare $ c1,c2 > 0 $ e $ n_0 >= 0 $ tali che $ c1*(f(n)+g(n))<=5f(n)+1/7g(n)<=c2*(f(n)+g(n)) $ per ogni $ n>=n_0 $
Detto questo, qual è il modo corretto per trovare $ c1 $ e $ c2 $?
Ho un dubbio sullo svolgimento della parte a) dell'esercizio, quello relativo alle notazioni asintotiche.
Secondo definizione, per verificare se $ 5f(n)+1/7g(n)inTheta(f(n)+g(n)) $ devo trovare $ c1,c2 > 0 $ e $ n_0 >= 0 $ tali che $ c1*(f(n)+g(n))<=5f(n)+1/7g(n)<=c2*(f(n)+g(n)) $ per ogni $ n>=n_0 $
Detto questo, qual è il modo corretto per trovare $ c1 $ e $ c2 $?
Ciao,
lo avevo introdotto in qualche post di questo stesso topic, forse è scritto male...
Prova a vedere qui, dove è spiegato praticamente tutto.
Scrivi pure qua i passaggi così vediamo se è ok, è molto semplice.
lo avevo introdotto in qualche post di questo stesso topic, forse è scritto male...
Prova a vedere qui, dove è spiegato praticamente tutto.
Scrivi pure qua i passaggi così vediamo se è ok, è molto semplice.
Innanzitutto grazie per la risposta! Ho letto il post che mi hai linkato, quindi per semplificare il tutto posso procedere a verificare prima l'upper bound ($ O $) e poi il lower bound ($ Omega $), ovvero
$ 5f(n)+1/7g(n)<=c*(f(n)+g(n)) $ per una qualche costante $ c>0 $ e per ogni $ n>=n_0 $ e
$ 5f(n)+1/7g(n)>=d*(f(n)+g(n)) $ per una qualche costante $ d>0 $ e per ogni $ n>=n_0 $
La prima parte posso riscriverla come $ 5f(n)+1/7g(n)<=c*f(n)+c'*g(n) $ ed è verificabile per $ c>=5 $ e per $ c'>=1/7 $
La seconda parte è praticamente identica (con segni di disuguaglianza invertiti).
Dato che, secondo definizione, $ f(n)=Theta g(n) $ se e solo se $ f(n)=Og(n) $ e $ f(n)=Omega g(n) $, la relazione è verificata.
Sbaglio qualcosa?
$ 5f(n)+1/7g(n)<=c*(f(n)+g(n)) $ per una qualche costante $ c>0 $ e per ogni $ n>=n_0 $ e
$ 5f(n)+1/7g(n)>=d*(f(n)+g(n)) $ per una qualche costante $ d>0 $ e per ogni $ n>=n_0 $
La prima parte posso riscriverla come $ 5f(n)+1/7g(n)<=c*f(n)+c'*g(n) $ ed è verificabile per $ c>=5 $ e per $ c'>=1/7 $
La seconda parte è praticamente identica (con segni di disuguaglianza invertiti).
Dato che, secondo definizione, $ f(n)=Theta g(n) $ se e solo se $ f(n)=Og(n) $ e $ f(n)=Omega g(n) $, la relazione è verificata.
Sbaglio qualcosa?
"carmine_c":
quindi per semplificare il tutto posso procedere a verificare prima l'upper bound ($ O $) e poi il lower bound ($ Omega $),
più che una semplificazione è la definizione di $Theta()$ vista in un altro modo
La prima parte posso riscriverla come $ 5f(n)+1/7g(n)<=c*f(n)+c'*g(n) $ ed è verificabile per $ c>=5 $ e per $ c'>=1/7 $
La seconda parte è praticamente identica (con segni di disuguaglianza invertiti).
attento meglio essere puntigliosi (visto la semplicità del tutto) non $c$ e $c'$ ma meglio usare nomi diversi $c'$ e $c''$ e manca di dire un $n_0$ qualunque (con condizione da definizione).
Dato che, secondo definizione, $ f(n)=Theta g(n) $ se e solo se $ f(n)=Og(n) $ e $ f(n)=Omega g(n) $, la relazione è verificata.
stessa cosa di sopra, visto che i nomi $f$ e $g$ sono legati hai millemila altri simboli da poter utilizzare
per il resto ok
Ok quindi devo solo fare attenzione all'uso di simboli diversi per le costanti.
In effetti per concludere potrei anche scrivere che
$ 5f(n)+1/7g(n)=O(f(n)+g(n)) $ e $ 5f(n)+1/7g(n)=Omega(f(n)+g(n)) $ pertanto la relazione $ 5f(n)+1/7g(n)=Theta(f(n)+g(n)) $ è verificata.
In sostanza, il procedimento è corretto?
stessa cosa di sopra, visto che i nomi f e g sono legati hai millemila altri simboli da poter utilizzare
In effetti per concludere potrei anche scrivere che
$ 5f(n)+1/7g(n)=O(f(n)+g(n)) $ e $ 5f(n)+1/7g(n)=Omega(f(n)+g(n)) $ pertanto la relazione $ 5f(n)+1/7g(n)=Theta(f(n)+g(n)) $ è verificata.
In sostanza, il procedimento è corretto?
si circa è quello
comunque visto che lo abbiamo scritto in troppi pezzi, ti riassumo circa quello penso il tuo docente si aspetti, si può impostare in diversi modi tutti equivalenti. Questo è uno di quelli.
Si consideri la seguente funzione generica: \(t(n) = 5f(n) + \frac{1}7g(n)\). Vogliamo provare che \(t(n) \in \Theta(f(n) + g(n))\).
Dobbiamo provare che:
\[\exists c > 0,\ d > 0,\ m \geq 0\ :\ c(f(n)+g(n)) \leq 5f(n) + \frac{1}7g(n) \leq d(f(n)+g(n))\ ,\ \forall n \geq m\]
Si può procedere così:
\[t(n) = 5f(n) + \frac{1}7g(n)\]
\[\leq d(f(n)+g(n)) = d_1f(n) + d_2g(n)\]
che e vera per un qualche $m \geq 0$ (non si sa nulla sulle funzioni) e \(d_1 \geq 5 \wedge d_2 \geq \frac{1}7\). Inoltre,
\[t(n) = 5f(n) + \frac{1}7g(n)\]
\[\geq c(f(n)+g(n)) = c_1f(n) + c_2g(n)\]
che e vera per qualche $m \geq 0$ (non si sa nulla sulle funzioni) e \(c_1 \leq 5 \wedge c_2 \leq \frac{1}7\).
comunque visto che lo abbiamo scritto in troppi pezzi, ti riassumo circa quello penso il tuo docente si aspetti, si può impostare in diversi modi tutti equivalenti. Questo è uno di quelli.
Si consideri la seguente funzione generica: \(t(n) = 5f(n) + \frac{1}7g(n)\). Vogliamo provare che \(t(n) \in \Theta(f(n) + g(n))\).
Dobbiamo provare che:
\[\exists c > 0,\ d > 0,\ m \geq 0\ :\ c(f(n)+g(n)) \leq 5f(n) + \frac{1}7g(n) \leq d(f(n)+g(n))\ ,\ \forall n \geq m\]
Si può procedere così:
\[t(n) = 5f(n) + \frac{1}7g(n)\]
\[\leq d(f(n)+g(n)) = d_1f(n) + d_2g(n)\]
che e vera per un qualche $m \geq 0$ (non si sa nulla sulle funzioni) e \(d_1 \geq 5 \wedge d_2 \geq \frac{1}7\). Inoltre,
\[t(n) = 5f(n) + \frac{1}7g(n)\]
\[\geq c(f(n)+g(n)) = c_1f(n) + c_2g(n)\]
che e vera per qualche $m \geq 0$ (non si sa nulla sulle funzioni) e \(c_1 \leq 5 \wedge c_2 \leq \frac{1}7\).
Ok tutto chiaro!
Ti ringrazio, sei stato di grande aiuto!
Alla prossima.
Ti ringrazio, sei stato di grande aiuto!
Alla prossima.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo