- 1. La teoria della complessità computazionale è una branca dell'informatica teorica che si concentra sulla classificazione dei problemi computazionali in base alla loro difficoltà intrinseca e alla quantità di risorse richieste, come tempo e spazio. Si occupa di comprendere l'efficienza degli algoritmi, di analizzare la fattibilità della risoluzione dei problemi su diversi tipi di macchine e di determinare i limiti della potenza di calcolo. Studiando la teoria della complessità computazionale, i ricercatori cercano di indagare i confini della computazione e di identificare le capacità e i limiti dei computer nel risolvere vari tipi di problemi.
Su cosa si concentra la teoria della complessità computazionale?
A) Progettazione hardware per computer
B) Sviluppo di nuovi linguaggi di programmazione
C) Analizzare le risorse necessarie per risolvere i problemi computazionali.
D) Aspetti psicologici dell'interazione uomo-computer
- 2. Quale notazione è comunemente usata per indicare la complessità degli algoritmi?
A) Numeri romani
B) Notazione Big O
C) Codice binario
D) Lettere greche
- 3. Quale classe di complessità contiene problemi decisionali che sono verificabili in modo efficiente?
A) BPP
B) NP
C) PSPACE
D) EXP
- 4. Che cosa significa "EXP" nella teoria della complessità computazionale?
A) Espanso
B) Esplorativo
C) Tempo esponenziale
D) Esperto
- 5. Qual è la classe di complessità che rappresenta i problemi più difficili in NP?
A) NP-completo
B) P
C) BPP
D) TEMPO SPERIMENTALE
- 6. Qual è l'obiettivo principale della teoria della complessità computazionale?
A) Creare computer più veloci
B) Per generare numeri casuali
C) Costruire supercomputer
D) Classificare i problemi computazionali in base alla loro difficoltà intrinseca.
- 7. A cosa si riferisce il teorema di Cook-Levin nella teoria della complessità computazionale?
A) NP-completezza
B) Calcolo parallelo
C) Problema P vs NP
D) Algoritmi quantistici
- 8. Quale classe di complessità viene utilizzata per classificare i problemi che possono essere risolti da un computer quantistico in tempo polinomiale?
A) BQP
B) SPAZIO
C) PSPACE
D) NP-completo
|