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