Archivo de abril, 2011

ALAN TURING: GENIALIDAD, PERSECUCIÓN Y MUERTE

Alan Mathison Turing nació en Londres el 23 de Junio de 1912.  Desde niño mostró una inteligencia fuera de lo normal, aprendió a leer por sí solo en tres semanas, y una ávida curiosidad hacia los acertijos y rompecabezas, lo que ya adelantaba su predisposición por las matemáticas y la ciencia.  Era tan grande su ansia de saber que en su primer día de estudios secundarios, a pesar de coincidir con una huelga general en Inglaterra, recorrió en bicicleta las sesenta millas que lo separaban de la escuela. Hubo de pasar la noche en una posada y la prensa local acabó haciéndose eco de la proeza.

Su concurso fue fundamental  en la decodificación y ruptura de los códigos nazis durante la Segunda Guerra Mundial, principalmente los de la máquina Enigma, lo que sin duda ayudó a adelantar la derrota del Eje; diseñó las primeras computadoras y dedicó la última parte de su vida, antes de que debido a su homosexualidad fuera encausado judicialmente, a la biología matemática.

Si hay que escoger entre alguna de sus muchas aportaciones a las matemáticas, podríamos fijarnos en su revisión de los resultados de Kurt Gödel de 1931 en su trabajo “Los números computables, con una aplicación al Entscheidungsproblem”, publicado en 1936. El Entscheidungsproblem se traduce en castellano como “problema de la decisión” y como enunciado sencillo podríamos aportar el siguiente: ¿es posible encontrar un algoritmo que tome como entradas un lenguaje y una sentencia en tal lenguaje, y proporcione como salida un “verdadero” o “falso” para tal sentencia? El algoritmo no necesitaría proporcionar una demostración de su resultado ya que éste sería siempre correcto. Tal algoritmo sería capaz por ejemplo de decidir si la conjetura de Goldbach o la hipótesis de Riemann, grandes problemas abiertos de las matemáticas, son verdaderas o falsas. El resultado de Turing al respecto, y casi simultáneamente de Alonzo Church, es negativo: es imposible decidir algorítmicamente si una sentencia en aritmética es verdadera o falsa.  En las entrañas de la demostración de Turing está el diseño de las denominadas “máquinas de Turing”, dispositivos sencillos que manipulan símbolos en una cinta de acuerdo a una serie de reglas. A pesar de su aparente simplicidad, una máquina de Turing puede simular la lógica de cualquier algoritmo y es particularmente útil para comprender cómo funciona la CPU de un ordenador moderno.

Con sus estudios teóricos en algoritmia y sus trabajos en el diseño de las primeras computadoras, como por ejemplo el ACE (Automatic Computing Engine) durante su servicio en el Laboratorio Nacional de Física, se lo puede considerar como el padre de la informática y de la computación modernas, áreas de la ciencia que, salta a la vista, han transformado el mundo de manera radical. Quizá por tratarse de un hombre que trabajó con los pies en el futuro se antoja tan brutal y anacrónica la forma en que acabaron sus días.

Su muerte resultó tan trágica como, desde un punto de vista actual, grotesca y absurda. En 1952 la casa de Turing fue desvalijada por un cómplice de Arnold Murray, el último amante del matemático, quien en su compañía había pasado allí algunas noches. Turing denunció el robo. Durante la investigación reconoció sus relaciones homosexuales con Murray, lo que acabó conduciéndolo a un proceso por indecencia grave y perversión sexual. Lo que ahora puede resultar esperpéntico en el mundo occidental ocurría entonces en Reino Unido: los actos de  homosexualidad eran ilegales y por tanto Alan Turing fue encausado bajo la Seción 11 del Criminal Law Amendment Act 1885. Oscar Wilde, 50 años antes, sufrió la misma vergüenza. Wilde inició un juicio por injurias contra el padre de su amante, que por supuesto perdió y que acabó derivando en el proceso por perversión contra el escritor. Pasó dos años en la cárcel sometido a trabajos forzados. De aquel tiempo nació la inolvidable De profundis, larguísima carta a Lord Alfred Douglas, su amante y principal instigador del primer juicio contra su padre, en la que Wilde, lleno de resentimiento, describe su  ímproba estancia en prisión.

Alan Turing no estaba lleno de resentimiento. Muy al contrario, pensaba que no tenía nada de qué avergonzarse y no se defendió de los cargos. Le dieron a elegir entre la prisión y un tratamiento hormonal para reducir la libido (en otras palabras “castración química”). Optó por lo segundo, lo que le produjo graves alteraciones físicas tales como un gran aumento de peso o impotencia sexual.

