Scheda di esercizi di Algoritmi e complessità con soluzioni

Quale di questi tempi di esecuzione è polinomiale?

1. AO(2ⁿ)
2. BO(n!)
3. CO(nⁿ)
4. DO(n³)

Che cos'è un algoritmo?

1. AUn linguaggio di programmazione progettato per scrivere formule matematiche
2. BUna sequenza finita di passi ben definiti che risolve un problema
3. CUna struttura dati che memorizza numeri
4. DQualsiasi programma con un'interfaccia grafica

Quale notazione descrive un limite superiore della crescita?

1. AOmega piccolo (little omega)
2. BOmega grande (Big Omega)
3. CTheta grande (Big Theta)
4. DO grande (Big O)

Qual è la soluzione della ricorrenza T(n) = T(n − 1) + O(1)?

1. AO(n)
2. BO(log n)
3. CO(2ⁿ)
4. DO(n²)

Qual è la soluzione della ricorrenza T(n) = 2T(n/2) + O(1)?

1. AO(n²)
2. BO(log n)
3. CO(n)
4. DO(n log n)

In un array ordinato cerchi due elementi la cui somma sia un valore dato muovendo un puntatore da ciascuna estremità verso l'interno. Qual è la complessità temporale?

1. AO(log n)
2. BO(n²)
3. CO(n log n)
4. DO(n)

Perché qualsiasi ricerca basata su confronti in un array ordinato richiede Ω(log n) confronti nel caso peggiore?

1. AOgni elemento deve essere confrontato almeno una volta
2. BUn albero di decisione con n esiti possibili deve avere profondità almeno log₂ n
3. CLa ricerca binaria è l'unico algoritmo possibile e richiede log₂ n confronti
4. DOgni confronto richiede un tempo logaritmico

Qual è la differenza tra un problema indecidibile e uno intrattabile?

1. AI problemi indecidibili sono in NP, mentre quelli intrattabili sono in P
2. BEntrambi significano che il problema non ha alcun algoritmo
3. CPer un problema indecidibile non esiste alcun algoritmo valido per tutti gli input; uno intrattabile ne ha uno, ma è troppo lento
4. DI problemi intrattabili non si possono risolvere con alcun algoritmo, mentre quelli indecidibili richiedono solo tempo esponenziale