Scheda di esercizi di Algoritmi e complessità con soluzioni

Quale algoritmo di ordinamento sceglie un pivot e partiziona l'array in elementi minori e maggiori?

1. AMerge sort
2. BQuicksort
3. CBubble sort
4. DInsertion sort

Un problema si dice di solito trattabile se:

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

Che cos'è un algoritmo a forza bruta?

1. AUn algoritmo che usa sempre la ricorsione
2. BUn algoritmo che gira su molti processori
3. CUn algoritmo che tira a indovinare una risposta a caso
4. DUn algoritmo che prova tutte le possibili soluzioni candidate

La ricorrenza T(n) = 2T(n/2) + O(n) ha come soluzione:

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

Perché la programmazione dinamica non dà un vero guadagno di velocità per il merge sort?

1. AI suoi sottoproblemi non si sovrappongono, quindi non c'è nulla da riutilizzare
2. BIl merge sort non ha una struttura ricorsiva
3. CIl merge sort è già O(n)
4. DLa programmazione dinamica funziona solo sui problemi su grafi, non sugli array

La complessità temporale del Fibonacci ricorsivo ingenuo (fib(n) = fib(n−1) + fib(n−2)) è:

1. ACostante
2. BLineare
3. CEsponenziale
4. DLogaritmica

L'algoritmo di Strassen moltiplica matrici usando 7 invece di 8 moltiplicazioni ricorsive di blocchi di metà dimensione. Qual è il suo tempo di esecuzione?

1. AΘ(n² log n)
2. BΘ(n²)
3. CΘ(n^{log₂ 7}), circa n^2,81
4. DΘ(n³)

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

1. ATutti gli algoritmi a tempo esponenziale diventerebbero subito lineari
2. BOgni problema in NP si potrebbe risolvere in tempo polinomiale, quindi P = NP
3. CSolo quel problema passerebbe in P
4. DIl problema della fermata diventerebbe decidibile