Menú

Máquinas inspiradas en la naturaleza viva (II)

4 de abril de 2007

Atención: Esta anotación es la continuación de Máquinas inspiradas en la naturaleza viva (I)

Hace algunas semanas estuve escribiendo un poco acerca de la problemática actual en la computación, las limitaciones de los ordenadores tradicionales y la necesidad de superar esas limitaciones para resolver problemas de la vida real. Como decía, la existencia de problemas NP-Completos que no son posibles de resolver en tiempo polinomial en una computadora convencional, ha llevado a los investigadores a diseñar nuevos modelos de computación que en un futuro puedan superar estas barreras de eficiencia. Muchos de vosotros seguramente habrá leído sobre la computación cuántica y cómo con ella se ha consigue (teóricamente) romper algunas claves de encriptación.
Efectivamente, la computación cuántica es un modelo de computación no convencional. Sin embargo, yo quería hablar otros dos modelos, menos conocidos, que entran dentro de la denominada Computación Natural: La Computación Molecular basada en ADN (Adleman, 1994) y la Computación con Membranas (Gh. Paun, 1998).

Computación Molecular basada en ADN

En 1953 James Watson y Francis Crick presentaron su modelo de ADN de doble hélice. En él se describía la composición de los cromosomas como una doble hélice, donde cada una de ellas estaba a su vez compuesta por una cadena de aminoácidos. Este estudio les supuso el Premio Nobel.

ADN40 años después, Leonard Adleman, inventor de la criptografía RSA de la que hablábamos un poco en artículo anterior, estaba leyéndose el trabajo de estos dos físicos. Observó que en la mitosis de la célula, cuando se produce la replicación del ADN, interviene una enzima, la polimerasa. Al fijarse en cómo esta enzima creaba una copia perfecta de la información genética, se maravilló con el parecido que tenía ésta en su forma de actuar con una máquina de Turing de doble cinta (estas cosas siempre me hacen pensar en si las matemáticas se inventan o se descubren…). Inmediatamente se puso a trabajar en la elaboración de un experimento que utilizara el ADN para realizar cálculos computacionales. En 1994 publicaría este experimiento en una revista científica (la revista Science, creo), en el que resolvía una instancia del problema del Camino Hamiltoniano (un problema NP-Completo) con 7 vértices. Hay que aclarar que tanto el problema como la solución se encontraban codificados apropiadamente en cadenas de ADN, donde el alfabeto está formado por las posibles bases nitrogenadas: Adenina, Citosina, Timina y Guanina.
¿Cómo es posible construir un modelo computacional basado en ADN? Bueno, si nos abstraemos lo suficiente podemos llegar a ver que para construir un modelo computacional necesitamos dos cosas: Un soporte para almacenar información y la posibilidad de realizar operaciones sobre esa información. Y esto es lo que Adleman descubrió y aprovechó para construir su modelo, formado principalmente por tubos (recipientes) que contenían multiconjuntos de agregados (datos), y las operaciones de extraer de un tubo, meclar dos tubos y detectar alguna sustancia en un tubo. Con este modelo, su experimento consistió, resumiendo mucho, en:

  1. Generar aleatoreamente el conjunto de secuencias de vértices, donde cada una es un posible camino.
  2. Eliminar, por filtrado, las codificaciones que no correspondan con los caminos que empiecen y acaben por los vértices de los que parte el problema
  3. Eliminar, también por filtrado, todas las secuencias no compuestas por los n vértices del grafo.
  4. Eiminar todas las secuencias que contengan algún vértice repetido.
  5. Si el tubo final, resultado de todos los filtrados anteriores, sigue conteniendo secuencias de ADN, devolver sí. En caso contrario, devolver no.

Y bueno, por último, quería contar qué es lo que cambia en este modelo con respecto a un modelo de computación tradicional: La clave está en el paralelismo masivo. El hecho de que en un tubo se estén realizando millones de operaciones simultáneas por segundo, hace posible que problemas NP-Completos se puedan resolver en tiempos polinomiales. Es por ello que la computación basada en ADN haya tenido tanto éxito, porque constituye una huída hacia adelante en la investigación para la resolución de problemas de la vida real que con máquinas convencionales no pueden ser resueltos.

Continuará…

FON en España

22 de marzo de 2007

