ThatQuiz Elenco di test Affronta questo test adesso
Teoria della complessità computazionale - Quiz
Con il contributo di: Mancini
  • 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) Aspetti psicologici dell'interazione uomo-computer
D) Analizzare le risorse necessarie per risolvere i problemi computazionali.
  • 2. Quale notazione è comunemente usata per indicare la complessità degli algoritmi?
A) Notazione Big O
B) Lettere greche
C) Codice binario
D) Numeri romani
  • 3. Quale classe di complessità contiene problemi decisionali che sono verificabili in modo efficiente?
A) EXP
B) NP
C) BPP
D) PSPACE
  • 4. Qual è l'obiettivo principale della teoria della complessità computazionale?
A) Classificare i problemi computazionali in base alla loro difficoltà intrinseca.
B) Creare computer più veloci
C) Costruire supercomputer
D) Per generare numeri casuali
  • 5. A cosa si riferisce il teorema di Cook-Levin nella teoria della complessità computazionale?
A) Calcolo parallelo
B) NP-completezza
C) Problema P vs NP
D) Algoritmi quantistici
  • 6. Quale classe di complessità viene utilizzata per classificare i problemi che possono essere risolti da un computer quantistico in tempo polinomiale?
A) SPAZIO
B) NP-completo
C) BQP
D) PSPACE
  • 7. Che cosa significa "EXP" nella teoria della complessità computazionale?
A) Espanso
B) Esperto
C) Tempo esponenziale
D) Esplorativo
  • 8. Qual è la classe di complessità che rappresenta i problemi più difficili in NP?
A) NP-completo
B) BPP
C) P
D) TEMPO SPERIMENTALE
  • 9. Cos'è un problema computazionale?
A) Un'equazione matematica che non può essere risolta.
B) Una domanda teorica irrisolvibile.
C) Un problema hardware nei computer.
D) Un compito risolto da un computer utilizzando un algoritmo.
  • 10. Qual è la scelta più comune per l'alfabeto quando si rappresentano istanze di problemi?
A) L'insieme di tutte le lettere minuscole
B) L'insieme dei caratteri ASCII
C) L'alfabeto esadecimale
D) L'alfabeto binario {0,1}
  • 11. Qual è un'assunzione comune nelle dimostrazioni dei teoremi della teoria della complessità?
A) Una scelta specifica e concreta della codifica degli input.
B) Non è necessaria alcuna codifica.
C) Codifica tramite linguaggio naturale.
D) Utilizzo esclusivo della notazione decimale.
  • 12. Fornire un esempio di un problema decisionale che coinvolge i grafi.
A) Determinare se un grafo dato è connesso o meno.
B) Trovare il percorso più breve in un grafo.
C) Calcolare il flusso massimo in una rete.
D) Determinare il numero di nodi in un grafo.
  • 13. Qual è un esempio di problema algoritmico?
A) Controllare se un grafo è bipartito.
B) Il problema del commesso viaggiatore.
C) Determinare se un numero è primo.
D) Verificare se due grafi sono isomorfi.
  • 14. Qual è l'unità di misura comunemente utilizzata per indicare la dimensione dell'input nella teoria della complessità computazionale?
A) Byte
B) Parole
C) Caratteri
D) Bit
  • 15. Qual è lo scopo principale di una macchina di Turing?
A) Un dispositivo per manipolare oggetti fisici.
B) Un modello teorico per la computazione generale.
C) Una tecnologia di calcolo pratica.
D) Una forma primitiva di hardware informatico.
  • 16. Quale tesi è associata all'affermazione che qualsiasi problema risolvibile tramite un algoritmo può essere risolto da una macchina di Turing?
A) Il teorema di Cook-Levin.
B) Il teorema P vs NP.
C) I teoremi di incompletezza di Gödel.
D) La tesi di Church-Turing.
  • 17. Quale tipo di macchina di Turing utilizza bit casuali per prendere decisioni?
