Libertonia
Portada · Todo · Software Libre · Desarrolladores · Comunidad · Internet · Tecnología · Meta · Diarios
Ver: Modo: Orden:
Lo reconozco, tengo un problema | 12 comentarios (12 temáticos, editoriales, 0 ocultos)
sobre problemas NP (none / 0) (#12)
por slashem a las Sat Jun 7th, 2003 at 02:36:04 PM CET
(Información Usuario)

El juego del buscaminas, al igual que el tetris y muchos otros es un problema NP-completo. La teoria es un poco larga de explicar, asignatura "computabilidad y complejidad". Pero básicamente te puedo decir que se tratan de una serie de problemas que se pueden demostrar que son intratables ( ya que cualquier otro problema es más sencillo de calcular en tiempo que él ) . Asi en bajo nivel te puedo decir que significa. Los algoritmos tienen asociado un orden de tiempo de ejcucion dependiendo del tamaño de entrada . Si un problema tarda un tiempo por cada dato se dice que es orden n . O(n) . Si tarda el cuadrado es de orden O(n²) y asi sucesivamente. Pero a partir de ordenes O(2^n) ( como pueden ser O(n!) o orden O(n^m) y un tamaño lo suficientemente grande el tiempo que puede tardar cualquier ordenador puede ser mayor que lo que se le supone que le queda de vida al planeta tierra. ( 4.500 millones de años ) Sino haz la prueba fijate en el crecimiento de la funcion 2^n . A partir de un numero relativamente pequeño ya no entra en la calculadora. Esto quiere decir que el buscaminas con un tablero lo suficientemente grande no hay un sistema efectivo de ganar ya que el calculo para hacerlo es intratable.

[ Padre ]


Lo reconozco, tengo un problema | 12 comentarios (12 temáticos, editoriales, 0 ocultos)
Ver: Modo: Orden:
Menu
· crear cuenta
· FAQ
· búsqueda
· Fuentes de Noticias

Login
Nueva cuenta
Usuario:
Contraseña:

ecol Logo Powered by Scoop
Todas las Marcas Registradas y copyrights de esta página son propiedad de sus respectivos dueños.
Los comentarios son propiedad del que los escribe.
Los iconos de las noticias y el logotipo son propiedad de Javier Malonda.
El Resto © 2002 Escomposlinux.org y aledaños.

Puedes sindicar los contenidos de libertonia en formato RSS 1.0 y RDF 0.9. También se puede sindicar la cola de envíos pendientes de moderación.

El proyecto escomposlinux.org está dedicado a la memoria de tas

crear cuenta | faq | búsqueda