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