Forum Informatica Unict

Vecchi ordinamenti ad esaurimento => Algoritmi 1 => Topic started by: danilotrix on 19-02-2009, 16:24:11



Title: risposte esatte
Post by: danilotrix on 19-02-2009, 16:24:11
qualcuno sa le risposte esatte del compito B?
saluti


Title: Re:risposte esatte
Post by: Syco on 19-02-2009, 17:04:35
se postate anche le domande qualche anima pia potrebbe risolverli...così possono rispondere solo quelli che c'erano e se le ricordano...


Title: Re:risposte esatte
Post by: danilotrix on 19-02-2009, 17:14:12
sia T un albero RB aumentato con il campo size [ x ] per ogni nodo x. Allora, la procedura Select(x,i) che trova lo i-esimo elemento del sottoalbero di radice x, è implementata

a)
Code:
if(i=j)
        then return x
else if i<j
        then return Select(left[x],i)
else
        return Select(right[x],i)
con j=size[x]

b)
Code:
if(i=j)
        then return x
else if i<j
        then return Select(left[x],i)
else
        return Select(right[x],i)
con j=size[left[x]]+1

c)
Code:
if(i=j)
        then return x
else if i<j
        then return Select(left[x],i)
else
        return Select(right[x],i-j)
con j=size[left[x]]+1

d)
Code:
if(i=j)
        then return x
else if i<j
        then return Select(left[x],i-j)
else
        return Select(right[x],i)
con j=size[left[x]]+1

grazie


Title: Re:risposte esatte
Post by: info on 19-02-2009, 17:21:35
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


Title: Re:risposte esatte
Post by: rob on 19-02-2009, 17:40:43
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
Risposta giusta d


Title: Re:risposte esatte
Post by: rob on 19-02-2009, 17:46:24
sia T un albero RB aumentato con il campo size [ x ] per ogni nodo x. Allora, la procedura Select(x,i) che trova lo i-esimo elemento del sottoalbero di radice x, è implementata

a)
Code:
if(i=j)
        then return x
else if i<j
        then return Select(left[x],i)
else
        return Select(right[x],i)
con j=size[x]

b)
Code:
if(i=j)
        then return x
else if i<j
        then return Select(left[x],i)
else
        return Select(right[x],i)
con j=size[left[x]]+1

c)
Code:
if(i=j)
        then return x
else if i<j
        then return Select(left[x],i)
else
        return Select(right[x],i-j)
con j=size[left[x]]+1

d)
Code:
if(i=j)
        then return x
else if i<j
        then return Select(left[x],i-j)
else
        return Select(right[x],i)
con j=size[left[x]]+1

grazie
risposta esatta c


Title: Re:risposte esatte
Post by: info on 19-02-2009, 18:13:41
ok grazie cm pensavo...cmq ormai che ci siamo, posto anche qste due su cui ho avuto dubbi:
======= ======= ======= ======= =======
si vogliono ordinare n numeri interi rappresentabili con m bits. si vuole utilizzare radix sort raggruppando i bits di ogni numero in m cifre. per utilizzare radix sort si suddividono i numeri input in gruppi da r cifre, per quale valore di r il tempo è minimo?
a)r=log m
b)r=log n
c)r=2 log m
d)r=2 log n

======= ======= ======= ======= =======
sia T(n) una funzione che indica la complessità computazionale dell'algoritmo select nel caso medio. allora per n>1 è costanti a e b abbiamo:
a)T(n)<= ∑ per i che va da 1 a n-1 T(i)+ bn + a
b)T(n)<= (∑ per i che va da 1 a n-1 T(i))/n+ bn + a
c)T(n)<= 2 ∑ per i che va da 1 a n-1 T(i)+ bn + a
d)T(n)<= 2 (∑ per i che va da 1 a n-1 T(i))/n+ bn + a


grazie ciao


Title: Re:risposte esatte
Post by: rob on 19-02-2009, 18:20:57
Quote
sia T(n) una funzione che indica la complessità computazionale dell'algoritmo select nel caso medio. allora per n>1 è costanti a e b abbiamo:
a)T(n)<= ∑ per i che va da 1 a n-1 T(i)+ bn + a
b)T(n)<= (∑ per i che va da 1 a n-1 T(i))/n+ bn + a
c)T(n)<= 2 ∑ per i che va da 1 a n-1 T(i)+ bn + a
d)T(n)<= 2 (∑ per i che va da 1 a n-1 T(i))/n+ bn + a


grazie ciao
risposta esatta d
L'altra ancora non l'ho risolta.....è abbastanza rognosa


Title: Re:risposte esatte
Post by: Yngwie on 19-02-2009, 18:25:20

si vogliono ordinare n numeri interi rappresentabili con m bits. si vuole utilizzare radix sort raggruppando i bits di ogni numero in m cifre. per utilizzare radix sort si suddividono i numeri input in gruppi da r cifre, per quale valore di r il tempo è minimo?
a)r=log m
b)r=log n
c)r=2 log m
d)r=2 log n

sono quasi sicuro che è la b...infatti sbagghiai  :-)| :-)| :-)|


Title: Re:risposte esatte
Post by: info on 19-02-2009, 19:01:29
grazie Yngwie, cmq vediamo se qlcuno conosce la risposta certa.
ciao


Title: Re:risposte esatte
Post by: bakks87 on 19-02-2009, 19:58:34
ragazzi ma per il compito A ?
qualcuno che abbia verificato le domande da fonti attendibili?


Title: Re:risposte esatte
Post by: bakks87 on 19-02-2009, 20:21:57
ad esempio nel compito A, domanda 8:
"Data una lista di n numeri interi compresi tra 1 e 1000, quale tra questi è il miglior algoritmo possibile per ordinarli?

a)Bucket Sort
b)Insertion Sort
c)Quick Sort
d)Merge Sort

io ho messo la b, poichè Insertion Sort è efficiente per piccoli input; a questo punto, la proposizione "piccoli numeri interi compresi tra 0 e 1000" , soddisfa la condizione *per piccoli input* ??
ho un dubbio in questo punto...forse la risposta esatta è una tra c) e d)   .penso


Title: Re:risposte esatte
Post by: info on 19-02-2009, 20:28:24
ma perchè hai escluso il Bucket Sort che è in tempo lineare?


Title: Re:risposte esatte
Post by: bakks87 on 19-02-2009, 20:29:09
mmm .leggo
ho escluso la risposta esatta?


Title: Re:risposte esatte
Post by: goblin on 19-02-2009, 20:42:24
mmm .leggo
ho escluso la risposta esatta?

Se dividi l'input per 1000,otteresti un input compreso [0,1)..bucketsort..


Title: Re:risposte esatte
Post by: info on 19-02-2009, 20:48:27
beh l'insertion è veloce solo nel caso in cui l'array è già ordinato altrimenti la complessità è teta di n^2 qndi un algoritmo lineare è sicuramente preferibile...


Title: Re:risposte esatte
Post by: Yngwie on 19-02-2009, 20:56:20
chissà a che ora usciranno i risultati.... .bah


Title: Re:risposte esatte
Post by: bakks87 on 19-02-2009, 20:58:12
beh l'insertion è veloce solo nel caso in cui l'array è già ordinato altrimenti la complessità è teta di n^2 qndi un algoritmo lineare è sicuramente preferibile...

l'insertion è veloce solo nel caso in cui l'array è già ordinato????????????????    .bah
forse volevi dire nel caso in cui l'array è di piccole dimensioni!!!?


Title: Re:risposte esatte
Post by: Syco on 19-02-2009, 21:00:15
chissà a che ora usciranno i risultati.... .bah
per il primo appello sono usciti alle 2340...e gli orali erano fissati per le 9...
buona attesa... .whistling


Title: Re:risposte esatte
Post by: Yngwie on 19-02-2009, 21:01:58
vabbè ke il primo appello terminava verso le 18....


Title: Re:risposte esatte
Post by: Erithema on 19-02-2009, 21:02:06
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


Title: Re:risposte esatte
Post by: info on 19-02-2009, 21:59:29
beh l'insertion è veloce solo nel caso in cui l'array è già ordinato altrimenti la complessità è teta di n^2 qndi un algoritmo lineare è sicuramente preferibile...

l'insertion è veloce solo nel caso in cui l'array è già ordinato????????????????    .bah
forse volevi dire nel caso in cui l'array è di piccole dimensioni!!!?
SI l'insertion è lineare se l'array è già ordinato, in quanto non cicla nel while...(caso opposto è l'array ordinato in senso inverso -> teta di N^2 ) altrimenti per input di piccole dimensioni è + conveniente del merge e del quick.
ovviamente però algoritmi lineari come bucket o counting sono preferibili per ovvi motivi...



Title: Re:risposte esatte
Post by: Worm on 19-02-2009, 22:07:26
mmm .leggo
ho escluso la risposta esatta?

Se dividi l'input per 1000,otteresti un input compreso [0,1)..bucketsort..

Si ma la domanda dice "n numeri interi compresi tra 1 e 1000" se hai 1000 e dividi 1000/1000 = 1 quindi non va bene il bucketsort perchè l'imput deve essere compreso tra [0,1), io penso che sia il mergesort.


Title: Re:risposte esatte
Post by: Syco on 19-02-2009, 22:30:10
mmm .leggo
ho escluso la risposta esatta?

Se dividi l'input per 1000,otteresti un input compreso [0,1)..bucketsort..

Si ma la domanda dice "n numeri interi compresi tra 1 e 1000" se hai 1000 e dividi 1000/1000 = 1 quindi non va bene il bucketsort perchè l'imput deve essere compreso tra [0,1), io penso che sia il mergesort.

nessuno vieta di fare (1-1)/1000 e (1000-1)/1000, i numeri li possiamo rimappare come vogliamo. e poi la condizione *per piccoli input* si riferisce al fatto di avere pochi numeri 100 o 1000...non  di avere infiniti numeri compresi tra 1 e 10


Title: Re:risposte esatte
Post by: shiny on 19-02-2009, 22:49:21
Quote
Data una lista di n numeri interi compresi tra 1 e 1000, quale tra questi è il miglior algoritmo possibile per ordinarli?

a)Bucket Sort
b)Insertion Sort
c)Quick Sort
d)Merge Sort

