Pages: 1 [2] 3   Go Down
Print
Author Topic: Domande dell'esame odierno  (Read 3463 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #15 on: 04-02-2013, 21:21:11 »

Purtroppo non ho lo scanner al momento, la domanda diceva:

Data l'equazione di ricorrenza T(n)=2T(n/k)+T(2n/k)+n, per quale valore di k, T(n)=theta(n)?

a) k=2
b) k=3
c) k=4
d) nessuna delle precedenti

se sostituisco con k=2 dovrebbe uscire l'equazione di ricorrenza di prima che ho scritto sopra

Si si esce quella cmq allora vale il discorso di prima, secondo me non termina infatti anche facendo un albero di ricorsione avresti altezza infinita.
Per cui è d pure questa?
Logged
207
Matricola
*
Offline Offline

Posts: 95


« Reply #16 on: 04-02-2013, 21:30:12 »

Infatti penso anche io sia come dici tu, per quello ho messo d  ok
Logged
VanDir
Matricola
*
Offline Offline

Posts: 68


« Reply #17 on: 04-02-2013, 23:57:51 »

Si è D anche questa
Infatti penso anche io sia come dici tu, per quello ho messo d  ok

Perfetto   ok
Logged
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #18 on: 05-02-2013, 00:03:46 »

Ma la 12? Che avete messo?
Logged
Twitch
Apprendista Forumista
**
Offline Offline

Posts: 183


Orange Moka Frappucinoooo!!!


« Reply #19 on: 05-02-2013, 08:56:59 »

Qualcuno può postare gentilmente il testo?
Logged
Il Capitano
Apprendista Forumista
**
Offline Offline

Posts: 409


« Reply #20 on: 05-02-2013, 09:51:04 »

Ragazzi ma nella 1 per verificare la A e la B che passaggi avete fatto?
Logged
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #21 on: 06-02-2013, 09:06:24 »

Ragazzi alla 9 che spiegazione date?
Logged
VanDir
Matricola
*
Offline Offline

Posts: 68


« Reply #22 on: 06-02-2013, 11:04:37 »

Ragazzi alla 9 che spiegazione date?

Buona sera a tutti, ragazzi secondo me la risposta alla domanda 9 è la d poichè la mediana è calcolata da un insieme di numeri ordinati, gli array A e B sono ordinati ma bisogna fonderli, seconde me si intende questo per concatenamento. Voi cosa ne pensate? Non avrebbe senso concatenare A e B così come sono e calcolare la mediana poichè non si hanno garanzie che tutti gli elementi del secondo array siano maggiori degli elementi del primo array. 

Io ho messo che è logaritmica e il prof. stesso qui conferma:
http://forum.sdai.unict.it/index.php?topic=12428.msg76819#msg76819
Logged
207
Matricola
*
Offline Offline

Posts: 95


« Reply #23 on: 06-02-2013, 11:13:41 »

Buongiorno ragazzi mi è venuto un dubbio che la risposta a questa domanda sia n log n:

Il tempo di esecuzione di Quicksort quando tutti gli elementi dell'array sono uguali è:
a) n
b) n log n
c) n^2
d) n^2 log n

Se provo ad eseguire partition lo divide sempre in due metà esatte, a causa del minore senza uguale nel ciclo di Partition, voi ci avevate fatto caso?
Logged
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #24 on: 06-02-2013, 11:47:12 »

Buongiorno ragazzi mi è venuto un dubbio che la risposta a questa domanda sia n log n:

Il tempo di esecuzione di Quicksort quando tutti gli elementi dell'array sono uguali è:
a) n
b) n log n
c) n^2
d) n^2 log n

Se provo ad eseguire partition lo divide sempre in due metà esatte, a causa del minore senza uguale nel ciclo di Partition, voi ci avevate fatto caso?
Ci sono  diverse teorie
http://forum.sdai.unict.it/index.php?topic=13810.0
Logged
atrix0ne
Forumista
***
Offline Offline

Posts: 607


homo faber fortunae suae


« Reply #25 on: 06-02-2013, 12:24:28 »

Ragazzi,voi della programazzione dinamica fino a dove studiate?La più lunga sottosequenza comune si deve studiare?
Logged

VanDir
Matricola
*
Offline Offline

Posts: 68


« Reply #26 on: 06-02-2013, 12:30:21 »

Secondo me è n^2 perchè anche se metti il minore senza uguale divide lo stesso in due partizioni una di dimensione 0 e una di dimensione n - 1.
Infatti se guardate il codice di partition a pag 142 del libro, supponendo che il confronto si faccia col minore senza uguale, l'indice i non viene mai incrementato nel ciclo e quindi nella riga 7 del codice il pivot viene scambiato con l'elemento che sta in prima posizione del sottoarray. L'unica differenza con l'usare il minore con l'uguale è che in questo caso l'indice i verrebbe incrementato sempre e quindi il pivot alla fine viene scambiato con se stesso creando lo stesso due partizione col massimo sbilanciamento. Tra l'altro l'array è ordinato e quindi si va nel caso peggiore. Sperando che con QuickSort non intendesse la versione randomizzata.  [Emoticon] Asd
Ragazzi,voi della programazzione dinamica fino a dove studiate?La più lunga sottosequenza comune si deve studiare?
Si a lezione l'abbiamo fatta.
« Last Edit: 06-02-2013, 12:38:19 by VanDir » Logged
atrix0ne
Forumista
***
Offline Offline

Posts: 607


homo faber fortunae suae


« Reply #27 on: 06-02-2013, 12:39:49 »

Anche alberi binari di ricerca ottimi?per la programmazione dinamica
Logged

VanDir
Matricola
*
Offline Offline

Posts: 68


« Reply #28 on: 06-02-2013, 12:41:17 »

Anche alberi binari di ricerca ottimi?per la programmazione dinamica
No no quello no
Logged
atrix0ne
Forumista
***
Offline Offline

Posts: 607


homo faber fortunae suae


« Reply #29 on: 06-02-2013, 12:43:10 »

e per quanto riguarda Algoritmi golosi?fino al codice di huffman?
Logged

Pages: 1 [2] 3   Go Up
Print
Jump to: