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