io ho risposto a anche perchè la rsp mi sembra ovvia, bucket sort è un algoritmo che ordina i numeri in tempo lineare di gran lunga migliore rispetto agl' algortmi che usano solo confronti.

Adesso vi cito la definizione del bucketsort tratta dalle slide del prof
Quote
L’algoritmo BucketSort assume che i valori da    
ordinare siano numeri reali in un intervallo    
semiaperto [a,b) che per semplicità di esposizione    
assumiamo sia l’intervallo [0,1).    

Inoltre vi cito anche una parte del libro che spezza una lancia in favore del bucketsort anche per distribuzioni non uniformi.
Quote
Anche se l’input non proviene da una distribuzione uniforme, bucket sort può
essere ancora eseguito in tempo lineare. Finchè l’ input ha la proprietà che la somma
dei quadrati delle dimensioni dei bucket è lineare nel numero totale degli
elementi, l’equazione (8.1) ci dice che bucket sort sarà eseguito in tempo lineare.


Title: Re:risposte esatte
Post by: shiny on 20-02-2009, 00:14:59
Quote
si vogliono ordinare n numeri interi rappresentabili con m bits. si vuole utilizzare radix sort raggruppando i bits di ogni numero in m cifre. per utilizzare radix sort si suddividono i numeri input in gruppi da r cifre, per quale valore di r il tempo è minimo?
a)r=log m
b)r=log n
c)r=2 log m
d)r=2 log n

Per la risoluzione di questo esercizio vi cito un periodo tratto dal libro
Quote
Dati i valori di n e b(numero di bits), scegliamo il valore di r, con r ≤ b, che rende minima
l’espressione (b/r)(n + 2r). Se b < floor(lg n), allora per qualsiasi valore di r ≤ b, si ha (n + 2r) = Θ(n). Quindi, scegliendo r = b, si ottiene un tempo di esecuzione (b/b)(n +2b) = Θ(n),
che è asintoticamente ottimale.
Se b ≥ floor(lg n), allora scegliendo r = floor(lg n) si ottiene il tempo migliore a meno di un fattore
costante, che possiamo verificare nel modo seguente. Scegliendo r = floor(lg n), si ha
un tempo di esecuzione pari a Θ(bn/ lg n). Aumentando r oltre floor(lg n), il termine 2^r nel numeratore cresce più rapidamente del termine r nel denominatore; quindi,
aumentando r oltre floor(lg n), si ottiene un tempo di esecuzione pari a Ω(bn/ lg n).


Title: Re:risposte esatte
Post by: bimbo87 on 20-02-2009, 09:52:02
salve.. nel testo c'era questa ricorrenza:
T(n)= 2T(n-1)+n

potreste dirmi come l'avete risolta?


Title: Re:risposte esatte
Post by: Pandemia000 on 20-02-2009, 11:54:43
salve.. nel testo c'era questa ricorrenza:
T(n)= 2T(n-1)+n

potreste dirmi come l'avete risolta?

Ci provo.
Si può utilizzare l'albero di ricorsione. Infatti otterremo un albero binario completo con radice n e nodi (n-1) con costo per ogni livello di 2(n-1).                     
a livello i avremmo log(2n-2) nodi di costo n. La soluzione dovrebbe essere dunque Theta(nlog(2n-2)).
Confermate o smentite ?


Title: Re:risposte esatte
Post by: James on 20-02-2009, 12:56:17
Ricordo che BucketSort utilizza insertionSort per ordinare ogni singola lista dell'array ausiliario, inoltre ricordo che per array di piccole dimensioni anche insertionSort è eseguito in tempo lineare, quindi credo che la risposta esatta sia la B


Title: Re:risposte esatte
Post by: Mosquito on 20-02-2009, 13:25:53
salve.. nel testo c'era questa ricorrenza:
T(n)= 2T(n-1)+n

potreste dirmi come l'avete risolta?

Ci provo.
Si può utilizzare l'albero di ricorsione. Infatti otterremo un albero binario completo con radice n e nodi (n-1) con costo per ogni livello di 2(n-1).                     
a livello i avremmo log(2n-2) nodi di costo n. La soluzione dovrebbe essere dunque Theta(nlog(2n-2)).
Confermate o smentite ?

Io credo che a livello i ci saranno 2^i nodi di costo (n-i) ciascuno. Quindi la ricorsione dovrebbe fermarsi a livello n. Avendo quindi n livelli di costo n T(n)=n^2. Se mi sbaglio correggetemi.


Title: Re:risposte esatte
Post by: Pandemia000 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).


Title: Re:risposte esatte
Post by: IRon on 20-02-2009, 14:11:52
n livelli di costo (2^i)*(n-i), dove i è il livello.


Title: Re:risposte esatte
Post by: Vincenzo Cutello 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  .coolio


Title: Re:risposte esatte
Post by: goblin on 20-02-2009, 14:51:29
In altre parole la soluzione è esponenziale..


Title: Re:risposte esatte
Post by: Pandemia000 on 20-02-2009, 15:35:00
la soluzione dell'equazione di ricorrenza è allora Theta(n^2)?


Title: Re:risposte esatte
Post by: Pandemia000 on 20-02-2009, 16:16:13
 .penso 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


Title: Re:risposte esatte
Post by: IRon on 20-02-2009, 16:51:00
L'albero è sbagliato: l'input decresce di uno per ogni livello.


Title: Re:risposte esatte
Post by: Mosquito 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).


Title: Re:risposte esatte
Post by: IRon 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.


Title: Re:risposte esatte
Post by: AngelEvil 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??


Title: Re:risposte esatte
Post by: goblin 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


Title: Re:risposte esatte
Post by: AngelEvil 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?


Title: Re:risposte esatte
Post by: shiny 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).


Title: Re:risposte esatte
Post by: bimbo87 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


Title: Re:risposte esatte
Post by: Crazy Diamond 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.


Title: Re:risposte esatte
Post by: info on 26-02-2009, 21:56:06
si hai ragione Crazy Diamond ho poi controllato meglio...
inoltre...
Quote
sia T(n) una funzione che indica la complessità computazionale dell'algoritmo select nel caso medio. allora per n>1 è costanti a e b abbiamo:
a)T(n)<= ∑ per i che va da 1 a n-1 T(i)+ bn + a
b)T(n)<= (∑ per i che va da 1 a n-1 T(i))/n+ bn + a
c)T(n)<= 2 ∑ per i che va da 1 a n-1 T(i)+ bn + a
d)T(n)<= 2 (∑ per i che va da 1 a n-1 T(i))/n+ bn + a


grazie ciao
risposta esatta d
L'altra ancora non l'ho risolta.....è abbastanza rognosa
volevo far notare che la risposta giusta non dovrebbe essere la D ma la B in quanto l'ultima è l'equazione di ricorrenza valida per il quicksort che lavora su due sotto-problemi. invece il select lavora solamente in metà array di volta in volta.


Title: Re:risposte esatte
Post by: Acicatena86 on 08-04-2009, 17:46:41
Riprendo questo topic per chiedere un'aiuto  (anzi due  .whistling)

1) Sia G un grafo orientato e aciclico . Siano P1 e P2 due permutazioni  rappresentanti ordinamenti topologici di G. Quale delle seguenti affermazioni è vera?

a)P1=P2
b) Se u precede v in P1,u precede v in P2
c) Il primo elemento di P1 e uguale al primo elemento di P2
d) Nessuna delle affermazioni sopra è sempre vera




2)Sia G un grafo orientato,GC il relativo grafo delle  componenti fortemente connesse. Quali delle seguenti affermazioni è vera?

a) E' possibile ordinare topologicamente i vertici di G
b) E' possibile ordinare topologicamente i vertici di GC
c) E' possibile che i vertici di G siano meno dei vertici di GC
d) Nessuna delle affermazioni sopra è vera



Io sulla prima ho una (vaga) idea su quale possa essere la risposta giusta, ma sulla seconda non ho idea
Help please! :pray


Title: Re:risposte esatte
Post by: Acicatena86 on 09-04-2009, 15:23:09
Riprendo questo topic per chiedere un'aiuto  (anzi due  .whistling)

1) Sia G un grafo orientato e aciclico . Siano P1 e P2 due permutazioni  rappresentanti ordinamenti topologici di G. Quale delle seguenti affermazioni è vera?

a)P1=P2
b) Se u precede v in P1,u precede v in P2
c) Il primo elemento di P1 e uguale al primo elemento di P2
d) Nessuna delle affermazioni sopra è sempre vera






2)Sia G un grafo orientato,GC il relativo grafo delle  componenti fortemente connesse. Quali delle seguenti affermazioni è vera?

a) E' possibile ordinare topologicamente i vertici di G
b) E' possibile ordinare topologicamente i vertici di GC
c) E' possibile che i vertici di G siano meno dei vertici di GC
d) Nessuna delle affermazioni sopra è vera



