Pages: [1] 2 3 ... 5   Go Down
Print
Author Topic: Domanda compito  (Read 9296 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« on: 02-03-2010, 19:26:05 »

Sia f(n)=O(g(n)), quale delle seguenti affermazioni potrebbe essere non vera


a.  f(n)=O(2*g(n))

b.  g(n)=O(f(n)) 

c.  g(n)=\Omega(f(n))

d.  f(n)=O(4*g(n))

Secondo me la risposta errata è la b; voi che ne pensate?
Logged
Psycho
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 497



« Reply #1 on: 02-03-2010, 19:35:48 »

anche secondo me dovrebbe essere la b  ok
Logged

Segnate le date, cancellate gli altri impegni, chiudete i libri e i quaderni e per un attimo accorgetevi che la vita non è piatta ma può essere... 3d!
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #2 on: 02-03-2010, 19:54:26 »

grazie per avermi risposto,  ok

ho ragionato così:

la a e la d sono vere per definizione di O(g(n)); la c risulta vera perchè per definizone  \Omega(g(n)) è un limite inferiore per f(n); quindi credo che se f(n)=O(g(n)) significa che f(n) sta al di sotto di g(n) e se g(n)=\Omega(f(n)) significa che g(n) sta al di sopra di f(n); cioè le due cose sono equivalenti. Facendo analoghi ragionamenti la risposta b risulta errata.

Non so se voi avete pensato in questo modo.
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #3 on: 02-03-2010, 22:38:41 »

si è giusto il tuo ragionamento. Oltre ad essere una proprietà, potevi banalmente pensare che g sta sopra all'infinito, di conseguenza f sempre sta sotto.
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #4 on: 03-03-2010, 19:53:04 »

Data l'equazione di ricorrenza  T(n)=T(n/2)+\sqrt(n), la sua soluzione è (scegliere il bound più stretto)

a.    T(n)=O(log n)

b.    T(n)=O(\sqrt n)

c.    T(n)=O(n)

d.    T(n)=O(n log n)


Secondo me applicando il Teorema Master rientriamo nel 3° caso e quindi la soluzione sarebbe T(n)=\Theta(\sqrt n);
poi ho pensato che se f(n)=\Theta(g(n)) ==> f(n)=O(g(n)) e quindi deduco che  T(n)=O(\sqrt n); in questo caso avrei risposto mettendo b.

Non mi è chiaro però quando si chiede di prendere il bound più stretto; in tal caso la mia risposta sarebbe stata c.

Voi come rispondereste a questa domanda?

Grazie 
Logged
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #5 on: 03-03-2010, 20:13:55 »

secondo me è anche la B.

è il terzo caso perchè f(n)= omega(n^log2+e) , di conseguenza la soluzione è f(n)

invece vi vorrei chiedere perchè questa ricorrenza

T(n) = 4T(n/5) + T(n/6) + n

risulta O(n)??

mi potreste dimostrare il perchè si ottiene questa soluzione?
« Last Edit: 03-03-2010, 20:20:06 by Alex_47 » Logged
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #6 on: 04-03-2010, 09:00:59 »

e che mi dite invece riguardo al prendere la soluzione con bound più stretto ? la soluzione della ricorrenza risulterebbe comunque O(\sqrt n) ?
« Last Edit: 04-03-2010, 09:02:48 by gam » Logged
Eleirgab
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 344


Apprezzatemi ora. Eviterete la fila


WWW
« Reply #7 on: 04-03-2010, 13:30:56 »

e che mi dite invece riguardo al prendere la soluzione con bound più stretto ? la soluzione della ricorrenza risulterebbe comunque O(\sqrt n) ?
Scusa, ma O(n) è un bound meno stretto di O(\sqrt{n})
E' normale che per sostituzione ti risulti lo stesso Cheesy
Logged

Collettivo SDAI

-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GIT d-- s+:+ a-- C++ UL++ P L+++ E- W+++>$ N? o? K- w-- O? M V? PS++ PE- Y+ PGP- t 5? X+ R>+ tv-- b++ DI+++ D- G e h! r y+
------END GEEK CODE BLOCK-----
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #8 on: 04-03-2010, 14:07:26 »

in definitiva la risposta è b ,vero?
Logged
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #9 on: 04-03-2010, 16:59:42 »

Data l'equazione di ricorrenza  T(n)=T(n-1)+\frac{1}{n}, la sua soluzione è (scegliere il bound più stretto)

a.    T(n)=O(1)

b.    T(n)=O(log n)

c.    T(n)=O(n)

d.    T(n)=O(n log n)


Secondo me applicando la tecnica del Telescoping risulta come soluzione T(n)=O(1); quindi avrei messo a.

secondo voi?

Grazie 
Logged
Psycho
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 497



« Reply #10 on: 04-03-2010, 17:55:28 »

utilizzando il telescoping si ha la sommatoria per i che va da 0 a n di 1/i, il risultato dovrebbe essere O(logn)
Logged

Segnate le date, cancellate gli altri impegni, chiudete i libri e i quaderni e per un attimo accorgetevi che la vita non è piatta ma può essere... 3d!
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #11 on: 04-03-2010, 18:01:37 »

si hai ragione ho capito dove sbagliavo. Per la sommatoria hai considerato la serie armonica? e da li ti sei ricondotto al logn?
Logged
Psycho
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 497



« Reply #12 on: 04-03-2010, 18:09:08 »

esattamente 
Logged

Segnate le date, cancellate gli altri impegni, chiudete i libri e i quaderni e per un attimo accorgetevi che la vita non è piatta ma può essere... 3d!
Gam
Apprendista Forumista
**
Offline Offline

Posts: 385



« Reply #13 on: 04-03-2010, 18:45:07 »

Il numero massimo di elementi in una heap di altezza h>0 è (una heap con un solo elemento ha altezza zero)

a.   2^h

b.   2^h +1

c.   2^{h+1} -1

d.  2^{h+1}


Per rispondere a questa domanda ho ragionato così:

Una Heap è un albero binario completo fino al penultimo livello (questo conterrà esattamente 2^{h-1} nodi); siccome viene chiesto il numero massimo di nodi ad altezza h, allora secondo me significa che l'ultimo livello sarà composto da 2^{h}-1 nodi.

Se adesso andiamo a sommare il numero di nodi per ogni livello di questo albero binario, dovremmo ottenere 2^{h+1}-1.
A questo punto risponderei mettendo c

Secondo voi è la risposta giusta oppure sbaglio nel ragionamento?
Grazie.
Logged
Daniele
Matricola
*
Offline Offline

Posts: 81


« Reply #14 on: 04-03-2010, 18:53:01 »

anche secondo me è la c, ogni livello ha 2^i nodi  quindi svolgendo la sommatoria che va da i=0 a h di 2^i ottieni proprio 2^(h+1)-1
Logged
Pages: [1] 2 3 ... 5   Go Up
Print
Jump to: