Teoria de la complexitat computacional - Qüestionari
A) Disseny de maquinari per a ordinadors. B) Analitzar els recursos necessaris per resoldre problemes computacionals. C) Desenvolupar nous llenguatges de programació. D) Aspectes psicològics de la interacció entre humans i ordinadors.
A) Numerals romans B) Codi binari C) Notació Big O D) Lletres gregues
A) PSPACE B) BPP C) NP D) EXP
A) Generar números aleatoris. B) Classificar els problemes computacionals en funció de la seva dificultat intrínseca. C) Construir superordinadors. D) Crear ordinadors més ràpids.
A) EXPTIME B) P C) NP-complet D) BPP
A) Ampliat B) Temps exponencial C) Expert D) Exploratori
A) Problema P vs NP B) Algorismes quàntics C) Complexitat NP-completa D) Càlcul paral·lel
A) EXPSPACE B) NP-complet C) BQP D) PSPACE
A) Una tasca resolta per un ordinador mitjançant un algorisme. B) Una pregunta teòrica que no té solució. C) Un problema de maquinari en els ordinadors. D) Una equació matemàtica que no es pot resoldre.
A) L'alfabet binari {0, 1} B) El conjunt de caràcters ASCII C) El conjunt de totes les lletres minúscules D) L'alfabet hexadecimal
A) Una opció concreta de codificació de les dades d'entrada B) Ús exclusiu de la notació decimal C) No cal cap codificació D) Codificació utilitzant llenguatge natural
A) Calcular el flux màxim en una xarxa. B) Determinar si un graf donat és connex o no. C) Trobar el camí més curt en un graf. D) Determinar el nombre de nodes en un graf.
A) El problema del venedor ambulant. B) Determinar si dos grafs són isomòrfics. C) Determinar si un nombre és primer. D) Comprovar si un graf és bipartit.
A) Bytes B) Bits C) Paraules D) Caràcters
A) Una forma inicial de maquinari informàtic. B) Una tecnologia de computació pràctica. C) Un dispositiu per manipular objectes físics. D) Un model teòric per a la computació general.
A) El teorema P vs NP. B) Els teoremes de incompletitud de Gödel. C) La tesi de Church-Turing. D) El teorema de Cook-Levin.
A) Màquina de Turing quàntica. B) Màquina de Turing determinista. C) Màquina de Turing probabilística. D) Màquina de Turing no determinista.
A) Estan limitats a un temps polinòmic. B) Funcionen de manera determinista. C) Requereixen una implementació física. D) Utilitzen bits aleatòries per al càlcul.
A) Axiomes de complexitat de Blum B) Teorema de Cook-Levin C) Axiomes de P vs NP D) Axiomes de completitud de Turing
A) Complexitat del circuit B) Complexitat de l'entrellament quàntic C) Complexitat de la comunicació D) Complexitat de l'arbre de decisions
A) Complexitat de la comunicació B) Complexitat espacial C) Complexitat de circuits D) Complexitat temporal
A) Complexitat en el pitjor dels casos B) Anàlisi amortitzada C) Complexitat en el millor dels casos D) Complexitat en el cas mitjà
A) PSPACE B) EXPTIME C) NP D) FP
A) Teorema de l'arquitectura temporal B) Problema P vs NP C) Teorema de Cook-Levin D) Teorema de Savitch
A) NP B) EXPTIME C) P D) TOTS
A) Teorema de Cook-Levin B) Teorema de la jerarquia de temps C) Teorema de la jerarquia d'espais D) Teorema de Savitch
A) BPP B) AC C) QMA D) NC
A) QMA B) BPP C) RP D) AC
A) QMA B) IP C) BPP D) NC
A) #P B) RP C) NC D) BPP
A) Reducció en temps logarítmic. B) Reducció en temps polinòmic. C) Reducció en temps exponencial. D) Reducció en temps lineal.
A) co-NP B) PP C) BQP D) NP
A) co-P seria igual a co-NP B) P no seria igual a NP C) NP no seria igual a co-NP D) co-P no seria igual a co-NP
A) NL B) PP C) NC D) L
A) BQP B) PP C) MA D) PH
A) Algoritmes probabilístics. B) Màquines d'estats finits. C) Processament de senyals digitals. D) Sistemes dinàmics continus i equacions diferencials.
A) Expressions booleanes. B) Funcions contínues. C) Grafs discrets. D) Estats quàntics.
A) Juris Hartmanis B) Richard E. Stearns C) Gabriel Lamé D) Alan Turing
A) 1945 B) 1965 C) 1936 D) 1950
A) Edmonds B) Leonid Levin C) Gabriel Lamé D) Juris Hartmanis
A) Hisao Yamada B) Raymond Smullyan C) Boris Trakhtenbrot D) John Myhill
A) Càlculs en temps real B) Mètodes de mesura de la complexitat C) Autòmats linealment limitats D) Conjunts elementals
A) Boris Trakhtenbrot B) Hisao Yamada C) Raymond Smullyan D) John Myhill
A) 1971 B) 1956 C) 1960 D) 1955
A) "Complexitat computacional" B) "Funció de senyalització" C) "Màquina de Turing" D) "Temps polinòmic"
A) 1971 B) 1965 C) 1967 D) 1972
A) 21 B) 10 C) 30 D) 15
A) Arora, Sanjeev; Barak, Boaz B) Wuppuluri, Shyam; Doria, Francisco A. C) Garey, Michael R.; Johnson, David S. D) Downey, Rod; Fellows, Michael
A) Cook, Stephen; Fortnow, Lance B) Wuppuluri, Shyam; Doria, Francisco A. C) Papadimitriou, Christos; Sipser, Michael D) Downey, Rod; Fellows, Michael
A) Fortnow, Lance; Homer, Steven B) Cook, Stephen C) Mertens, Stephan D) Khalil, Hatem; Ulery, Dana
A) Michael Sipser B) Sanjeev Arora C) Boaz Barak D) Christos Papadimitriou
A) Michael R. Garey; David S. Johnson B) Christos Papadimitriou C) Sanjeev Arora; Boaz Barak D) Oded Goldreich
A) Christos Papadimitriou B) Oded Goldreich C) Michael R. Garey; David S. Johnson D) Sanjeev Arora; Boaz Barak |
Prova creada amb That Quiz —
el lloc on es poden crear i avaluar proves matemàtiques i d'altres matèries.