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