Scheda di esercizi di Algoritmi e complessità con soluzioni

Che cos'è un algoritmo?

1. AQualsiasi programma con un'interfaccia grafica
2. BUna sequenza finita di passi ben definiti che risolve un problema
3. CUna struttura dati che memorizza numeri
4. DUn linguaggio di programmazione progettato per scrivere formule matematiche

Che cosa descrive il tempo di esecuzione nel caso peggiore di un algoritmo?

1. AIl tempo impiegato su un computer lento
2. BIl tempo atteso su un input casuale di dimensione n
3. CIl tempo impiegato sull'input più piccolo
4. DIl tempo massimo impiegato su tutti gli input di dimensione n

Qual è la complessità temporale per trovare il valore massimo in un array non ordinato di n numeri?

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

Perché nell'O grande la base del logaritmo di solito si omette, come in O(log n)?

1. ALa base conta solo per n piccolo
2. BI logaritmi sono sempre arrotondati a interi
3. CTutti i logaritmi in informatica hanno base 10, quindi è sottintesa
4. DLogaritmi con basi diverse differiscono solo per un fattore costante

In un array ordinato cerchi due elementi la cui somma sia un valore dato muovendo un puntatore da ciascuna estremità verso l'interno. Qual è la complessità temporale?

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

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

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

Quale affermazione sulla notazione o piccolo è corretta?

1. An = o(n), perché ogni funzione è o piccolo di se stessa
2. B2n = o(n), perché 2n cresce lentamente
3. Cn² = o(n)
4. Dn = o(n²), ma n non è o(n)

Qual è la differenza tra un problema indecidibile e uno intrattabile?

1. AI problemi intrattabili non si possono risolvere con alcun algoritmo, mentre quelli indecidibili richiedono solo tempo esponenziale
2. BEntrambi significano che il problema non ha alcun algoritmo
3. CPer un problema indecidibile non esiste alcun algoritmo valido per tutti gli input; uno intrattabile ne ha uno, ma è troppo lento
4. DI problemi indecidibili sono in NP, mentre quelli intrattabili sono in P