Scheda di esercizi di Algoritmi e complessità con soluzioni

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

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

Quale notazione descrive un limite superiore della crescita?

1. ATheta grande (Big Theta)
2. BOmega piccolo (little omega)
3. CO grande (Big O)
4. DOmega grande (Big Omega)

Che cos'è un algoritmo?

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

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

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

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

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

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

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

Prendere entrambi gli estremi di ogni arco di un matching massimale dà una copertura dei vertici. Quanto è buona questa copertura?

1. ADi qualità ignota rispetto all'ottimo
2. BAl massimo il doppio della dimensione di una copertura dei vertici minima
3. CAl massimo log n volte il minimo
4. DSempre una copertura dei vertici minima

Per dimostrare che un nuovo problema X è NP-difficile, che cosa devi fare?

1. ADimostrare che X non ha un algoritmo polinomiale per input piccoli
2. BRidurre in tempo polinomiale X a un problema NP-difficile noto
3. CRidurre in tempo polinomiale un problema NP-difficile noto a X
4. DDimostrare che X si può verificare in tempo polinomiale