Scheda di esercizi di Algoritmi e complessità con soluzioni

Che cos'è la memoizzazione?

1. AConvertire automaticamente la ricorsione in un ciclo equivalente così da non avere bisogno dello stack delle chiamate
2. BMemorizzare i risultati delle chiamate di funzione così che le chiamate ripetute ottengano la risposta dalla memoria
3. CScrivere commenti accanto a ogni riga di codice
4. DLiberare la memoria dopo il ritorno di una funzione

Quanto vale log₂ 1024?

1. A32
2. B512
3. C10
4. D12

Un algoritmo O(n) impiega 3 secondi per n = 1 milione. Circa quanto impiega per n = 2 milioni?

1. A9 secondi
2. B3 secondi
3. C12 secondi
4. D6 secondi

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

1. ALineare
2. BEsponenziale
3. CCostante
4. DLogaritmica

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

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

La programmazione dinamica è utile quando un problema presenta:

1. ANessun sottoproblema, quindi si risolve in un solo passo
2. BSolo input casuali
3. CUn unico ciclo
4. DSottoproblemi sovrapposti e sottostruttura ottima

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. COgni confronto richiede un tempo logaritmico
4. DLa ricerca binaria è l'unico algoritmo possibile e richiede log₂ n confronti

Quale definizione della classe P è corretta?

1. AProblemi che si possono risolvere in parallelo
2. BProblemi che richiedono tempo esponenziale su ogni computer
3. CProblemi le cui soluzioni si possono verificare ma mai trovare in tempo polinomiale
4. DProblemi decisionali risolvibili da un algoritmo deterministico in tempo polinomiale