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