Io sulla prima ho una (vaga) idea su quale possa essere la risposta giusta, ma sulla seconda non ho idea
Help please! :pray


Mi auto-rispondo io (grazie per la  partecipazione)

Allora per la prima la risposta giusta (credo), è la c) Il primo elemento di P1 e uguale al primo elemento di P2

Per la seconda  la risposta giusta  è la b) E' possibile ordinare topologicamente i vertici di GC

Qualcuno può confermare? prof??



Title: Re:risposte esatte
Post by: Vincenzo Cutello on 11-04-2009, 10:31:27
Per la prima la risposta esatta è la d. Pensa a questo semplice grafo: a-->c,  b-->c che ha i seguenti ordinamenti topologici:
1. a,b,c
2. b,a,c

Per la seconda, la risposta esatta è ovviamente la b, per la definizione stessa di grafo delle componenti fortememente connesse.


Title: Re:risposte esatte
Post by: Acicatena86 on 11-04-2009, 10:42:50
Per la prima la risposta esatta è la d. Pensa a questo semplice grafo: a-->c,  b-->c che ha i seguenti ordinamenti topologici:
1. a,b,c
2. b,a,c

Per la seconda, la risposta esatta è ovviamente la b, per la definizione stessa di grafo delle componenti fortememente connesse.
Grazie per i chiarimenti professore!


Title: Re:risposte esatte
Post by: Acicatena86 on 14-04-2009, 14:16:25
Salve ragazzi ,mi dareste un'opinione su questa domanda?


Qual è la complessità di un algoritmo di ordinamento ,che preso un array A di 2n elementi , ordina i primi n con QuickSort, i secondi n elementi con HeapSort e poi fa il Merging delle due array ordinate?

a) O(n)
b) O(nlogn)
c) O(n2 )
d) O(n2log n)


Allora se consideriamo il caso Peggiore avremo: O(n2) +O(nlogn)+ O(2n), quindi O(n2)


Nel caso migliore invece : O(nlogn)+O(nlogn)+O(2n),quindi O(nlogn)


Al 90% sono convinto di dover considerare il caso peggiore ,quindi O(n2), Qualcuno può confermare??
thanks  .camberman



Title: Re:risposte esatte
Post by: Root on 14-04-2009, 14:41:58
Si, quando non richiesto altrimenti bisogna considerare il caso peggiore.


Title: Re:risposte esatte
Post by: Acicatena86 on 14-04-2009, 14:50:37
Si, quando non richiesto altrimenti bisogna considerare il caso peggiore.
Grazie ! :yoh


Title: Re:risposte esatte
Post by: Nova on 15-04-2009, 10:35:13
Vi chiedo una mano: ho fatto questo compito: http://img6.imageshack.us/img6/9898/2702aw.jpg (http://img6.imageshack.us/img6/9898/2702aw.jpg)
vorrei sapere se le risposte che ho dato sono corrette :p

1) b
2) b
3) b
4) a: falsa
5) d
6) a
7) c
8 ) non ne ho idea, mi illuminate?
9) a

Grazie ^^


Title: Re:risposte esatte
Post by: Acicatena86 on 15-04-2009, 11:51:38
Vi chiedo una mano: ho fatto questo compito: http://img6.imageshack.us/img6/9898/2702aw.jpg (http://img6.imageshack.us/img6/9898/2702aw.jpg)
vorrei sapere se le risposte che ho dato sono corrette :p

1) b
2) b
3) b
4) a: falsa
5) d
6) a
7) c
8 ) non ne ho idea, mi illuminate?
9) a

Grazie ^^

8 ) a  =>Praticamente è il tempo del CountigSort


Per me la 5 ) è la c
Per la 9) sono indeciso tra la c) e la b)

Tu che ne pensi?


Title: Re:risposte esatte
Post by: ForbiddenAlex on 15-04-2009, 12:42:02
Vi chiedo una mano: ho fatto questo compito: http://img6.imageshack.us/img6/9898/2702aw.jpg (http://img6.imageshack.us/img6/9898/2702aw.jpg)
vorrei sapere se le risposte che ho dato sono corrette :p

1) b
2) b
3) b
4) a: falsa
5) d
6) a
7) c
8 ) non ne ho idea, mi illuminate?
9) a

Grazie ^^

8 ) a  =>Praticamente è il tempo del CountigSort


Per me la 5 ) è la c
Per la 9) sono indeciso tra la c) e la b)

Tu che ne pensi?

Secondo me la risposta alla 9 è la d)...
Non vorrei dire una baggianata ma, considerato che un albero rosso-nero non è altro che un albero binario di ricerca con l'aggiunta di un bit per l'attributo color
  • , potrei non considerare più tale parametro, invece quel che devo fare è effettuare un delete su nil[T], il nodo speciale utilizzato come puntatore nullo, poichè quindi ogni foglia fa puntare i propri figli ad esso(compreso il padre della radice), presupposto che l'albero abbia altezza n, avrà logn foglie, dovendo effettuare la cancellazione, che di per se impiega O(n), logn volte, l'algoritmo impiegherà O(2nlogn), il 2 poichè devo cancellare il puntatore sia al figlio destro che a quello sinistro di ogni foglia, quindi:
O(2nlogn)=O(nlogn)......non fustigatemi se ho detto una castroneria!!!  .arrossisco


Title: Re:risposte esatte
Post by: Acicatena86 on 15-04-2009, 12:44:10
Vi chiedo una mano: ho fatto questo compito: http://img6.imageshack.us/img6/9898/2702aw.jpg (http://img6.imageshack.us/img6/9898/2702aw.jpg)
vorrei sapere se le risposte che ho dato sono corrette :p

1) b
2) b
3) b
4) a: falsa
5) d
6) a
7) c
8 ) non ne ho idea, mi illuminate?
9) a

Grazie ^^

8 ) a  =>Praticamente è il tempo del CountigSort


Per me la 5 ) è la c
Per la 9) sono indeciso tra la c) e la b)

Tu che ne pensi?

Secondo me la risposta alla 9 è la d)...
Non vorrei dire una baggianata ma, considerato che un albero rosso-nero non è altro che un albero binario di ricerca con l'aggiunta di un bit per l'attributo color
  • , potrei non considerare più tale parametro, invece quel che devo fare è effettuare un delete su nil[T], il nodo speciale utilizzato come puntatore nullo, poichè quindi ogni foglia fa puntare i propri figli ad esso(compreso il padre della radice), presupposto che l'albero abbia altezza n, avrà logn foglie, dovendo effettuare la cancellazione, che di per se impiega O(n), logn volte, l'algoritmo impiegherà O(2nlogn), il 2 poichè devo cancellare il puntatore sia al figlio destro che a quello sinistro di ogni foglia, quindi:
O(2nlogn)=O(nlogn)......non fustigatemi se ho detto una castroneria!!!  .arrossisco

potresti aver ragione invece .penso


Title: Re:risposte esatte
Post by: Nova on 15-04-2009, 14:21:30
Per le altre siete d'accordo?


Title: Re:risposte esatte
Post by: Acicatena86 on 15-04-2009, 14:35:12
Per le altre siete d'accordo?

io si  :yoh


