Forum Informatica Unict

Vecchi ordinamenti ad esaurimento => Algoritmi 2 => Topic started by: Dajsy on 10-02-2010, 19:58:14



Title: Info 3 prova in itinere
Post by: Dajsy on 10-02-2010, 19:58:14
Come avete svolto la 3 prova in itinere?


Title: Re:Info 3 prova in itinere
Post by: shiny on 10-02-2010, 21:14:54
io ho usato l'algoritmo per i DAG dopo aver dimostrato che il grafo e' aciclico.
Si poteva anche scorrere i nodi della matrice per riga e su ognuno chiamare una scan.
Per quanto riguarda la complessita' era  O(V+E) e riportato ad n, nel caso medio e pessimo (rispettivamente \frac{n}{2} e  n-1 archi per nodo) O(n^4) mentre nel caso migliore (un solo arco per nodo) \Theta(n^2)


Title: Re:Info 3 prova in itinere
Post by: Slayer on 10-02-2010, 21:19:22
Non capisco perchè il numero di archi dovrebbe essere n/2 e n-1 nel caso medio e nel caso peggiore rispettivamente. Potresti spiegarlo per piacere?


Title: Re:Info 3 prova in itinere
Post by: shiny on 10-02-2010, 21:47:28
ho sbagliato a scrivere: caso medio \frac{n^2}{4} e caso pessimo  n^2-1
se consideri che mediamente la matrice contiene \frac{n^2}{2} nodi e che mediamente ogni nodo e' collegato con meta' dei nodi presenti hai \frac{n^2}{4} archi per nodo
nel caso pessimo la matrice e' piena n^2 nodi e ogni nodo collegato con tutti gli altri meno se stesso,  n^2- 1 archi per nodo


Title: Re:Info 3 prova in itinere
Post by: Slayer on 10-02-2010, 22:25:20
Nel caso pessimo, ogni nodo è collegato solo con i nodi che si trovano nella sottomatrice che ha in questo il proprio angolo in alto a sinistra. Quindi, solo nel caso in cui il nodo si trova nella posizione di indici 1,1 ci sono n2-1 archi che lo collegano agli altri nodi.


Title: Re:Info 3 prova in itinere
Post by: shiny on 11-02-2010, 02:28:05
Nel caso pessimo, ogni nodo è collegato solo con i nodi che si trovano nella sottomatrice che ha in questo il proprio angolo in alto a destra. Quindi, solo nel caso in cui il nodo si trova nella posizione di indici 1,1 ci sono n2-1 archi che lo collegano agli altri nodi.
hai perfettamente ragione e nel compito mi sa che ho sbagliato XD

Comunque ho risolto la seguente doppia sommatoria  \sum_{i=1}^n \sum_{j=1}^n [(n-i+1)(n-j+1)] - 1 che dovrebbe rappresentare il numero massimo di archi e il termine col grado piu' alto e' sempre n^4.