Pages: 1 2 [3] 4 5 ... 12   Go Down
Print
Author Topic: risposte esatte  (Read 30976 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Pandemia000
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.714


Γνῶθι Σεαυτόν


« Reply #30 on: 20-02-2009, 14:01:22 »

si dovrebbero sommare tutti i livelli quindi a livello 0 avremmo n, a livello 1 2(n+1), a livello 2 2(n+1), a livello i,  log(2n+2), da cui segue sommatoria(per i che va da i a log(2n+2)+1 di 2n+2. Portando questo ultimo termine fuori dal segno di sommatoria poichè non dipende da i, otteniamo (2n+2)(log(2n+2)+1). Moltiplicando e prendendo i termini di ordine superiore otteniamo  2n log(2n+2).
Logged

La disumanità del computer sta nel fatto che, una volta programmato e messo in funzione, si comporta in maniera perfettamente onesta. (Isaac Asimov)
IRon
Matricola
*
Offline Offline

Posts: 84



« Reply #31 on: 20-02-2009, 14:11:52 »

n livelli di costo (2^i)*(n-i), dove i è il livello.
Logged
Vincenzo Cutello
Administrator
Forumista
*****
Offline Offline

Gender: Male
Posts: 600


« Reply #32 on: 20-02-2009, 14:47:03 »

si dovrebbero sommare tutti i livelli quindi a livello 0 avremmo n, a livello 1 2(n+1), a livello 2 2(n+1), a livello i,  log(2n+2), da cui segue sommatoria(per i che va da i a log(2n+2)+1 di 2n+2. Portando questo ultimo termine fuori dal segno di sommatoria poichè non dipende da i, otteniamo (2n+2)(log(2n+2)+1). Moltiplicando e prendendo i termini di ordine superiore otteniamo  2n log(2n+2).

Caro Pandemia, prima di postare faresti meglio a ripassare 
Logged
goblin
Guest
« Reply #33 on: 20-02-2009, 14:51:29 »

In altre parole la soluzione è esponenziale..
Logged
Pandemia000
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.714


Γνῶθι Σεαυτόν


« Reply #34 on: 20-02-2009, 15:35:00 »

la soluzione dell'equazione di ricorrenza è allora Theta(n^2)?
Logged

La disumanità del computer sta nel fatto che, una volta programmato e messo in funzione, si comporta in maniera perfettamente onesta. (Isaac Asimov)
Pandemia000
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.714


Γνῶθι Σεαυτόν


« Reply #35 on: 20-02-2009, 16:16:13 »

  allora...  L'albero dovrebbe essere così

           n ---->n
    n-1       n-1    ---> 2 (n-1)
n-2 n-2  n-2 n-2 ----> 4(n-2)
...
....
n-i n-i ....       -----> 2^i (n-i)
.....
T(1)....T(1)   ------>Theta(n^2)
se l'altezza dell'albero è h=logn  e sommiamo i costi di tutti i livelli  otteniamo

logn -1                                                
   S   2^i(n-i)  + Theta(n^2)  =   Theta(n^2)  
  i=0                                                        

Si infatti ho dimenticato di decrementare n ad ogni livello e di calcolare il costo dell'ultimo livello. Inoltre ho corretto la sommatoria
« Last Edit: 20-02-2009, 17:26:41 by Pandemia000 » Logged

La disumanità del computer sta nel fatto che, una volta programmato e messo in funzione, si comporta in maniera perfettamente onesta. (Isaac Asimov)
IRon
Matricola
*
Offline Offline

Posts: 84



« Reply #36 on: 20-02-2009, 16:51:00 »

L'albero è sbagliato: l'input decresce di uno per ogni livello.
Logged
Mosquito
Guest
« Reply #37 on: 20-02-2009, 17:33:04 »

L'input non decresce di uno per ogni livello. Ad ogni livello hai DUE sottoproblemi di dimensione (n-1).
Logged
IRon
Matricola
*
Offline Offline

Posts: 84



« Reply #38 on: 20-02-2009, 18:17:44 »

L'input non decresce di uno per ogni livello. Ad ogni livello hai DUE sottoproblemi di dimensione (n-1).
Dimmi qual è la differenza nel caso specifico.
Ogni livello dell'albero rappresenta un livello di ricorsione e l'etichetta di ogni nodo rappresenta il costo di un sottoproblema: quindi affermare che ad ogni livello l'input decresce di 1(UNO) significa che ogni sottoproblema/i avrà input(in questo caso anche costo) inferiore di 1(UNO) rispetto al livello precedente.
Logged
AngelEvil
Forumista
***
Offline Offline

Posts: 616



« Reply #39 on: 20-02-2009, 19:28:56 »

Ragazzi per la numero 7 compito A cosa avete risposto?!?!?

  Sia T(n) una funzione che indica la complessità di Quicksort nel caso medio....

      a: ∑ i=1... n-1 T(i) +bn+a
      b: (∑ i=1...n-1 T(i))/n+bn+a
      c: 2∑  i=1...n-1 T(i)+bn+a
      d: 2(∑ i=1...n-1 T(i))/n+bn+a

io ho risposto la d



Perchè è la d??
Logged

goblin
Guest
« Reply #40 on: 20-02-2009, 22:26:22 »

Ragazzi per la numero 7 compito A cosa avete risposto?!?!?

  Sia T(n) una funzione che indica la complessità di Quicksort nel caso medio....

      a: ∑ i=1... n-1 T(i) +bn+a
      b: (∑ i=1...n-1 T(i))/n+bn+a
      c: 2∑  i=1...n-1 T(i)+bn+a
      d: 2(∑ i=1...n-1 T(i))/n+bn+a

io ho risposto la d



Perchè è la d??

si,la soluzione è T(n)=O(2^n) e non T(n)=O(n^2) ..questo perchè il numero di volte che la sommatorio dev'essere eseguita è pari a n e non logn..

Saluti
Logged
AngelEvil
Forumista
***
Offline Offline

Posts: 616



« Reply #41 on: 21-02-2009, 09:15:33 »

Ragazzi per la numero 7 compito A cosa avete risposto?!?!?

  Sia T(n) una funzione che indica la complessità di Quicksort nel caso medio....

      a: ∑ i=1... n-1 T(i) +bn+a
      b: (∑ i=1...n-1 T(i))/n+bn+a
      c: 2∑  i=1...n-1 T(i)+bn+a
      d: 2(∑ i=1...n-1 T(i))/n+bn+a

io ho risposto la d



Perchè è la d??

si,la soluzione è T(n)=O(2^n) e non T(n)=O(n^2) ..questo perchè il numero di volte che la sommatorio dev'essere eseguita è pari a n e non logn..

Saluti



si ma perchè bisogna fare la sommatoria 2 volte?non dovrebbe essere la b?
Logged

shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #42 on: 21-02-2009, 17:10:53 »

le chiamate ricorsive del quick son 2: quick(A, first, m-1) quick(A, m+1, last) dove m è l'indice restituito dalla partition.

Essendo tutti i numeri equiprobabili, aventi probabilità 1/n, quindi tutte le partizioni sono equiprobili; le partizioni possono avere i elementi con i=1,2,3,... ,n-1 elementi.

Adesso fatte queste supposizioni posso scrivere l'eq di ric del quick come
T(n) = 1/n ∑  i=1...n-1 (T(i) + T(n-i)) + Theta(n),
ma la somma del tempo di esecuzione sulle partizioni T(i) è uguale a quello sulle partizioni T(n-i) con i=1,2,3,... ,n-1 e quindi possiam scrivere
2∑  i=1...n-1 T(i) + Theta(n).
Logged
bimbo87
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 129



WWW
« Reply #43 on: 26-02-2009, 18:39:32 »

e la soluzione di qsta:
un grafo orientato si dice fortemente connesso se e solo se:
a)esiste un cammino da un dato vertice u ad ogni altro vertice v
b)esiste un cammino da ogni vertice u ad un dato vertice v
c)esiste un cammino da un dato vertice u ad un dato vertice v
d)esiste un cammino da ogni vertice u ad ogni altro vertice v

grazie
ciao

per me la giusta è la B
Logged
Crazy Diamond
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 243



WWW
« Reply #44 on: 26-02-2009, 19:02:26 »

e la soluzione di qsta:
un grafo orientato si dice fortemente connesso se e solo se:
a)esiste un cammino da un dato vertice u ad ogni altro vertice v
b)esiste un cammino da ogni vertice u ad un dato vertice v
c)esiste un cammino da un dato vertice u ad un dato vertice v
d)esiste un cammino da ogni vertice u ad ogni altro vertice v

grazie
ciao

per me la giusta è la B

Quella giusta è la D, ovvero:

un grafo orientato si dice fortemente connesso quando esiste un cammino da ogni vertice u ad ogni altro vertice.
Logged

"God does not care about our mathematical difficulties. He integrates empirically." (A. Einstein)
________________________

www.davidemoltisanti.com | La mia galleria fotografica
Pages: 1 2 [3] 4 5 ... 12   Go Up
Print
Jump to: