Biografía de Lester Randolph Ford, Jr

Lester Randolph Ford, Jr

   

Nacido el 23 de septiembre 1927, Houston

Es un  matemático americano especializado en el flujo de red problemas. Él es el hijo del matemático Lester R. Ford, padre .

El papel de Ford con DR Fulkerson en el problema de flujo máximo y el algoritmo de Ford-Fulkerson para resolverlo, publicado como un informe técnico en 1954 y en un diario en 1956, estableció el máximo de flujo min de corte teorema . Con Richard Bellman , Ford también desarrolló el algoritmo de Bellman-Ford para encontrar los caminos más cortos en los gráficos que tienen bordes negativamente ponderado.

También le acredita su trabajo 'Pointwise Discontinuous Functions' que era la base de su trabajo para un grado de M.S. del departamento de matemáticas en la universidad de Missouri-Colombia en 1912. Tal fue su contribución a las matemáticas, que en 1964 se estableció el Lester R. Ford Award para reconocer la contribución a las matemáticas de excelentes autores matemáticos publicados en The American Mathematical Monthly o Mathematics Magazine. 

Junto con Richard E. Bellman (26 de agosto 1920 – 19 marzo de 1984) desarrollaron el algoritmo de 'corrección de etiquetas' que calcula el camino más corto en un digrafo ponderado (donde incluso y a diferencia de Dijkstra, los pesos de los arcos pueden ser negativos). 

La mayoría del trabajo de Ford lo hizo en la colaboración con Fulkerson, al parecer los dos hacían una buena asociación. Sin embargo, en 1956 presentó varios artículos firmados por él sólo. Ha sido el autor de diversos algoritmos que se han refinado con los años y que todavía se utilizan para solucionar la mayoría de problemas de grafos. 

Referencias: 

Lester Randolph Ford Jr. (En linea) http://arodrigu.webs.upv.es/grafos/doku.php?id=algoritmo_bellman_ford
Consulta 23 de Septiembre de 2012
 

Lester Randolph Ford Jr. (Imágen) http://arodrigu.webs.upv.es/grafos/doku.php?id=algoritmo_bellman_ford
Consulta 23 de Septiembre de 2012
 

Biografia de Joseph Kruskal

Joseph Kruskal

 

Joseph B. Kruskal (29 de enero de 1928 – Maplewood, Nueva Jersey, 19 de septiembre de 2010)¹ fue un matemático y estadístico estadounidense.

  

Biografía

Investigador del Math Center (Bell-Labs), en 1956 descubrió un algoritmo para la resolución del problema del árbol recubridor mínimo, el cual es un problema típico de optimización combinatoria, que fue considerado originalmente por Otakar Boruvka (1926) mientras estudiaba la necesidad de electrificación rural en el sur de Moravia en Checoslovaquia.
El objetivo del algoritmo de Kruskal es construir un árbol (subgrafo sin ciclos) formado por arcos sucesivamente seleccionados de mínimo peso a partir de un grafo con pesos en los arcos.
Un árbol (spanning tree) de un grafo es un subgrafo que contiene todos sus vértices o nodos. Un grafo puede tener múltiples árboles. Por ejemplo, un grafo completo de cuatro nodos (todos relacionados con todos) tendría 16 árboles.
La aplicación típica de este problema es el diseño de redes telefónicas. Una empresa con diferentes oficinas, trata de trazar líneas de teléfono para conectarlas unas con otras. La compañía telefónica le ofrece esta interconexión, pero ofrece tarifas diferentes o costes por conectar cada par de oficinas. Cómo conectar entonces las oficinas al mínimo coste total.
La formulación del MST también ha sido aplicada para hallar soluciones en diversas áreas (diseño de redes de transporte, diseño de redes de telecomunicaciones - TV por cable, sistemas distribuidos, interpretación de datos climatológicos, visión artificial - análisis de imágenes - extracción de rasgos de parentesco, análisis de clusters y búsqueda de superestructuras de quasar, plegamiento de proteínas, reconocimiento de células cancerosas, y otros).
Otra aplicación menos obvia es que el árbol de coste total mínimo puede ser usado como solución aproximada al problema del viajante de comercio, el cual es NP-completo. La manera formal de definir este problema es encontrar la trayectoria más corta para visitar cada punto al menos una vez. Nótese que si se visitan todos los puntos exactamente una vez, lo que se tiene es un tipo especial de árbol. En el ejemplo anterior, 12 de los 16 árboles son trayectorias de este tipo. Si se tiene una trayectoria que visita algunos vértices más de una vez, siempre se puede soltar algunos nodos del árbol. En general el peso del árbol total mínimo es menor que el del viajante de comercio, debido a que su minimización se realiza sobre un conjunto estrictamente mayor. Existen diferentes algoritmos y maneras de usar el árbol de coste total mínimo para encontrar la solución al problema del viajante de comercio (con resultados cercanos al óptimo).

Familia

Joseph era hermano del matemático y estadístico William Kruskal (autor de la Prueba de Kruskal-Wallis), y del matemático y físico Martin Kruskal (autor de las coordenadas de Kruskal-Szekeres).

Referencias:

Joseph Kruskal (En linea) http://es.wikipedia.org/wiki/Joseph_Kruskal

Consulta 23 de Septiembre de 2012 <Anónimo>

Joseph Kruskal (Imagen) http://www.umass.edu/wsp/images/kruskal2.jpg
Consulta 23 de Septiembre de 2012