Newtonpedia EN
Inicio › Informática › Jack Edmonds
Jack Edmonds
Imagen: Wikimedia Commons

Jack Edmonds

Matemático e informático canadiense de origen estadounidense, pionero de la optimización combinatoria y de la teoría de la complejidad algorítmica · 1934

Nacimiento
5 de abril de 1934
País
Canadá
Sección
Informática

Biografía

Jack Edmonds (Estados Unidos, 1934) es un matemático e informático, nacido en Estados Unidos pero formado y activo en Canadá durante buena parte de su vida. Su obra sentó las bases de la optimización combinatoria, el campo que busca la mejor combinación posible entre muchas opciones, y de la idea de qué problemas pueden resolverse de forma práctica con un ordenador. Su trabajo de los años sesenta sigue siendo una referencia central en la teoría de algoritmos.

Edmonds estudió en la escuela técnica McKinley de Washington, en la que más tarde reconoció la influencia que tuvo en su carrera. Cursó estudios en la Universidad de Duke y se graduó en la Universidad George Washington en 1957. Obtuvo después un máster en 1960 en la Universidad de Maryland, bajo la dirección de Bruce L. Reinhart, con una tesis sobre cómo encajar gráficas en superficies, es decir, cómo dibujar redes de puntos y líneas sobre una superficie sin que se crucen.

Entre 1959 y 1969 trabajó en el Instituto Nacional de Estándares y Tecnología, entonces llamado Oficina Nacional de Estándares. Allí fue miembro fundador, en 1961, de la sección de investigación de operaciones que creó Alan Goldman, quien resultó decisivo para su carrera. Gracias a él pudo asistir a un taller patrocinado por la RAND Corporation en Santa Mónica, California, donde presentó por primera vez sus ideas sobre una clase de algoritmos que podían funcionar con más eficiencia. En aquella época, la mayoría de los especialistas en combinatoria no se ocupaban de los algoritmos, pero Edmonds se sintió atraído por ellos, y estas primeras investigaciones fueron clave para su trabajo posterior.

Entre 1961 y 1965 se dedicó al problema de si los problemas que se verifican rápidamente también pueden resolverse rápidamente, conocido como P frente a NP. En 1966 planteó dos conjeturas sobre esa cuestión, que siguen sin resolverse. Su artículo de 1965 «Caminos, árboles y flores» fue decisivo al proponer la posibilidad de construir una teoría matemática de los algoritmos combinatorios eficientes. En él describe el algoritmo de emparejamiento, ideado en 1961, que sirve para encontrar la mejor manera de unir pares de elementos en una red. Fue el primer algoritmo de tiempo polinómico para ese problema, es decir, uno cuyo tiempo de cálculo crece de forma manejable al aumentar el tamaño de los datos. Edmonds también distinguió entre problemas resolubles en tiempo polinómico y los que no lo son, una idea que dio origen a la tesis Cobham-Edmonds.

En otros trabajos mostró cómo una buena descripción geométrica de un problema de optimización permite diseñar un algoritmo eficiente para resolverlo, utilizando la dualidad de la programación lineal, una técnica que convierte un problema de maximizar o minimizar en otro equivalente. También describió de forma completa los árboles que conectan todos los puntos de una gráfica y, de forma más general, los conjuntos independientes de un matroide, una estructura abstracta que generaliza la idea de independencia lineal. Con ello demostró el teorema de la intersección de matroides, que relaciona problemas de máximo y mínimo y sitúa el problema en las clases NP y co-NP. Junto a Richard Karp trabajó en algoritmos más rápidos para calcular flujos en redes, y es conocido por sus teoremas sobre ramificaciones de peso máximo. Introdujo los polimatroides y, con Richard Giles, los flujos submodulares, y acuñó términos como «clúster» y «bloqueador» en el estudio de hipergráficas. Un hilo conductor de su obra es buscar algoritmos cuyo tiempo de cálculo crezca de forma polinómica con el tamaño de la entrada.

