Scheda di esercizi di Algoritmi e complessità con soluzioni

Un problema si dice di solito trattabile se:

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

Quale strategia di progettazione usa il merge sort?

1. AForza bruta
2. BScelta greedy (golosa)
3. CProgrammazione dinamica
4. DDivide et impera

Che cosa significa che un'operazione ha tempo O(1)?

1. APuò essere eseguita una sola volta
2. BRichiede sempre esattamente un secondo
3. CIl suo tempo di esecuzione non cresce con la dimensione dell'input
4. DElabora esattamente un elemento per ogni secondo di tempo di esecuzione

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

1. ALineare
2. BLogaritmica
3. CCostante
4. DEsponenziale

La visita in ampiezza (BFS) su un grafo non pesato trova:

1. AI cammini minimi in grafi che contengono archi con peso negativo
2. BI cammini minimi in numero di archi dal nodo di partenza
3. CL'albero ricoprente minimo
4. DUn ordinamento topologico in tutti i grafi

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

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

La moltiplicazione di Karatsuba soddisfa T(n) = 3T(n/2) + O(n). Qual è la soluzione?

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

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