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