Quesiti vari
In un test ho trovato queste domande, vorrei chiedere un parere sulle mie risposte:
1)Se G è un grafo orientato con |V| n vertici implementato mediante liste di adiacenza, qual è il costo computazione per aggiungere un arco al grafo?
a)O(1)
b)O(V)
c)O(V+E)
d)O(E)
Secondo me è la b, perchè io se devo aggiungere un' arco ad un nodo devo trovarlo, e quindi scorro i vertici in tempo O(V), e poi inserisco in lista di adiacenza in testa il nodo adiacente per cui creo l' arco in tempo O(1).
2)Sia G un grafo come quello precedente ma implementato mediante matrice di adiacenza, qual è il costo per eliminare da un dato vertice v i suoi archi uscenti?
a)O(V)
b)O(V+E)
c)O(V^2)
d)O(E)
Secondo me la c, perchè devo trovare il vertice nella matrice, e poi scorrere a destra la matrice per verificare se vi sia un arco, cioè un valore 1 nelle locazione della matrice.
3) Ho un grafo orientato ed aciclico con n vertici ed n archi e OT un ordinamento topologico. Se considero il grafo trasposto qual è la complessità per trovare il nuovo ordinamento topologico?
a)O(1)
b)O(V)
c)O(V+E)
d)O(OT)
Qui non saprei....mi verrebbe da dire che il tempo è lo stesso e dovrebbe essere la c.
4)Sia G un grafo orientato fortemente connesso, quale delle seguenti affermazioni è sicuramente vera?
a)Esiste un vertice la cui rimozione dal grafo rende il grafo aciclico.
b)Esiste un ciclo semplice che coinvolge tutti i vertici del grafo.
c)Esiste un arco la cui rimozione dal grafo rende aciclico il grafo.
d)Nessuna delle precedenti.
Io ho provato a rappresentare un paio di grafi, e mi risulta la d), nessuna è sicuramente vera.
5) Sia A un array di n interi maggiori di 2. Supponiamo di poter trovare i divisori primi di un intero k in tempo O(k) e che tutte le altre operazioni aritmetiche possano essere svolte in tempo pari ad O(1). Qual è la complessità del migliore algoritmo che verifichi se tutti gli n elementi abbiamo almeno un divisore comune?
a)O(k)
b)O(n+k)
c)O(nk)
d)O(n^k)
Secondo me la d, perchè basta prendere il primo numero e i suoi divisori, che vengono trovati in tempo O(k), e li confronto con quelli degli altri numeri, quindi io faro n confronti k volte.
1)Se G è un grafo orientato con |V| n vertici implementato mediante liste di adiacenza, qual è il costo computazione per aggiungere un arco al grafo?
a)O(1)
b)O(V)
c)O(V+E)
d)O(E)
Secondo me è la b, perchè io se devo aggiungere un' arco ad un nodo devo trovarlo, e quindi scorro i vertici in tempo O(V), e poi inserisco in lista di adiacenza in testa il nodo adiacente per cui creo l' arco in tempo O(1).
2)Sia G un grafo come quello precedente ma implementato mediante matrice di adiacenza, qual è il costo per eliminare da un dato vertice v i suoi archi uscenti?
a)O(V)
b)O(V+E)
c)O(V^2)
d)O(E)
Secondo me la c, perchè devo trovare il vertice nella matrice, e poi scorrere a destra la matrice per verificare se vi sia un arco, cioè un valore 1 nelle locazione della matrice.
3) Ho un grafo orientato ed aciclico con n vertici ed n archi e OT un ordinamento topologico. Se considero il grafo trasposto qual è la complessità per trovare il nuovo ordinamento topologico?
a)O(1)
b)O(V)
c)O(V+E)
d)O(OT)
Qui non saprei....mi verrebbe da dire che il tempo è lo stesso e dovrebbe essere la c.
4)Sia G un grafo orientato fortemente connesso, quale delle seguenti affermazioni è sicuramente vera?
a)Esiste un vertice la cui rimozione dal grafo rende il grafo aciclico.
b)Esiste un ciclo semplice che coinvolge tutti i vertici del grafo.
c)Esiste un arco la cui rimozione dal grafo rende aciclico il grafo.
d)Nessuna delle precedenti.
Io ho provato a rappresentare un paio di grafi, e mi risulta la d), nessuna è sicuramente vera.
5) Sia A un array di n interi maggiori di 2. Supponiamo di poter trovare i divisori primi di un intero k in tempo O(k) e che tutte le altre operazioni aritmetiche possano essere svolte in tempo pari ad O(1). Qual è la complessità del migliore algoritmo che verifichi se tutti gli n elementi abbiamo almeno un divisore comune?
a)O(k)
b)O(n+k)
c)O(nk)
d)O(n^k)
Secondo me la d, perchè basta prendere il primo numero e i suoi divisori, che vengono trovati in tempo O(k), e li confronto con quelli degli altri numeri, quindi io faro n confronti k volte.
Risposte
Non capisco perché ritieni che cercare un nodo in una matrice o in una lista di adiacenza richieda una complessità di \( O(V) \). A meno di usare una lista concatenata per l'implementazione delle due strutture, una pessima idea a mio parere, la complessità può essere molto minore. Usando per esempio un semplice array o una tabella di hash si può avere complessità di \( O(1) \) per la ricerca del nodo. Per cui secondo me le soluzioni più sensate in questo caso sono a per la prima domanda e d per la seconda (anche se dipende appunto dall'effettiva implementazione*).
Per la terza domanda dovrei pensarci. Immagino però che si possa usare l'ordinamento del grafo per ottenere quello del secondo. Siccome le relazioni sono invertite, immagino possa essere semplicemente l' "inverso" dell'ordinamento del grafo iniziale. Ci vorrebbe una dimostrazione, ma se questo fosse un ordinamento topologico valido come immagino, la risposta sarebbe la b.
Sulla 4 ci dovrei pensare. È abbastanza facile trovare un esempio contro b, che esempi hai trovato contro a e c?
Sulla 5 secondo me si può fare di meglio.
* Il tuo professore ha fornito una qualche implementazione?
Per la terza domanda dovrei pensarci. Immagino però che si possa usare l'ordinamento del grafo per ottenere quello del secondo. Siccome le relazioni sono invertite, immagino possa essere semplicemente l' "inverso" dell'ordinamento del grafo iniziale. Ci vorrebbe una dimostrazione, ma se questo fosse un ordinamento topologico valido come immagino, la risposta sarebbe la b.
Sulla 4 ci dovrei pensare. È abbastanza facile trovare un esempio contro b, che esempi hai trovato contro a e c?
Sulla 5 secondo me si può fare di meglio.
* Il tuo professore ha fornito una qualche implementazione?
"apatriarca":
Per la terza domanda dovrei pensarci. Immagino però che si possa usare l'ordinamento del grafo per ottenere quello del secondo. Siccome le relazioni sono invertite, immagino possa essere semplicemente l' "inverso" dell'ordinamento del grafo iniziale. Ci vorrebbe una dimostrazione, ma se questo fosse un ordinamento topologico valido come immagino, la risposta sarebbe la b.
invece io direi che è $c$. Dato che di solito l'ordinamento topologico si utilizza la proprietà dei grafi aciclici, e la visita DFS.
Visto che un grafo ed il suo trasposto sono simmetrici, ed esistendo un cammino tra i nodi ($(u,v)^T=(v,u)$), da ciò si capisce che il tempo di visita è identico, se non sbaglio
Ma nell'esercizio si fa riferimento ad un ordinamento topologico del grafo iniziale. Calcolare un nuovo ordinamento richiede una complessità di \( O(V + E) \), ma è possibile fare di meglio sfruttando l'ordinamento che già si conosce. Sia infatti
\[ v_{\sigma(1)}, v_{\sigma(2)} \dots, v_{\sigma(V)} \]
l'ordinamento topologico del grafo (\(\sigma\) è una permutazione). Voglio dimostrare che
\[ v_{\sigma(V)}, v_{\sigma(V-1)}, \dots, v_{\sigma(1)} \]
è un ordinamento topologico per il grafo trasposto. Verifichiamo quindi la definizione di ordinamento topologico. Siano quindi \(i < j\) due indici, dobbiamo mostrare che non esiste alcun percorso da \(v_{\sigma(V-j)}\) a \(v_{\sigma(V-i)}\) nel grafo trasposto. Ma se esistesse, dovrebbe esistere un percorso da \(v_{\sigma(V-i)}\) a \(v_{\sigma(V-j)}\) nel grafo iniziale che è assurdo perché abbiamo supposto quello di sopra un ordinamento topologico. È quindi sufficiente "capovolgere" l'ordinamento del grafo*.
* Se si vuole effettivamente creare la lista si ha una complessità di \(O(V)\), ma per molte applicazioni non è in effetti necessario costruire una nuova lista e quindi si ha una complessità costante \(O(1)\).
\[ v_{\sigma(1)}, v_{\sigma(2)} \dots, v_{\sigma(V)} \]
l'ordinamento topologico del grafo (\(\sigma\) è una permutazione). Voglio dimostrare che
\[ v_{\sigma(V)}, v_{\sigma(V-1)}, \dots, v_{\sigma(1)} \]
è un ordinamento topologico per il grafo trasposto. Verifichiamo quindi la definizione di ordinamento topologico. Siano quindi \(i < j\) due indici, dobbiamo mostrare che non esiste alcun percorso da \(v_{\sigma(V-j)}\) a \(v_{\sigma(V-i)}\) nel grafo trasposto. Ma se esistesse, dovrebbe esistere un percorso da \(v_{\sigma(V-i)}\) a \(v_{\sigma(V-j)}\) nel grafo iniziale che è assurdo perché abbiamo supposto quello di sopra un ordinamento topologico. È quindi sufficiente "capovolgere" l'ordinamento del grafo*.
* Se si vuole effettivamente creare la lista si ha una complessità di \(O(V)\), ma per molte applicazioni non è in effetti necessario costruire una nuova lista e quindi si ha una complessità costante \(O(1)\).
@apatriarca:
ma perciò quel OT è l'ordinamente topologico già calcolato. Non avevo capito questo
Te perciò riutilizzi questo OT per calcolare il nuovo ordinamento, interessante. Se sì allora $OT(G^T)=OT^(-1)(G)$?
ma perciò quel OT è l'ordinamente topologico già calcolato. Non avevo capito questo
Te perciò riutilizzi questo OT per calcolare il nuovo ordinamento, interessante. Se sì allora $OT(G^T)=OT^(-1)(G)$?
Per la prima domanda sto pensando che forse è effettivamente la a), perchè non dice di inserire un arco ad un vertice preciso, ma al grafo, quindi posso inserirlo in tempo O(1) nella lista del primo elemento dell' array.
Quanto alla seconda, non capisco perchè parli di tabelle di hash, qui parliamo di matrice di adiacenza, l' implementazione è quella. DIce il costo per eliminare gli archi uscenti di un vertice v, quindi secondo me prima devo trovare nella matrice, nella prima colonna per intenderci questo v, e poi scorro a destra per vedere quali sono gli archi uscenti....quindi dovrebbe essere [tex]O(V+E)[/tex]
Il grafo che ho considerato, sperando di non sbagliare è:
http://imageshack.us/photo/my-images/84/grafo.jpg/
Quanto alla seconda, non capisco perchè parli di tabelle di hash, qui parliamo di matrice di adiacenza, l' implementazione è quella. DIce il costo per eliminare gli archi uscenti di un vertice v, quindi secondo me prima devo trovare nella matrice, nella prima colonna per intenderci questo v, e poi scorro a destra per vedere quali sono gli archi uscenti....quindi dovrebbe essere [tex]O(V+E)[/tex]
Il grafo che ho considerato, sperando di non sbagliare è:
http://imageshack.us/photo/my-images/84/grafo.jpg/
@apatriarca:
per puro interesse, mi piacerebbe sapere se quanto scrissi sull'ordinamento topologico è valido o meno. Quando puoi mi risponderesti
per puro interesse, mi piacerebbe sapere se quanto scrissi sull'ordinamento topologico è valido o meno. Quando puoi mi risponderesti
Immagino che tutto dipenda dal significato dell'espressione \(OT^{-1}(G)\). Se significa "leggere l'ordinamento al contrario" allora è quello che dovrei essere riuscito a dimostrare. Sarei comunque cauto nell'usare il simbolo di inverso a meno che tu non sappia che è effettivamente il simbolo usato in questo caso. Non è comunque il mio campo di studi per cui è il risultato al quale sono pervenuto e dovrebbe essere corretto, ma non ho idea dove e se sia possibile trovare questa proposizione su un qualche libro. Ma l'idea di riutilizzare l'ordinamento non è del tutto campata in aria e doveva esserci un simile legame per questioni di "dualità"*.
* La dualità (in tutti i suoi significati) è probabilmente uno dei più potenti strumenti nelle mani dei matematici. Anche se probabilmente non è particolarmente utile per un informatico.
* La dualità (in tutti i suoi significati) è probabilmente uno dei più potenti strumenti nelle mani dei matematici. Anche se probabilmente non è particolarmente utile per un informatico.
@apatriarca:
perfetto, ti ringrazio della risposta
diciamo "abuso di notazione",
non vedo ambiguità, comunque hai ragione
ah la dualità, la ho incontrata alcune volte. Ma solo nello studio della programmazione lineare e del flusso minimo, ne ho potuto vedere la terminologia in modo più esteso. Non potrei comprenderne la "potenza" oltre questi due campi di problemi. Anche se in questo caso se parli di dualità riesco a vederne l'utilizzo
perfetto, ti ringrazio della risposta
"apatriarca":
Immagino che tutto dipenda dal significato dell'espressione \(OT^{-1}(G)\). Se significa "leggere l'ordinamento al contrario" allora è quello che dovrei essere riuscito a dimostrare. Sarei comunque cauto nell'usare il simbolo di inverso a meno che tu non sappia che è effettivamente il simbolo usato in questo caso.
diciamo "abuso di notazione",
non vedo ambiguità, comunque hai ragione
Non è comunque il mio campo di studi per cui è il risultato al quale sono pervenuto e dovrebbe essere corretto, ma non ho idea dove e se sia possibile trovare questa proposizione su un qualche libro. Ma l'idea di riutilizzare l'ordinamento non è del tutto campata in aria e doveva esserci un simile legame per questioni di "dualità"*.
* La dualità (in tutti i suoi significati) è probabilmente uno dei più potenti strumenti nelle mani dei matematici. Anche se probabilmente non è particolarmente utile per un informatico.
ah la dualità, la ho incontrata alcune volte. Ma solo nello studio della programmazione lineare e del flusso minimo, ne ho potuto vedere la terminologia in modo più esteso. Non potrei comprenderne la "potenza" oltre questi due campi di problemi. Anche se in questo caso se parli di dualità riesco a vederne l'utilizzo
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo