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