En busca de los algoritmos perfectos

Científicos y estudiantes de 20 países participan en un curso avanzado sobre algoritmos, combinatoria y optimización

Por Diego Freire  |  Agência FAPESP – Los algoritmos están presentes básicamente en todas las tecnologías: desde el GPS instalado en los teléfonos inteligentes, que traza las mejores rutas posibles entre un punto y otro de un trayecto, hasta los complejos programas que controlan una sonda lanzada y en camino hacia Marte. Estas “recetas” matemáticas, que suministran el paso a paso necesario para que las máquinas ejecuten toda suerte de actividades, constituyen el objeto de estudio de científicos de distintas áreas relacionadas con la Ciencia de la Computación. Y algunos de ellos se reunieron entre los días 18 y 29 de julio en São Paulo, Brasil, durante la São Paulo School of Advanced Science on Algorithms, Combinnatorics and Optimization.

El evento, realizado por el Departamento de Ciencia de la Computación del Instituto de Matemática y Estadística (IME) de la Universidad de São Paulo (USP) con el apoyo del programa Escuela São Paulo de Ciencia Avanzada (ESPCA), de la FAPESP, les brindó a 150 jóvenes investigadores y estudiantes de instituciones de 20 países clases, charlas y otras actividades sobre algoritmos, combinatoria y optimización, ramas interrelacionadas de la Matemática y de la Ciencia de la Computación con innumerables aplicaciones tecnológicas.

“En tanto que los algoritmos son secuencias finitas de instrucciones para la realización de determinadas actividades, la combinatoria y la optimización operan en el análisis de las posibilidades y en los esfuerzos destinados a que las soluciones sean más eficientes, respectivamente. Los investigadores seleccionados para tomar parte en el curso apuntan en sus países e instituciones de origen a trabajar con algoritmos tendientes a atender las diversas y crecientes demandas tecnológicas globales, lo cual requiere que se desarrollen nuevas técnicas para resolver problemas cada vez más complejos”, dijo Yoshiko Wakabayashi, coordinadora del curso.

Wakabayashi es una de las investigadoras principales del proyecto temático intitulado "Estructuras combinatorias, optimización y algoritmos en Teoría de la Computación", en el cual, con el apoyo de la FAPESP, se apunta a desarrollar nuevos algoritmos y estrategias para la resolución de problemas de distintas áreas del conocimiento.

Fue de esa forma que su grupo avanzó en el tratamiento de un problema persistente en el análisis de datos de árboles filogenéticos, representaciones gráficas en forma de árboles de las relaciones evolutivas entre diversas especies u otros seres vivos que puedan tener un ancestro común.

“Esos árboles se representan mediante grafos, conjuntos de puntos, llamados vértices o nodos conectados por aristas, que modelan matemáticamente diversos fenómenos que, en el caso de nuestro estudio, son las características compartidas por individuos de una misma especie. El análisis de las relaciones entre esos vértices y esas aristas permite descubrir, matemáticamente, si existe alguna cadena biológica que señala un parentesco entre un individuo y otro, por ejemplo”, explicó Karla Roberta Pereira Sampaio Lima, de la Escuela de Artes, Ciencias y Humanidades (EACH) de la USP.

Pero el análisis de estas relaciones, realizado con computadoras, no constituye una tarea fácil. Un grafo de 50 vértices –en el caso de un árbol filogenético, cincuenta individuos de una misma especie– requeriría alrededor de 17 horas de estudio para poder contestar una pregunta sobre sus relaciones. Los investigadores utilizaron técnicas de programación y métodos de optimización para acortar este proceso, eliminando soluciones que no interesaban y haciendo que el sistema se enfocase en respuestas óptimas.

Los experimentos demostraron que el algoritmo desarrollado con base en la investigación puede emplearse para resolver grafos con 1.500 vértices en 40 minutos, un desempeño muy superior al alcanzado por otros algoritmos propuestos en la literatura. Manoel Campêlo, Alexandre S. Freire, Karla R. Lima, Phablo F. S. Moura y Yoshiko Wakabayashi publicaron un artículo con estos resultados en la revista Mathematical Programming, que se encuentra disponible en el siguiente enlace: link.springer.com/article/10.1007%2Fs10107-015-0880-7.

El problema del secretario

A juicio de los expertos, la ciencia de la computación adolece de un problema o, a decir verdad, de varios. Pero una vez resuelto el primero, esto podría ayudar a solucionar los restantes con mayor eficiencia: la cuestión P versus NP, que, en términos generales, apunta a averiguar qué problemas computacionales pueden resolverse eficientemente mediante algoritmos “astutos” (P) y cuáles, aparentemente, sólo pueden resolverse solamente testeándose una por una las respuestas posibles (NP).

