A) Sviluppo di nuovi linguaggi di programmazione B) Aspetti psicologici dell'interazione uomo-computer C) Analizzare le risorse necessarie per risolvere i problemi computazionali. D) Progettazione hardware per computer
A) Numeri romani B) Lettere greche C) Codice binario D) Notazione Big O
A) PSPACE B) NP C) EXP D) BPP
A) Per generare numeri casuali B) Costruire supercomputer C) Creare computer più veloci D) Classificare i problemi computazionali in base alla loro difficoltà intrinseca.
A) NP-completezza B) Calcolo parallelo C) Problema P vs NP D) Algoritmi quantistici
A) NP-completo B) BQP C) PSPACE D) SPAZIO
A) Espanso B) Tempo esponenziale C) Esplorativo 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 esadecimale C) L'insieme di tutte le lettere minuscole D) L'alfabeto binario {0,1}
A) Codifica tramite linguaggio naturale. B) Non è necessaria alcuna codifica. C) Una scelta specifica e concreta della codifica degli input. D) Utilizzo esclusivo della notazione decimale.
A) Determinare se un grafo dato è connesso o meno. B) Calcolare il flusso massimo in una rete. C) Trovare il percorso più breve in un grafo. D) Determinare il numero di nodi in un grafo.
A) Determinare se un numero è primo. B) Il problema del commesso viaggiatore. C) Verificare se due grafi sono isomorfi. D) Controllare se un grafo è bipartito.
A) Caratteri B) Parole C) Bit D) Byte
A) Una forma primitiva di hardware informatico. B) Una tecnologia di calcolo pratica. C) Un modello teorico per la computazione generale. D) Un dispositivo per manipolare oggetti fisici.
A) I teoremi di incompletezza di Gödel. B) Il teorema P vs NP. C) Il teorema di Cook-Levin. D) La tesi di Church-Turing.
A) Macchina di Turing deterministica. B) Macchina di Turing probabilistica. C) Macchina di Turing quantistica. D) Macchina di Turing non deterministica.
A) Sono limitati a un tempo di esecuzione polinomiale. B) Utilizzano bit casuali per i calcoli. C) Richiedono una realizzazione fisica. D) Funzionano in modo deterministico.
A) Teorema di Cook-Levin B) Assiomi relativi al problema P vs NP C) Assiomi di complessità di Blum D) Assiomi di completezza di Turing
A) Complessità degli alberi decisionali B) Complessità della comunicazione C) Complessità dei circuiti D) Complessità dell'entanglement quantistico
A) Complessità dei circuiti B) Complessità temporale C) Complessità spaziale D) Complessità comunicativa
A) "Funzione di segnalazione" B) "Macchina di Turing" C) "Complessità computazionale" D) "Tempo polinomiale"
A) PP B) co-NP C) NP D) BQP
A) Alan Turing B) Juris Hartmanis C) Gabriel Lamé D) Richard E. Stearns
A) 1965 B) 1967 C) 1972 D) 1971
A) Teorema di Savitch B) Teorema di Cook-Levin C) Teorema della gerarchia temporale D) Problema P vs NP
A) Automi a confini lineari B) Misure di complessità C) Calcoli in tempo reale D) Insiemi elementari
A) 30 B) 10 C) 15 D) 21
A) Downey, Rod; Fellows, Michael B) Arora, Sanjeev; Barak, Boaz C) Garey, Michael R.; Johnson, David S. D) Wuppuluri, Shyam; Doria, Francisco A.
A) TUTTO B) P C) EXPTIME D) NP
A) Sanjeev Arora; Boaz Barak B) Oded Goldreich C) Christos Papadimitriou D) Michael R. Garey; David S. Johnson
A) Sistemi dinamici continui ed equazioni differenziali. B) Elaborazione di segnali digitali. C) Algoritmi probabilistici. D) Macchine a stati finiti.
A) PP B) BQP C) PH D) MA
A) Leonid Levin B) Gabriel Lamé C) Juris Hartmanis D) Edmonds
A) Michael R. Garey; David S. Johnson B) Christos Papadimitriou C) Sanjeev Arora; Boaz Barak D) Oded Goldreich
A) Funzioni continue. B) Espressioni booleane. C) Stati quantistici. D) Grafi discreti.
A) #P B) NC C) RP D) BPP
A) L B) NL C) PP D) NC
A) Teorema di Savitch B) Teorema della gerarchia degli spazi C) Teorema della gerarchia del tempo D) Teorema di Cook-Levin
A) 1971 B) 1956 C) 1960 D) 1955
A) EXPTIME B) FP C) NP D) PSPACE
A) Complessità nel caso peggiore B) Analisi ammortizzata C) Complessità nel caso medio D) Complessità nel caso migliore
A) Boris Trakhtenbrot B) Hisao Yamada C) Raymond Smullyan D) John Myhill
A) Khalil, Hatem; Ulery, Dana B) Mertens, Stephan C) Fortnow, Lance; Homer, Steven D) Cook, Stephen
A) P non sarebbe uguale a NP B) co-P non sarebbe uguale a co-NP C) co-P sarebbe uguale a co-NP D) NP non sarebbe uguale a co-NP
A) Raymond Smullyan B) Boris Trakhtenbrot C) John Myhill D) Hisao Yamada
A) Riduzione in tempo polinomiale. B) Riduzione in tempo logaritmico. C) Riduzione in tempo esponenziale. D) Riduzione in tempo lineare.
A) QMA B) NC C) AC D) BPP
A) IP B) NC C) QMA D) BPP
A) Boaz Barak B) Michael Sipser C) Sanjeev Arora D) Christos Papadimitriou
A) 1945 B) 1965 C) 1936 D) 1950
A) Wuppuluri, Shyam; Doria, Francisco A. B) Downey, Rod; Fellows, Michael C) Papadimitriou, Christos; Sipser, Michael D) Cook, Stephen; Fortnow, Lance
A) AC B) BPP C) QMA D) RP |