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