Teoría de la complejidad computacional - Examen
A) Analizar los recursos necesarios para resolver problemas informáticos B) Diseño de hardware para ordenadores C) Desarrollo de nuevos lenguajes de programación D) Aspectos psicológicos de la interacción persona-ordenador
A) Notación Big O B) Código binario C) Letras griegas D) Números romanos
A) PSPACE B) BPP C) EXP D) NP
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) EXPTIME B) BPP C) NP-completo D) P
A) NP-completitud B) Computación paralela C) Problema P vs NP D) Algoritmos cuánticos
A) PSPACE B) NP-completo C) EXPSPACIO D) BQP
A) Exploración B) Tiempo exponencial C) Ampliado D) Experto
A) Un problema de hardware en las computadoras. B) Una pregunta teórica que no tiene solución. C) Una ecuación matemática que no se puede resolver. D) Una tarea resuelta por una computadora utilizando un algoritmo.
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) Una elección concreta de codificación de la entrada C) Uso exclusivo de notación decimal D) No es necesaria ninguna codificación
A) Determinar el número de nodos en un grafo. B) Determinar si un grafo dado está conectado o no. 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) El problema del viajante de comercio. C) Verificar si un grafo es bipartito. D) Determinar si un número es primo.
A) Caracteres B) Bits C) Palabras D) Bytes
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 de Cook-Levin. B) El teorema P vs NP. C) La tesis de Church-Turing. D) Los teoremas de incompletitud de Gödel.
A) Máquina de Turing cuántica. B) Máquina de Turing determinista. C) Máquina de Turing probabilística. D) Máquina de Turing no determinista.
A) Operan de manera determinista. B) Requieren ser físicamente realizables. C) Están limitados a un tiempo polinómico. D) Utilizan bits aleatorios para realizar cálculos.
A) Axiomas de completitud de Turing B) Axiomas relacionados con la clase P vs NP C) Teorema de Cook-Levin D) Axiomas de complejidad de Blum
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 espacial B) Complejidad de la comunicación C) Complejidad de los circuitos D) Complejidad temporal
A) Complejidad en el caso promedio B) Análisis amortizado C) Complejidad en el peor de los casos D) Complejidad en el mejor de los casos
A) FP B) EXPTIME C) NP D) PSPACE
A) Problema P vs NP B) Teorema de Cook-Levin C) Teorema de Savitch D) Teorema de la jerarquía temporal
A) TODAS B) P C) NP D) EXPTIME
A) Teorema de la jerarquía de tiempos B) Teorema de la jerarquía de espacios C) Teorema de Savitch D) Teorema de Cook-Levin
A) NC B) AC C) BPP D) QMA
A) AC B) QMA C) RP D) BPP
A) BPP B) QMA C) IP D) NC
A) RP B) NC C) #P D) BPP
A) Reducción en tiempo logarítmico. B) Reducción en tiempo lineal. C) Reducción en tiempo polinomial. D) Reducción en tiempo exponencial.
A) NP B) PP C) co-NP D) BQP
A) P no sería igual a NP B) NP no sería igual a co-NP C) co-P sería igual a co-NP D) co-P no sería igual a co-NP
A) NC B) L C) PP D) NL
A) PH B) MA C) PP D) BQP
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) Estados cuánticos. B) Expresiones booleanas. C) Funciones continuas. D) Gráficos discretos.
A) Alan Turing B) Juris Hartmanis C) Richard E. Stearns D) Gabriel Lamé
A) 1965 B) 1945 C) 1950 D) 1936
A) Gabriel Lamé B) Juris Hartmanis C) Leonid Levin D) Edmonds
A) Hisao Yamada B) Raymond Smullyan C) Boris Trakhtenbrot D) John Myhill
A) Conjuntos elementales B) Cálculos en tiempo real C) Medidas de complejidad D) Autómatas de límites lineales
A) Hisao Yamada B) Boris Trakhtenbrot C) John Myhill D) Raymond Smullyan
A) 1955 B) 1960 C) 1971 D) 1956
A) "Máquina de Turing" B) "Complejidad computacional" C) "Tiempo polinomial" D) "Función de señalización"
A) 1967 B) 1971 C) 1972 D) 1965
A) 21 B) 30 C) 10 D) 15
A) Wuppuluri, Shyam; Doria, Francisco A. B) Papadimitriou, Christos; Sipser, Michael C) Cook, Stephen; Fortnow, Lance D) Downey, Rod; Fellows, Michael
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) Sanjeev Arora; Boaz Barak B) Oded Goldreich C) Christos Papadimitriou D) Michael R. Garey; David S. Johnson
A) Michael R. Garey; David S. Johnson B) Christos Papadimitriou C) Sanjeev Arora; Boaz Barak D) Oded Goldreich |
Examen creado con That Quiz —
donde la práctica de matemáticas se hace fácil.