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