19 / 24
www.
edises
.it
Capitolo 1
Modelli dell’informatica
9
C. Alla deduzione
D. All’intuizione
31) Si consideri l’automa descritto dalla tabella seguente:
q 0
q 1
a
(q 0 , a)
(q 1 , b)
b (q 1 , b)
(q 0 , a)
Qual è la sequenza di simboli prodotta dall’automa in risposta alla
sequenza di ingresso “baaa”?
A. “baaa”
B. “baba”
C. “bbbb”
D. “qaqa”
32) Un algoritmo euristico:
A. porta ad una soluzione ottima per quel dato problema
B. costituisce la strategia ideale per risolvere problemi non troppo com-
plessi
C. fornisce soluzioni molto costose in termini di tempo o di capacità di ela-
borazione
D. fornisce un’alternativa quando la risoluzione del problema ottimo può
essere impossibile
33) La soluzione di un problema basato sulla definizione di un algoritmo
euristico non è consigliata quando:
A. la risoluzione del problema ottimo può essere raggiunta con complessità
computazionale logaritmica
B. la risoluzione del problema ottimo può essere impossibile
C. la risoluzione del problema ottimo può essere troppo costosa in termini
di tempo o di capacità di elaborazione
D. la risoluzione del problema ottimo può essere troppo costosa in termini
di sola capacità di elaborazione
34) Quale delle seguenti definizioni non rappresenta il concetto di
algoritmo?
A. Un algoritmo è un procedimento formato da una sequenza finita di ope-
razioni elementari che trasforma uno o più valori di ingresso in uno o più
valori di uscita