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