A) Macchina di Turing non deterministica.
B) Macchina di Turing quantistica.
C) Macchina di Turing deterministica.
D) Macchina di Turing probabilistica.
  • 18. Qual è una caratteristica comune a tutti i modelli di calcolo discussi nella teoria della complessità?
A) Richiedono una realizzazione fisica.
B) Funzionano in modo deterministico.
C) Utilizzano bit casuali per i calcoli.
D) Sono limitati a un tempo di esecuzione polinomiale.
  • 19. Quale insieme di assiomi viene utilizzato per definire le misure di complessità in modo molto generale?
A) Assiomi di complessità di Blum
B) Assiomi relativi al problema P vs NP
C) Teorema di Cook-Levin
D) Assiomi di completezza di Turing
  • 20. Quale delle seguenti opzioni NON è una misura di complessità comunemente utilizzata nella teoria della complessità?
A) Complessità dei circuiti
B) Complessità della comunicazione
C) Complessità degli alberi decisionali
D) Complessità dell'entanglement quantistico
  • 21. Quale misura di complessità tiene conto della quantità di informazioni scambiate tra le parti?
A) Complessità comunicativa
B) Complessità spaziale
C) Complessità dei circuiti
D) Complessità temporale
  • 22. Quale termine ha coniato Boris Trakhtenbrot nel 1955 e che oggi è noto come 'misura di complessità'?
A) "Macchina di Turing"
B) "Funzione di segnalazione"
C) "Complessità computazionale"
D) "Tempo polinomiale"
  • 23. A quale classe di complessità si ritiene che appartengano i problemi complementari di NP?
A) co-NP
B) PP
C) NP
D) BQP
  • 24. Chi ha effettuato l'analisi della complessità computazionale dell'algoritmo euclideo nel 1844?
A) Juris Hartmanis
B) Gabriel Lamé
C) Alan Turing
D) Richard E. Stearns
  • 25. In quale anno Richard Karp ha pubblicato il suo articolo sui problemi NP-completi?
A) 1965
B) 1967
C) 1971
D) 1972
  • 26. Quale teorema afferma che PSPACE = NPSPACE?
A) Problema P vs NP
B) Teorema di Savitch
C) Teorema di Cook-Levin
D) Teorema della gerarchia temporale
  • 27. Cosa ha studiato Raymond Smullyan nel 1961?
A) Insiemi elementari
B) Automi a confini lineari
C) Calcoli in tempo reale
D) Misure di complessità
  • 28. Quanti problemi combinatori e di teoria dei grafi Richard Karp ha dimostrato essere NP-completi?
A) 15
B) 21
C) 30
D) 10
  • 29. Chi ha curato il libro 'Unravelling Complexity: The Life and Work of Gregory Chaitin'?
A) Wuppuluri, Shyam; Doria, Francisco A.
B) Garey, Michael R.; Johnson, David S.
C) Downey, Rod; Fellows, Michael
D) Arora, Sanjeev; Barak, Boaz
  • 30. A quale classe di complessità appartengono tutti i problemi decisionali?
A) P
B) TUTTO
C) EXPTIME
D) NP
  • 31. Chi sono gli autori del libro 'Computational Complexity' pubblicato nel 1994?
A) Christos Papadimitriou
B) Oded Goldreich
C) Michael R. Garey; David S. Johnson
D) Sanjeev Arora; Boaz Barak
  • 32. Cosa implica il calcolo analogico secondo la teoria della complessità continua?
A) Sistemi dinamici continui ed equazioni differenziali.
B) Macchine a stati finiti.
C) Elaborazione di segnali digitali.
D) Algoritmi probabilistici.
  • 33. A quale classe di complessità si sa che sia contenuta all'interno di PSPACE?
A) BQP
B) PH
C) PP
D) MA
  • 34. Chi ha suggerito che un algoritmo 'buono' dovrebbe avere un tempo di esecuzione limitato da un polinomio della dimensione dell'input?
