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