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