Desde 1969 y hasta su jubilación en 1999 fue profesor en el Departamento de Combinatoria y Optimización de la Facultad de Matemáticas de la Universidad de Waterloo, con la excepción de los años 1991 a 1993. Dirigió la tesis doctoral de una docena de estudiantes y dio clases o pasó estancias de investigación en numerosas universidades de Estados Unidos, Asia y Europa. Entre 1991 y 1993 protagonizó el llamado asunto Edmonds, una disputa con la Universidad de Waterloo: la institución consideró que una carta suya era una renuncia, algo que él negó. El conflicto se resolvió en 1993 con su regreso a la universidad.

Su vida familiar también tiene relación con la ciencia: su hijo Jeff Edmonds es profesor de informática en la Universidad de York, y su esposa, Kathie Cameron, es profesora de matemáticas en la Universidad Laurier.

Entre sus reconocimientos destacan el Premio de Teoría John von Neumann, que recibió en 1985, la distinción de su artículo de 1965 como publicación destacada por el Instituto Nacional de Estándares y Tecnología en 2001, su elección como miembro del Instituto de Investigación de Operaciones y Ciencias de la Gestión en 2002, y un doctorado honoris causa de la Universidad del Sur de Dinamarca en 2006. Su legado es hoy el de un autor que unió la geometría de los poliedros, la lógica de la complejidad y la práctica de los algoritmos, y que estableció la distinción entre problemas tratables e intratables que sigue guiando la informática teórica.

Aportaciones principales

  • 1961Algoritmo de emparejamiento (blossom): método para encontrar el mejor emparejamiento de elementos en una red, descubierto en 1961 y publicado en 1965.
  • 1965«Caminos, árboles y flores»: artículo que propuso la posibilidad de construir una teoría matemática de los algoritmos eficientes.
  • 1965Tesis Cobham-Edmonds: distinción entre problemas resolubles en tiempo polinómico y los que no lo son, base de la noción de problema tratable.
  • 1966Conjeturas NP ≠ P y NP ∩ coNP = P: dos planteamientos sobre la complejidad de los problemas que siguen sin resolverse.
  • 1970Teorema de la intersección de matroides: resultado que relaciona problemas de máximo y mínimo y sitúa el problema en las clases NP y co-NP.
  • Polimatroides: estructura abstracta que generaliza la idea de independencia, introducida por Edmonds.
  • Teorema de descomposición de Edmonds-Gallai: describe las gráficas finitas desde el punto de vista de los emparejamientos.

Maestros y alumnos

Formó a:

William H. CunninghamEphraim KorachWilliam R. PulleyblankKomei FukudaVictor GriffinT. A. JenkynsFrederick Richard GilesArnaldo MandelEtan KochGilberto Calvillo VivesJulian Arturo Araoz DurandMustafa AkgülPeyton Young

Ver su árbol de maestros y alumnos →

Curiosidades y anécdotas

Un instituto con huella

Edmonds ha reconocido en varias ocasiones la influencia de la escuela técnica McKinley, a la que asistió antes de su carrera universitaria.

Un doctorado de una reina

En 2006 la reina de Dinamarca le entregó un doctorado honoris causa de la Universidad del Sur de Dinamarca.

Sus contemporáneos

Mientras vivía Jack Edmonds (1934–)…

Vivieron a la vez

Se descubrió o inventó en esos años

  • 1945
    ComputadoraMáquina programable que recibe datos, los procesa siguiendo instrucciones y entrega resultados, con una arquitectura de hardware y software que puede cambiar de tarea sin cambiar de cuerpo.
  • 1957
    Satélite artificialUn satélite artificial es un objeto construido por personas y puesto en órbita alrededor de un cuerpo celeste, normalmente la Tierra, para recoger información, transmitirla o cumplir una función concreta.
  • 1969
    InternetRed mundial de redes de ordenadores interconectadas que se comunican mediante el conjunto de protocolos TCP/IP.
  • 1971
    Correo electrónicoServicio de red que permite enviar y recibir mensajes digitales entre usuarios mediante una cuenta con dirección propia, como el correo postal pero electrónico.
  • 1973
    Teléfono móvilDispositivo electrónico portátil que permite hacer llamadas por radiofrecuencia mientras el usuario se desplaza dentro de la zona de cobertura de una red.
  • 1989
    World Wide WebSistema de documentos y recursos interconectados por enlaces (hipervínculos) y accesibles a través de Internet mediante navegadores web.

Ver su vida en la línea de tiempo →

Más protagonistas de informática