Lo que el algoritmo desarrollado en el IME hace a los efectos de analizar un árbol filogenético es eliminar, entre ciertos algoritmos “astutos”, las posibles respuestas que no tienen posibilidades de constituir en la mejor solución.

“Se trata de un esfuerzo de muchos investigadores que trabajan para desarrollar algoritmos referentes a problemas para los cuales aún no se conocen algoritmos eficientes. Cada vez que un investigador descubre una solución eficiente, aumenta la cantidad de problemas que sabemos que se encuentran en la clase P, lo que demuestra que ciertos problemas computacionales admiten soluciones eficientes”, comentó Yoshiharu Kohayakawa, también del IME, miembro de la comisión organizadora de la São Paulo School of Advanced Science on Algorithms, Combinnatorics and Optimization.

Entre los más eminentes investigadores dedicados a hallar soluciones óptimas de problemas complejos se encuentra Robert Kleinberg, de la Cornell University, en Estados Unidos, quien dicta a lo largo del cursado clases sobre búsqueda estocástica combinatoria, un campo de la Matemática en el cual se modelan sistemas que se comportan de forma aleatoria, pero siguiendo las leyes de la probabilidad.

“Las clases se concentran en problemas que abarcan el proyecto de algoritmos para la toma de decisiones de cara de incertidumbres sobre futuras entradas y restricciones combinatorias. Un ejemplo de ello es el clásico ‘problema del secretario’, estudiado extensivamente en los campos de la probabilidad aplicada, la estadística y la teoría de la decisión”, dijo Kleinberg.

Este problema plantea un escenario en el cual un administrador pretende contratar al mejor secretario entre todos los postulantes disponibles. La decisión sobre cada candidato debe tomarse inmediatamente después de la entrevista y, una vez que ha sido rechazado, el solicitante no puede ser tenido en cuenta. El administrador puede calificarlo con base en las entrevistas anteriores, pero no tiene conocimiento acerca de las cualidades de los postulantes que aún no han sido entrevistados.

“¿Qué estrategias adoptar entonces para saber a qué hora dar por terminadas las entrevistas sin disminuir la probabilidad de seleccionar al mejor postulante? Si la decisión pudiese postergarse hasta que todos fuesen entrevistados, el algoritmo para arribar a una respuesta óptima sería sencillo, teniendo en cuenta que las cualidades de todos los postulantes son conocidas. En caso de que se necesite contratar a la persona inmediatamente, el algoritmo óptimo opera con miras a privilegiar al mejor postulante con base en la cantidad de entrevistas que se harán: si uno entrevista únicamente a tres postulantes, la mejor solución consistirá en basarse en el segundo: si éste es mejor que el primero, uno lo contrata; si no lo es, contrata al tercero y último postulante. En caso de que sean cinco personas, uno debe esperar hasta la tercera para empezar a tomar su decisión, y así sucesivamente”, explicó.

Las clases de Kleinberg y de los demás investigadores que formaron parte de la programación de la São Paulo School of Advanced Science on Algorithms, Combinnatorics and Optimization se extendieron hasta el día 29 de julio en el Centro de Difusión Internacional de la USP.

“Este curso constituye un esfuerzo más de la FAPESP tendiente a impulsar interacciones entre los científicos y las instituciones de investigación del estado de São Paulo con la comunidad científica internacional, al mostrarle al mundo las grandes contribuciones y los potenciales locales, y también al atraer a jóvenes y brillantes investigadores de todos los continentes para que realicen trabajos en colaboración”, dijo Carlos Henrique de Brito Cruz, director científico de la Fundación, durante la apertura de la programación.

El rector de la USP, Marco Antonio Zago, destacó en la oportunidad la importancia del fomento al intercambio científico que el curso promovió. “La FAPESP ha hecho su aporte para diversificar aún más el universo académico paulista y la investigación científica que se lleva adelante en el estado de São Paulo, al apoyar la realización de cursos como éste y también a través de otras modalidades de apoyo. La USP mantiene sus puertas abiertas”, declaró.

Además de Zago y Brito Cruz, participaron en la apertura Clodoaldo Grotta Ragazzo, director del IME, Marcelo Viana, director general del Instituto Nacional de Matemática Pura y Aplicada (Impa), y Roberto Marcondes César Junior, de la Coordinación Adjunta de Ciencias Exactas e Ingenierías de la FAPESP.

Puede obtenerse más información sobre la São Paulo School of Advanced Science on Algorithms, Combinnatorics and Optimization en el siguiente enlace: sp- school2016.ime.usp.br.