Scheda di esercizi di Algoritmi e complessità con soluzioni

Scheda di esercizi di Algoritmi e complessità gratuita e stampabile: 8 esercizi dal livello facile a quello d’esame, con le soluzioni. Stampala o salvala come PDF.

Nuova schedaEsercitati online con i suggerimenti

Per i docenti: gratuita da stampare, copiare e usare in classe. Ogni nuova scheda ha nuovi valori e le sue soluzioni. Un link a ExamProblems nella pagina del corso è molto apprezzato.

Nome: ____________________   Data: ____________

1.Facile

Che cos'è un algoritmo a forza bruta?

  1. AUn algoritmo che tira a indovinare una risposta a caso
  2. BUn algoritmo che usa sempre la ricorsione
  3. CUn algoritmo che gira su molti processori
  4. DUn algoritmo che prova tutte le possibili soluzioni candidate
2.Facile

Che cosa significa che un'operazione ha tempo O(1)?

  1. APuò essere eseguita una sola volta
  2. BElabora esattamente un elemento per ogni secondo di tempo di esecuzione
  3. CRichiede sempre esattamente un secondo
  4. DIl suo tempo di esecuzione non cresce con la dimensione dell'input
3.Facile

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

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

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

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

Qual è la complessità temporale dell'algoritmo di Bellman–Ford su un grafo con V vertici ed E archi?

  1. AO(E log V)
  2. BO(V × E)
  3. CO(V + E)
  4. DO(V³ × E)
6.Media

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

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

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
8.Difficile

Quale limite è corretto per log(n!)?

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

Soluzioni

  1. 1. D · Un algoritmo che prova tutte le possibili soluzioni candidate
  2. 2. D · Il suo tempo di esecuzione non cresce con la dimensione dell'input
  3. 3. D · Il tempo massimo impiegato su tutti gli input di dimensione n
  4. 4. A · Ω(n log n)
  5. 5. B · O(V × E)
  6. 6. A · Sì, perché l'O grande è un limite superiore e n² non cresce più velocemente di n³
  7. 7. C · Per un problema indecidibile non esiste alcun algoritmo valido per tutti gli input; uno intrattabile ne ha uno, ma è troppo lento
  8. 8. B · Θ(n log n)

Soluzioni complete passo passo: esercitati su questo argomento su examproblems.com.