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