El “oscuro algoritmo” de la vida, descrito por Bill Gates

El problema de ordenar es uno de los temas básicos en  la formación de todo programador. Pero quizás este  conocido problema encierre la clave para entender como funciona la evolución de la vida. ¿Cómo? Esa es una historia que involucra nada menos que Bill Gates, pero antes de contarla repasemos este clásico problema informático.

 Bill Gates
¿Cómo ordenamos una serie de datos? Esta es una tarea tán básica, que la damos casi por sentada, incluso viene incluida en nuestros lenguajes, sistemas operativos, o incorporada como función estándar en todo programa  de planillas de cálculos.

Un ejercicio que se ha vuelto popular es: ¿cuál es la manera más eficiente de ordenar un millón de enteros de 32 bits? incluso como prueba de selección. La respuesta por supuesto depende de muchos supuesto. Al menos Barack Obama sabe que bublesort no es el mejor algoritmo, pero ¿un algoritmo “eficiente”, como quicksort, o heapsort son  la mejor manera de resolver este problema?

¿Cómo mides la eficiencia de un algoritmo? ¿Por el tiempo que toma ejecutar, o por la memoria que ocupa? Por eso que hay variantes de este problema, como una bastante popular que dice: ¿cómo ordenas un millón de enteros de 32bits en 2 megabyte de memoria?, pregunta con trampa, porque un millón de enteros de 32bit ocupan 4 megabytes. Aunque no lo crean, hasta los más grandes se complican con esta pregunta, como el gran Guido Van Rossum (creador de python), como pueden apreciar en este artículo.

Otra forma clásica de este problema aparece en el primer capítulo de  ese maravilloso libro que todo desarrollador debe tener en su biblioteca: Programming Pearls (2nd Edition), escrito por Jon Bentley. Afortunadamente el artículo de Bentley se encuentra disponible online, y recomiendo su lectura (pero compren el libro y guárdenlo bajo su almohada).

El problema de Bentley es ordenar un archivo de números en el rango que va de 0 a 999.999, con sólo 1 megabyte de memoria. Lo interesante del artículo de Bentley es que enseña la importancia de precisar la especificación, para llegar a una solución adecuada.  En el caso de Bentley no sólo logra una solución que funcione en un espacio reducido de memoria, sino que logra además un algoritmo eficiente O(n), usando una estructura de datos muy eficiente.
Pero vamos a la historia sorprendente sobre ordenamiento, que involucra a un millonario, y a unos panqueques.

Bill Gates Ordena Panqueques

Quizás lo que no muchos de ustedes saben es que Bill Gates  hizo una contribución científica al problema de ordenamiento escribiendo un paper (el único artículo matemático conocido que lleva su nombre) describiendo el oscuro algoritmo Pancake Sorting, si no me creen 

La verdad es que es complicado,  pero aquí les dejo otro enlace para cuando decidan investigar bio informática y jugar con bacterias que revuelven segmentos de ADN.

Lo importante es que el ADN evoluciona a partir de pequeñas mutaciones, en el entendimiento de estas mutaciones, los biólogos encontraron que este oscuro problema matemático puede dar luces en la forma en que la vida evoluciona mediante mutaciones.

Quien sabe, quizás un día Bill Gates pase a la historia no por ser el super empresario agresivo, sino que el descubridor accidental de un mecanismo fundamental para enteder como funciona la vida.
 Fuente

saludos

ms, 2-8-2010