![]()
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.
A) Lettere greche B) Numeri romani C) Notazione Big O D) Codice binario
A) PSPACE B) EXP C) NP D) BPP
A) Creare computer più veloci B) Classificare i problemi computazionali in base alla loro difficoltà intrinseca. C) Costruire supercomputer D) Per generare numeri casuali
A) Problema P vs NP B) Algoritmi quantistici C) Calcolo parallelo D) NP-completezza
A) SPAZIO B) BQP C) NP-completo D) PSPACE
A) Tempo esponenziale B) Esplorativo C) Espanso D) Esperto
A) P B) NP-completo C) BPP D) TEMPO SPERIMENTALE
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.
A) L'insieme dei caratteri ASCII B) L'alfabeto binario {0,1} C) L'alfabeto esadecimale D) L'insieme di tutte le lettere minuscole
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.
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.
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.
A) Byte B) Parole C) Bit D) Caratteri
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.
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.
A) Macchina di Turing probabilistica. B) Macchina di Turing non deterministica. C) Macchina di Turing quantistica. D) Macchina di Turing deterministica.
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.
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
A) Complessità della comunicazione B) Complessità dell'entanglement quantistico C) Complessità dei circuiti D) Complessità degli alberi decisionali
A) Complessità temporale B) Complessità dei circuiti C) Complessità spaziale D) Complessità comunicativa
A) "Complessità computazionale" B) "Funzione di segnalazione" C) "Macchina di Turing" D) "Tempo polinomiale"
A) BQP B) co-NP C) NP D) PP
A) Alan Turing B) Juris Hartmanis C) Richard E. Stearns D) Gabriel Lamé
A) 1971 B) 1965 C) 1967 D) 1972
A) Teorema di Cook-Levin B) Problema P vs NP C) Teorema della gerarchia temporale D) Teorema di Savitch
A) Calcoli in tempo reale B) Insiemi elementari C) Automi a confini lineari D) Misure di complessità
A) 15 B) 21 C) 10 D) 30
A) Garey, Michael R.; Johnson, David S. B) Wuppuluri, Shyam; Doria, Francisco A. C) Arora, Sanjeev; Barak, Boaz D) Downey, Rod; Fellows, Michael
A) TUTTO B) EXPTIME C) P D) NP
A) Michael R. Garey; David S. Johnson B) Oded Goldreich C) Christos Papadimitriou D) Sanjeev Arora; Boaz Barak
A) Macchine a stati finiti. B) Sistemi dinamici continui ed equazioni differenziali. C) Algoritmi probabilistici. D) Elaborazione di segnali digitali.
A) MA B) BQP C) PP D) PH
A) Edmonds B) Gabriel Lamé C) Juris Hartmanis D) Leonid Levin
A) Michael R. Garey; David S. Johnson B) Oded Goldreich C) Sanjeev Arora; Boaz Barak D) Christos Papadimitriou
A) Espressioni booleane. B) Grafi discreti. C) Funzioni continue. D) Stati quantistici.
A) #P B) NC C) RP D) BPP
A) NC B) PP C) NL D) L
A) Teorema di Savitch B) Teorema di Cook-Levin C) Teorema della gerarchia degli spazi D) Teorema della gerarchia del tempo
A) 1955 B) 1971 C) 1960 D) 1956
A) PSPACE B) FP C) NP D) EXPTIME
A) Complessità nel caso medio B) Complessità nel caso peggiore C) Analisi ammortizzata D) Complessità nel caso migliore
A) Hisao Yamada B) John Myhill C) Boris Trakhtenbrot D) Raymond Smullyan
A) Cook, Stephen B) Fortnow, Lance; Homer, Steven C) Mertens, Stephan D) Khalil, Hatem; Ulery, Dana
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
A) Hisao Yamada B) John Myhill C) Boris Trakhtenbrot D) Raymond Smullyan
A) Riduzione in tempo esponenziale. B) Riduzione in tempo logaritmico. C) Riduzione in tempo polinomiale. D) Riduzione in tempo lineare.
A) AC B) QMA C) BPP D) NC
A) BPP B) QMA C) NC D) IP
A) Michael Sipser B) Christos Papadimitriou C) Boaz Barak D) Sanjeev Arora
A) 1945 B) 1965 C) 1936 D) 1950
A) Downey, Rod; Fellows, Michael B) Cook, Stephen; Fortnow, Lance C) Papadimitriou, Christos; Sipser, Michael D) Wuppuluri, Shyam; Doria, Francisco A.
A) BPP B) QMA C) AC D) RP |