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