Pages: 1 [2] 3 4 ... 12   Go Down
Print
Author Topic: risposte esatte  (Read 31026 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
info
Guest
« Reply #15 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...
Logged
Yngwie
Forumista
***
Offline Offline

Gender: Male
Posts: 849


Maestro! mi dia un MI in chiave di SOL!


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

chissà a che ora usciranno i risultati....
Logged

bakks87
Apprendista Forumista
**
Offline Offline

Posts: 162


« Reply #17 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?Huh?Huh?Huh?Huh?Huh?   
forse volevi dire nel caso in cui l'array è di piccole dimensioni!!!?
Logged
Syco
Matricola
*
Offline Offline

Gender: Male
Posts: 31


WWW
« Reply #18 on: 19-02-2009, 21:00:15 »

chissà a che ora usciranno i risultati....
per il primo appello sono usciti alle 2340...e gli orali erano fissati per le 9...
buona attesa...
Logged

Yngwie
Forumista
***
Offline Offline

Gender: Male
Posts: 849


Maestro! mi dia un MI in chiave di SOL!


« Reply #19 on: 19-02-2009, 21:01:58 »

vabbè ke il primo appello terminava verso le 18....
Logged

Erithema
Matricola
*
Offline Offline

Posts: 12


« Reply #20 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
Logged
info
Guest
« Reply #21 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?Huh?Huh?Huh?Huh?Huh?   
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...

Logged
Worm
Matricola
*
Offline Offline

Posts: 24



« Reply #22 on: 19-02-2009, 22:07:26 »

mmm
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.
Logged
Syco
Matricola
*
Offline Offline

Gender: Male
Posts: 31


WWW
« Reply #23 on: 19-02-2009, 22:30:10 »

mmm
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
Logged

shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #24 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.
« Last Edit: 19-02-2009, 22:51:25 by shiny » Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #25 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).
Logged
bimbo87
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 129



WWW
« Reply #26 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?
Logged
Pandemia000
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.714


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


« Reply #27 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 ?
« Last Edit: 20-02-2009, 12:39:22 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)
James
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 209



« Reply #28 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
« Last Edit: 20-02-2009, 12:58:08 by James » Logged

Whatever people say i am, that's what i'm not
Mosquito
Guest
« Reply #29 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.
Logged
Pages: 1 [2] 3 4 ... 12   Go Up
Print
Jump to: