- 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) Sviluppo di nuovi linguaggi di programmazione
B) Progettazione hardware per computer
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) Notazione Big O
B) Lettere greche
C) Numeri romani
D) Codice binario
- 3. Quale classe di complessità contiene problemi decisionali che sono verificabili in modo efficiente?
A) PSPACE
B) NP
C) BPP
D) EXP
- 4. Qual è l'obiettivo principale della teoria della complessità computazionale?
A) Costruire supercomputer
B) Per generare numeri casuali
C) Creare computer più veloci
D) Classificare i problemi computazionali in base alla loro difficoltà intrinseca.
- 5. Quale classe di complessità viene utilizzata per classificare i problemi che possono essere risolti da un computer quantistico in tempo polinomiale?
A) NP-completo
B) BQP
C) PSPACE
D) SPAZIO
- 6. Qual è la classe di complessità che rappresenta i problemi più difficili in NP?
A) NP-completo
B) TEMPO SPERIMENTALE
C) BPP
D) P
- 7. Che cosa significa "EXP" nella teoria della complessità computazionale?
A) Esperto
B) Esplorativo
C) Tempo esponenziale
D) Espanso
- 8. A cosa si riferisce il teorema di Cook-Levin nella teoria della complessità computazionale?
A) Algoritmi quantistici
B) NP-completezza
C) Calcolo parallelo
D) Problema P vs NP
|