Ser el primero en acceder a las noticias en Internet y detectar rápidamente un foco de contaminación en cualquier punto de la red de abastecimiento de agua es un problema muy parecido, por lo menos desde el punto de vista de un informático. Ambos problemas pueden ser resueltos gracias a un algoritmo tremendamente versátil desarrollado por investigadores de la Universidad Carnegie Mellon.
En matemáticas, ciencias de la computación, y disciplinas relacionadas, un algoritmo es una lista bien definida, ordenada y finita de operaciones que permite hallar la solución a un problema. Dado un estado inicial y una entrada, a través de pasos sucesivos y bien definidos se llega a un estado final, obteniendo una solución.
Usando el algoritmo Cascades, Carlos Guestrin, que es profesor asistente de informática y aprendizaje automático y sus alumnos, han conseguido compilar una lista con los 100 mejores blogs de Internet que permiten acceder a la mejor información de la web lo antes posible.
Este listado incluye blogs muy conocidos, como Instapundit o Boing Boing y otros más desconocidos, como Watcher of Weasels o Don Surber. “La finalidad de nuestro sistema es vigilar los blogs para detectar la mejor información tan pronto como se produzca y tan cerca de la fuente original como sea posible”, comenta Guestrin en un comunicado de la universidad.
Guestrin, junto Andreas Krause y Jure Leskovec, que son estudiantes de doctorado, han analizado un total de 45.000 blogs (sobre todo los que se linkan a otros blogs) para compilar la lista, prestando especial atención al registro temporal para determinar qué noticias son puestas primero online.
100, demasiado
Pero leer 100 blogs, muchos de ellos con cientos de entradas, es demasiada información para ser asumida por alguien. Para solucionar este problema, los investigadores han usado el algoritmo para compilar una lista de blogs para que el internauta tenga acceso a sólo 5.000 notas publicadas en los blogs, de forma resumida y esquemática para escoger más fácilmente la que más le interesa.
Pero las aplicaciones de este algoritmo no se limitan a facilitar la vida del internauta que busca información en el océano de los blogs. Guestrin y sus estudiantes han utilizado el mismo algoritmo para determinar el número óptimo de sensores y el lugar idóneo para colocarlos, optimizando así la detección de elementos contaminantes en la red de aguas de un pueblo.
El informe de los resultados obtenidos en la búsqueda de blogs, así como los arrojados en la colocación de los sensores en la red de suministro de agua, fue presentado en una conferencia organizada por la Association for Computing Machinery.
“Nada demuestra más a las claras la versatilidad de este algoritmo que su capacidad para resolver dos problemas tan complicados y, a priori, tan diferentes”, comenta Randal E. Bryant, que es Decano de la Escuela de Informática de la Universidad Carnegie Mellon. “Es un buen testimonio del poder del pensamiento computacional. Los informáticos están desarrollando cada vez más métodos comunes para resolver problemas que pueden ser aplicados a muchas disciplinas”.
Sensores inalámbricos
Guestrin empezó a trabajar en este algoritmo en 2004, para compensar el coste de recoger información con la necesidad de recogerla lo más pronto posible y pegada a su fuente original.
Este problema se planteaba en el diseño de redes de sensores wireless (inalámbricos), una tecnología que puede, potencialmente, monitorizar la calidad del agua, la temperatura de un edificio, la proliferación de algas en un lago o la integridad de la estructura de un puente. En todos estos casos, desplegar el número equivocado de sensores o colocarlos en el lugar menos indicado puede hacer perder mucho dinero o puede generar una información pobre o inservible.
El algoritmo Cascades permite el emplazamiento de los sensores usando una propiedad llamada “submodularidad”. En el caso de Cascades, la submodularidad significa que añadir un sensor a una red de cinco tiene mucha más repercusión que añadir ese mismo sensor a una red de diez mil. El algoritmo también tiene en cuenta la propiedad de la localización (la idea de que los sensores que están a cierta distancia proporcionan también información independiente).
El trabajo de Guestrin se centra ahora en detectar la polución en lagos y ríos, así como en asegurar el funcionamiento en las redes Wi-Fi de las ciudades. “Es una bonita teoría aplicada a datos del mundo real”. El desarrollo de Cascades ha contado con el apoyo de empresas como Intel, Microsoft, IBM o Hewlett-Packard.
Hacer un comentario