Dos años después fue encontrado muerto en su habitación. El motivo de la muerte,  determinado a posteriori, fue envenenamiento por cianuro. Después de algunas investigaciones su muerte se consideró un suicidio: aparentemente, se administró la dosis letal por medio de una manzana envenenada que fue encontrada junto a su cama y que no terminó de comer.

Desde una postura menos políticamente correcta se podría decir que a Alan Turing se le dio a elegir entre la cárcel y la tortura. Fue gubernamentalmente torturado en contra de su naturaleza sexual, lo que probablemente lo llevó a la desesperación y al sacrificio final. Tan ridículo resulta el proceso hoy en día que el 10 de Septiembre de 2009 el primer ministro británico Gordon Brown, después de una movilización pública, pidió disculpas oficialmente por el trato que Turing recibió en los últimos años de su vida.

No es la primera vez que alguna institución debe pedir disculpas por el maltrato a los científicos. Juan Pablo II lo hizo a principios de los noventa al hilo del proceso de rehabilitación, que patéticamente no terminó de manera positiva, relacionado con la condena por parte de la Inquisición a Galileo por defender el Heliocentrismo. Galileo fue condenado a pesar de abjurar de sus ideas, lo que transformó la pena de prisión en arresto domiciliario. La leyenda dice que después de hacerlo masculló entre dientes “eppur si muove” (y sin embargo se mueve), refiriéndose a la Tierra en su órbita alrededor del Sol. Alan Turing ni siquiera murió por defender sus ideas: fue perseguido por su condición sexual.

Además de por su inigualable aportación científica, su memoria se engrandece tanto por no haber abjurado nunca de su propia naturaleza como por morir de manera digna después de verse sometido a la tortura y al descrédito.

____________

Fernando Jiménez Alburqueque (CSIC) es investigador del Instituto de Ciencias Matemáticas (ICMAT).

Etiquetas:
Categorias: General

Ramón María Aller, científico gallego de 2011

El próximo día 26 de abril la Real Academia Galega de Ciencias conmemorará al astrónomo y matemático Ramón María Aller al que está dedicado el Día del Científico Gallego. Esta conmemoración comenzó en 2008, y Ramón María Aller sucede a los profesores Enrique Vidal Abascal (2008), Isidro Parga Pondal (2009), y Cruz Gallástegui Unamuno (2010).