No todo fue interesante en Imaginatica 07. La conferencia que dio Antonio Sáez fue más bien una exhibición de cómo un empresario en internet puede manipular a sus clientes y encima hacerles creer que les está haciendo un favor. Porque a mi entender, eso es lo que está pasando con FON.
Aquí hay unos señores con mucha reputación (empresarial) que han decidido crear una empresa con buena imagen para así recibir capital de inversores. ¿Cómo lo hacen? Promoviendo el ideal de “¡Vamos a compartir! !Compartir es bueno! ¡Todos salimos ganando si compartimos!”
En un principio tú dices: “Pues sí, sería genial que todos pudiésemos conectarnos a internet desde cualquier lugar del mundo aprovechando la conexión sobrante de los demás.” Y está muy bien oye. Promover ese tipo de ideas le daría muchos puntos a FON si no fuera porque sus intereses no son precisamente ésos. Como una empresa que es, FON existe para ganar dinero. Y si lo observan, ganan dinero porque nosotros compartimos la conexión a internet que estamos pagando. Por tanto, están ganando dinero a costa de predigar generosidad.

Pero no, durante la hora y media que Antonio Sáez habló sobre FON no mencionó lo que a mí verdaderamente me interesa: cuánto dinero van a ganar con FON o cuánto dinero están ganando ya. Y es porque me da la impresión de que si lo dijeran seguramente más de uno dejaría de ser fonero. No, en su lugar, este hombre se dedicó a vacilar de lo buen empresario que es y lo mucho que ha triunfado en la vida, de su éxito en Terra y Ya.com. Ah, y también a soltar perlas como la siguiente:

“Nosotros participamos en el desarrollo de la banda ancha en España cuando sacamos la adsl de 256 Kbps, que bueno, como garantizábamos el 10 % se quedaba en 20 K. Además fuimos los primeros en regalar un modem usb. Eso sí, como nos gastamos una pasta en esos modem usb, cuando el usb aún era desconocido, qué menos que haceros firmar una permanencia mínima de 18 meses.”

Antonio Sáez, en la conferencia FON en España el miércoles 7 de marzo.

WTF?!! ¿De verdad este tío ha sido cofundador de Terra y Ya.com? Es decir, cualquier blogger de tres al cuarto como yo sabe que si contratas un 1 Mbps tu conexión descargará a poco más de 100 KB/s por la conversión de Kilobit a KiloByte. Si con una conexión de 256 Kbps te dieran el 10 % de lo contratado tu conexión sería más lenta que una de 56 Kbps. Me sorprende que alguien tan molón no sepa esto…
Por otro lado… ¿de verdad se siente orgulloso de haberse inventado el contrato de permanencia de 18 meses a cambio de un modem usb? Lo digo porque más de un amigo mío iría a profanar las tumbas de los antepasados de este señor si supieran que esta idea se le ocurrió a él (que visto lo visto, permítanme que empiece a dudarlo). Además, tampoco creo que haya sido un éxito expandir la conexión Adsl, con A de asimétrica, en este país, que se sitúa entre los países con conexiones de banda ancha más caras y de peor calidad de Europa.

En fin, que en la conferencia sobre FON se habló de todo menos de FON. Y yo sólo quería dar mi opinión sobre la tomadura de pelo a la que asistí. Ahora pueden apuñalarme en los comentarios.

Máquinas inspiradas en la naturaleza viva (I)

21 de marzo de 2007

Detrás del título de esta conferencia que impartió Mario de J. Pérez Jiménez el miércoles 7 de marzo, nos encontramos con uno de los aspectos más apasionantes de la computación. Y si además quien habla de ello es este profesor del departamento de Ciencias de la Computación e Inteligencia Artificial mucho mejor. Tuve el honor de tenerlo en la asignatura Computabilidad y Complejidad el pasado cuatrimestre y verdaderamente es un hombre que contagia su ímpetu y sus ganas de aprender y seguir investigando. Su conferencia, sobre computación natural, fue densa, llena de conceptos, pero todo ello necesario para comprender en qué consiste su actual línea de investigación.

Y es que estamos hablando del que sea posiblemente el problema matemático más importante del milenio: La conjetura P=NP. De hecho, este problema es el primero de la lista que el Instituto Clay de Matemáticas (Cambridge, Massachusetts) elaboró, premiando con un millón de dólares a aquél que sea capaz de resolver alguno de ellos. Como curiosidad, tan sólo uno ha sido resuelto por ahora, la conjetura de Poincaré (ahora ya teorema), hace sólo algunos meses. Pero cuando la conjetura P=NP está la primera en la lista es sin duda por algo. Y es que la demostración de ésta llevaría consigo muchísimas cosas, y entre ellas la posibilidad de resolver los 5 restantes problemas.

¿Pero en qué consiste esta igualdad? ¿Qué es P y qué es NP?