Title: Re:risposte esatte
Post by: ForbiddenAlex on 15-04-2009, 15:34:24
Dimenticate quello che ho precedentemente scritto, per ora non posso ma dopo aver rifatto qualche conticino cercherò di ripostare una soluzione alla 9, comunque sono quasi certo di aver detto una stupidaggine...dato che(esiste pure il lemma tra l'altro)...l'altezza massima di un albero rosso-nero con n nodi interni è di 2log(n+1)...devo rifare qualche calcolo...in ogni caso le foglie, alla luce di questa tesi, sono al più 2^2log(n+1)...


Title: Re:risposte esatte
Post by: Acicatena86 on 15-04-2009, 15:51:13
Dimenticate quello che ho precedentemente scritto, per ora non posso ma dopo aver rifatto qualche conticino cercherò di ripostare una soluzione alla 9, comunque sono quasi certo di aver detto una stupidaggine...dato che(esiste pure il lemma tra l'altro)...l'altezza massima di un albero rosso-nero con n nodi interni è di 2log(n+1)...devo rifare qualche calcolo...in ogni caso le foglie, alla luce di questa tesi, sono al più 2^2log(n+1)...

Invece io pensavo a una cosa:

Ma un albero rosso-nero è già un albero binario di ricerca,ha solamente il  campo color in più.
Quindi per trasformare un RB in un semplice albero binario di ricerca ,dobbiamo "scolorire" ogni singolo nodo.

Supponiamo che l'operazione di "scolorimento" sia O (1) ripetuto per n-volte => O(n) ??
 .whistling .ciaociao :-)|


Title: Re:risposte esatte
Post by: ForbiddenAlex on 15-04-2009, 16:56:59
Dimenticate quello che ho precedentemente scritto, per ora non posso ma dopo aver rifatto qualche conticino cercherò di ripostare una soluzione alla 9, comunque sono quasi certo di aver detto una stupidaggine...dato che(esiste pure il lemma tra l'altro)...l'altezza massima di un albero rosso-nero con n nodi interni è di 2log(n+1)...devo rifare qualche calcolo...in ogni caso le foglie, alla luce di questa tesi, sono al più 2^2log(n+1)...

Invece io pensavo a una cosa:

Ma un albero rosso-nero è già un albero binario di ricerca,ha solamente il  campo color in più.
Quindi per trasformare un RB in un semplice albero binario di ricerca ,dobbiamo "scolorire" ogni singolo nodo.


Supponiamo che l'operazione di "scolorimento" sia O (1) ripetuto per n-volte => O(n) ??
 .whistling .ciaociao :-)|

Probabilmente è come dici tu, anche perchè ha più senso "scolorire" che eliminare ogni riferimento che punti a nil[T], dato che, se effettuassi un insert otterrei come risultato che una delle foglie punterebbe al nuovo nodo ed il nuovo elemento non verrebbe collegato ulteriormente a nil[T], di conseguenza perderei il riferimento senza troppi fronzoli...in ogni caso, poichè rimango un pò perplesso(sull'effettuare o meno il delete) aspettiamo che il prof legga e magari ci fornisca delucidazioni a riguardo!!!  .whistling


Title: Re:risposte esatte
Post by: ale on 15-04-2009, 18:45:58
Qualcuno potrebbe aiutarmi? come si risolve l'equazione di ricorrenza: T(n)= 2*T(n/3)+2*T(n/9)+n....  .poverinoi


Title: Re:risposte esatte
Post by: Nova on 16-04-2009, 07:03:23
In effetti non c'è da effettuare nessun delete eh!
Un albero BT mnon è altro che un BST con un solo campo in più (il campo color) e le foglie ed il padre della radice puntano ad una sentinella. Non c'è da cancellare, al massimo si devono rimuovere dei puntatori a foglie, non a nodi interni e non per tutti i nodi. Io alla luce del fatto che un alberto BT è già un BST ho messo O(1).

Per quato riguarda quella ricorrenza io l'ho fatta con la sostituzione: n=3^k


Title: Re:risposte esatte
Post by: ale on 16-04-2009, 08:54:02
Non è che mi potresti postare lo svolgimento? Non sono riuscita a risolverla...grazie mille!  .arrossisco


Title: Re:risposte esatte
Post by: Acicatena86 on 16-04-2009, 13:18:45
Qualcuno potrebbe aiutarmi? come si risolve l'equazione di ricorrenza: T(n)= 2*T(n/3)+2*T(n/9)+n....  .poverinoi


Code:

                                                    albero                                                                                                 costo

0)                                                      n                                                                                                        n
1)        n/3                                        n/3                                   n/9                              n/9                               8 n/9
2) n/9 n/9 n/27 n/27                              n/9 n/9 n/27 n/27           n/27 n/27 n/81 n/81              n/27 n/27 n/81 n/81                          64n/81




Ad ogni livello avremo un costo pari a (8/9)in
Il ramo più lungo è quello più a sinistra ,cioè   (n/3)i ed è uguale a 1 quando i=log3n


Poichè l'albero non è completo, possiamo trascurare il costo delle foglie. Quindi risolviamo la seguente serie:


serie i=0, log3n     ((8/9)in) <= 1/(1-(8/9))*n= O(n)


Title: Re:risposte esatte
Post by: ale on 16-04-2009, 17:44:06
Grazie mille!!!  .ciaociao


Title: Re:risposte esatte
Post by: AngelEvil on 16-04-2009, 20:51:17
Qualcuno potrebbe aiutarmi? come si risolve l'equazione di ricorrenza: T(n)= 2*T(n/3)+2*T(n/9)+n....  .poverinoi



qualcuno sa come si risolve con il metodo della sostituzione?


Title: Re:risposte esatte
Post by: Nova on 18-04-2009, 08:09:33
Con la sostituzione credo non si possa, io ho fatto un ragionamento simile alla sostituzione e per fortuna ha funzionato ma mi rendo conto che il metodo che spacca il capello è quello dell'albero!


Ora, io ho fatto tutti i compiti di qui: http://www.mytwocent.it/varie/cmptalg.zip (http://www.mytwocent.it/varie/cmptalg.zip)

19 - 02 A

1) c
2) d
3) a
4) c
5) b
6) c
7) a
8) d
9) c
10) b
11) c
12) a
13) a
14) c
15) c

19 - 02 B

1) d
2) b
3) b
4) b
5) b
6) b
7) d
8) b
9) b
10) b
11) b
12) a
13) c
14) a
15) c

27 - 02

1) b
2) b
3) b
4) a: falsa
5) d
6) a
7) c
8 ) non ne ho idea, mi illuminate?
9) a

02 - 03

1) c
2) c
3) c
4) a
5) d
6) d
7) c
8) d
9) c
10) d
11) c
12) b
13) c
14) d
15) d

Queste sono le mie risposte, ovviamente NON CORRETTE! Le confrontiamo?


Title: Re:risposte esatte
Post by: Acicatena86 on 20-04-2009, 10:52:20
 19 Febbraio compito A

RISPOSTE:

1-2-3-4-12-13-15  Uguali a Nova

5 ) d
6 ) a
7 ) c
8 ) a
9 ) c
10 ) a
11 ) a
14 ) d


Title: Re:risposte esatte
Post by: morpheus on 22-04-2009, 09:49:16
Compito del 2 marzo 2009.
alla 2 ho riposto b, secondo voi è giusta?

alla 4 cosa avete risposto e perchè?

Grazie a tutti voi!


Title: Re:risposte esatte
Post by: Pandemia000 on 23-04-2009, 17:11:01
Propongo la seguente equazione di ricorrenza: T(n)=7T(n/2)+n^2 con l'albero di ricorsione dovrebbe essere

                        n^2
(n/2)^2.........................fino a 7....... ( n/2)  => 7/4 n^2
...
a livello i-esimo                                            => (7/4)^i n^2

T(1).................................................T(1)       =>Theta(n^log7)      
 

La dimensione del sottoproblema diventa n=1 quando n/2^i=1 cioè quando i=logn. Dunque l'albero ha logn +1 livelli.All'ultimo livello ci sono 7^logn nodi di costo T(1) per un costo di Theta(nlog7). Quindi risolviamo

serie per i che va da 0 a logn-1 di (7/4)^i n^2 +Theta(n^log7).  e dovrebbe venire Theta(n^2). Spero di aver non sparato boiate.  .ciaociao            


Title: Re:risposte esatte
Post by: Nova on 23-04-2009, 18:32:03
Mi spiegate come si arriva ad (n/2)^i = 1 per i=logn (log base 2)


Title: Re:risposte esatte
Post by: Pandemia000 on 23-04-2009, 19:26:32
Con il procedere dell'algoritmo la dimensione del sottoproblema diminuisce, in questo caso ad ogni ricorsione dimezza (infatti viene diviso per due). Abbiamo quindi n/2 al primo livello, n/4 al secondo, n/8 e all'i-esimo livello abbiamo n/2^i. L'ultimo livello si avrà quando n/2^i=1.Basta estrarre il logaritmo per ottenere i=log(n).


Title: Re:risposte esatte
Post by: Nova on 24-04-2009, 07:01:24
Chiarissimo, sono io che avevo sbagliato a scrivere e non riuscivo a fare il logaritmo :p Grazie mille!


Title: Re:risposte esatte
Post by: Pandemia000 on 24-04-2009, 09:10:37
è un piacere !!! :-ciao :-ciao


Title: Re:risposte esatte
Post by: Nova on 24-04-2009, 15:59:19
Altro dubbio: Dopo che noi otteniamo il costo e risolviamo la serie non si dovrebbe moltiplicare tale costo per l'altezza dell'albero?


Title: Re:risposte esatte
Post by: Pandemia000 on 24-04-2009, 18:02:00
no attenzione. Il costo dell'intero albero è ottenuto dalla somma di tutti i livelli. La serie permette di calcolare la somma dei costi di tutti i livelli dell'albero ad eccezione delle foglie. Le foglie infatti hanno costo T(1) e sono un numero pari a x ^ h dove h è l'altezza dell'albero, e x è il numero di divisione del sottoproblema. Tutto l'intero costo dell'albero è ottenuto dalla somma del valore ottenuto dalla serie più il costo delle foglie. In alcuni casi i costi delle foglie sono trascurabili (l'albero non è completo), e quindi non si valutano.


Title: Re:risposte esatte
Post by: Nova on 24-04-2009, 19:26:00
Certo, capito ^^ Si vede che son stanco porca miseria :p


Title: Re:risposte esatte
Post by: Pandemia000 on 24-04-2009, 19:34:04
la stanchezza fa brutti scherzi  :-OK :-OK


Title: Re:risposte esatte
Post by: Pandemia000 on 25-04-2009, 08:30:06
Posto le mie soluzioni del compito del 27 febbraio 2009:

1b-2b-3b-4c-5d-6d-7c-8c-9c-10c-11d-12a-13b-14b-15a


Title: Re:risposte esatte
Post by: Pandemia000 on 25-04-2009, 13:07:10
Compito del 2 marzo 2009.
alla 2 ho riposto b, secondo voi è giusta?

alla 4 cosa avete risposto e perchè?

Grazie a tutti voi!

Si infatti perchè avete scelto la a nella numero 4 del 2 marzo ?


Title: Re:risposte esatte
Post by: Pandemia000 on 25-04-2009, 14:19:53
anche io alla 2 ho risposto b. Infatti dato T(n)=4T(n/5)++T(n/6) avremo un albero incompleto di altezza logaritmo in base 5 di n e per tanto trascuriam le foglie. A livello i avremo un costo di (29/30)i n e risolviamo dunque la serie per i che va da 0 a log in base 5 di n di (29/30)in , che una minorante per la stessa serie per i che va da 0 a infinito ed otteniamo un valore numerico che possiamo trascurare ottendo la soluzione O(n).


Title: Re:risposte esatte
Post by: Root on 25-04-2009, 18:14:29
Ora, io ho fatto tutti i compiti di qui: http://www.mytwocent.it/varie/cmptalg.zip (http://www.mytwocent.it/varie/cmptalg.zip)

19 - 02 A

1) c
2) d
3) a


