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