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) Desarrollo de nuevos lenguajes de programación
B) Diseño de hardware para ordenadores
C) Analizar los recursos necesarios para resolver problemas informáticos
D) Aspectos psicológicos de la interacción persona-ordenador
- 2. ¿Qué notación se utiliza habitualmente para denotar la complejidad de los algoritmos?
A) Letras griegas
B) Números romanos
C) Notación Big O
D) Código binario
- 3. ¿Qué clase de complejidad contiene problemas de decisión que son eficientemente verificables?
A) NP
B) PSPACE
C) EXP
D) BPP
- 4. ¿Qué clase de complejidad se utiliza para clasificar los problemas que puede resolver un ordenador cuántico en tiempo polinómico?
A) EXPSPACIO
B) BQP
C) PSPACE
D) NP-completo
- 5. ¿Qué significa "EXP" en la teoría de la complejidad computacional?
A) Experto
B) Exploración
C) Ampliado
D) Tiempo exponencial
- 6. ¿Con qué se relaciona el teorema de Cook-Levin en la teoría de la complejidad computacional?
A) Problema P vs NP
B) Algoritmos cuánticos
C) Computación paralela
D) NP-completitud
- 7. ¿Cuál es la clase de complejidad que representa los problemas más difíciles en NP?
A) NP-completo
B) EXPTIME
C) P
D) BPP
- 8. ¿Cuál es el principal objetivo de la teoría de la complejidad computacional?
A) Para crear ordenadores más rápidos
B) Para generar números aleatorios
C) Clasificar los problemas computacionales en función de su dificultad inherente.
D) Construir superordenadores
|