Crear cuenta / - Bitacoras.comAgregador → Enlace permanente ¬

0puntos votar

La Complejidad de Mario Bros.

¿Alguna vez jugaron Mario Bros.? Mi hermano y yo pasamos horas y horas de diversión tratando de ganar monedas, aplastar koopas, y salvar a la princesa. ¿Lo encontraron difícil? Conozco a varias personas que podían acabarlo en unas pocas horas. ¿Cuál fue su tiempo récord para acabarlo? Ahora bien, ¿qué tan difícil creen que Mario Bros. sea para una computadora? Resulta que Greg Aloupis de la Universidad Libre de Bruselas y algunos de sus colegas demostraron que varios juegos de video clásicos de Nintendo, incluyendo Mario Bros., son NP-duros. Ahh... ¿Y esto qué fregados quiere decir? Para responder esta pregunta es necesario entender la noción de complejidad computacional. En términos burdos, la complejidad computacional de un problema establece qué tanto tiempo o espacio (memoria) es requerido por una computadora para resolverlo, medido en términos del tamaño de los datos de entrada del problema. Por ejemplo, si nuestro problema es ordenar un conjunto de N números, podríamos preguntarnos cuántos segundos (o b...
tags
Continuar leyendo

Recomienda esta anotación por e-mail

Ayúdanos a hacer de Bitacoras.com un servicio mejor para todos. Lee nuestros consejos.

Ningún usuario registrado ha votado aún.