Scheda di esercizi di Algoritmi e complessità con soluzioni

Qual è la complessità temporale della ricerca lineare in un array non ordinato di n elementi (caso peggiore)?

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

La complessità spaziale misura:

1. ALa quantità di memoria di cui un algoritmo ha bisogno al crescere dell'input
2. BLe dimensioni fisiche del computer
3. CIl numero di righe di codice
4. DLo spazio su disco del file del programma una volta compilato

Qual è la complessità temporale nel caso peggiore dell'insertion sort?

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

Che cosa misura l'analisi ammortizzata?

1. AIl costo atteso su input casuali
2. BIl costo di un algoritmo sull'input migliore
3. CIl costo della singola operazione più costosa in un punto qualsiasi della sequenza
4. DIl costo medio per operazione su una sequenza di operazioni nel caso peggiore

Qual è la complessità temporale ammortizzata dell'aggiunta in coda a un array dinamico che raddoppia la capacità quando è pieno?

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

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

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

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

1. ARidurre in tempo polinomiale un problema NP-difficile noto a X
2. BDimostrare che X non ha un algoritmo polinomiale per input piccoli
3. CDimostrare che X si può verificare in tempo polinomiale
4. DRidurre in tempo polinomiale X a un problema NP-difficile noto

Quale definizione della classe P è corretta?

1. AProblemi le cui soluzioni si possono verificare ma mai trovare in tempo polinomiale
2. BProblemi che si possono risolvere in parallelo
3. CProblemi che richiedono tempo esponenziale su ogni computer
4. DProblemi decisionali risolvibili da un algoritmo deterministico in tempo polinomiale