Avrei da ridire sulla soluzione della domanda 3, non è (secondo me) la A ma la D.

T(n) = T(n-1)+T(n-2)+n

un generico livello i comporta lavoro
2i(n-3i/2)
[/b]

L'albero delle chiamate è alto n e dunque possiamo ricavare la seguente sommatoria

(http://www.mytwocent.it/varie/eq.jpg)

Questa funzione non è una O(2^n) e quindi il bound più stretto accettabile è O(n^n)

Sbaglio a fare questa affermazione?

:S
Dario


Title: Re:risposte esatte
Post by: Pandemia000 on 26-04-2009, 08:40:30
ma il livello i-esimo non dovrebbe avere costo 2in-3i ?


Title: Re:risposte esatte
Post by: Root on 26-04-2009, 17:37:16
ma il livello i-esimo non dovrebbe avere costo 2in-3i ?

Non credo... cosa ti porta ad affermarlo?

Altro dubbio, la risposta data da Nova alla domanda 11 del compito del 19-02 B è la B.
Ora, se noi non sappiamo la posizione di y rispetto a p[y] prima della rotazione, come facciamo a dire che p[y] diventi un figlio destro/sinistro di y?

Mi spiego meglio:
una rotazione sinistra su un nodo y fà diventare y figlio somostrp del suo figlio destro x; ma il figlio sinistro di y rimane, dopo la rotazione, il figlio destro di y.

Quindi  .penso , la risposta potrebbe essere la D?

Tutti questi dubbi sono buoni motivi per odiare i compiti a risposta multima.


Title: Re:risposte esatte
Post by: Yngwie on 26-04-2009, 18:03:57
qualcuno sa se ci verrà dato l'eserciziario che ci era stato promesso un mese fa?


Title: Re:risposte esatte
Post by: Pandemia000 on 26-04-2009, 18:58:37
perchè abbiamo (n-1)+(n-2)= 2n-3 al livello 1; (n-2)+(n-3)+(n-3)+(n-4)= 4n-12 e quindi a livello i 2^1n-3i . Scusa per eventuali Orrori ma sono un pò stanco....


Title: Re:risposte esatte
Post by: Root on 26-04-2009, 19:31:27
Beh...
secondo il tuo termine dovremmo avere

(2^1)n-3*1 = 2n-3 al livello 1
(2^2n)-3*2 =  4n-6 al livello 2

ma invece, (come hai detto tu) abbiamo:

2n-3 al livello 1, ovvero 2^1(n-3*1/2) = 2n-3
4n-12 al livello 2, ovvero 2^2(n-3*2/2) = 4n-12

... ho qualche dubbio però sulla soluzione della somma...



Title: Re:risposte esatte
Post by: Pandemia000 on 26-04-2009, 21:36:33
ok ho sbagliato io ... cmq credo la sommatoria sia giusta. .ciaociao


Title: Re:risposte esatte
Post by: Yngwie on 27-04-2009, 08:55:59
Propongo la seguente equazione di ricorrenza: T(n)=7T(n/2)+n^2 con l'albero di ricorsione dovrebbe essere 

col teorema master non si può fare?
verrebbe nlog27, dove 2 < log27 < 3, quindi per ε~log27-2, abbiamo che n2=O(nlog27-ε), quindi 1° caso del teorema master--> Θ(nlog27)
giusto? .leggo


Title: Re:risposte esatte
Post by: Pandemia000 on 27-04-2009, 10:01:22
Propongo la seguente equazione di ricorrenza: T(n)=7T(n/2)+n^2 con l'albero di ricorsione dovrebbe essere 

col teorema master non si può fare?
verrebbe nlog27, dove 2 < log27 < 3, quindi per ε~log27-2, abbiamo che n2=O(nlog27-ε), quindi 1° caso del teorema master--> Θ(nlog27)
giusto? .leggo

non credo perchè il log 7 è circa 0.85 che è minore di 1 e non puoi travare un valore di ε>0 tale che 2=log7-ε.
Anche il secondo caso non va bene per ovvi motivi. Il terzo invece si se dimostriamo la condizione di regolarità.


Title: Re:risposte esatte
Post by: Yngwie on 27-04-2009, 10:08:00
no...il log è in base 2, non in base 10 (infatti l'ho specificato log27)
grossolanamente si sa che log24=2 e log28=3...


Title: Re:risposte esatte
Post by: Nova on 27-04-2009, 10:35:12
Ora, io ho fatto tutti i compiti di qui: http://www.mytwocent.it/varie/cmptalg.zip (http://www.mytwocent.it/varie/cmptalg.zip)

19 - 02 A

1) c
2) d
3) a


Avrei da ridire sulla soluzione della domanda 3, non è (secondo me) la A ma la D.

T(n) = T(n-1)+T(n-2)+n

un generico livello i comporta lavoro
2i(n-3i/2)
[/b]


Fin qui siamo d'accordo, sono stato avventato nella mia risposta, ho fatto un calcolo  molto semplicistico ma...

Quote

L'albero delle chiamate è alto n e dunque possiamo ricavare la seguente sommatoria

(http://www.mytwocent.it/varie/eq.jpg)

Questa funzione non è una O(2^n) e quindi il bound più stretto accettabile è O(n^n)

Sbaglio a fare questa affermazione?

:S
Dario

... Non capisco come hai sviluppato la sommatoria ç_ç E manca un giorno all'esame ç_ç

Non è che magari sono sti compiti che sono un po troppo cattivi?


Title: Re:risposte esatte
Post by: Nova on 27-04-2009, 10:53:06
no...il log è in base 2, non in base 10 (infatti l'ho specificato log27)
grossolanamente si sa che log24=2 e log28=3...

Credo proprio che tu abbia ragione.

@Root: Ho capito la sommatoria e mi sa che hai beccato un altro mio errore :p Grazie ^^


Title: Re:risposte esatte
Post by: Pandemia000 on 27-04-2009, 11:37:49
ops chiedo venia........


Title: Re:risposte esatte
Post by: Asknet on 27-04-2009, 11:42:02
Con la sostituzione credo non si possa, io ho fatto un ragionamento simile alla sostituzione e per fortuna ha funzionato ma mi rendo conto che il metodo che spacca il capello è quello dell'albero!

...

02 - 03

1) c
2) c
3) c
4) a
5) d
6) d
7) c
8) d
9) c
10) d
11) c
12) b
13) c
14) d
15) d

Queste sono le mie risposte, ovviamente NON CORRETTE! Le confrontiamo?

Ho fatto qualche prova e io alla 9) risponderei d.

Confermate o smentite?


Title: Re:risposte esatte
Post by: Yngwie on 27-04-2009, 11:46:27
compito 2 marzo
nella numero 12 cosa avete messo?
Se ho un grafo NON ORIENTATO rappresentato da una matrice di adiacenza, devo trovare l'unico vertice che non ha ciclo, quindi devo scorrere la diagonale della matrice e trovare uno zero: sarebbe O(|V|). Mentre se è ORIENTATO, la matrice potrebbe anche non essere |V|x|V| (ad esempio se ci sono nodi isolati e senza archi)...in questo caso cosa si fa? .leggo


Title: Re:risposte esatte
Post by: Yngwie on 27-04-2009, 11:50:28
compito 2 marzo
nella numero 12 cosa avete messo?
Se ho un grafo NON ORIENTATO rappresentato da una matrice di adiacenza, devo trovare l'unico vertice che non ha ciclo, quindi devo scorrere la diagonale della matrice e trovare uno zero: sarebbe O(|V|). Mentre se è ORIENTATO, la matrice potrebbe anche non essere |V|x|V| (ad esempio se ci sono nodi isolati e senza archi)...in questo caso cosa si fa? .leggo

non fateci caso...ho letto male la domanda :-)|
in ogni caso cosa avete risposto e perchè?


Title: Re:risposte esatte
Post by: Acicatena86 on 27-04-2009, 14:24:39
compito 2 marzo
nella numero 12 cosa avete messo?
Se ho un grafo NON ORIENTATO rappresentato da una matrice di adiacenza, devo trovare l'unico vertice che non ha ciclo, quindi devo scorrere la diagonale della matrice e trovare uno zero: sarebbe O(|V|). Mentre se è ORIENTATO, la matrice potrebbe anche non essere |V|x|V| (ad esempio se ci sono nodi isolati e senza archi)...in questo caso cosa si fa? .leggo

non fateci caso...ho letto male la domanda :-)|
in ogni caso cosa avete risposto e perchè?

Credo sia la  b) O(V+E) .

Sappiamo che la DFS ci dice se un grafo è aciclico o no. Quindi in questo caso basterebbe modificare l'algoritmo in modo tale da ritornare l'unico vertice che non ha archi all'indietro. Spero di non aver detto cavolate  :-ciao


Title: Re:risposte esatte
Post by: Acicatena86 on 27-04-2009, 14:50:20
per la n° 4 del compito 2-3-09 , risolvetevi le due equazioni e confrontate i risultati.


A me S1( a )= nloga2a  ed S2=nlogn

Quindi la risposta falsa è la a) E' possibile trovare un valore di a : S1 ( a )=Theta(S2 (a ))



