A) Analizar los recursos necesarios para resolver problemas informáticos B) Aspectos psicológicos de la interacción persona-ordenador C) Desarrollo de nuevos lenguajes de programación D) Diseño de hardware para ordenadores
A) Letras griegas B) Números romanos C) Notación Big O D) Código binario
A) EXP B) NP C) BPP D) PSPACE
A) Clasificar los problemas computacionales en función de su dificultad inherente. B) Para generar números aleatorios C) Construir superordenadores D) Para crear ordenadores más rápidos
A) NP-completo B) P C) BPP D) EXPTIME
A) Algoritmos cuánticos B) Problema P vs NP C) NP-completitud D) Computación paralela
A) BQP B) EXPSPACIO C) NP-completo D) PSPACE
A) Ampliado B) Tiempo exponencial C) Experto D) Exploración
A) Una pregunta teórica que no tiene solución. B) Una ecuación matemática que no se puede resolver. C) Un problema de hardware en las computadoras. D) Una tarea resuelta por una computadora utilizando un algoritmo.
A) El conjunto de todas las letras minúsculas B) El alfabeto hexadecimal C) El conjunto de todos los caracteres ASCII D) El alfabeto binario {0, 1}
A) Uso exclusivo de notación decimal B) Una elección concreta de codificación de la entrada C) No es necesaria ninguna codificación D) Codificación utilizando lenguaje natural
A) Determinar si un grafo dado está conectado o no. B) Determinar el número de nodos en un grafo. C) Encontrar el camino más corto en un grafo. D) Calcular el flujo máximo en una red.
A) Determinar si dos grafos son isomorfos. B) Determinar si un número es primo. C) Verificar si un grafo es bipartito. D) El problema del viajante de comercio.
A) Caracteres B) Bytes C) Bits D) Palabras
A) Una forma temprana de hardware informático. B) Un dispositivo para manipular objetos físicos. C) Un modelo teórico para la computación general. D) Una tecnología de computación práctica.
A) El teorema P vs NP. B) La tesis de Church-Turing. C) Los teoremas de incompletitud de Gödel. D) El teorema de Cook-Levin.
A) Máquina de Turing cuántica. B) Máquina de Turing no determinista. C) Máquina de Turing determinista. D) Máquina de Turing probabilística.
A) Requieren ser físicamente realizables. B) Utilizan bits aleatorios para realizar cálculos. C) Están limitados a un tiempo polinómico. D) Operan de manera determinista.
A) Axiomas de completitud de Turing B) Axiomas relacionados con la clase P vs NP C) Teorema de Cook-Levin D) Axiomas de complejidad de Blum
A) Complejidad de los circuitos B) Complejidad de la comunicación C) Complejidad del entrelazamiento cuántico D) Complejidad de los árboles de decisión
A) Complejidad de los circuitos B) Complejidad temporal C) Complejidad espacial D) Complejidad de la comunicación
A) Complejidad en el peor de los casos B) Análisis amortizado C) Complejidad en el caso promedio D) Complejidad en el mejor de los casos
A) PSPACE B) NP C) EXPTIME D) FP
A) Teorema de la jerarquía temporal B) Teorema de Cook-Levin C) Teorema de Savitch D) Problema P vs NP
A) P B) NP C) EXPTIME D) TODAS
A) Teorema de la jerarquía de espacios B) Teorema de Cook-Levin C) Teorema de Savitch D) Teorema de la jerarquía de tiempos
A) AC B) NC C) QMA D) BPP
A) BPP B) AC C) RP D) QMA
A) BPP B) IP C) QMA D) NC
A) #P B) NC C) BPP D) RP
A) Reducción en tiempo exponencial. B) Reducción en tiempo polinomial. C) Reducción en tiempo logarítmico. D) Reducción en tiempo lineal.
A) co-NP B) PP C) BQP D) NP
A) co-P no sería igual a co-NP B) NP no sería igual a co-NP C) co-P sería igual a co-NP D) P no sería igual a NP
A) NL B) PP C) L D) NC
A) MA B) PP C) PH D) BQP
A) Procesamiento de señales digitales. B) Algoritmos probabilísticos. C) Máquinas de estados finitos. D) Sistemas dinámicos continuos y ecuaciones diferenciales.
A) Expresiones booleanas. B) Funciones continuas. C) Estados cuánticos. D) Gráficos discretos.
A) Richard E. Stearns B) Gabriel Lamé C) Alan Turing D) Juris Hartmanis
A) 1965 B) 1950 C) 1936 D) 1945
A) Juris Hartmanis B) Edmonds C) Gabriel Lamé D) Leonid Levin
A) Hisao Yamada B) Raymond Smullyan C) John Myhill D) Boris Trakhtenbrot
A) Conjuntos elementales B) Medidas de complejidad C) Autómatas de límites lineales D) Cálculos en tiempo real
A) Hisao Yamada B) Boris Trakhtenbrot C) Raymond Smullyan D) John Myhill
A) 1955 B) 1971 C) 1960 D) 1956
A) "Complejidad computacional" B) "Tiempo polinomial" C) "Función de señalización" D) "Máquina de Turing"
A) 1965 B) 1967 C) 1971 D) 1972
A) 21 B) 15 C) 10 D) 30
A) Downey, Rod; Fellows, Michael B) Wuppuluri, Shyam; Doria, Francisco A. C) Cook, Stephen; Fortnow, Lance D) Papadimitriou, Christos; Sipser, Michael
A) Khalil, Hatem; Ulery, Dana B) Mertens, Stephan C) Fortnow, Lance; Homer, Steven D) Cook, Stephen
A) Michael Sipser B) Boaz Barak C) Sanjeev Arora D) Christos Papadimitriou
A) Michael R. Garey; David S. Johnson B) Christos Papadimitriou C) Oded Goldreich D) Sanjeev Arora; Boaz Barak
A) Oded Goldreich B) Michael R. Garey; David S. Johnson C) Sanjeev Arora; Boaz Barak D) Christos Papadimitriou |