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