Teoría de la complejidad computacional
- 1. La teoría de la complejidad computacional es una rama de la informática teórica que se centra en clasificar los problemas computacionales en función de su dificultad inherente y de la cantidad de recursos necesarios, como tiempo y espacio. Se ocupa de comprender la eficiencia de los algoritmos, analizar la viabilidad de resolver problemas en distintos tipos de máquinas y determinar las limitaciones de la potencia de cálculo. Mediante el estudio de la teoría de la complejidad computacional, los investigadores tratan de investigar los límites de la computación e identificar las capacidades y limitaciones de los ordenadores para resolver diversos tipos de problemas.
¿En qué se centra la teoría de la complejidad computacional?
A) Diseño de hardware para ordenadores
B) Desarrollo de nuevos lenguajes de programación
C) Aspectos psicológicos de la interacción persona-ordenador
D) Analizar los recursos necesarios para resolver problemas informáticos
- 2. ¿Qué notación se utiliza habitualmente para denotar la complejidad de los algoritmos?
A) Letras griegas
B) Números romanos
C) Código binario
D) Notación Big O
- 3. ¿Qué clase de complejidad contiene problemas de decisión que son eficientemente verificables?
A) EXP
B) PSPACE
C) BPP
D) NP
- 4. ¿Qué clase de complejidad se utiliza para clasificar los problemas que puede resolver un ordenador cuántico en tiempo polinómico?
A) NP-completo
B) EXPSPACIO
C) PSPACE
D) BQP
- 5. ¿Qué significa "EXP" en la teoría de la complejidad computacional?
A) Exploración
B) Experto
C) Ampliado
D) Tiempo exponencial
- 6. ¿Con qué se relaciona el teorema de Cook-Levin en la teoría de la complejidad computacional?
A) Computación paralela
B) Problema P vs NP
C) NP-completitud
D) Algoritmos cuánticos
- 7. ¿Cuál es la clase de complejidad que representa los problemas más difíciles en NP?
A) NP-completo
B) P
C) BPP
D) EXPTIME
- 8. ¿Cuál es el principal objetivo de la teoría de la complejidad computacional?
A) Para generar números aleatorios
B) Construir superordenadores
C) Para crear ordenadores más rápidos
D) Clasificar los problemas computacionales en función de su dificultad inherente.
|