Teoria della calcolabilità e complessità computazionale

Qual è il concetto chiave della macchina di Turing?

• Capacità di decriptare comunicazioni cifrate

• Capacità di scrivere su di un nastro infinito

• Capacità di eseguire un algoritmo in modo automatico e deterministico

• Capacità di pensare come un essere umano

Quali sono alcune classi di complessità computazionale?

• P, NP, NP-complete, NP-hard

• PSPACE

• EXPTIME

• LOGSPACE

In cosa consiste il problema dell'arresto?

• Nel rallentamento di una macchina a causa dell'eccessivo costo dell'algoritmo.

• Nell'impossibilità di scrivere un programma che possa determinare se un altro programma terminerà o meno.

• Nella determinazione delle condizioni di arresto di un algoritmo.

• Nella ricerca, da parte di Turing, di un algoritmo sempre valido.

Qual è la differenza tra P e NP problem?

• I problemi P possono essere risolti in tempo polinomiale, mentre i problemi NP possono solo essere verificati.

• I problemi P e NP sono equivalenti

• I problemi P richiedono più risorse rispetto ai problemi NP

• I problemi NP possono essere risolti in tempo polinomiale

Spiega il concetto di calcolo del costo di un algoritmo.

• Il calcolo del costo di un algoritmo si basa esclusivamente sul tempo di esecuzione dell'algoritmo.

• Il calcolo del costo di un algoritmo non tiene conto della dimensione dell'input.

• Il calcolo del costo di un algoritmo si riferisce alla determinazione della complessità spaziale dell'algoritmo.

• Il calcolo del costo di un algoritmo si riferisce alla determinazione del numero di passaggi o risorse necessari per eseguire l'algoritmo in relazione alla dimensione dell'input.

Come funziona la macchina di Turing?

• La macchina di Turing funziona trasformando i simboli del nastro in numeri

• La macchina di Turing funziona leggendo un simbolo dal nastro, consultando la tabella di transizione per determinare l'azione successiva fino allo stato finale.

• La macchina di Turing funziona eseguendo operazioni matematiche complesse

• La macchina di Turing funziona contando i passi eseguiti

Cosa si intende per NP-hard?

• Problemi difficili come il più difficile problema NP, ma che non sono necessariamente NP.

• Problemi più semplici di quelli di classe P.

• Problemi risolvibili in complessità logaritmica.

• Problemi risolvibiili in tempo polinomiale.

Perché il problema dell'arresto è indecidibile?

• Il problema dell'arresto è indecidibile perché dipende dal giorno della settimana in cui viene eseguito il programma.

• Il problema dell'arresto è indecidibile perché è una questione di opinione e non ha una risposta definitiva.

• Il problema dell'arresto è indecidibile perché non esiste un algoritmo che possa determinare in modo generale se un programma terminerà o meno su un input specifico.

• Il problema dell'arresto è decidibile perché esiste un algoritmo che può determinare in modo generale se un programma terminerà o meno su un input specifico.

Come si calcola la complessità di un algoritmo?

• Misurando il consumo di memoria dell'algoritmo

• Contando il tempo di esecuzione dell'algoritmo

• Considerando solo il numero di cicli for nell'algoritmo

• Valutando il numero di operazioni elementari in relazione alla dimensione dell'input

Qual è il ruolo della macchina di Turing nella teoria della calcolabilità?

• La macchina di Turing è un concetto obsoleto nella teoria della calcolabilità

• La macchina di Turing è fondamentale nella teoria della calcolabilità poiché dimostra la possibilità di risolvere qualsiasi problema computabile in modo algoritmico.

• La macchina di Turing è stata superata da modelli più avanzati nella teoria della calcolabilità

• La macchina di Turing è solo un esperimento teorico senza applicazioni pratiche