Scheda di esercizi di Algoritmi e complessità con soluzioni

Che cos'è un algoritmo?

1. AUna sequenza finita di passi ben definiti che risolve un problema
2. BUn linguaggio di programmazione progettato per scrivere formule matematiche
3. CQualsiasi programma con un'interfaccia grafica
4. DUna struttura dati che memorizza numeri

Come funziona il selection sort?

1. AInserisce ogni elemento in una parte ordinata crescente spostando gli altri
2. BScambia ripetutamente elementi adiacenti che sono nell'ordine sbagliato
3. CTrova ripetutamente il minimo della parte non ordinata e lo scambia portandolo in testa
4. DDivide l'array a metà e le fonde

Quali sono i tre passi di un algoritmo divide et impera?

1. ALeggi, calcola, scrivi
2. BOrdina, cerca, restituisci
3. CIndovina, verifica, ripeti
4. DDividi, risolvi (impera), combina

Che cosa calcola l'algoritmo di Floyd–Warshall, e con quale velocità?

1. AI cammini minimi da un vertice sorgente a tutti gli altri in O(V + E)
2. BI cammini minimi tra tutte le coppie di vertici in O(V³)
3. CUn albero ricoprente minimo in O(E log V)
4. DUn ordinamento topologico in O(V²)

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

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

Qual è la complessità temporale dell'algoritmo di Bellman–Ford su un grafo con V vertici ed E archi?

1. AO(V × E)
2. BO(V³ × E)
3. CO(V + E)
4. DO(E log V)

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

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

Un problema è NP-completo se:

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