Pages: [1]   Go Down
Print
Author Topic: Info 3 prova in itinere  (Read 1708 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Dajsy
Matricola
*
Offline Offline

Gender: Female
Posts: 39



« on: 10-02-2010, 19:58:14 »

Come avete svolto la 3 prova in itinere?
Logged

La felicità non và ricercata nel cielo sempre sereno...ma nelle piccole cose con le quali costruiamo la vita!!
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #1 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)
Logged
Slayer
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 106



« Reply #2 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?
Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #3 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
Logged
Slayer
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 106



« Reply #4 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.
« Last Edit: 11-02-2010, 09:54:04 by Slayer » Logged
shiny
Forumista
***
Offline Offline

Posts: 810



WWW
« Reply #5 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.
Logged
Pages: [1]   Go Up
Print
Jump to: