Scheda di esercizi di Algoritmi e complessità con soluzioni

Quale di queste cresce più lentamente quando n diventa grande?

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

Un ciclo parte con i = 1 e raddoppia i a ogni iterazione finché i > n. Quante iterazioni esegue?

1. ACirca n / 2
2. BCirca log₂ n
3. CCirca n
4. DCirca n²

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

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

Qual è la complessità temporale di: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

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

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

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

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

Un problema è NP-completo se:

1. AÈ al di fuori di NP ma più difficile di tutti i problemi NP, come il problema della fermata
2. BÈ risolvibile in tempo polinomiale
3. CÈ impossibile da risolvere
4. DAppartiene a NP e ogni problema NP si riduce a esso in tempo polinomiale

Come si classifica il problema del commesso viaggiatore?

1. ALa versione decisionale è NP-completa e la versione di ottimizzazione è NP-difficile
2. BÈ in P perché l'algoritmo di Dijkstra lo risolve visitando ogni città una sola volta
3. CLa versione decisionale è in P ma quella di ottimizzazione è NP-completa
4. DÈ indecidibile