Ramón Aller nació el el 3 de febrero de 1878 en Lalín (Pontevedra), en la parroquia de Donramiro. Estudió en el seminario de Lugo y fue ordenado sacerdote tras obtener un doctorado en teología (en 1989). Estudió Ciencias Exactas, primero en la Universidad de Oviedo y después en la Universidad de Madrid (actual Universidad Complutense de Madrid, en la que se licencia en 1904.

Ya en 1905 comenzó a realizar observaciones astronómicas en su casa de Lalí, que van dando lugar a varias publicaciones que se alternan con otras de ámbito matemático. En 1917 decidió crear su propio observatorio.

En 1918, publicó su primer libro, Algoritmia (un compendio de análisis matemático), con la ayuda financiera de su tío Saturnino. Este le deja su herencia, con la que aumenta sus instrumentos y así puede mejorar notablemente sus observaciones. Fruto de las mismas son varios artículos que aparecen en revistas internacionales, como la alemana Astronomische Nachrichten, y la francesa L´astronomie. Sus estudios sobre las estrellas dobles fueron pioneros en España.

Su labor como profesor en la Universidad de Santiago de Compostela comienza en 1940, y es en 1943, cuando se inaugura, apoyado por el Consejo Superior de Investigaciones Científicas, el Observatorio actual del campus de esta universidad, al que traslada todo el instrumental que poseía en Lalín. El profesor Vidal Abascal desempeñó un papel decisivo en estos logros.

Observatorio astronómico Ramón María Aller, situado en el campus de la Universidad de Santiago de Compostela, en Galicia, España.
Autor de la fotografía: Xosema

Por el Observatorio de Santiago pasaron numerosos estudiantes y colaboradores, muchos de los cuáles desempeñaron un papel importantísimo en el desarrollo de las matemáticas en la Universidad de Santiago de Compostela.

En 1943 presentó en la Universidad de Madrid su tesis de doctorado en Ciencias Exactas, titulada Algunas experiencias que conviene realizar en observaciones de pasos por verticales, y publica un nuevo libro, Introducción a la Astronomía“.  Tras el nombramiento como director del Observatorio ese mismo año, se crea la cátedra de Astronomía de la universidad, de la que es nombrado catedrático en 1949 (aunque fue el encargado de la cátedra desde 1944); como tal permanece hasta 1965.

Su dimensión internacional queda también de manifiesto en que fue miembro de la Comisión 26 de la Unión Astronómica Internacional (IAU), y miembro de la Comisión Nacional de Astronomía, que representa a España en la IAU.

Su producción científica, teniendo en cuenta las circunstancias de la época, cabe calificarla de extraordinaria: 78 publicaciones que comprenden artículos, notas y comentarios y 4 libros. Dirigió 5 tesis de doctorado, descubrió 4 estrellas dobles y diseñó multitud de aparatos de observación así como cálculos y catalogos estelares. Recordemos que su fama llevó a que el astrónomo Hugh Percy Wilkins bautizara un cráter lunar con el nombre de Aller.

Ocupó cargos importantes en reconocimiento a su prestigio científico, como los siguientes:

  • Académico correspondiente de de la Real Academia de Ciencias Exactas, Físicas y de la Naturaleza (1939).
  • Académico Numerario de la Real Academia Galega de Ciencias (1941).
  • Vocal de la Sección Alfonso X el Sabio j Uan de la Cierva del CSIC (1943).
  • Vocal de la Delegación de Galicia del CSIC (1943).
  • Consejero de Honor del CSIC (1944).

Perteneció también a varias sociedades científicas:

  • Sociedad Española de Astronomía
  • Real Sociedad Matemática Española
  • Sociedad Astronómica de Francia
  • Sociedad Belga de Astronomía y Ciencias Afines.

Don Ramón María Aller falleció a los 88 años en Lalín el 28 de marzo de 1966.

Entre las tesis que dirigió, estaba la del profesor Enrique Vidal Abascal defendida en 1944 en la Universidad de Madrid; 34 años después, el autor de este post leyó su tesis doctoral en la Universidad de Santiago de Compostela, bajo la dirección de Vidal Abascal. Vaya aquí, como nieto científico de Ramón María Aller, este modesto homenaje a su figura.

______________________________

Manuel de León (CSIC, Real Academia de Ciencias) es Director del Instituto de Ciencias Matemáticas (ICMAT), Miembro del Comité Ejecutivo de IMU y Miembro del Core Group de PESC (ESF).

Etiquetas:
Categorias: General

¡Logicomix al fin en español!

Hace ahora algo más de un año (enero de 2010) nos hacíamos eco en Matemáticas y sus fronteras de la aparición de un comic singular, LOGICOMIX.

LOGICOMIX es lo que se denomina una novela gráfica, que está dedicada a uno de los más apasionantes períodos de las matemáticas, la búsqueda de la fundamentación de las mismas. El terremoto causado en la disciplina entre finales del siglo XIX y principios del XX fue de una magnitud inimaginable.

Betrand Russell

Todo esta aventura es narrada por uno de sus principales protagonistas, Bertrand Russell. Todos los actores van pasando por las páginas de LOGICOMIX, Frege, Hilbert, Poincaré, Wittgenstein, Gödel, lo acompañan en la búsqueda del Santo Grial de los Fundamentos de las Matemáticas, una historia que no tiene parangón en minguna otrra ciencia.

Recordemos algunos datos sobre los autores. Apostolos Doxiadis estudió matemáticas en la universidad de Columbia; consiguió un éxito espectacular con su novela El tío Petros y la conjetura de Goldbach. Se dedica también al cine y al teatro.

Christos Papadimitriou es profesor de Informática de la Universidad de California, en Berkeley. Su investigación swe ecntra en la complejidad computacional y la teoría de juegos y sus algoritmos. Es autor de una novela sobre Alan Turing titulada A Novel about Computation.

El griego Alecos Papadatos (que ha trabajado en la industria de la animación cinematográfica en Francia y Grecia) y su esposa, la francesa Annie Di Donna (con una larga experiencia como animadora en gran cantidad de producciones) son el dibujante y la colorista del volumen, respectivamente.

LOGICOMIX viene avalada como un éxito internacional, recordemos que ha sido durante 11 semanas la obra más vendida en la lista de cómics de The New York Times. Nuestros mejores deseos para que ese éxito se consiga también en España.

Recomendamenos también la excelente presentación en el suplemento Babelia de El País de este sábado (9 de abril de 2011), que incluye tres viñetas especialmente diseñadas por los autores para este periódico.

DATOS DEL COMIC

Logicomix, por Apostolos Doxiadis, Christos H. Papadimi

Editorial: Ediciones Sins Entido, 2011

Prólogo de Fernando Savater

Formato: 17×24, Encuadernación: Rústica con solapas

Nº Pág.: 352

ISBN: 9788496722743

______________________________

Manuel de León (CSIC, Real Academia de Ciencias) es Director del Instituto de Ciencias Matemáticas (ICMAT), Miembro del Comité Ejecutivo de IMU y Miembro del Core Group de PESC (ESF).

Etiquetas:
Categorias: General

La fórmula de Euler

Si una aburrida noche de invierno decidideran acudir a un restaurante de las Matemáticas y pidieran una paella con “un poco de todo” o, más precisamente, “un poco de todo lo importante”, probablemente les llevarían a la mesa la ecuación del título. Ésta, a pesar de tratarse de una pura tautología, es muy conocida entre la comunidad científica por su simplicidad y casi sobrenatural completitud: contiene en una sola línea elementos de lo más diverso y de cierta relevancia en la historia de las Matemáticas.

De derecha a izquierda:

0: a pesar de su enorme utilidad, el cero tardó mucho tiempo en aparecer en escena. Algunas culturas (Antiguo Egipto, Babilonia, Antigua Grecia o la cultura Maya) ya poseían documentos de carácter matemático o astronómico con símbolos relativos al valor cero. Sin embargo, no fue hasta alrededor del año 810 D.C. cuando el cero tal y como hoy lo conocemos apareció en la civilización hindú. La India es la cuna de la numeración moderna, y el 0 apareció allí al introducir los hindúes un sistema posicional con nueve dígitos en el que la posición era clave. Más allá de las discusiones filosóficas acerca de si “el vacío” debe tener o no un símbolo que lo represente, resulta bastante comprensible que éste tardara tanto en manifestarse: para contar animales, útiles, haciendas o cualquier otro tipo de objetos, el cero es completamente innecesario.

= : aunque parezca extraño, en los albores del álgebra se utilizaban palabras en lugar de símbolos para representar los objetos matemáticos (por ejemplo se denominaba “cosa”, en su traducción latina, a cualquier incógnita x, y, z). Lo mismo ocurría con el símbolo para la igualdad: era la abreviatura “ae” de la denominación latina aequalis, lo que se utilizaba en su lugar. Fue el galés Robert Recorde (1510-1558) quien por primera vez introdujo el símbolo = en su libro The Whetstone of Witte. En dicha obra los segmentos eran de mayor longitud que los ahora utilizados, lo que da sentido a la elección de Recorde: Establezco este síimbolo como igualdad porque no puedo imaginar otras dos cosas que sean más iguales que un par de paralelas.

1: uno, la unidad, el primero lo los números naturales, el comienzo de las décadas, los siglos, los milenios; el inicio de la numeración. Como se mencionaba antes, fue en la India donde se desarrolló el sistema de numeración moderna. La escritura en base diez (y que tengamos diez dedos en plas manos debe de tener algo que ver con la popularidad de esta base), con nueve dígitos posicionales incluyendo un cero, es la primera de sus grandes contribuciones a las matemáticas. Los árabes llevaron este sistema a Occidente y crearon las cifras llamadas “gubar” del cero al nueve para representar cualquier número (prácticamente como en la actualidad). Una vez conocido, el sistema se expandió por todo el mundo, imponiéndose a cualquier otro preexistente.

e : el número e es una de las constantes más importantes en matemáticas. Es un número trascendente y por lo tanto no puede ser obtenido mediante la resolución de una ecuación algebrica. Por lo tanto es irracional y no puede ser expresado con un número finito de decimales o decimales periódicos. Su valor es aproximadamente e=2.71828…. A pesar de que las primeras referencias a esta constante, conocida a veces como número de Euler o constante de Napier, aparecen en tablas de logaritmos elaboradas por John Napier, su descubrimiento está acreditado a Jacob Bernoulli, quien se topó con ella mientras resolvía un problema de interés compuesto. Si no reuniera ya suficientes características especiales, se puede decir que define la función exponencial, función cuya derivada es ella misma, convirtiéndola muy frecuentemente en solución de ecuaciones diferenciales sencillas. Es la base además del logaritmo neperiano (en referencia a John Napier, matemático escocés que introdujo el concepto de logaritmo en el cálculo matemático) y puede ser obtenida como límite de cierta sucesión o como la suma infinita del inverso del factorial de los números naturales. Por todo esto se puede decir que el número e es la constante más importante en el análisis matemático.

i : nos encontramos aquí con la unidad imaginaria. Esta denominación puede resultar demasiado atractiva para la mística, pero significa simplemente que tratamos con un número cuyo cuadrado es negativo, es decir i2 = -1. Esta circunstancia es imposible para los números reales (el cuadrado de un real, ya sea positivo o negativo, siempre es positivo), por lo que la existencia la unidad imaginaria extiende la noción de estos hasta la de números complejos: aquellos que tienen una parte real y otra imaginaria. A pesar de que hay referencias a este tipo de números desde la antigua Grecia, no fue hasta el siglo XVIII, por medio de los trabajos de Leonard Euler y Carl Friedrich Gauss, cuando su uso fue generalmente aceptado. Si e es la constante fundamental del análisis real, podemos decir que i lo es del análisis complejo, área de las matemáticas con múltiples aplicaciones, algunas de ellas tan poco imaginarias como las relacionadas con ingeniería.

Π: el número de los números; quien más y quien menos conoce las primeras cifras de su valor: Π =3.1415….. Al igual que en el caso de e, π es un número trascendente y no puede expresarse de manera finita. Su definición más habitual es la siguiente: π es la relación entre la longitud y el diámetro de una circunferencia, así de sencillo. De hecho, el uso de la letra griega Π para definirlo proviene de las palabras periferia y perímetro, cuya inicial, también en griego, es precisamente π. Tal vez debido a su relación con la geometría básica, su existencia y nombre es tan difundido, así como comprensible su presencia en textos matemáticos desde los albores de los tiempos. Ya en la actualidad, π se ha convertido en un símbolo de las Matemáticas, y se usa tanto como título de película como en los diseños de camisetas. Por si fuera poco, hay competiciones internacionales cuyo objetivo, por medio de supercomputadoras, es calcular la mayor cantidad posible de sus decimales.

Sea quien sea, felicitemos al cocinero.

____________

Fernando Jiménez Alburqueque (CSIC) es investigador del Instituto de Ciencias Matemáticas (ICMAT).

Etiquetas:
Categorias: General

EuroGIGA: geometría, computación y matemática discreta en la base de la innovación tecnológica

Recogemos en Matemáticas y sus fronteras la noticia del próximo inicio de un programa europeo en el que grupos de investigadores de varios países, España entre ellos, van a cooperar de forma intensa y transversal en temas que se hallan en el corazón matemático del avance tecnológico.

El marco europeo del programa

A mediados de 2009 la European Science Foundation recibió 70 propuestas de programas de investigación para que se considerara su realización dentro de las iniciativas EuroCORES, un marco concebido para el desarrollo de investigaciones consideradas prioritarias y difícilmente abordables sin un amplio esfuerzo cooperativo internacional. Tras un extenso proceso de sucesivos arbitrajes por expertos y de valoraciones de financiación e impacto, en 2010 se seleccionaron 7 de las propuestas para que se llevaran a cabo, entre ellas EuroGIGA, la primera de carácter matemático en la historia de EuroCORES. La convocatoria de participación condujo a la formulación de varios proyectos específicos de investigación para el período 2011-2014, inscritos en EuroGIGA, cada uno integrado por equipos de diversos países europeos, en los cuales está prevista la intervención de dos equipos españoles coordinados por el el profesor Alberto Márquez (Universidad de Sevilla ) y el profesor Ferran Hurtado (Universidad Politécnica de Cataluña).

Una de las herramientas para el tratamiento de la información consiste en el uso de grandes grafos geométricos, con un número a menudo enorme de nodos-vértices que se conectan de acuerdo a un determinado significado.

La temática de EuroGIGA

El núcleo central del programa consiste en el estudio de diversos grafos e hipergrafos geométricos que se hallan en el corazón de la geometría discreta y computacional, y son a su vez herramientas básicas en numerosas aplicaciones tecnológicas en el campo de la informática y de las comunicaciones.

El tratamiento automático de la información (es decir, ¡la informática!) y la tecnología digital tienen primordialmente asociada una rama de las matemáticas, la matemática discreta, cuyos pilares básicos son la combinatoria y la teoría de grafos. La combinatoria estudia el recuento y enumeración de objetos, permitiendo estimar la complejidad de un objeto, algoritmo o estructura, y la generación y exploración de sus variantes. Los grafos son estructuras abstractas formadas por unos nodos o vértices, cada dos de los cuales se consideran conectados cuando cumplen cierta propiedad o relación. A menudo los nodos se representan como puntos del plano y las conexiones o aristas por segmentos o arcos de curva que los unen. Podemos imaginarnos un grafo en el que los nodos correspondan a empresas y las conexiones a las relaciones comerciales, otro en que los nodos estén asociados a servidores de internet y las aristas sean los vínculos directos entre ellos, o un tercero en que los vértices sean puntos del plano o del espacio cuyas coordenadas hayan sido capturadas por un cañón láser, unidos por aristas que constituyan una malla que permita representarlos.

La abstracta versatilidad de los grafos como estructura es lo que explica el gran espectro de aplicaciones en que se utilizan hoy en día; lo mismo que sucede -y no es causalidad- en informática, donde vemos, por ejemplo, como música, texto o imagen se trasladan a formatos únicos de codificación de la información. El estudio de los grafos contiene una disciplina matemática intrínseca pero inseparable de otras áreas de la matemática, como el álgebra, el análisis o la geometría.

Muchos grafos son por naturaleza geométricos, como las redes de transporte, las mallas que se utilizan para la representación gráfica de los objetos, o los grafos de proximidad que permiten analizar las nubes de puntos, pero hay muchísimos más, como es el caso de las estructuras moleculares, por ejemplo las proteínas, algunas de cuyas propiedades se estudian en términos de rigidez, plegado y acoplamiento, cuya formulación es claramente geométrica. Es uno de los campos de interacción entre la biología computacional y la geometría computacional.

La imagen de la izquierda es una malla toroidal: un grafo 4-regular trazable sobre el toro. La imagen de la derecha es la de una proteína, que se estudia desde el punto de vista cinemático y de rigidez.


La geometría computacional es una disciplina a caballo entre las matemáticas y la informática teórica. Su objetivo principal es el diseño y análisis de algoritmos para resolver eficazmente problemas geométricos, que típicamente involucran el manejo de datos masivos. Por consiguiente, una tarea fundamental es la identificación de conceptos, propiedades y técnicas que ayuden al descubrimiento e implementación de dichos algoritmos, lo que lleva al estudio de las estructuras de datos geométricos, la complejidad de los algoritmos, la representación y manipulación de figuras y de objetos, la construcción de lugares geométricos y, más en general, al desarrollo de los fundamentos matemáticos correspondientes. En particular, los problemas que se estudian incluyen la búsqueda y el recuento geométricos, la convexidad y sus generalizaciones, la proximidad, la intersección, descomposición y aproximación de formas y la visibilidad. Las áreas principales de aplicación son la informática gráfica, el diseño y fabricación asistidos por ordenador, el reconocimiento automático de formas, el diseño de grandes circuitos integrados, la visión artificial, los sistemas de información geográfica y la robótica.

Una de las características de muchos de los problemas de geometría computacional es la necesidad de manejar cantidades ingentes de datos, lo que hace que problemas aparentemente inocentes dejen de serlo. Por ejemplo, supongamos que nos dan 100.000 puntos del plano, descritos por sus coordenadas, y que necesitamos saber qué par de puntos de entre los dados está a distancia mínima. El problema parece que puede resolverse de manera muy sencilla: calcúlese la distancia entre cada par y tómese el mínimo valor obtenido. Sin embargo, esto es inviable en la práctica, porque hay aproximadamente diez mil millones de distancias que tendrían que ser calculadas. Si, por ejemplo, cada una se calcula en un una milésima de segundo, nos harían falta ¡unos cuatro meses de cálculos! Parece sorprendente, pero el estudio estructural y algorítmico del problema demuestra que basta con evaluar unas 300.000 de esas distancias “adecuadamente escogidas”, con lo que, siguiendo con el ejemplo, bastan unos pocos segundos para realizar el cómputo completo. Las “distancias adecuadas” son, precisamente, las aristas de cierto grafo geométrico que se construye tomando los puntos dados como vértices.

La geometría computacional es inseparable de la geometría discreta y combinatoria, que estudia conjuntos discretos o finitos de objetos básicos, particularmente la complejidad combinatoria de los arreglos y de las estructuras que los describen: cómo se cortan, cómo descomponen el espacio, como se pueden formar recubrimientos, etcétera. Esta disciplina tiene también un solapamiento sustancial con otras bien establecidas, como la geometría convexa, o muy recientes, como la geometría digital. Aunque a menudo todas estas disciplinas se usan conjunta e inseparablemente en la resolución de un problema, hay algunos que permiten enfatizar el papel de cada una. Por ejemplo, consideremos un conjunto de n cuerpos convexos en en el espacio tridimensional. Si existe una recta orientada que los corta a todos, una 1-transversal, ésta induce un orden o permutación geométrica de los objetos. Cuántos de estos órdenes distintos pueden generar los mismos n objetos es un problema propio de la geometría combinatoria. Hallar condiciones necesarias y suficientes para que existan 1-transversales, lo es de la geometría discreta. Finalmente, dados n cuerpos específicos, hallar efectivamente sus 1-transversales, si es que existen, corresponde a la geometría computacional. Como el lector sin duda ya adivina, la capacidad de resolver cualquiera de estos problemas exige hacerlo en todas sus facetas.

Diagramas de Voronoi

Uno de los proyectos de EuroGIGA está centrado en el estudio de los diagramas de Voronoi. En el caso más sencillo, se tienen n puntos (o lugares) del plano y a cada uno de ellos se le asocia una región convexa, la región de Voronoi de ese lugar, de forma que los puntos del plano que están dentro de su región están más cerca del lugar que la define que de cualquiera de los restantes. De esta manera se obtiene un complejo celular que captura muy eficazmente la noción de proximidad y, en particular, es un potente modelo para simular el crecimiento competitivo de los organismos, o las áreas de influencia de tiendas y servicios, o calcular la ubicación óptima de cualquiera de ellos. La parte derecha de la figura adjunta muestra el diagrama de Voronoi de un conjunto de puntos no regular pero sí distribuidos con cierta uniformidad, evidenciando el carácter celular de un tejido que se ha formado por propagación simultánea desde unos núcleos iniciales. La figura de la izquierda muestra el diagrama generado por las capitales de provincia sobre un plano euclídeo ideal. Pese al carácter isotrópico del modelo usado, que ignora la influencia de la historia y la de la geografía, es notable la correlación que se observa con la realidad.

Los diagramas de Voronoi se pueden generalizar de muchas maneras, como cambiando el espacio ambiente, tomando otras métricas, o incluyendo obstáculos y zonas en que la propagación de la influencia tenga distintas velocidades. Esto permite una enorme flexibilidad en la modelización de fenómenos, que permite usarlos en áreas muy diversas, desde la arqueología a la zoología, pasando por la cristalografía, el estudio del voto político, los estudios de climatología, y la planificación de trayectorias sin colisión en robótica o de las de menor riesgo en cirugía asistida por ordenador.

Izquierda: Diagrama de Voronoi de las capitales de provincia (sobre un plano ideal dotado de la métrica euclídea). Derecha. diagrama de Voronoi de un conjunto numeroso de puntos.

Si conectamos los lugares que tienen regiones vecinas en un diagrama de Voronoi, se forma el grafo de Delaunay, que en el caso del plano es una triangulación. Este grafo tiene también muchas aplicaciones tecnológicas. Por ejemplo, es el que se usa en los modelos digitales del terreno, tanto en cartografía como en simuladores de vuelo y en juegos de ordenador y consola. También es la herramienta básica en la reconstrucción digital de superficies y sólidos a partir de datos que frecuentemente son puntos muestreados vía láser o secciones obtenidas tomográficamente.

Aunque se ha investigado mucho en estos temas, siguen surgiendo numerosos problemas además, aparte de que otros que siguen sin resolverse por completo. En EuroGIGA se estudiarán varios de ellos, como la complejidad y cálculo de los diagramas de puntos en movimiento, las generalizaciones de los diversos ejes esqueletales que se usan en el reconocimiento automático de formas, o las variantes de las triangulaciones y de los grafos de proximidad, que permiten el análisis de datos discretos espaciales dotándoles de estructura y forma, y permitiendo técnicas de discriminación o agrupamiento.

El tratamiento automático de la información geográfica (GIS) es una de las áreas de aplicación de los temas estudiados en EuroGIGA.

Geometría combinatoria y grafos geométricos

En los apartados anteriores hemos visto varias veces que los datos de partida son en muchas ocasiones conjuntos de puntos discretos, muy numerosos. Para poder analizarlos o desarrollar métodos eficaces que permitan agruparlos, conectarlos o simplificarlos, de cara a las diversas aplicaciones, es necesario entender con profundidad su estructura combinatoria. Imaginemos que trazamos 3 puntos distintos sobre el plano, ¿de cuántas maneras distintas puede hacerse? Si las distancias no son el aspecto más importante, podríamos decir que sólo hay dos maneras, o bien que formen un triángulo, o bien que estén alineados. De acuerdo; pues entonces ¿de cuántas maneras distintas se pueden disponer 7 puntos sobre el plano? ¿Y si son 70.000? Supongamos que estamos en este último caso, y que no hay tres de ellos alineados, ¿será cierto que siempre podremos encontrar una recta por dos de ellos que deje exactamente la mitad (34999) de los restantes a cada lado? Y si es así, ¿cuántas de esas rectas puede haber en un conjunto? La respuesta a la primera pregunta es que sí, que siempre se puede partir equilibradamente con una recta `por dos de los puntos … ¡pero la segunda pregunta es un problema que sigue abierto cuarenta años después de que fuera formulado!

Posiblemente el lector se pregunte qué sentido tiene un problema como el descrito, aparte de la curiosidad matemática. Lo cierto es que muchos algoritmos que han de procesar grandes cantidades de puntos empiezan por dividirlos en dos mitades mediante una recta, y luego procesan los dos subconjuntos de manera recursiva. El análisis completo del comportamiento de estos procedimientos está indisolublemente ligado a la comprensión combinatoria de estructuras como la bipartición que hemos explicado.

Hay muchos problemas en este campo que pueden formularse de manera muy sencilla y sin embargo ser extremadamente difíciles. Por ejemplo, puede decirse que cuando el número de puntos se hace muy grande, sea cual sea su posición, empiezan a aparecer subconjuntos en posición “bastante regular”. En particular, y siendo más precisos, se puede demostrar que para cualquier valor entero n existe otro número f(n) tal que cualquier conjunto que conste de al menos f(n) puntos contiene un subconjunto de n puntos que constituyen los vértices de un polígono convexo (véase figura). Esto es lo que se llama el teorema de Erdős-Szekeres. Sin embargo, se desconoce el valor preciso de f(n), lo que se sabe es que, aproximadamente, 2^n ≤ f(n) ≤ 4^n, y estrechar el margen entre la cota inferior y la cota superior es un problema que lleva abierto muchos años.

El nombre del teorema anterior alude a dos investigadores húngaros, uno de los cuales, Paul Erdős, está considerado como uno de los más grandes matemáticos del siglo XX, y precisamente fue uno de los grandes estudiosos de la geometría combinatoria. Veamos otro problema que planteó él. Supongamos que tenemos dos conjuntos, cada uno con n puntos, y queremos saber si son exactamente el mismo, incluidas las distancias. Es decir, queremos decidir si el segundo conjunto se ha obtenido simplemente trasladando y girando el primero, de forma rígida que no altere las distancias entre cada dos puntos. El enfoque natural de cualquier algoritmo empieza por ver si ciertas distancias que se observan en el primer conjunto entre pares de puntos aparecen también en el segundo; o sea, buscando distancias repetidas.
Para ver si entendemos bien lo que estamos haciendo, podemos empezar por pensar, dado un único conjunto de n puntos, cuántas veces puede aparecer repetida una misma distancia. Por ejemplo, si n=3, podemos conseguir que una misma distancia aparezca tres veces, pues basta formar con los puntos un triángulo equilátero. Sin embargo, ¡de nuevo la respuesta exacta es desconocida para valores generales de n!

Uno de los proyectos de EuroGIGA se dedica especialmente a estudiar este tipo de problemas de geometría combinatoria, incluyendo varias extensiones del teorema de Erdős-Szekeres. Por otra parte, cuando los puntos de un conjunto finito se conectan mediante segmentos se obtiene un grafo geométrico, alguno de los cuales ya hemos mencionado, como las triangulaciones, y en el proyecto se estudiarán sus propiedades, su recuento, sus valores extremos, así como el diseño de algoritmos para la construcción de grafos óptimos según distintos criterios. También es un grafo geométrico el 1-esqueleto de un politopo, que es la envolvente convexa de un conjunto finito de puntos, y por supuesto los politopos son también un tema central de estudio dentro del proyecto. Un politopo puede definirse también por desigualdades lineales, lo que nos podría llevar a comentar el extensísimo campo de aplicaciones de la programación lineal. Remitimos al lector al artículo ya aparecido en este blog en el que se habló de este tema, con ocasión de la refutación de la conjetura de Hirsch por parte del profesor Francisco Santos, que es uno de los investigadores integrados en el equipo español de este proyecto dentro de EuroGIGA.

Uno de los máximos impulsores de la geometría combinatoria fue el matemático húngaro Paul Erdős (1913-1996). A la derecha, ilustración del teorema de Erdős-Szekeres

Conclusión

El tratamiento automático de información geométrica masiva está presente en la manipulación de imágenes digitales, desde los videojuegos a los métodos de diagnosis médica menos invasiva, pasando por la cirugía moderna, por los procesos industriales que incorporan control de calidad mediante visión artificial o diseño asistido por ordenador, o por los modelos de terrenos que permiten el tratamiento de la información geográfica o la simulación eficaz de fenómenos naturales.

Subyaciendo a toda esta tecnología que evoluciona muy rápidamente se ha generado la necesidad de dar respuesta matemática a muchos interrogantes nuevos. Sólo en el marco de proyectos cooperativos como EuroGIGA, combinando el esfuerzo de muchas instituciones e investigadores europeos, podemos esperar que se produzcan avances no sólo al ritmo de esa demanda, sino también anticipando y creando el futuro.
Nota. Agradecemos la cesión de diversas figuras: terreno triangulado (R. Silveira), proteína (I. Streinu), mapa de España (J. Cáceres), diagrama de Voronoi (K. Sugihara), malla toroidal (S. Kobourov). Los dos grandes grafos que aparecen en la primera figura están tomados del blog AI3 de M.Bergmann (http://www.mkbergman.com/date/2008/02/).

____________________________________________

Ferran Hurtado, Dept. de Matem. Aplicada II, Universitat Politècnica de Catalunya, Barcelona

Etiquetas:
Categorias: General