[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
La ragione della mia domanda sull'uso di strutture ulteriori riguarda l'ovvia possibilità di memorizzare i valori da qualche parte in modo da contarli.
Avevo capito infatti, e visto che è generico come potrei procedere?
Vorrei postare qui alcune domande per capire se effettivamente ho risposto in modo corretto.
1) se un problema P ha complessità intrinseca teta(n^2) allora esiste almeno un algoritmo risolutore di P che ha complessità teta(n). RISPOSTA: falso
2) se una funzione f=O(n) allora è anche teta(n^2) RISPOSTA: falso
3) l'inserimento di un elemento in un heap ha complessità temporale teta(1) nel caso migliore RISPOSTA: vero
4) la funzione f(n)=nlogn è O(n^2) RISPOSTA: falso
Grazie!
1) se un problema P ha complessità intrinseca teta(n^2) allora esiste almeno un algoritmo risolutore di P che ha complessità teta(n). RISPOSTA: falso
2) se una funzione f=O(n) allora è anche teta(n^2) RISPOSTA: falso
3) l'inserimento di un elemento in un heap ha complessità temporale teta(1) nel caso migliore RISPOSTA: vero
4) la funzione f(n)=nlogn è O(n^2) RISPOSTA: falso
Grazie!
1. La proposizione è falsa in quanto \(f(n) \in \Theta(n^2)\) significa che \(f(n)\) è limitata sia superiormente che inferiormente da \(n^2\) (a meno di qualche costante). Ogni algoritmo risolutore avrà quindi complessità \(\Theta(n^2)\).
2. La proposizione è falsa per ragioni del tutto analoghe a quella precedente. In particolare \(O(n)\) è un limite superiore e \(\Theta(n^2)\) è anche un limite inferiore.
3. Corretto. In effetti la complessità è costante anche nel caso medio.
4. Questa proposizione è vera. È infatti vero che esistono \(k > 0\) e \( n_0 \in \mathbb{N} \) per cui \( n\,\log\,n \leq k\,n^2 \) per ogni \( n > n_0. \) Puoi in effetti prendere per esempio \(k = 1\) e \(n_0 = 2.\)
2. La proposizione è falsa per ragioni del tutto analoghe a quella precedente. In particolare \(O(n)\) è un limite superiore e \(\Theta(n^2)\) è anche un limite inferiore.
3. Corretto. In effetti la complessità è costante anche nel caso medio.
4. Questa proposizione è vera. È infatti vero che esistono \(k > 0\) e \( n_0 \in \mathbb{N} \) per cui \( n\,\log\,n \leq k\,n^2 \) per ogni \( n > n_0. \) Puoi in effetti prendere per esempio \(k = 1\) e \(n_0 = 2.\)
Tendenzialmente l'idea per l'altro problema è di usare una seconda funzione ricorsiva che prende l'albero e una mappa (l'implementazione non ha importanza) e riempie la mappa con il numero di occorrenze dei valori trovati nell'albero. Per implementare questa funzione è sufficiente incrementare il valore contenuto nella mappa per il valore del nodo corrente e poi lanciare la funzione ricorsivamente sui figli.
Un'altra soluzione può essere di fare una visita dell'albero (non importa quale) e scrivere i valori in un array. Puoi quindi a questo punto riordinare tutto e confrontare valori consecutivi di questo array ordinato per contare le occorrenze.
Un'altra soluzione può essere di fare una visita dell'albero (non importa quale) e scrivere i valori in un array. Puoi quindi a questo punto riordinare tutto e confrontare valori consecutivi di questo array ordinato per contare le occorrenze.
Grazie mille, credo che proverò ad utilizzare il secondo metodo che mi hai consigliato.
Posto altre domande perché ho dei dubbi :
1. un albero binario è bilanciato se la differenza tra l'altezza del sotto albero sinistro della radice e l'altezza del sotto albero destro della radice è minore o uguale a 1. RISPOSTA vero
2. In un grado non orientato è connesso con n nodi ed n-1 archi, il numero di componenti connesse è uguale ad n. RISPOSTA: so che il numero di componenti connesse dovrebbe essere n-m quindi mi verrebbe da dire che la risposta è sbagliata e che sarebbe uguale a 1.
3. Un albero binario è completo se è solo se per tutti i nodi x la differenza fra l'altezza del sotto albero sinistro di x e l'altezza del sotto albero destro di x è minore o uguale a 1. RISPOSTA falso
4. Un grafo orientato è debolmente connesso se sostituendo tutti gli archi diretti con archi indiretti si ottiene un grafo connesso. RISPOSTA: falso
5. Se un problema P ha complessità intrinseca omega(n^2) allora esiste almeno un algoritmo risolutore di P che ha complessità omega(n). RISPOSTA
6. Se una funzione f(n)=O(n) allora è anche omega(n^2). RISPOSTA: falso
1. un albero binario è bilanciato se la differenza tra l'altezza del sotto albero sinistro della radice e l'altezza del sotto albero destro della radice è minore o uguale a 1. RISPOSTA vero
2. In un grado non orientato è connesso con n nodi ed n-1 archi, il numero di componenti connesse è uguale ad n. RISPOSTA: so che il numero di componenti connesse dovrebbe essere n-m quindi mi verrebbe da dire che la risposta è sbagliata e che sarebbe uguale a 1.
3. Un albero binario è completo se è solo se per tutti i nodi x la differenza fra l'altezza del sotto albero sinistro di x e l'altezza del sotto albero destro di x è minore o uguale a 1. RISPOSTA falso
4. Un grafo orientato è debolmente connesso se sostituendo tutti gli archi diretti con archi indiretti si ottiene un grafo connesso. RISPOSTA: falso
5. Se un problema P ha complessità intrinseca omega(n^2) allora esiste almeno un algoritmo risolutore di P che ha complessità omega(n). RISPOSTA
6. Se una funzione f(n)=O(n) allora è anche omega(n^2). RISPOSTA: falso
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo