Scheda di esercizi di Algoritmi e complessità con soluzioni

Che cosa richiede la ricerca binaria al suo input?

1. ALa lunghezza dell'array deve essere una potenza di due
2. BL'array deve contenere solo numeri positivi
3. CL'array non deve avere più di 1000 elementi
4. DL'array deve essere ordinato

Quale di questi tempi di esecuzione è polinomiale?

1. AO(2ⁿ)
2. BO(nⁿ)
3. CO(n³)
4. DO(n!)

Quanto vale log₂ 1024?

1. A32
2. B512
3. C10
4. D12

È corretto dire che un algoritmo O(n²) è anche O(n³)?

1. ANo, perché l'O grande deve indicare sempre l'esatto tasso di crescita della funzione
2. BNo, perché per n grande n³ è minore di n²
3. CSì, perché l'O grande è un limite superiore e n² non cresce più velocemente di n³
4. DSì, ma solo se n è minore di 100

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(E log V)
4. DO(V³ × E)

Quanto spazio di stack usa una semplice funzione fattoriale ricorsiva fact(n) = n × fact(n − 1)?

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

Il problema della fermata dimostra che:

1. AAlcuni programmi girano più velocemente su computer più veloci, quindi la terminazione dipende dall'hardware
2. BI cicli andrebbero evitati
3. CNessun algoritmo può decidere, per ogni programma e ogni input, se il programma si ferma
4. DOgni programma prima o poi si ferma

Quale affermazione su P e NP è corretta?

1. AÈ stato dimostrato che P ≠ NP
2. BOgni problema in P appartiene anche a NP
3. CLe soluzioni dei problemi NP non possono essere verificate rapidamente
4. DNP significa «non polinomiale»