Scheda di esercizi di Algoritmi e complessità con soluzioni

Quale notazione descrive un limite inferiore alla crescita?

1. Ao (o piccolo)
2. BΩ (Omega grande)
3. CO (O grande)
4. DΘ (Theta grande)

Un algoritmo con due cicli annidati, ciascuno eseguito n volte, ha tipicamente quale complessità?

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

Un problema si dice di solito trattabile se:

1. ANon ha soluzione
2. BPuò essere risolto solo provando ogni possibilità
3. CPuò essere risolto in tempo costante
4. DPuò essere risolto in tempo polinomiale

Che cosa misura l'analisi ammortizzata?

1. AIl costo di un algoritmo sull'input migliore
2. BIl costo della singola operazione più costosa in un punto qualsiasi della sequenza
3. CIl costo medio per operazione su una sequenza di operazioni nel caso peggiore
4. DIl costo atteso su input casuali

Un algoritmo greedy (goloso):

1. AFornisce sempre la soluzione ottima
2. BUsa solo la ricorsione
3. CCompie la scelta localmente migliore a ogni passo
4. DProva ogni soluzione possibile

Quanto spazio di stack usa una semplice funzione fattoriale ricorsiva fact(n) = n × fact(n − 1)?

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

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

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

Che cosa seguirebbe se qualcuno trovasse un algoritmo in tempo polinomiale per un problema NP-completo?

1. AIl problema della fermata diventerebbe decidibile
2. BTutti gli algoritmi a tempo esponenziale diventerebbero subito lineari
3. COgni problema in NP si potrebbe risolvere in tempo polinomiale, quindi P = NP
4. DSolo quel problema passerebbe in P