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