A) Edmonds
B) Gabriel Lamé
C) Leonid Levin
D) Juris Hartmanis
  • 35. Chi ha scritto 'Computational Complexity: A Conceptual Perspective'?
A) Sanjeev Arora; Boaz Barak
B) Christos Papadimitriou
C) Oded Goldreich
D) Michael R. Garey; David S. Johnson
  • 36. Nel contesto della teoria della complessità continua, cosa viene approssimato attraverso la discretizzazione?
A) Grafi discreti.
B) Funzioni continue.
C) Espressioni booleane.
D) Stati quantistici.
  • 37. A quale classe di complessità appartengono i problemi di conteggio?
A) BPP
B) NC
C) RP
D) #P
  • 38. A quale classe di complessità appartengono i problemi risolvibili con una quantità di memoria logaritmica?
A) L
B) NL
C) NC
D) PP
  • 39. Quale teorema implica che L sia strettamente contenuta in PSPACE?
A) Teorema della gerarchia degli spazi
B) Teorema di Cook-Levin
C) Teorema di Savitch
D) Teorema della gerarchia del tempo
  • 40. In quale anno Boris Trakhtenbrot ha iniziato i suoi studi sulla complessità computazionale?
A) 1955
B) 1960
C) 1971
D) 1956
  • 41. Qual è l'insieme corrispondente di problemi decisionali per la classe di complessità P?
A) FP
B) NP
C) EXPTIME
D) PSPACE
  • 42. Quale analisi considera sia le operazioni più costose che quelle meno costose, prendendo in considerazione l'intera sequenza di operazioni?
A) Complessità nel caso peggiore
B) Analisi ammortizzata
C) Complessità nel caso migliore
D) Complessità nel caso medio
  • 43. Chi ha definito gli automi lineari limitati nel 1960?
A) John Myhill
B) Boris Trakhtenbrot
C) Hisao Yamada
D) Raymond Smullyan
  • 44. Chi ha scritto 'A Short History of Computational Complexity'?
A) Cook, Stephen
B) Mertens, Stephan
C) Khalil, Hatem; Ulery, Dana
D) Fortnow, Lance; Homer, Steven
  • 45. Se P fosse uguale a NP, cosa si potrebbe dedurre su co-P e co-NP?
A) P non sarebbe uguale a NP
B) NP non sarebbe uguale a co-NP
C) co-P non sarebbe uguale a co-NP
D) co-P sarebbe uguale a co-NP
  • 46. Chi ha studiato i calcoli in tempo reale nel 1962?
A) Hisao Yamada
B) John Myhill
C) Boris Trakhtenbrot
D) Raymond Smullyan
  • 47. Quale tipo di riduzione è più comunemente utilizzato nella teoria della complessità?
A) Riduzione in tempo polinomiale.
B) Riduzione in tempo logaritmico.
C) Riduzione in tempo esponenziale.
D) Riduzione in tempo lineare.
  • 48. A quale classe di complessità si fa riferimento utilizzando le macchine di Turing probabilistiche?
A) NC
B) AC
C) BPP
D) QMA
  • 49. A quale classe di complessità si fa riferimento utilizzando sistemi di verifica interattivi?
A) QMA
B) NC
C) IP
D) BPP
  • 50. Chi ha scritto 'Introduzione alla teoria della computazione'?
A) Michael Sipser
B) Sanjeev Arora
C) Christos Papadimitriou
D) Boaz Barak
  • 51. In quale anno Alan Turing ha definito le macchine di Turing?
A) 1950
B) 1965
C) 1936
D) 1945
  • 52. Chi sono gli autori di 'Parameterized complexity'?
A) Wuppuluri, Shyam; Doria, Francisco A.
B) Papadimitriou, Christos; Sipser, Michael
C) Cook, Stephen; Fortnow, Lance
D) Downey, Rod; Fellows, Michael
  • 53. A quale classe di complessità si fa riferimento utilizzando circuiti booleani?
A) RP
B) AC
C) BPP
D) QMA
Creato con That Quiz — un sito di test di matematica per studenti di tutti i livelli.