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