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