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