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