Pages: [1] 2   Go Down
Print
Author Topic: Aiuto esercizi  (Read 3028 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Angelo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 274



« on: 05-09-2011, 09:10:41 »

Link Immagine

Ragazzi (perdonatemi se non ho scritto il testo e ho preferito postare le immagini)..sapreste spiegarmi questi due esercizi?

nella mia testa pensavo di averli capiti..e invece.. 
Logged

..elimindo il ponte pedonale di andrea doria..hanno eliminato una parte di me!..
Mimmo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 433


We don't need no thought control...


« Reply #1 on: 05-09-2011, 09:42:38 »

Ciao,
per il primo posso dirti che secondo me la soluzione è a perché:

2^{\log_4(n)}=n^{log_4(2)}=n^{1/2}=\sqrt{n}

per cui:

\sqrt{n}=O(n^2) ma non è vero \sqrt{n}=\Omega(n^2)

Lo stesso ragionamento per dimostrare le altre risposte...

Per il secondo esercizio io risponderei b perché:

9^{\log_3(n)}=n^{\log_3(9)}=n^2

poiché n\sqrt{n}=n^{1.5} e  1.5<2 segue che n\sqrt{n}=O(9^{\log_3(n)})

io ho ragionato così
 
Logged

A strange game. The only winning move is not to play. How about a nice game of chess? [Joshua]
Vincenzo Cutello
Administrator
Forumista
*****
Offline Offline

Gender: Male
Posts: 600


« Reply #2 on: 05-09-2011, 12:13:58 »

Ciao,
per il primo posso dirti che secondo me la soluzione è a perché:

2^{\log_4(n)}=n^{log_4(2)}=n^{1/2}=\sqrt{n}

per cui:

\sqrt{n}=O(n^2) ma non è vero \sqrt{n}=\Omega(n^2)

Sei proprio sicuro di questa affermazione???


Logged
Mimmo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 433


We don't need no thought control...


« Reply #3 on: 05-09-2011, 14:26:25 »

  Vediamo, ricomincio prestando maggiore attenzione

partendo dalla notazione \Theta abbiamo:

\Theta(n^2)=(2^{log_4(n)} : \exists c_1 , c_2 , n_0 > 0 : 0 \leq c_1n^2 \leq 2^{log_4(n)} \leq c_2n^2)

in effetti prendendo c_1=\frac{1}{n^2} e c_2=1 riusciamo a soddisfare c_1n^2 \leq n^{log_4(2)} \leq c_2n^2

che diventa

1 \leq n^{log_4(2)} \leq n^2 =>  n^0 \leq n^{log_4(2)} \leq n^2 =>  0 \leq log_4(2) \leq 2

però dalla definizione sappiamo che c_1 è una costante, per cui non sono sicuro di poter prendere c_1=\frac{1}{n^2} al variare di n

Per cui ho provato a fare qualche calcolo:
posto n_0=4 ho:

c_1 \leq \frac{1}{8} e c_2 \geq \frac{1}{8}

posto c_1 =\frac{1}{8} e c_2 =5 con n \geq 4 a meno che non ho sbagliato qualche calcolo la c_1n^2 \leq n^{log_4(2)} \leq c_2n^2 mi risulta sempre falsa tranne per n=4...a questo punto continuerei a dire che la risposta è la a e se sbagliata chiedo a chi più competente di me di correggere il ragionamento...prima che mi venga qualche crisi esistenziale!  testate
« Last Edit: 06-09-2011, 06:53:29 by Mimmo » Logged

A strange game. The only winning move is not to play. How about a nice game of chess? [Joshua]
Vincenzo Cutello
Administrator
Forumista
*****
Offline Offline

Gender: Male
Posts: 600


« Reply #4 on: 05-09-2011, 21:30:36 »

Vediamo, ricomincio prestando maggiore attenzione



EDIT. qualche collega mi ha detto di cancellare il ragionamento perché è sbagliato...io non lo tolgo perché vorrei essere corretto, visto che nessuno nasce "imparato"
Scusami, senza occhiali avevo letto male il tuo post precedente.
Quello che avevi scritto e' corretto.
Quindi alla mia domanda, rispondi: SI! 
Logged
mafalda
Apprendista Forumista
**
Offline Offline

Posts: 430


CЯΣDΣЯCI SΣMPЯΣ, ΛЯЯΣПDΣЯSI MΛI!


« Reply #5 on: 14-09-2011, 11:36:08 »

Mi sorge un dubbio...
Applicando il Teorema Master, la soluzione di questa ricorrenza T(n)= 5T(\frac{n}{5}) + n\log n è:
O(n) oppure O(n^{2}\log n) ?
Logged

...๔єςเ, ๔єςเ, ๔єςเ...
Crasher
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 417



« Reply #6 on: 14-09-2011, 13:41:53 »

Mi sorge un dubbio...
Applicando il Teorema Master, la soluzione di questa ricorrenza T(n)= 5T(\frac{n}{5}) + n\log n è:
O(n) oppure O(n^{2}\log n) ?
http://forum.sdai.unict.it/index.php?topic=13511.0
Logged

Diventa ciò che sei nato per essere
Misa
Matricola
*
Offline Offline

Posts: 57



« Reply #7 on: 14-09-2011, 13:42:55 »

Mi sorge un dubbio...
Applicando il Teorema Master, la soluzione di questa ricorrenza T(n)= 5T(\frac{n}{5}) + n\log n è:
O(n) oppure O(n^{2}\log n) ?

Non puoi applicare il teorema master per trovare la soluzione di tale ricorrenza.
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #8 on: 14-09-2011, 17:47:17 »

Premesso che Crasher ha quotato quello che vi serve:

Quote
Non puoi applicare il teorema master per trovare la soluzione di tale ricorrenza.

Non sono d' accordo......
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #9 on: 14-09-2011, 18:23:54 »

Non puoi applicare il teorema master per trovare la soluzione di tale ricorrenza.
E perche' mai?  testate
Logged
Misa
Matricola
*
Offline Offline

Posts: 57



« Reply #10 on: 15-09-2011, 08:38:39 »

Perche' siamo nel terzo caso e non e' soddisfatta la condizione:

af(\frac{n}{b}) < cf(n), per una c<1 ed N sufficientemente alto.

Che dite?
Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #11 on: 15-09-2011, 09:11:09 »

Perche' siamo nel terzo caso e non e' soddisfatta la condizione:

af(\frac{n}{b}) < cf(n), per una c<1 ed N sufficientemente alto.

Che dite?
Che hai toppato  testate

La ricorrenza ha la seguente soluzione per il 2 caso del teorema Master
T(n) = \Theta(n\ \log^2 n)
                  univ
Logged
Misa
Matricola
*
Offline Offline

Posts: 57



« Reply #12 on: 15-09-2011, 09:29:05 »

Che hai toppato  testate

La ricorrenza ha la seguente soluzione per il 2 caso del teorema Master
T(n) = \Theta(n\ \log^2 n)
                  univ

Il secondo caso del teorema master si applica:
-Se  f(n) = \Theta( n^{log_b(a)}) , cioe'
 f(n) = \Theta( n^{log_5(5)})
 f(n) = \Theta( n^1)

ma noi abbiamo:

 nlogn = \Theta( n) . che e' falso!
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #13 on: 15-09-2011, 11:31:32 »

Purtroppo non è così. shiny ha molta più esperienza di noi in materia, mi ha aiutato molto per questo esame. 
Il nostro è il secondo caso generalizzato del teorema Master.

f(n)=\theta(n^{\log_b(a)}*\log_b(n)^k) con k\geq 0

Che mi sembra funzioni alla grande.
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Misa
Matricola
*
Offline Offline

Posts: 57



« Reply #14 on: 15-09-2011, 11:46:23 »

Purtroppo non è così. shiny ha molta più esperienza di noi in materia, mi ha aiutato molto per questo esame.  
Il nostro è il secondo caso generalizzato del teorema Master.

f(n)=\theta(n^{\log_b(a)}*\log_b(n)^k) con k\geq 0

Che mi sembra funzioni alla grande.

Adesso si che le cose cambiano. Grazie, aggiungero' questa clausola nei miei appunti.
(mi sembra strano che sulle slide non ci sia, e che sul Cormen sia ben nascosta :/ )
« Last Edit: 15-09-2011, 11:49:22 by Misa » Logged
Pages: [1] 2   Go Up
Print
Jump to: