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