Scheda di esercizi di Algoritmi e complessità con soluzioni

Accedere a un elemento di un array tramite indice richiede:

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

Che cosa significa f(n) = Θ(g(n))?

1. Af cresce allo stesso ritmo di g, limitata superiormente e inferiormente da multipli costanti di g
2. Bf è sempre minore di g per ogni n, quindi g la limita superiormente ma mai inferiormente
3. Cf cresce strettamente più velocemente di g
4. Df cresce strettamente più lentamente di g

Che cosa richiede la ricerca binaria al suo input?

1. AL'array deve contenere solo numeri positivi
2. BL'array non deve avere più di 1000 elementi
3. CLa lunghezza dell'array deve essere una potenza di due
4. DL'array deve essere ordinato

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

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

Qual è la complessità temporale del calcolo dell'n-esimo numero di Fibonacci con una tabella bottom-up?

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

È corretto dire che un algoritmo O(n²) è anche O(n³)?

1. ANo, perché l'O grande deve indicare sempre l'esatto tasso di crescita della funzione
2. BSì, ma solo se n è minore di 100
3. CNo, perché per n grande n³ è minore di n²
4. DSì, perché l'O grande è un limite superiore e n² non cresce più velocemente di n³

Che cosa ha stabilito il teorema di Cook–Levin?

1. AOgni problema NP si può risolvere in tempo esponenziale
2. BIl problema della fermata è indecidibile
3. CP è diverso da NP
4. DIl problema della soddisfacibilità booleana (SAT) è NP-completo

Prendere entrambi gli estremi di ogni arco di un matching massimale dà una copertura dei vertici. Quanto è buona questa copertura?

1. ADi qualità ignota rispetto all'ottimo
2. BAl massimo log n volte il minimo
3. CSempre una copertura dei vertici minima
4. DAl massimo il doppio della dimensione di una copertura dei vertici minima