Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Algoritmi, 9 CFU => Topic started by: alex180788 on 20-01-2011, 22:49:23



Title: Domada d'esame
Post by: alex180788 on 20-01-2011, 22:49:23
Sia OT un ordinamento topologico di un grafo orientato aciclico G con |V|=n vertici ed |E|=n archi. Sia Gt il grafo trasposto di G.
Qual'è la compessità del migliore algoritmo possibile per calcolare un ordinamento topologico per Gt?

a) O(1)
b) O(V)
c) O(V+E)
d) O(OT)

non ne sono sicuro ma posso ottenere l'ordinamento topologico di Gt semplicemente invertendo l'ordinamento topologico di G?... OT è un ordinamento dei vertici di G lungo una linea orizzontale in modo che tutti gli archi orientati siano diretti da sinistra a destra..... se leggo OT al "contrario" non ottengo un ordinamento topologico di Gt ?

secondo voi come si deve rispondere a questa domanda?


Title: Re:Domada d'esame
Post by: KingDavid on 21-01-2011, 09:23:00
[...]
secondo voi come si deve rispondere a questa domanda?
studiando e ragionandoci un po su...


Title: Re:Domada d'esame
Post by: alex180788 on 21-01-2011, 09:58:47
non ne sono sicuro ma posso ottenere l'ordinamento topologico di Gt semplicemente invertendo l'ordinamento topologico di G?... OT è un ordinamento dei vertici di G lungo una linea orizzontale in modo che tutti gli archi orientati siano diretti da sinistra a destra..... se leggo OT al "contrario" non ottengo un ordinamento topologico di Gt ?

secondo voi come si deve rispondere a questa domanda?

ci sto provando.... non ho mica chiesto di farlo al posto mio, magari studiando (da soli) e ragionandoci (da soli) possiamo imparare l'uno dall'altro confrontandoci (insieme) e posso capire che il mio ragionamento è giusto o completamente sbagliato oppure un altro collega può sfruttare questo topic per approfondire o per confermare se quello che ha capito è giusto/sbagliato ... insomma il forum serve proprio per confrontarsi altrimenti non l'avrei postata, ma se uno ha un dubbio credo che sia lecito chiedere (il topic sotto questo ha 5 pagine 61 risposte e  2066 visite di discussione su esercizi di compito e credo che i partecipanti o anche solo chi ha letto ne abbiano tratto dei benefici nello studiio di questa materia) ai colleghi sfruttando questo strumento che non hanno tutte le facoltà invece di invadere gli uffici dei professori.