Teoría de la complejidad computacional - Examen
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) Notación Big O C) Código binario D) Números romanos
A) PSPACE B) BPP C) NP D) EXP
A) Construir superordenadores B) Para crear ordenadores más rápidos C) Clasificar los problemas computacionales en función de su dificultad inherente. D) Para generar números aleatorios
A) BPP B) EXPTIME C) P D) NP-completo
A) NP-completitud B) Algoritmos cuánticos C) Computación paralela D) Problema P vs NP
A) NP-completo B) PSPACE C) EXPSPACIO D) BQP
A) Experto B) Tiempo exponencial C) Exploración D) Ampliado
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 conjunto de todas las letras minúsculas B) El alfabeto binario {0, 1} C) El alfabeto hexadecimal D) El conjunto de todos los caracteres ASCII
A) Una elección concreta de codificación de la entrada B) Codificación utilizando lenguaje natural C) Uso exclusivo de notación decimal D) No es necesaria ninguna codificación
A) Encontrar el camino más corto en un grafo. B) Determinar si un grafo dado está conectado o no. C) Calcular el flujo máximo en una red. 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 dos grafos son isomorfos. D) Determinar si un número es primo.
A) Bits B) Palabras C) Caracteres 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) Los teoremas de incompletitud de Gödel. B) El teorema de Cook-Levin. C) La tesis de Church-Turing. D) El teorema P vs NP.
A) Máquina de Turing determinista. B) Máquina de Turing cuántica. C) Máquina de Turing probabilística. D) Máquina de Turing no determinista.
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 relacionados con la clase P vs NP B) Axiomas de complejidad de Blum 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 del entrelazamiento cuántico D) Complejidad de los circuitos
A) Complejidad temporal B) Complejidad de la comunicación C) Complejidad de los circuitos D) Complejidad espacial
A) Complejidad en el mejor de los casos B) Complejidad en el peor de los casos C) Análisis amortizado D) Complejidad en el caso promedio
A) PSPACE B) EXPTIME C) FP D) NP
A) Teorema de la jerarquía temporal B) Problema P vs NP C) Teorema de Cook-Levin D) Teorema de Savitch
A) EXPTIME B) P C) NP D) TODAS
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) BPP C) AC D) NC
A) BPP B) RP C) QMA D) AC
A) QMA B) IP C) BPP D) NC
A) RP B) BPP C) #P D) NC
A) Reducción en tiempo logarítmico. B) Reducción en tiempo lineal. C) Reducción en tiempo exponencial. D) Reducción en tiempo polinomial.
A) PP B) BQP C) NP D) co-NP
A) co-P sería igual a co-NP B) co-P no sería igual a co-NP C) NP no sería igual a co-NP D) P no sería igual a NP
A) NL B) NC C) L D) PP
A) PH B) BQP C) MA D) PP
A) Máquinas de estados finitos. B) Algoritmos probabilísticos. C) Sistemas dinámicos continuos y ecuaciones diferenciales. D) Procesamiento de señales digitales.
A) Gráficos discretos. B) Funciones continuas. C) Estados cuánticos. D) Expresiones booleanas.
A) Gabriel Lamé B) Juris Hartmanis C) Alan Turing D) Richard E. Stearns
A) 1945 B) 1965 C) 1950 D) 1936
A) Edmonds B) Juris Hartmanis C) Leonid Levin D) Gabriel Lamé
A) Raymond Smullyan B) Boris Trakhtenbrot C) John Myhill D) Hisao Yamada
A) Conjuntos elementales B) Medidas de complejidad C) Cálculos en tiempo real D) Autómatas de límites lineales
A) Raymond Smullyan B) John Myhill C) Hisao Yamada D) Boris Trakhtenbrot
A) 1955 B) 1971 C) 1960 D) 1956
A) "Máquina de Turing" B) "Complejidad computacional" C) "Tiempo polinomial" D) "Función de señalización"
A) 1971 B) 1972 C) 1965 D) 1967
A) 10 B) 15 C) 30 D) 21
A) Papadimitriou, Christos; Sipser, Michael B) Downey, Rod; Fellows, Michael C) Cook, Stephen; Fortnow, Lance D) Wuppuluri, Shyam; Doria, Francisco A.
A) Mertens, Stephan B) Cook, Stephen C) Fortnow, Lance; Homer, Steven D) Khalil, Hatem; Ulery, Dana
A) Boaz Barak B) Sanjeev Arora C) Michael Sipser D) Christos Papadimitriou
A) Christos Papadimitriou B) Sanjeev Arora; Boaz Barak C) Oded Goldreich D) Michael R. Garey; David S. Johnson
A) Oded Goldreich B) Michael R. Garey; David S. Johnson C) Sanjeev Arora; Boaz Barak D) Christos Papadimitriou |
Examen creado con That Quiz —
donde la práctica de matemáticas se hace fácil.