Title: Re:risposte esatte
Post by: Yngwie on 27-04-2009, 15:08:08
per S1: nloga2a = nloga2+1 = n*nloga2
per essere vera quella risposta, allora loga2 dovrebbe essere = 0, cosa non possibile per qualsiasi a>1...quindi la soluzione è falsa, cioè la risposta è vera :-)|  :-OK


Title: Re:risposte esatte
Post by: Acicatena86 on 27-04-2009, 17:54:09
Ora, io ho fatto tutti i compiti di qui: http://www.mytwocent.it/varie/cmptalg.zip (http://www.mytwocent.it/varie/cmptalg.zip)

19 - 02 A

1) c
2) d
3) a


Avrei da ridire sulla soluzione della domanda 3, non è (secondo me) la A ma la D.

T(n) = T(n-1)+T(n-2)+n

un generico livello i comporta lavoro
2i(n-3i/2)
[/b]


Fin qui siamo d'accordo, sono stato avventato nella mia risposta, ho fatto un calcolo  molto semplicistico ma...

Quote

L'albero delle chiamate è alto n e dunque possiamo ricavare la seguente sommatoria

(http://www.mytwocent.it/varie/eq.jpg)

Questa funzione non è una O(2^n) e quindi il bound più stretto accettabile è O(n^n)

Sbaglio a fare questa affermazione?

:S
Dario

... Non capisco come hai sviluppato la sommatoria ç_ç E manca un giorno all'esame ç_ç

Non è che magari sono sti compiti che sono un po troppo cattivi?


Invece io non capisco perchè affermi che la soluzione sia (nn)
 :-)|


Title: Re:risposte esatte
Post by: Nova on 27-04-2009, 18:55:14

Ho fatto qualche prova e io alla 9) risponderei d.  (compito 2 marzo)

Confermate o smentite?

Io direi che l'altezza dei sotto alberi della radice può essere diversa, è l'altezza nera che DEVE essere uguale, percui io direi che la risposta è la C


Title: Re:risposte esatte
Post by: Asknet on 27-04-2009, 19:03:36
Hai ragione, non avevo letto bene la domanda.  Anche secondo me è la c)   :-)H(-:



Title: Re:risposte esatte
Post by: Yngwie on 27-04-2009, 21:50:06
compito 27 febbraio
la numero 8 è c) o d)? vediam se il procedimento è giusto 8-|


Title: Re:risposte esatte
Post by: Acicatena86 on 28-04-2009, 14:57:40
compito 27 febbraio
la numero 8 è c) o d)? vediam se il procedimento è giusto 8-|


Per me è la a )     :big_smile:

Perchè ti dice che rad(n) sono compresi tra 0 e k

Allora CountingSort ha complessità O( n+k) ,poi se k è nell'ordine di n è O(n)
Quindi penso che  la risposta corretta sia O (n+k*rad(n) )


Title: Re:risposte esatte
Post by: Yngwie on 28-04-2009, 15:08:48
corretto :-OK


Title: Re:risposte esatte
Post by: Root on 28-04-2009, 16:58:35
compito 27 febbraio
la numero 8 è c) o d)? vediam se il procedimento è giusto 8-|


Per me è la a )     :big_smile:

Perchè ti dice che rad(n) sono compresi tra 0 e k

Allora CountingSort ha complessità O( n+k) ,poi se k è nell'ordine di n è O(n)
Quindi penso che  la risposta corretta sia O (n+k*rad(n) )


io direi che non è vero quello che hai detto... counting sort assume che tutti gli elementi dell'array appartengano ad un dato intervallo quindi di quella "cosina li" non sappiamo che farcene.
Risposta esatta C


Title: Re:risposte esatte
Post by: Acicatena86 on 28-04-2009, 17:11:06
compito 27 febbraio
la numero 8 è c) o d)? vediam se il procedimento è giusto 8-|


Per me è la a )     :big_smile:

Perchè ti dice che rad(n) sono compresi tra 0 e k

Allora CountingSort ha complessità O( n+k) ,poi se k è nell'ordine di n è O(n)
Quindi penso che  la risposta corretta sia O (n+k*rad(n) )


io direi che non è vero quello che hai detto... counting sort assume che tutti gli elementi dell'array appartengano ad un dato intervallo quindi di quella "cosina li" non sappiamo che farcene.
Risposta esatta C

 la risposta O(nlogn) non mi convince proprio però!


Title: Re:risposte esatte
Post by: Nova on 28-04-2009, 17:14:07
Concordo con root, non importa che una parte degli elementi goda di quella proprietà, per applicare il counting-sort è necessario che ne godano tutti gli elementi.

Anche se noi ordinassimo prima quegli elementi con counting-sort e poi con un algoritmo (tipo heap-sort) che sia O(nlogn) avremmo comunque che il miglior modo di ordinare sarebbe O(nlogn). Sbaglio?


Title: Re:risposte esatte
Post by: Yngwie on 28-04-2009, 17:15:37
io direi che non è vero quello che hai detto... counting sort assume che tutti gli elementi dell'array appartengano ad un dato intervallo quindi di quella "cosina li" non sappiamo che farcene.
Risposta esatta C
azz...hai ragione!! :-)| solo una parte degli elementi, rad(n), sono compresi tra 0 e k...
sti confronti sul forum mi sanno di "spara e cogghi" .bah ci vorrebbe più sicurezza nelle risposte .penso


Title: Re:risposte esatte
Post by: Yngwie on 28-04-2009, 17:27:45
domanda: quanto tempo occorre per verificare se un array (ad esempio di interi) è una max/min heap?


Title: Re:risposte esatte
Post by: Root on 28-04-2009, 17:39:18
Per ogni nodo x devi controllare se i suoi figli hanno chiavi minori/maggiori della chiave di x... dunque lineare.

:D
Dario


Title: Re:risposte esatte
Post by: Nova on 28-04-2009, 17:40:39
Io ti direi un bel Theta(n) in quanto l'heap non è altro che un albero binario nel quale devi controllare soltanto se tutti i nodi sono al loro posto e per farlo li devi controllare tutti


Title: Re:risposte esatte
Post by: Acicatena86 on 28-04-2009, 17:43:51
Per ogni nodo x devi controllare se i suoi figli hanno chiavi minori/maggiori della chiave di x... dunque lineare.

:D
Dario
Esatto
 :yoh


Title: Re:risposte esatte
Post by: Asknet on 28-04-2009, 17:49:29
Posto le mie soluzioni del compito del 27 febbraio 2009:

1b-2b-3b-4c-5d-6d-7c-8c-9c-10c-11d-12a-13b-14b-15a

Io credo che per la 12 sia corretta la A perchè in questa situazione le liste di adiacenza risultano più convenienti in termini di memoria. Confermate?


Title: Re:risposte esatte
Post by: Yngwie on 28-04-2009, 17:52:03
altri quesiti succulenti:

1) tempo necessario per trasformare una max heap in una min heap e viceversa
2) tempo necessario per trasformare albero binario di ricerca in una heap (min o max) o in un RBTree e viceversa
3) tempo necessario per ordinare un array costruendo un albero binario di ricerca e applicando la visita in-order

 :yoh :yoh


Title: Re:risposte esatte
Post by: ale on 28-04-2009, 17:55:21
Asknet volevi dire la  B allora....con le liste ovviamente conviene...  .ciaociao


Title: Re:risposte esatte
Post by: Asknet on 28-04-2009, 18:05:39
Asknet volevi dire la  B allora....con le liste ovviamente conviene...  .ciaociao
Si, volevo dire la B, sorry... sarà la stanchezza   .wink


Title: Re:risposte esatte
Post by: Nova on 28-04-2009, 18:42:17
altri quesiti succulenti:

1) tempo necessario per trasformare una max heap in una min heap e viceversa

il tempo necessario è quello che prevede la procedura Build-max-heap: O(n)

Quote
2) tempo necessario per trasformare albero binario di ricerca in una heap (min o max) o in un RBTree e viceversa

Da BST a heap il tempo è sempre O(n) I suppose. Da BST a RBTree basta aggiungere un bit ad ogni nodo, percui basta modificare la struttura del nodo, percui O(1). Sbaglio?

Quote
3) tempo necessario per ordinare un array costruendo un albero binario di ricerca e applicando la visita in-order

Non capisco la domanda :S

Sono stanchissimo, perdonami :p


Title: Re:risposte esatte
Post by: Yngwie on 28-04-2009, 18:47:36
la spiego meglio:
ho un array di n elementi, trovare la complessità di un algoritmo che costruisce, a partire dall'array, un albero binario di ricerca e poi effettua la visita inorder...l'array risulta infine ordinato: quanto costa tutto ciò?
io sarei propenso per O(nlogn)


Title: Re:risposte esatte
Post by: Pandemia000 on 28-04-2009, 20:34:10
1) quoto
2) da heap a albero penso bisogna effettuari n chiamate a Tree-insert. Da Heap ad albero RB n chiamate a RB-Insert.
3) n chiamate a Tree-Insert e poi una Inorder-Tree-Walk.


Title: Re:risposte esatte
Post by: Pandemia000 on 28-04-2009, 20:48:22
per la 2) credo ci sia questo ragionamento da fare. Se la chiamata Tree-Insert ha costo O(h) per un albero di altezza h, allora la complessità sarà O(nLog(n!)).


Title: Re:risposte esatte
Post by: Yngwie on 28-04-2009, 20:53:12
ma così il costo della 3 diventa O(n2logn)?


