Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Algoritmi, 9 CFU => Topic started by: aga84 on 28-05-2011, 08:41:05



Title: Esame del 27 Maggio
Post by: aga84 on 28-05-2011, 08:41:05
Salve a tutti,per chi ieri ha fatto l'appello straordinario come avete risposto alle domande numero 4 , 13 e 15?? Penso che la maggior parte di voi ricordi la domanda o ha il testo dell'esame.....


Title: Re:Esame del 27 Maggio
Post by: Grillo on 28-05-2011, 08:46:09
Io 4:d 13:b 15:d


Title: Re:Esame del 27 Maggio
Post by: Vivynz on 28-05-2011, 08:53:20
Alla 4 ho risposto a B cioè O(n), considerando l'equazione di ricorrenza del Mergesort che è T(n)=2T(n/2)+\Theta(n) che diventerebbe T(n)=2T(n/2)+\Theta(logn) e risolvendo questa nuova ricorrenza.

Alla 13 ho risposto la A ma onestamente non ero molto convinta...

Alla 15 ho risposto A perchè essendo il grafo fortemente connesso, per qualunque vertice che viene selezionato come sorgente tutti gli altri vertici saranno raggiungibili, dunque non rimarrano vertici inesplorati da selezionare come nuove sorgenti e di conseguenza come radici di altri alberi.


Title: Re:Esame del 27 Maggio
Post by: crypt0 on 28-05-2011, 09:01:18
4: B (per lo stesso ragionamento di Vivynz

13: A ... Alla matrice di adiacenza si accede con indirizzamento diretto, con le liste di adiacenza è necessario un minimo di scorrimento, quindi C2 potrebbe essere maggiore di C1 che, invece, ha sempre durata costante


Title: Re:Esame del 27 Maggio
Post by: Vivynz on 28-05-2011, 09:03:35
4: B (per lo stesso ragionamento di Vivynz

13: A ... Alla matrice di adiacenza si accede con indirizzamento diretto, con le liste di adiacenza è necessario un minimo di scorrimento, quindi C2 potrebbe essere maggiore di C1 che, invece, ha sempre durata costante
si in effetti per la 13 ho fatto un ragionamento simile..anche perchè lo spazio per la matrice è già allocato, si tratta solo di cambiare il valore di una cella, mentre con le liste bisogna aggiungere un nuovo elemento nelle liste dei 2 vertici.


Title: Re:Esame del 27 Maggio
Post by: esteta84 on 28-05-2011, 09:24:16
4:d 13:b 15:d


Title: Re:Esame del 27 Maggio
Post by: gabfri on 28-05-2011, 10:25:37
secondo me li risposte giuste sono:
1-b 2-c 3-d 4-d (anche se mi ha convinto la risposta scritta da voi) 5-c 6-a 7-b 8-b 9-d 10-b 11-d 12-a 13-b 14-c 15-d



Title: Re:Esame del 27 Maggio
Post by: aga84 on 28-05-2011, 10:30:49
Io ho risposto così :

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

Di tutti questi sono in fortissimo dubbio per la 4,7,9,13 e 15


Title: Re:Esame del 27 Maggio
Post by: gabfri on 28-05-2011, 10:59:27
se volete io sono in aula studio, possiamo confrontare le risposte e ripassiamo


Title: Re:Esame del 27 Maggio
Post by: N@deg@ on 28-05-2011, 11:33:35
secondo me li risposte giuste sono:
1-b 2-c 3-d 4-d (anche se mi ha convinto la risposta scritta da voi) 5-c 6-a 7-b 8-b 9-d 10-b 11-d 12-a 13-b 14-c 15-d



Quelle che sono giuste a mio parere sono queste.. apparte per la 4 che è b, per i motivi già detti,e la 15 credo sia a per qualche appunto preso al riguardo.


Title: Re:Esame del 27 Maggio
Post by: vincenzo86 on 28-05-2011, 12:16:59
Qualcuno potrebbe postare il testo dell'esame? Grazie


Title: Re:Esame del 27 Maggio
Post by: InfoArtist on 28-05-2011, 17:17:39
Per evitare di perdere tempo a ricopiarlo ho fatto delle foto. Sono qua:
http://nonsoloubuntu.altervista.org/esame-algoritmi-27052011/ (http://nonsoloubuntu.altervista.org/esame-algoritmi-27052011/)
Ciao


Title: Re:Esame del 27 Maggio
Post by: vincenzo86 on 29-05-2011, 08:43:45
Ti ringrazio per il testo postato.. In bocca al lupo a tutti


Title: Re:Esame del 27 Maggio
Post by: nolight76 on 29-05-2011, 08:55:27
Immagino che i risultati il prof li pubblichera' Lunedi'... speriamo di farcela va...comunque, ecco i miei:

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


Title: Re:Esame del 27 Maggio
Post by: vincenzo86 on 29-05-2011, 12:19:08
Scusate nella domanda 14 sul grafo orientato dice così:
"Un grafo orientato è aciclico se e solo se la visita in profondità non genera:
a. Archi d'albero;
b. Archi in avanti;
c. Archi all'indietro;
d. Archi trasversali.

io so che un grafo orientato è acicilico quando nel grafo non sono presenti percorsi chiusi che partono e terminano dallo stesso nodo; quindi in questo caso se si mette la c non è sbagliato?
Se nella domanda non ci fosse stato quel "non genera" ma bensì "genera" allora sarebbe stata la lettera c.


Title: Re:Esame del 27 Maggio
Post by: Vivynz on 29-05-2011, 12:26:37
gli archi all'indietro sono proprio quelli che collegano un vertice ad un antenato...perchè dovrebbe essere sbagliato? Lemma 22.11 del Cormen: Un grafo orientato G è aciclico se e soltanto se una visita in profondità NON GENERA archi all'indietro


Title: Re:Esame del 27 Maggio
Post by: esteta84 on 29-05-2011, 12:55:14
I cammini che partono e terminano nello stesso vertice sono cicli e gli archi all'indietro generano cicli. Ne è un esempio particolare un cappio, che è sia un arco all'indietro, sia un ciclo di lunghezza 1  .ciaociao


Title: Re:Esame del 27 Maggio
Post by: gabfri on 29-05-2011, 20:25:33
gli archi all'indietro sono proprio quelli che collegano un vertice ad un antenato...perchè dovrebbe essere sbagliato? Lemma 22.11 del Cormen: Un grafo orientato G è aciclico se e soltanto se una visita in profondità NON GENERA archi all'indietro

sono assolutamente d'accordo con te!

ma invece per quanto riguarda la domanda n°9 la risposta corretta è la D vero???
leggendolo e rileggendolo  (o per lo meno parlando con qualche collega) mi sono venuti dubbi che la rispsota potrebbe essere anche la A... fatemi sapere


Title: Re:Esame del 27 Maggio
Post by: InfoArtist on 29-05-2011, 20:29:57
Si, la 9 è la d. Il tempo per partizionare attorno alla mediana delle mediane è O(n) quindi non può essere la a.


Title: Re:Esame del 27 Maggio
Post by: gabfri on 29-05-2011, 20:47:42
Si, la 9 è la d. Il tempo per partizionare attorno alla mediana delle mediane è O(n) quindi non può essere la a.

grazie per il chiarimento... un pensiero in meno  .camberman


Title: Re:Esame del 27 Maggio
Post by: Vivynz on 29-05-2011, 21:47:39
Sisi   .smile
Spero che domani oltre ai risultati si potranno avere le risposte giuste "ufficiali", non si sa mai, anche per conoscenza :D