[Algoritmi] Domande Vero o Falso
Ciao a tutti, siccome, a breve, dovrei sostenere l'esame di algoritmi e in giro non si trova neanche un frammento di appello svolto, avrei pensato di postare una parte di un esercizio dell'esame composto da domande V o F.
Allora io avrei pensato di scrivere le domande, fornire e spiegare la risposta e magari discuterne in caso una risposta, secondo voi sia sbagliata.
Le risposte le copro in modo che se c'è qualcuno che vuole provare a farle per conto suo e libero di non essere influenzato.
1) La complessità (temporale) intrinseca del problema di calcolare la somma di un array di interi è \(\displaystyle \Omega(n) \), dove \(\displaystyle n \) è il numero di interi presenti nel array.
2) La complessità temporale del problema dell’inserimento in una array ordinato di interi è \(\displaystyle \Omega(log(n)) \).
3) La funzione \(\displaystyle f(n) \) = \(\displaystyle 2n log(n^2) \) è \(\displaystyle O(n log(n)) \).
4) Sia G un grafo non orientato che contiene almeno un ciclo. Il numero di componenti connesse massimali è minore o uguale a n-2, dove n è il numero di nodi di G
5) Sia G un grafo pesato connesso, orientato, ed aciclico i cui pesi sono numeri positivi. l’algoritmo di Floyd potrebbe non essere in grado di calcolare le distanze minime fra tutte le coppie di nodi di G.
6)La complessità dell’inserimento di un elemento in una tabella hash in cui sono presenti n elementi nel caso peggiore è \(\displaystyle \Theta(n) \).
7) La complessità spaziale della visita infissa di un albero è \(\displaystyle \Omega(n^2) \), dove \(\displaystyle n \) è il numero di nodi presenti nell’albero.
8) La complessità temporale dell’algoritmo di Dijkstra è \(\displaystyle \Theta(n^2) \), dove \(\displaystyle n \) è il numero di nodi presenti nel grafo, nel caso di rappresentazione con liste di adiacenza.
9) Per ogni coppia di nodi u,v appartenenti ad un grafo orientato debolmente connesso esiste sempre un cammino dal nodo u al nodo v e dal nodo v al nodo u.
10) Un grafo non orientato connesso e pesato (sugli archi) ammette sempre un unico albero ricoprenti di costo minimo.
Allora io avrei pensato di scrivere le domande, fornire e spiegare la risposta e magari discuterne in caso una risposta, secondo voi sia sbagliata.
Le risposte le copro in modo che se c'è qualcuno che vuole provare a farle per conto suo e libero di non essere influenzato.
1) La complessità (temporale) intrinseca del problema di calcolare la somma di un array di interi è \(\displaystyle \Omega(n) \), dove \(\displaystyle n \) è il numero di interi presenti nel array.
2) La complessità temporale del problema dell’inserimento in una array ordinato di interi è \(\displaystyle \Omega(log(n)) \).
3) La funzione \(\displaystyle f(n) \) = \(\displaystyle 2n log(n^2) \) è \(\displaystyle O(n log(n)) \).
4) Sia G un grafo non orientato che contiene almeno un ciclo. Il numero di componenti connesse massimali è minore o uguale a n-2, dove n è il numero di nodi di G
5) Sia G un grafo pesato connesso, orientato, ed aciclico i cui pesi sono numeri positivi. l’algoritmo di Floyd potrebbe non essere in grado di calcolare le distanze minime fra tutte le coppie di nodi di G.
6)La complessità dell’inserimento di un elemento in una tabella hash in cui sono presenti n elementi nel caso peggiore è \(\displaystyle \Theta(n) \).
7) La complessità spaziale della visita infissa di un albero è \(\displaystyle \Omega(n^2) \), dove \(\displaystyle n \) è il numero di nodi presenti nell’albero.
8) La complessità temporale dell’algoritmo di Dijkstra è \(\displaystyle \Theta(n^2) \), dove \(\displaystyle n \) è il numero di nodi presenti nel grafo, nel caso di rappresentazione con liste di adiacenza.
9) Per ogni coppia di nodi u,v appartenenti ad un grafo orientato debolmente connesso esiste sempre un cammino dal nodo u al nodo v e dal nodo v al nodo u.
10) Un grafo non orientato connesso e pesato (sugli archi) ammette sempre un unico albero ricoprenti di costo minimo.
Risposte
Ciao xneo 
Direi che hai fatto un buon lavoro e mi sembra un modo utile per prepararsi all'esame. In alcuni casi (in domande di questo genere) si può fornire un controesempio per avere una risposta immediata in altri invece serve un minimo di dimostrazione.
Direi che hai fatto un buon lavoro e mi sembra un modo utile per prepararsi all'esame. In alcuni casi (in domande di questo genere) si può fornire un controesempio per avere una risposta immediata in altri invece serve un minimo di dimostrazione.
grazie, avrei scommesso che la prima risposta fosse stata la tua 
Sempre utile.
Sempre utile.
E ti pareva che ti aspettassi la mia risposta 
. A noi comunque non hanno mai fatto nemmeno un esame con le domande vero/falso o a risposta multipla quindi, seppur si debba studiare tanto in ogni caso, secondo me potete ritenervi fortunati in un certo senso.
. A noi comunque non hanno mai fatto nemmeno un esame con le domande vero/falso o a risposta multipla quindi, seppur si debba studiare tanto in ogni caso, secondo me potete ritenervi fortunati in un certo senso.
Comunque l'esame non è composto solo da domande vero o falso, c'è anche un esercizio di programmazione con relativo calcolo della complessità temporale e spaziale nel caso peggiore e migliore e una domanda di teoria.
Inoltre molte domande vero o falso sono a trabocchetto e se sbagli vengono tolti dei punti.
Ora, siccome sei stato più utile del mio prof, posso ritenermi fortunato se riesce a filare tutto liscio all'esame.
Inoltre molte domande vero o falso sono a trabocchetto e se sbagli vengono tolti dei punti.
Ora, siccome sei stato più utile del mio prof, posso ritenermi fortunato se riesce a filare tutto liscio all'esame.
ciao, sto studiando il tuo stesso esame...tu lo hai fatto a settembre??
Ciao, sto preparando lo stesso esame e ho una domanda:
Esiste un algoritmo avente complessità spaziale teta(n) e complessità temporale teta(log(n))? n è la dimensione del input.
Io risponderei farlo perché mi viene in mente l algoritmo di ricerca binaria che ha una complessità temporale log(n) ma ma spaziale non è teta(n).
Grazie
Esiste un algoritmo avente complessità spaziale teta(n) e complessità temporale teta(log(n))? n è la dimensione del input.
Io risponderei farlo perché mi viene in mente l algoritmo di ricerca binaria che ha una complessità temporale log(n) ma ma spaziale non è teta(n).
Grazie
La prima risposta, nel caso parallelo non è precisa, seppur il professore probabilmente non volesse chiedere questo aspetto. La tua risposta è corretta se si suppone che il numero di processi paralleli sia fissato (e uguale a due). Supponi invece di averne infiniti e che ogni processore valuti una somma per unità temporale. Allora ad ogni passo ti trovi a dover calcolare la somma di un array che possiede la metà degli elementi. In totale quindi, in presenza di infiniti processori, puoi fare la somma in tempo logaritmico.
Quindi se suppongo che i processi paralleli siano fissati non esiste un algoritmo con complessità spaziale e temporale definita in quel modo?
Non ho capito la tua domanda, ma provo a darti una spiegazione di quello che puoi fare con processi paralleli. Consideriamo i valori con indici pari e quelli con indici dispari del nostro array. Se li sommiamo a coppie avremo un array di somme di lunghezza \(N/2\). Ripetendo il procedimento avremo un algoritmo che calcola la somma dell'array in \(\log_2 n\) passi \(p\) di costo \( N\,2^{-p}. \) Con un singolo processore la complessità è \(O(N).\) Se abbiamo \(K\) processori possiamo suddividere il costo di ogni step di \(K\) e quindi ottenere un costo \(K\) volte inferiore a quello originario (ma la complessità è comunque ancora lineare). Per ottenere una complessità diverse è necessario ricorrere ad un numero illimitato di processi paralleli in modo da ridurre il costo di ogni passo ad una costante e quindi avere una complessità logaritmica.
Mi riferivo alla discussione iniziale. Riguardo alla tua domanda dipende se consideri la dimensione del l'input incluso o meno nella complessità spaziale. Se lo è, allora qualsiasi algoritmo logaritmico su un array ne è un esempio. Altrimenti non è possibile: un qualsiasi algoritmo può produrre dati addizionali per step non maggiori di un multiplo costante del numero dei processi.
L'unico punto su cui non sono d'accordo è il seguente:
6. L'inserimento in una tabella di hash può avere costo lineare se tutti gli elementi inseriti sono stati mappati allo stesso valore di hash. Si tratta di un rischio (e attacco) reale in sistemi che fanno ricorso a tabelle di hash.
6. L'inserimento in una tabella di hash può avere costo lineare se tutti gli elementi inseriti sono stati mappati allo stesso valore di hash. Si tratta di un rischio (e attacco) reale in sistemi che fanno ricorso a tabelle di hash.
Vorrei fare una domanda: come faccio a calcolare il numero di occorrenze in un albero binario? In modo ricorsivo.
Verifico il caso base quindi se l'albero è vuoto restituisco zero, e anche se lo sono i sotto alberi sinistro r destro.
Poi dovrei effettuare il controllo, ma non riesco proprio in questo passaggio!
Verifico il caso base quindi se l'albero è vuoto restituisco zero, e anche se lo sono i sotto alberi sinistro r destro.
Poi dovrei effettuare il controllo, ma non riesco proprio in questo passaggio!
Con numero di occorrenze intendi il numero di volte che un particolare valore è presente nell'albero? Se è questo alla la risposta è uguale al numero di occorrenze nei figli più 1 se il nodo ha quel valore o zero altrimenti. Chiedevi questo?
e come faccio a calcolare le occorrenze nei figli?
Chiamando la funzione ricorsivamente sui due figli.
Allora se ho questo algoritmo
int contaRipetuti( AlberoB a){
If (a==null) return 0;
If(a.sin()==null && a.des()==null) return 0;
E poi? Se richiamo un altro metodo come verifico se due valori sono uguali? Cioè dovrei scrivere a.sin()==a.des() ?
int contaRipetuti( AlberoB a){
If (a==null) return 0;
If(a.sin()==null && a.des()==null) return 0;
E poi? Se richiamo un altro metodo come verifico se due valori sono uguali? Cioè dovrei scrivere a.sin()==a.des() ?
Ma come sono definiti i nodi del tuo albero? Cosa intendi dire con conteggio delle occorrenze esattamente? Quali dovrebbero essere gli input e gli output?
Mi chiede di implementare il metodo "int contaOccorrenze(Albero Binario a)" che restituisce il numero di valori che appaiono almeno due volte in a.
Ok, pensavo che il problema fosse un altro. L'albero binario è generico o contiene i valori ordinati (tipo in un albero di ricerca)? Si può fare ricorso a vettori o altre strutture dati aggiuntive?
È un albero binario generico, perché non mi dà nessun altra informazione!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo