Scheda di esercizi di Algoritmi e complessità con soluzioni

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

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

Come funziona il selection sort?

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

Quale notazione descrive un limite inferiore alla crescita?

1. AΘ (Theta grande)
2. BO (O grande)
3. Co (o piccolo)
4. DΩ (Omega grande)

Quale algoritmo trova i cammini minimi da una sorgente in un grafo con pesi degli archi non negativi?

1. ABellman-Ford è necessario in tutti i casi
2. BAlgoritmo di Kruskal
3. CVisita in profondità (DFS)
4. DAlgoritmo di Dijkstra

Qual è la complessità temporale della moltiplicazione di due matrici n × n con il triplo ciclo standard?

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

Il limite inferiore per l'ordinamento basato su confronti nel caso peggiore è:

1. AΩ(n)
2. BΩ(n log n)
3. CΩ(n²)
4. DΩ(log n)

Quali due cose bisogna dimostrare per provare che un problema decisionale X è NP-completo?

1. AX si riduce a un problema in P, e X è in NP
2. BX non ha un algoritmo polinomiale, e X è decidibile
3. CX è in NP, e un problema NP-completo noto si riduce a X in tempo polinomiale
4. DX è in P, e X si riduce a SAT

Come si classifica il problema del commesso viaggiatore?

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