Scheda di esercizi di Algoritmi e complessità con soluzioni

Un problema si dice di solito trattabile se:

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

Qual è la complessità temporale per trovare il valore massimo in un array non ordinato di n numeri?

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

Quanto vale log₂ 1024?

1. A512
2. B12
3. C32
4. D10

Qual è la complessità temporale di: for i = 1 to n: for j = 1 to i: lavoro O(1)?

1. AO(n²)
2. BO(n³)
3. CO(n log n)
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)

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

1. AEsponenziale
2. BCostante
3. CLineare
4. DLogaritmica

Per quale variante dello zaino la regola greedy "prendi gli oggetti in ordine di valore per peso" dà sempre una risposta ottima?

1. ALo zaino 0/1, in cui gli oggetti si devono prendere sempre interi
2. BLo zaino frazionario, in cui gli oggetti si possono dividere
3. CEntrambe le varianti
4. DNessuna delle due varianti

Quale di questi problemi di soddisfacibilità è noto per essere risolvibile in tempo polinomiale?

1. ALa soddisfacibilità dei circuiti
2. B2-SAT, in cui ogni clausola ha al massimo due letterali
3. C3-SAT, in cui ogni clausola ha esattamente tre letterali
4. DSAT generale su formule in forma normale congiuntiva