Scheda di esercizi di Algoritmi e complessità con soluzioni

Un problema si dice di solito trattabile se:

1. APuò essere risolto solo provando ogni possibilità
2. BNon ha soluzione
3. CPuò essere risolto in tempo costante
4. DPuò essere risolto in tempo polinomiale

Quale strategia di progettazione usa il merge sort?

1. ADivide et impera
2. BScelta greedy (golosa)
3. CForza bruta
4. DProgrammazione dinamica

Che cosa significa f(n) = Θ(g(n))?

1. Af cresce strettamente più velocemente di g
2. Bf cresce strettamente più lentamente di g
3. Cf cresce allo stesso ritmo di g, limitata superiormente e inferiormente da multipli costanti di g
4. Df è sempre minore di g per ogni n, quindi g la limita superiormente ma mai inferiormente

Ordini una volta un array di n elementi e poi rispondi a k query di appartenenza con la ricerca binaria. Qual è il costo totale?

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

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²)

È 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. BSì, ma solo se n è minore di 100
3. CNo, perché per n grande n³ è minore di n²
4. DSì, perché l'O grande è un limite superiore e n² non cresce più velocemente di n³

Perché qualsiasi ricerca basata su confronti in un array ordinato richiede Ω(log n) confronti nel caso peggiore?

1. ALa ricerca binaria è l'unico algoritmo possibile e richiede log₂ n confronti
2. BOgni confronto richiede un tempo logaritmico
3. COgni elemento deve essere confrontato almeno una volta
4. DUn albero di decisione con n esiti possibili deve avere profondità almeno log₂ n

Il problema della fermata dimostra che:

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