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