… o quizás una vuelta de tuerca al argumento de la simulación.
Archive for the ‘Algorítmica’ Category
Recursividad Indirecta
Posted by Carlos en mayo 5, 2008
Posted in Algorítmica, Comic, Filosofía | Etiquetado: Argumento de la Simulación, Recursividad, Xkcd | 4 Comments »
C.A.R. Hoare cumple hoy 74 años
Posted by Carlos en enero 11, 2008
«Hay dos formas de realizar un diseño software: hacer que sea tan simple que sea obvio que no tiene deficiencias, o hacer que sea tan complicado que no tenga deficiencias obvias. El primer método es más difícil.«
C.A.R. Hoare (1934-), informático británico
Las «viejos cocodrilos» de la programación siguen cumpliendo años, y hoy le toca a Sir Charles Anthony Richard «Tony» Hoare, que cumple 74. A Hoare le debemos una de las joyas de la algorítmica, el algoritmo de ordenación quicksort, y el lenguaje formal CSP, en el que se basa Occam (lenguaje que en su día me dio tardes de gloria programando transputers). También desarrolló una lógica formal para verificación pre-post de algoritmos (qué tiempos aquellos, buscando invariantes en los bucles; luego vendría Dijkstra con su semántica de transformación de predicados y sus precondiciones más débiles). En 1980 recibió el premio Turing por «sus contribuciones fundamentales a la definición y diseño de los lenguajes de programación». La frase del encabezado está tomada precisamente de su discurso de aceptación.
Hoare estuvo en 2005 en España, en el Primer Congreso Español de Informática, y dio una charla plenaria sobre software verificable. Se mostró en todo momento como una persona muy afable, y con toda amabilidad y la mayor de las sonrisas atendía a todo el que luego le buscaba para comentarle algo, o simplemente presentarle sus respetos. Sin duda, Sir C.A.R. Hoare es todo un caballero.
Posted in Algorítmica, Citas, Informática, Personajes, Programación | Etiquetado: C.A.R. Hoare, Ingeniería del Software, Verificación Formal | 4 Comments »
Donald Knuth cumple hoy 70 años
Posted by Carlos en enero 10, 2008
«Ciencia es aquello que conocemos lo suficientemente bien para explicárselo a un computador. El resto de lo que hacemos es Arte.«
Donald Ervin Knuth (1938-), informático estadounidense
Hoy cumple 70 años Donald E. Knuth, uno de los padres fundadores de la algorítmica. A él debemos The Art of Computer Programming y el TeX, gracias al cual toda la comunidad científica no está a estas horas en las manos de Microsoft Word. Además de científico genial, Knuth siempre ha tenido un humor y un punto geek fantásticos. Por ejemplo, la versión i-ésima de TeX se identifica con la expansión en i dígitos de π, al igual que hace con METAPOST y el número e. También tiene la ocurrencia de emitir cheques por 2.56$ (1 dólar hexadecimal) a favor de quien encuentre un error en algún libro suyo (estos cheques son un trofeo cotizadísimo).
Su padre tenía una imprenta, y por ahí quizás venga el desarrollo de TeX, y su obsesión por la tipografía, que le ha hecho afirmar que no puede ir a comer a un restaurante, ya que no deja de mirar las fuentes tipográficas de la carta del menú. De todas formas, además de con la cita de más arriba, me quedo con otra suya sobre las matemáticas:
«¡Una fórmula matemática no debería ser nunca propiedad de nadie! Las matemáticas pertenecen a Dios.»
y con otra bastante irónica sobre la verificación formal:
«Ten cuidado con este código. He demostrado su corrección, pero no lo he llegado a probar.»
, Profesor Knuth.
Posted in Algorítmica, Citas, Geek, Informática, Personajes, Programación | Etiquetado: Donald Knuth | 11 Comments »
La combinatoria de los brotes epidémicos
Posted by Carlos en agosto 28, 2007
Uno de los aspectos claves para lidiar con brotes epidémicos es la identificación de los mismos (luego viene algo mucho más complejo que es analizar su dinámica para localizar el origen/causa, y predecir su evolución, pero dejemos eso para otra ocasión). Esta identificación no es algo trivial. Indudablemente, si se detectan cientos de casos de una enfermedad muy rara en un área muy reducida se está ante un fenómeno epidémico, pero el objetivo es realizar la identificación en una etapa más temprana, antes de que la enfermedad se disemine sin control. La clave está entonces en realizar una evaluación de cuándo un cierto número de casos de una enfermedad puede estar siendo motivada por un brote epidémico. Esto lógicamente dependerá de diferentes factores, como el número de casos, la prevalencia de la enfermedad, o el tamaño de la comunidad en la que se han detectado los casos. La combinatoria nos puede echar una mano en este caso. Concretamente, el clásico modelo de bolas y cajas puede ser muy útil. Veamos cómo.
Supongamos que tenemos un número N de cajas, sobre las que distribuimos uniformemente al azar B bolas. Cada una de estas cajas representará lógicamente un grupo o comunidad, y cada bola será un caso de la enfermedad en cuestión. La pregunta que queremos hacernos es si el hecho de que hayan caído m bolas en una cierta caja representa un evento estadísticamente improbable y por lo tanto existe una probabilidad no desdeñable de que haya una causa para el mismo más allá del azar. ¿Cuál es la probabilidad de una cierta configuración de bolas en las cajas? Dicha probabilidad viene determinada por la bien conocida distribución multinomial:
donde pi es la probabilidad del evento i, xi es el número total de veces que se produce dicho evento, y x=x1+…+xk. En nuestro caso suponemos N eventos distintos (elegir una caja concreta), pi=1/N (todas las cajas tienen la misma probabilidad), y si bi es el número de bolas en la caja i, b1+…bN=B. Entonces,
La probabilidad de que el número de bolas en la caja que más tiene sea menor o igual a m es
Finalmente, la probabilidad de que haya m o más bolas en la caja que más tiene es 1-P(N,m-1,B). El problema que tiene calcular de manera precisa esta expresión es la explosión combinatoria para valores grandes de N y B, motivo por el cual se emplean aproximaciones (por ejemplo basadas en métodos de Monte Carlo). Al menos esto era hasta ahora, ya que Warren J. Ewens, y Herbert S. Wilf, de la Universidad de Pennsylvania, han encontrado una forma eficiente de realizar el cómputo, según describen en un artículo titulado
publicado en los Proceedings of the National Academy of Sciences. El método de Ewens y Wilf se basa en el hecho de que P(N,m,B) es B!/NB veces el coeficiente de xB en la serie em(x)N, donde em(x) es la expansión polinómica de la función ex truncada en el término (m+1)-ésimo, y que estos coeficientes se pueden calcular eficientemente mediante una relación recurrente. De hecho su algoritmo emplea una cantidad de memoria O(m), y tiene un coste computacional O(mN).
Ewens y Wolf ilustran el método con dos ejemplos. En el primero se analiza la aparición de 8 casos de leucemia infantil en un pueblo de 20,000 personas. Durante el periodo en el que surgieron estos casos el número medio en todo el país (EE.UU.) era de 1.6 por 20,000 habitantes, y la población total era por aquel entonces de 180 millones. El análisis se realiza entonces con N=9,000 (180,000,000/20,000), B=14,400 (1.6·9,000), y m=8, resultando en una probabilidad del 90%, lo que no apoya la hipótesis de una causa común para estos casos. En el segundo ejemplo se analizan 12 casos de leucemia linfocítica aguda en un pueblo de 24,000 personas, cuando el número esperado era de 1, y la población total del país es de 288 millones. Tenemos entonces N=12,000, B=12,000, y m=12. En este caso la probabilidad de que todo sea debido al azar es virtualmente cero (ya para m=8 es sólo del 0.6%), por lo que la hipótesis de la causa común no puede ser obviada.
Por supuesto, en ambos casos se trata sólo de una estimación estadística, pero puede ser de gran utilidad para activar los sistemas de alerta, máxime teniendo en cuenta que el cómputo puede realizarse en sólo unos segundos en un ordenador portátil.
Posted in Algorítmica, Matemáticas, Medicina | Etiquetado: Combinatoria, Epidemias | 1 Comment »
Exploración robótica del Cosmos: nuevos desafíos, nuevos algoritmos
Posted by Carlos en enero 23, 2007
El tema de la exploración humana del espacio es apasionante y controvertido. En muchas situaciones se tiende a hacer una analogía con los antiguos exploradores, que se adentraron en desconocidos territorios polares, desérticos, o selváticos, y aunque la imagen es evocadora, parece irreal. Básicamente, mucho antes de que se tengan los medios técnicos para una detallada exploración humana de, pongamos por caso, Marte, será factible realizarla mediante sondas robóticas. La lógica indica que este paso previo es mucho más prudente, con independencia de lo que luego se pudiera decidir sobre eventuales misiones tripuladas.
Credit: NASA
En relación con esta exploración robótica surgen diferentes cuestiones de gran interés. Por un lado está la planificación a gran escala de esta exploración. Jordi nos reseña en su bitácora un artículo en el que se aborda este tema. Es sin duda un asunto interesantísimo, y que se presta a diferentes análisis. No obstante, quería comentar algo en relación a otro aspecto de naturaleza más local, pero no por ello de menor importancia: el control de las sondas robóticas. Está claro que el límite físico de la velocidad de la luz impide que las comunicaciones se puedan desarrollar en tiempo real, y por lo tanto no es planteable que los robots sean meros instrumentos teledirigidos. Éste no es sólo el caso de una hipotética exploración de planetas extrasolares, sino que se trata de una consideración crucial para la exploración de Marte por ejemplo. Consideremos que la distancia que nos separa de Marte oscila entre unos 55 millones y unos 400 millones de kilómetros. Esto supone que los tiempos de comunicación bidireccional (mensaje y respuesta) oscilan entre poco más de seis minutos y casi 45 minutos. En general, esto significa que la sonda ha de tener un cierto grado de autonomía que le permita valerse por sí misma, e incluso planificar los detalles de la exploración. Para esto será necesario emplear técnicas de inteligencia artificial (IA), entendidas en un sentido amplio:
- Los métodos clásicos de IA tales como los sistemas expertos, el razonamiento basado en casos, o los métodos bayesianos pueden ser útiles a la hora de planificar a alto nivel los objetivos a largo plazo, construir modelos del entorno, o realizar toma de decisiones estratégicas.
- Los métodos modernos englobados dentro de la inteligencia computacional, tales como la computación evolutiva o los sistemas neurodifusos, resultarán imprescindibles a la hora de resolver problemas de medio alcance que se planteen en la consecución de los objetivos estratégicos, tales como planificación de tareas, interpretación visual, u optimización de maniobras.
- Finalmente, el nivel más bajo deberá ser puramente reactivo: reglas de actuación ante patrones de entrada sensorial, que permitan una respuesta rápida ante situaciones tales como obstáculos imprevistos, terrenos impracticables, etc. Por supuesto, este nivel reactivo básico puede estar sujeto a continuo refinamiento mediante técnicas de aprendizaje, tales como los algoritmos evolutivos.
Evidentemente, en el caso de Marte es factible cierto tipo de control remoto, no en tiempo real, pero si al menos para determinar la planificación a medio y largo plazo de la exploración. Sigue existiendo entonces la problemática del control a muy corto plazo, y muy en particular la del cómputo de las trayectorias. Para ello, la NASA está recurriendo a una solución mucho más conservadora que las descritas anteriormente, cosa que tampoco es excesivamente criticable, dado que en el fondo la proximidad de Marte facilita las cosas, esto es, no es necesaria una total independencia de la sonda (salvo en circunstancias puntuales y transitorias, como un ocultamiento de Marte por el Sol, aunque en ese caso, se opta por dar unas «vacaciones» a las sondas).
Courtesy NASA/JPL-Caltech
El mecanismo que se emplea en la Spirit y en la Opportunity en lo que a planificación de trayectorias se refiere es una variante del clásico algoritmo A*. A grandes rasgos, el A* es un algoritmo completo de búsqueda para la exploración de grafos. En este caso, el grafo representa el terreno sobre el que la sonda se ha de desplazar, discretizado como si se tratase de las casillas de un tablero de ajedrez. El desplazamiento de una casilla a otra tendrá un coste que dependerá de las características del terreno. El algoritmo explora sistemáticamente todos los caminos que parten de la posición inicial, construyendo una lista de caminos abiertos, y seleccionando para su extensión a aquellos que resultan más prometedores de acuerdo con una función de coste heurística. Para evitar ciclos, se mantiene también una lista de las casillas visitadas (la gestión de esta lista tiene algunos matices, pero podemos obviarlos de momento). Si la función heurística es optimista (es decir, nos proporciona siempre una cota inferior del coste final de un camino incompleto), tenemos garantizado el encontrar finalmente la solución óptima.
El problema del A* es que obviamente parte del conocimiento del terreno, cosa que no es totalmente realista en el caso de las sondas: a medida que éstas avanzan obtienen nuevas imágenes que revelan nuevos obstáculos, o alteran las características que se suponía tenía el terreno. Esto conlleva que el grafo subyacente debe ser modificado, y el camino óptimo recomputado. Afortunadamente, hay formas eficientes de realizar esto, ya que por definición, las modificaciones que se realizan afectan fundamentalmente a la vecindad inmediata del la sonda. El algoritmo que se emplea a tal efecto es el D* (la D es de «dinámico»), y se basa en una astuta gestión de la lista de caminos abiertos. Para más detalles, puede consultarse el trabajo titulado:
realizado por Anthony Stentz, de la Carnegie Mellon University, y publicado en la 1994 IEEE International Conference on Robotics and Automation. Con este algoritmo y gracias a las últimas mejoras en los sistemas de análisis visual de la sondas, será posible que alcancen un nivel de autonomía muchísimo mayor que el que disfrutaban hasta ahora. Poca cosa si se piensa en lo que será preciso en misiones de más calado en regiones mucho más lejanas del Universo, pero un paso necesario en cualquier caso.
Posted in Algorítmica, Astronáutica, Computación Evolutiva, Inteligencia Artificial | Etiquetado: Espacio, Mars Exploration Rover, Marte, NASA, Robótica, Sistema Solar, Sistema Solar Interior | Comentarios desactivados en Exploración robótica del Cosmos: nuevos desafíos, nuevos algoritmos