Bueno, ambas son clases de complejidad, es decir, conjuntos de problemas de decisión (con decisión me refiero a que su solución es una afirmación o una negación, un o un no, un 1 ó un 0) que guardan unas propiedades comunes:

  • La Clase P es el conjunto de problemas de decisión resolubles por una máquina de Turing determinista (o el equivalente a un ordenador convencional) en tiempo polinomial. Lo de determinista quiere decir que a valores iguales de entrada, el resultado siempre será el mismo. Esto es fácil de entender si alguna vez has hecho una función o un método en algún lenguaje de programación. Si llamas 2 veces a alguna de tus funciones con los mismos argumentos de entrada, el resultado será el mismo.
  • La Clase NP es el conjunto de problemas resolubles por una máquina de Turing no determinista en tiempo polinomial. Una máquina de Túring no determinista es áquella que posee varias computaciones diferentes para una misma entrada.

Hay que aclarar que la potencia de una MTD es la misma que la de una MTND. Ambas son capaces de resolver los mismos problemas. Su diferencia reside en la eficiencia. Y esta eficiencia es la que trae de cabeza a todos los investigadores, pues hay algunos problemas, los de mayor complejidad de la clase NP (los llamados problemas NP-Completos), que al intentar resolverlos con ordenadores convencionales tardan un tiempo exponencial en función del tamaño de la entrada.
Un ejemplo de este tipo de problemas lo encontramos en el Problema del Viajante. En él, un viajante intenta visitar una serie de ciudades conectadas entre sí (imagínense un grafo donde los vértices son las ciudades y las aristas un camino entre dos ciudades) sin pasar 2 veces por ninguna, visitándolas todas y terminando en la ciudad de partida, siendo mínima la distancia recorrida por éste. Si aumentamos el tamaño del grafo (el número de ciudades) el tiempo que tardará un ordenador en resolver el problema, por muy rápido que sea, aumentará exponencialmente, de modo que para valores no muy altos de entrada no hay computadora capaz de devolver una solución.

¿Por qué es tan importante la conjetura P=NP?

Los algoritmos criptográficos, que hacen que la información viaje segura y que nadie no autorizado pueda acceder a cierta información se basan precisamente en el largo tiempo que una máquina tarda en descifrar las claves. Por ejemplo, la seguridad del sistema de encriptación RSA se basa en la imposibilidad de que una máquina tradicional factorice un número grande en factores primos en un tiempo decente. De esta manera la clave de descifrado se mantiene segura.
Pero si la conjetura P=NP fuera cierta, entonces sería posible diseñar un algoritmo que hiciera esto en tiempo polinomial. Hablando claro, podríamos diseñar un decodificador universal, capaz de descifrar cualquier tipo de mensaje encriptado. Además, muchos problemas de la vida real que actualmente no tienen solución por encontrarse frenados por un problema NP-Completo podrían ser resueltos. Los avances en la ciencia serían inimaginables.
Desafortunadamente, aunque aún no está demostrado, todo parece indicar que P es distinto de NP. Si esto es así, el mundo de la computación tal y como la conocemos tiene los días contados. La necesidad de buscar solución a muchos grandes problemas de la vida real ha llevado a crear nuevos modelos de computación alternativos, que se alejan del circuito electrónico que conduce pulsos eléctricos…

Continuará…

Computación Sigilosa

20 de marzo de 2007

shhhhTras un breve descanso, retomo lo que será mi pequeña crónica sobre algunas de las charlas a las que asistí en la pasada Imaginática 2007. Una que me resultó curiosa fue la que dio JJ Merelo en la Facultad de Física. Tras el nombre de Computación Sigilosa, y tras muchas bromas (“Es lo que hacemos los informáticos cuando trabajamos por la noche para no despertar a nuestras familias, no?”, “Matemática Discreta, computación sigilosa… es que no queremos llamar la atención ¬¬”), finalmente la conferencia resultó tratar sobre el uso que han dado distintas organizaciones, ya sean con el consentimiento del administrador de la máquina o sin él, de los recursos sobrantes de las CPU de sus voluntarios/victimas de manera imperceptible para éstos (sigiloso).

Y bueno, como con ejemplos se vive mejor, JJ nos hablo un poquito del proyecto SETI@home (Search for ExtraTerrestrial Intelligence), proyecto en el que colaboré como voluntario hace algunos año dentro de un grupo (grupo Karnak), Seti@homey al que aporté un total de 433 horas de computación (ríanse, pero cuando teníamos conexiones lentas el pc no solía estar encendido durante mucho tiempo).

El proyecto SETI@home, para el que no lo conozca, se dedica a examinar señales electromagnéticas del espacio exterior, con el fin de encontrar alguna señal con coherencia, que demuestre la existencia de vida extraterrestre. Las señales capturadas con grandes radiotelescopios, son troceadas y enviadas a los voluntarios, que las descargan con un pequeñito programa que se activa a modo de protector de pantalla. Cuando el ordenador de un voluntario no esté siendo usado por éste, el programa se activa y comienza a procesar el paquete. Cuando termina, manda la información y vuelve a descargar otro paquete.
De esta manera, el proyecto SETI ha conseguido tener a su disposición la red de computación distribuida más grande del mundo, construyendo así un supercomputador con más redimiento que el mismísimo MareNostrum.