Title: Re:risposte esatte
Post by: Pandemia000 on 28-04-2009, 20:54:09
infatti ho detto una boiata, scusatemi ma sono tropo stanco. Il costo dovrebbe essere semplicemente O(logn) basta guardare la dimostrazione a pagina 224-225-226.Notte.


Title: Re:risposte esatte
Post by: Yngwie on 28-04-2009, 20:57:40
per la 2 invece pensavo: è necessario ricostruire l'albero con tree-insert? cioè se ho già un BST posso applicare direttamente max-heapify e ottenere una heap? .penso


Title: Re:risposte esatte
Post by: Pandemia000 on 28-04-2009, 20:59:41
Un albero binario è una struttura dati differenti. Qui c'è anche il problema di passare i nodi di un albero in un arrayperchè uno heap è un'array e non una struttura dati dinamica come un'albero


Title: Re:risposte esatte
Post by: Yngwie on 28-04-2009, 21:01:30
in effetti la differenza è sottile :-)|


Title: Re:risposte esatte
Post by: Pandemia000 on 28-04-2009, 21:04:44
a pag 112 c'è la dimostrazione di come costruire uno heap in tempo lineare a partire da array non ordinato.Credo che il fatto che abbiamo un'albero binario non ci aiuti molto perchè dovremmo inserire tutti gli n elementi dell'albero nell'array dello heap.


Title: Re:risposte esatte
Post by: Yngwie on 28-04-2009, 21:09:46
perfetto....quindi una qualsiasi visita dell'albero per creare l'array con tempo n + tempo n per creare l'heap con buildheap a partire da tale array...giusto?


Title: Re:risposte esatte
Post by: Yngwie on 29-04-2009, 08:51:18
alcune equazioni di ricorrenza:

T(n)=2T(n/3)+2T(n/9)+n     ----->  con sostituzione mi viene O(n)
T(n)=4T(n/2)+n2log2n    ----> con teorema master mi viene O(n2log3n)

confermate?


Title: Re:risposte esatte
Post by: Yngwie on 29-04-2009, 08:58:42
nella seconda equazione ho visto che se f(n) è asintoticamente positiva, il secondo caso del teorema cambia aggiungendo un logkn, ovvero se f(n)=Theta(nlogbalogkn), allora la soluzione è Theta(nlogbalogk+1n)
 .camberman


Title: Re:risposte esatte
Post by: Yngwie on 29-04-2009, 09:16:15
rispolvero questa
Quote
Data una lista di n numeri interi compresi tra 1 e 1000, quale tra questi è il miglior algoritmo possibile per ordinarli?

a)Bucket Sort
b)Insertion Sort
c)Quick Sort
d)Merge Sort

Bucketsort no perchè non considera numeri interi ma numeri distribuiti in [0,1)

secondo me è il quicksort


Title: Re:risposte esatte
Post by: Pandemia000 on 29-04-2009, 09:40:23
ecco un altro gran bel dubbio: domanda numero 4 del 27 febbraio io ho risolto le due equazioni di ricorrenza e la soluzione viene nlogb4 (n elevato a logaritmo in base b di 4) per entrambi con. Quindi penso la risposta sbagliata sia la b perchè le altre dovrebbero essere vere a per alcuni fattori costanti.


Title: Re:risposte esatte
Post by: Acicatena86 on 29-04-2009, 09:42:48
rispolvero questa
Quote
Data una lista di n numeri interi compresi tra 1 e 1000, quale tra questi è il miglior algoritmo possibile per ordinarli?

a)Bucket Sort
b)Insertion Sort
c)Quick Sort
d)Merge Sort

Bucketsort no perchè non considera numeri interi ma numeri distribuiti in [0,1)

secondo me è il quicksort

Per me invece potrebbe essere il MergeSort ,poichè nel caso peggiore è sempre O(nlog)
mentre QuickSort diventa O(n2)


Che ne dici?


Title: Re:risposte esatte
Post by: Pandemia000 on 29-04-2009, 09:51:53
ho trovato!! la falsa è la c basta trovare le soluzioni delle ricorrenze e applicare le definizioni delle notazioni.


Title: Re:risposte esatte
Post by: Acicatena86 on 29-04-2009, 09:55:05
ho trovato!! la falsa è la c basta trovare le soluzioni delle ricorrenze e applicare le definizioni delle notazioni.

Si esatto  .applausi ! !


Title: Re:risposte esatte
Post by: Yngwie on 29-04-2009, 10:18:54
Quale è quella corretta?

a) n2=Ω((n+logn)2)
b) n2=Ω((nlogn)2)
c) n2=Ω((nlogn)2)
d) nessuna delle precedenti

io rispondo d), voi?


Title: Re:risposte esatte
Post by: Asknet on 29-04-2009, 10:46:48
Compito del 27/02/2009  esercizio 3)

applicando il 3° caso del teorema master la soluzione mi viene Theta(n^2 log^2 n), quindi la soluzione corretta non dovrebbe essere la A ?


Title: Re:risposte esatte
Post by: Pandemia000 on 29-04-2009, 11:04:04
a me viene n^2 log^3 n perchè sviluppo la sommatoria per i che va da 0 a logn -1 di n^2log^2 (n/2i).


Title: Re:risposte esatte
Post by: Yngwie on 29-04-2009, 11:12:32
Compito del 27/02/2009  esercizio 3)

applicando il 3° caso del teorema master la soluzione mi viene Theta(n^2 log^2 n), quindi la soluzione corretta non dovrebbe essere la A ?

nella seconda equazione ho visto che se f(n) è asintoticamente positiva, il secondo caso del teorema cambia aggiungendo un logkn, ovvero se f(n)=Theta(nlogbalogkn), allora la soluzione è Theta(nlogbalogk+1n)
 .camberman


Title: Re:risposte esatte
Post by: Asknet on 29-04-2009, 11:53:39
a me viene n^2 log^3 n perchè sviluppo la sommatoria per i che va da 0 a logn -1 di n^2log^2 (n/2i).

 .penso  non capisco, potresti essere più preciso? Lo hai risolto con il metodo dell'esperto?


Title: Re:risposte esatte
Post by: Pandemia000 on 29-04-2009, 13:16:54
no ho usato il metodo dell'albero di ricorsione. Ora non ho gli appunti con me ma se sviluppi la sommatoria dei primi n-1 livelli troverai la soluzione.


Title: Re:risposte esatte
Post by: Pandemia000 on 29-04-2009, 20:12:46
Postiamo le soluzioni dei compiti di oggi: io mi ricordo le ricorrenze

3T(n/6)+T(n/2)+n mia soluzione: mi pare di ricordare nlogn.
5T(n/3)+n^2logn: n^2logn
2T(n/2)+3T(n/3)+1: non ne ho idea forse n^2 ?


Title: Re:risposte esatte
Post by: Asknet on 04-05-2009, 16:25:45
Quote
5T(n/3)+n^2logn: n^2logn

Potresti spiegare i tuoi passaggi?  A me viene O(n^2).


Title: Re:risposte esatte
Post by: Pandemia000 on 04-05-2009, 16:45:55
allora l'albero ha a livello i costo (5/9)^i log(n/3)^i e le foglie hanno costo n^(log in base 3 di 5) basta risolvere la sommatoria applicando le proprietà dei logaritmi per ottenere quel risultato.


Title: Re:risposte esatte
Post by: Yngwie on 04-05-2009, 16:47:34
con il teorema master penso venga più immediato no?


Title: Re:risposte esatte
Post by: Acicatena86 on 04-05-2009, 16:49:01
con il teorema master penso venga più immediato no?

Ragazzi mi potreste dire le vostre risposte del compito A?

In particolare le domande 5-6-7-8-10

Grazie


Title: Re:risposte esatte
Post by: Acicatena86 on 04-05-2009, 16:49:42
con il teorema master penso venga più immediato no?

Infatti


Title: Re:risposte esatte
Post by: Pandemia000 on 04-05-2009, 16:50:51
si con il teorema master fai subito


Title: Re:risposte esatte
Post by: Pandemia000 on 04-05-2009, 16:52:16
con il teorema master penso venga più immediato no?

Ragazzi mi potreste dire le vostre risposte del compito A?

In particolare le domande 5-6-7-8-10

Grazie

io avevo l'altro compito ma svolgendolo a casa ho dato come risposte:


5b-6d-7b-8a-10b


Title: Re:risposte esatte
Post by: ForbiddenAlex on 04-05-2009, 16:56:16
con il teorema master penso venga più immediato no?

Ragazzi mi potreste dire le vostre risposte del compito A?

In particolare le domande 5-6-7-8-10

Grazie

5-b (avevo letto se inverto i nodi y e z e ho risposto d)  :-)|  )

6-a

7-a (ho considerato un albero bilanciatissimo e ho risposto O(logn)  :-)|, quando invece un albero degenere formato da una catena discendete destra, non avendo figli sinistri ha il minimo elemento nella radice....quindi il caso migliore è questo per la ricerca del minimo, ovvero Theta(1)..... :-)|  )

8-b
10-c


Title: Re:risposte esatte
Post by: Acicatena86 on 04-05-2009, 16:58:40
con il teorema master penso venga più immediato no?

Ragazzi mi potreste dire le vostre risposte del compito A?

In particolare le domande 5-6-7-8-10

Grazie

io avevo l'altro compito ma svolgendolo a casa ho dato come risposte:


