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