Pero como antes comentaba, el concepto de computación sigilosa no implica necesariamente la voluntad del usuario del equipo. Desde hace años, la computación distribuida se utiliza para otros fines más negros. Máquinas infectadas por gusanos o/y troyanos son tomadas por mafias de manera imperceptible para su dueño. Cuando estos señores recopilan un buen número de máquinas zombie, éstas pasan a formar parte de una red, llamada BotNet, que en sí misma es una red de computación distribuida. De esta forma, los cyberdelincuentes llegan a poseer el equivalente a grandes supercomputadoras con un gasto prácticamente nulo. Estas grandes redes, que han llegado a estar formadas por cientos de miles de ordenadores, pueden después ser vendidas a empresas de spam, que las utilizan para enviar correos masivos (¿se imaginan tener a disposición 100 000 ordenadores mandando correos?). También se suelen usar para ataques de denegación de servicio masivos, que son capaces de tumbar cualquier servidor, con las pérdidas económicas que esto puede suponer para una gran empresa del sector…

El gran boom de las aplicaciones web 2.0 y la tecnología Ajax han hecho que en los 2 últimos años se empiece a pensar en el navegador web como un pequeño sistema operativo. a través de él, y gracias a grandes aplicaciones, ahora podemos escribir en procesadores de texto o hacer nuestras cuentas en hojas de cálculo online, entre otras muchas más utilidades. A JJ se le ocurrió enlazar este concepto con el de computación sigilosa. El resultado de esto ha sido un proyecto de computación distribuida a través de la web. Utilizando Ajax, consiguió un servicio que hacía uso de los recursos sobrantes de una máquina cuando ésta cargaba una página web desde un navegador. Aunque nos mostró algunos de sus resultados y comparaciones con distintos navegadores (Opera resultó ser el más veloz), parece que había problemas de eficiencia derivados del servidor que administraba el envío de los paquetes al cliente web. Con un proyecto un poco verde todavía, nos invitaba a colaborar. Requerimientos: Ruby on Rails para empezar.
En definitiva, una muy interesante conferencia aliñada con ese puntillo de humor geek del señor JJ. Una más que hace que Imaginática 07 haya merecido la pena.

Ruby on Rails, o cómo ser un feliz desarrollador de aplicaciones web

13 de marzo de 2007

Ruby on RailsFelicidad. Ésa creo que fue la palabra más repetida en la conferencia sobre Ruby on Rails del martes 6 de abril a la que asistí. Este framework de código abierto, que tan de moda se está poniendo por su potencia y facilidad de uso, también tuvo su riconcito en Imaginática 2007.
Creado por David Heinemeier Hansson, programador danés obsesionado por el código limpio y “bello”, ha tenido el reconocimiento de algunos conocidos sitios (La Coctelera entre ellos), que no han dudado en adoptar su filosofía del “No te repitas” (DRY) y su fácil manejo al programar con tecnología Ajax.
Inicialmente pensado para la creación de un administrador de proyectos (BaseCamp) con el fin de resolver los problemas de deshora con sus colegas que vivían en Chicago, la estructura definida gustó tanto que finalmente David la liberó en Julio de 2004.

Una de las que han aprovechado este framework, ha sido la empresa Flowers In Space, que se dedica al desarrollo de aplicaciones web, y aseguran estar muy contentos con Ruby on Rails. Tanto, que no dudaron en acudir a Imaginática y contarnos lo bien que se lo pasan con esta nueva ideología de programación feliz. Porque según sus impresiones, Rails mejora notablemente la calidad de vida del desarrollador web, pues éste ya no tiene que andar complicándose con los usuales servicios tediosos, que vienen de fábrica y listos para usar gracias a este novísimo framework.

Y tan nuevo que algunos interesados no se atreven a dar el paso. Hace algunos meses pude escuchar a Jero (emigrando.org) hablar del tema en su hora del café #5. Se contaba en su charla sobre frameworks que una desventaja de Rails era precisamente su juventud, y el hecho de que profundizar en el desarrollo con éste era una contínua búsqueda en listas de distribución.

Yo por mi parte estoy bastante interesado, y tengo pensado empezar a aprender a usarlo en cuanto me dejen un rato. Aunque en el taller que los majos señores de Flowers In Space organizaron el miércoles 7 de abril no pude acabar mi primera aplicación, me dejó muy buen sabor de boca, sobre todo en cuanto al manejo de bases de datos se refiere.

Enlaces relacionados: