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