5b-6d-7b-8a-10b
Alla n° 5 ho risp  d ) perchè ho letto due volte di seguito la risp a )  :-)|
Alla n° 6 ho risp d ) perchè dipende come sono fatti gli heap, ma mi sa che ho torto
Alla n° 7  b ) però nella domanda non dice che l'abero sia bilanciato, quindi potrebbe essere anche la  c
Alla n° 8      a )
Alla n°  10   b)

Che ne pensi?


Title: Re:risposte esatte
Post by: ForbiddenAlex on 04-05-2009, 17:04:09
con il teorema master penso venga più immediato no?

Ragazzi mi potreste dire le vostre risposte del compito A?

In particolare le domande 5-6-7-8-10

Grazie



io avevo l'altro compito ma svolgendolo a casa ho dato come risposte:


5b-6d-7b-8a-10b
Alla n° 5 ho risp  d ) perchè ho letto due volte di seguito la risp a )  :-)|
Alla n° 6 ho risp d ) perchè dipende come sono fatti gli heap, ma mi sa che ho torto
Alla n° 7  b ) però nella domanda non dice che l'abero sia bilanciato, quindi potrebbe essere anche la  c
Alla n° 8      a )
Alla n°  10   b)

Che ne pensi?

Allora la 6 è a in quanto se l'array A rappresenta una min heap, sicuramente nella radice avrà l'elemento minore e, poichè sia A che B sono sullo stesso identico insieme di numeri, tutti i numeri sono sicuramente >= A[1], ovvero la radice della min-heap.....

la 7 è la a in quanto qui ti chiede qual'è il numero minimo di confronti per trovare il minimo, beh come dicevo prima, se hai soltanto un sottoalbero destro(o una catena destra) basta scoprire l'inesistenza del figlio sinistro (left[root[T]=NIL) per scoprire che il minimo sta proprio in root[T], quindi effettui un singolo controllo!!!


edit: avevo sbagliato a posizionare nel quote....


Title: Re:risposte esatte
Post by: Pandemia000 on 04-05-2009, 17:17:01
della 7 non avevo letto il numero minimo di nodi .huh

rettifico la 6;

per la 8 non avevo letto array ordinato

per la c penso basti eseguire una versione modificata di heapyfy.


Title: Re:risposte esatte
Post by: Yngwie on 04-05-2009, 17:20:15
la ricorrenza n° 2 del compito b?


Title: Re:risposte esatte
Post by: Asknet on 04-05-2009, 17:24:05
si con il teorema master fai subito

Ecco, io l'ho fatto col teorema master e ho trovato che siamo nel caso 1. Quindi la soluzione dovrebbe essere Theta(n^log35). Tra quelle elencate, non ci si avvicina di più O(n^2)?


Title: Re:risposte esatte
Post by: Pandemia000 on 04-05-2009, 17:27:04
scusa ma credo che non si possa fare con il teorema master perchè non puoi verificare nessuno dei 3 casi


Title: Re:risposte esatte
Post by: Asknet on 04-05-2009, 17:42:53
scusa ma credo che non si possa fare con il teorema master perchè non puoi verificare nessuno dei 3 casi

Perchè no?

confrontando n2 con n^log35 vedi che n2 cresce più velocemente, quindi sei nel primo caso.


Title: Re:risposte esatte
Post by: ForbiddenAlex on 04-05-2009, 17:51:21
scusa ma credo che non si possa fare con il teorema master perchè non puoi verificare nessuno dei 3 casi

Perchè no?

confrontando n2 con n^log35 vedi che n2 cresce più velocemente, quindi sei nel primo caso.

La risposta è n^2(logn) dato che vi trovate nel terzo caso:

n^(log_a(b))=n^(log_3(5))=n^1,....   f(n) quindi è maggiore per una certa costante Epsilon>0(infatti n^2(logn) è sicuramente maggiore), e vi fate quattro conti e cercate di risolvere la condizione di regolarità scoprirete che essa è valida per   0<c<=5/9(log_2(9))...

non sapendo come fare ho inteso _ per base del logaritmo!


Title: Re:risposte esatte
Post by: Yngwie on 04-05-2009, 17:56:20
la ricorrenza n° 2 del compito b?
.quoto


Title: Re:risposte esatte
Post by: Asknet on 04-05-2009, 18:04:13
Quote
5-b (avevo letto se inverto i nodi y e z e ho risposto d)  testate  )

6-a

7-a (ho considerato un albero bilanciatissimo e ho risposto O(logn)  testate, quando invece un albero degenere formato da una catena discendete destra, non avendo figli sinistri ha il minimo elemento nella radice....quindi il caso migliore è questo per la ricerca del minimo, ovvero Theta(1)..... testate  )

8-b
10-c

Si parla del compito A. Potreste spiegarmi il perchè della b nella 8 ? Io ho risposto a


Title: Re:risposte esatte
Post by: ForbiddenAlex on 04-05-2009, 18:42:40
Quote
5-b (avevo letto se inverto i nodi y e z e ho risposto d)  testate  )

6-a

7-a (ho considerato un albero bilanciatissimo e ho risposto O(logn)  testate, quando invece un albero degenere formato da una catena discendete destra, non avendo figli sinistri ha il minimo elemento nella radice....quindi il caso migliore è questo per la ricerca del minimo, ovvero Theta(1)..... testate  )

8-b
10-c

Si parla del compito A. Potreste spiegarmi il perchè della b nella 8 ? Io ho risposto a

Guarda in questo momento sono fuso e non saprei spiegartelo, comunque io ho scelto di utilizzare un ipotetico algoritmo che posizionasse la mediana inferiore dell'array ordinato come radice del BST ed in seguito inserisse gli elementi dei 2 sottoarray restanti(sinistro elementi minori o uguali alla mediana, destro elementi maggiori) negli alberi radicati nei figli della radice, scusa ma sto ripassando da stamattina e ho il cervello mezzo fuso...credo che per oggi sono arrivato al capolinea!  :[Emoticon] Asd:


Title: Re:risposte esatte
Post by: Pandemia000 on 04-05-2009, 20:16:29
scusa ma credo che non si possa fare con il teorema master perchè non puoi verificare nessuno dei 3 casi

Perchè no?

confrontando n2 con n^log35 vedi che n2 cresce più velocemente, quindi sei nel primo caso.

La risposta è n^2(logn) dato che vi trovate nel terzo caso:

n^(log_a(b))=n^(log_3(5))=n^1,....   f(n) quindi è maggiore per una certa costante Epsilon>0(infatti n^2(logn) è sicuramente maggiore), e vi fate quattro conti e cercate di risolvere la condizione di regolarità scoprirete che essa è valida per   0<c<=5/9(log_2(9))...

non sapendo come fare ho inteso _ per base del logaritmo!

si infatti ci troviamo nel terzo caso, scusate ma ho il cervello fuso per ora....


Title: Re:risposte esatte
Post by: Yngwie on 04-05-2009, 20:23:50
La risposta è n^2(logn) dato che vi trovate nel terzo caso:

n^(log_a(b))=n^(log_3(5))=n^1,....   f(n) quindi è maggiore per una certa costante Epsilon>0(infatti n^2(logn) è sicuramente maggiore), e vi fate quattro conti e cercate di risolvere la condizione di regolarità scoprirete che essa è valida per   0<c<=5/9(log_2(9))...
esatto...ma non ho capito quel 5/9log29...non dovrebbe essere 5/9log23?

non sapendo come fare ho inteso _ per base del logaritmo!
puoi usare le funzioni:
Code:
[sup][/sup] per l'esponente
[sub][/sub] per l'apice
almeno quelle ci sono |-O


Title: Re:risposte esatte
Post by: ForbiddenAlex on 04-05-2009, 20:44:35
La risposta è n^2(logn) dato che vi trovate nel terzo caso:

n^(log_a(b))=n^(log_3(5))=n^1,....   f(n) quindi è maggiore per una certa costante Epsilon>0(infatti n^2(logn) è sicuramente maggiore), e vi fate quattro conti e cercate di risolvere la condizione di regolarità scoprirete che essa è valida per   0<c<=5/9(log_2(9))...
esatto...ma non ho capito quel 5/9log29...non dovrebbe essere 5/9log23?

non sapendo come fare ho inteso _ per base del logaritmo!


puoi usare le funzioni:
Code:
[sup][/sup] per l'esponente
[sub][/sub] per l'apice
almeno quelle ci sono |-O

hem, si hai ragione...sono molto stanco oggi, è logn...non log(n^2), comunque il succo del discorso è lo stesso, ovvero il fatto che c<1, che è quello che ci interessa, per valori di n grandi...


Title: Re:risposte esatte
Post by: ale on 04-05-2009, 20:59:29
Come avete risolto l'equazione di ricorrenza T(n)=3*T(n/6)+T(n/2)+n....  .poverinoi


Title: Re:risposte esatte
Post by: Acicatena86 on 04-05-2009, 21:07:46
Come avete risolto l'equazione di ricorrenza T(n)=3*T(n/6)+T(n/2)+n....  .poverinoi
Ragazzi ci vediamo domani! Ci aspetta una lunga attesa  :-ciao :-ciao :-ciao


Title: Re:risposte esatte
Post by: ale on 04-05-2009, 21:12:47
Sarebbe più utile saperlo ora che domani...  :pray


Title: Re:risposte esatte
Post by: Yngwie on 04-05-2009, 21:15:26
hem, si hai ragione...sono molto stanco oggi, è logn...non log(n^2), comunque il succo del discorso è lo stesso, ovvero il fatto che c<1, che è quello che ci interessa, per valori di n grandi...
mi venne invece un dubbio...può essere che c<=5/9 e basta?