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