Edición de «Final del 02/03/10 (Algoritmos III)»
De Cuba-Wiki
Puedes deshacer la edición. Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual | Tu texto | ||
Línea 39: | Línea 39: | ||
== Ejercicio 5 == | == Ejercicio 5 == | ||
a) ¿Qué es una máquina de Turing no determinística? | a) ¿Qué es una máquina de Turing no determinística? | ||
b) Enunciar el teorema de Cook y explicar su importancia en la teoría de la complejidad de algoritmos. | b) Enunciar el teorema de Cook y explicar su importancia en la teoría de la complejidad de algoritmos. | ||
c) ¿Es cierto que si se probara que P = NP entonces quedaría probado que todo problema NP-hard está en P? | c) ¿Es cierto que si se probara que P = NP entonces quedaría probado que todo problema NP-hard está en P? | ||
d) ¿Cuál es la importancia desde el punto de vista práctico (o sea cuando se necesita resolver un problema real) de saber que un problema es NP-Completo o NP-hard? | d) ¿Cuál es la importancia desde el punto de vista práctico (o sea cuando se necesita resolver un problema real) de saber que un problema es NP-Completo o NP-hard? | ||
[[Category:Finales]] | [[Category:Finales]] |