Lester Randolph Ford

Nacio el  25 de Octubre de  1886 en Missouri, USA
Murio el 11 de Noviembre de  1967 en  Charlottesville, Virginia, USA

Lester R Ford estudió en la Escuela Normal del Estado de Missouri  es Licenciado en Pedagogía

Fue galardonado con una maestría en el Departamento de Matemáticas de la Universidad de Missouri-Columbia en 1912 con una tesis sobre  funciones discontinuas.  Realizó una investigación en Harvard con Maxime Bôcher como su consejero, y se graduó MA en 1913. A partir de 1914 dio clases en la Universidad de Edimburgo en Escocia, donde fue nombrado como Profesor Ayudante en matemáticas después de la muerte de John Urquhart.

 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 mínimo de corte teorema .  Con Richard Bellman , Ford también ha desarrollado el algoritmo de Bellman-Ford para encontrar los caminos más cortos en grafos que tienen bordes negativamente ponderados.

Laster Randolph Ford.[en linea]:http://www-history.mcs.st-andrews.ac.uk/Biographies/Ford.html, 17 de septiembre de 2012, México D:F.

[Laster Randolph Ford] Recuperado: https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhE9CaxKRkZtGTxVS2atL9HgHZEtt_7eG2o0XK5KsgGVUtItTodR-Y3pkW9H5BuFjyJts5ngpykJsoZ6FJBd4FsveZECW0LHebeQyEwZ9FoKGBoQ1dVrWScsshX_UWqa0F01v4v81Opfas/s200/lesterrandolphford_foto.jpg, 17 de septiembre de 2012, México D.F.

Delbert Ray Fulkerson

Delbert Ray Fulkerson (*14 de agosto de 1924 - †10 de enero de 1976) fue un matemático estadounidense que desarrolló como co-autor, y junto con Lester Randolph Ford, Jr., el Algoritmo de Ford-Fulkerson, uno de los algoritmos más utilizados para computar el flujo máximo en una red de flujo.

Fulkerson recibió su Ph.D. en la Universidad de Wisconsin-Madison en 1951. En 1956, su importante artículo científico fue publicado.1 Desde 1979, la Sociedad de Programación Matemática (MPS) y la American Mathematical Society (AMS) otorgan cada tres años el Premio Fulkerson, para aquellos matemáticos que hayan creado artículos importantes en el área de la matemática discreta.

Delbert Ray Fulkerson. [en línea]:http://es.wikipedia.org/wiki/Delbert_Ray_Fulkerson, 17 de septiembre de 2012, México D.F.

[Delbert Ray Fulkerson] Recuperado: https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhnwhVuQkaH6Rb2gBY9oBVSFRmlrFoJKLR4iIm3uTnBqx2AEJ2KDMQ9ZgnAywiWbgjyGoFGN4HCERl8abCRIsIiaICfVPmMG9FotPitLMCjhzMsPtxLaEh58oWQUetf_YSfoaakyFjWrT2Q/s320/FULKERSON.jpg, 17 de septiembre de 2012, México D.F.

Robert W. Floyd 

Nacido en Nueva York, Floyd culminó bachillerato a los 14 años. Se graduó en la Universidad de Chicago en 1953 a los 17 años y como Físico en 1958.

Operador de computadoras en los años 60, publicó sus primeros artículos los cuales fueron de gran influencia y fue nombrado profesor asociado en la Universidad de Carnegie Mellon. Seis años más tarde fue nombrado profesor en la Universidad de Stanford.

Entre sus contribuciones se encuentran el diseño y análisis de algoritmos eficientes para encontrar el camino más corto en ungrafo y para el problema de reconocimiento de frases, pero probablemente su logro más importante fue el ser pionero, con su artículo de 1967 «Assigning Meanings to Programs», en el área de verificación de programas utilizando aserciones lógicas, donde aparece la importante noción de invariante, esencial para demostrar propiedades de programas iterativos.

Floyd recibió el Premio Turing de la ACM en 1978 «por tener una clara influencia en las metodologías para la creación de software eficiente y confiable, y por haber contribuido a la fundación de las subáreas teoría del reconocimiento de frases, semántica de los lenguajes de programación, verificación automatizada de programas, síntesis automatizada de programas y análisis de algoritmos».

Robert W. Floyd. [en linea]: http://es.wikipedia.org/wiki/Robert_W._Floyd , 16 de septiembre de 20012, México D.F.

[Robert W. Floyd] Recuperado de: http://rjlipton.files.wordpress.com/2010/08/050_rt8.jpeg. 16 de septiembre de 2012, México D.F.

Tarea 1.

Triptico de problema de transporte 

https://docs.google.com/document/pub?id=1o6fBKFefEMT673rqw2vEJU3B0pFaohPiOaqCsX5Wk-I

Algoritmo de Prim 

El algoritmo de Prim marco pariona es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyasaristas están etiquetadas.

En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.

El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera independiente por el científico computacional Robert C. Prim en 1957 y redescubierto porDijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de Jarnik.

Robert C. Prim.

 (nace  1921, Sweetwater, Estados Unidos) es un matemático e ingeniero informático.

Rober Prim desarrolló una segunda técnica para la construcción de un árbol óptimo. En este algoritmo voraz, los vértices del grafo se dividen en dos conjuntos: procesados y no procesados. Al principio, sólo hay un vértice en el conjunto P de los vértices procesados y los demás están en el conjunto N de vértices por procesar. Cada iteración del algoritmo incrementa el conjunto P en un vértice, mientras que el tamaño del conjunto N decrece en uno.

Robert C. Prim, [en línea]:http://es.wikipedia.org/wiki/Robert_C._Prim, 09 de septiembre de 20012, México D.F.

Algoritmo de Prim, [en línea]: http://dns.uls.cl/~ej/fit_2009/teo_fit_2009/Lect_2009/Fit_1998/robert.htm, 09 de septiembre de 2012, México D.F.

Algoritmo de Prim, [en línea]: http://es.wikipedia.org/wiki/Algoritmo_de_Prim, 09 de septiembre de 2012, México D.F.

[Algoritmo de Prim], Recuperado de : http://upload.wikimedia.org/wikipedia/commons/thumb/b/b4/Prim_Algorithm_3.svg/200px-Prim_Algorithm_3.svg.png, 09 de septiembre de 2012. 

Algoritmo de Kruskal 

El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor total de todas las aristas del árbol es el mínimo. Si el grafo no es conexo, entonces busca un bosque expandido mínimo (un árbol expandido mínimo para cada componente conexa). El algoritmo de Kruskal es un ejemplo de algoritmo voraz.

Funciona de la siguiente manera:

• se crea un bosque B (un conjunto de árboles), donde cada vértice del grafo es un árbol separado
• se crea un conjunto C que contenga a todas las aristas del grafo
• mientras C es no vacío
  • eliminar una arista de peso mínimo de C
  • si esa arista conecta dos árboles diferentes se añade al bosque, combinando los dos árboles en un solo árbol
  • en caso contrario, se desecha la arista

Al acabar el algoritmo, el bosque tiene un solo componente, el cual forma un árbol de expansión mínimo del grafo.

Este algoritmo fue publicado por primera vez en Proceedings of the American Mathematical Society, pp. 48–50 en 1956, y fue escrito porJoseph Kruskal.

Joseph Kruskal. 

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óncombinatoria, que fue considerado originalmente por Otakar Boruvka (1926) mientras estudiaba la necesidad de electrificación rural en el sur de Moravia en Checoslovaquia.

Algoritmo de Kruskal,[en linea]:http://es.wikipedia.org/wiki/Algoritmo_de_Kruskal, 09 de septiembre de 2012, México D.F.

Joseph Kruskal, [en linea]:http://es.wikipedia.org/wiki/Joseph_Kruskal, 09 de septiembre de 2012, México D.F

[Algoritmo de Kruskal]. Recuperado de: http://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Minimum_spanning_tree.svg/220px-Minimum_spanning_tree.svg.png, 09 de septiembre de 2012, México D.F.

Edsger Dijkstra

Nació el 11 de mayo de 1930, murió el 6 de agosto de 2002

Matemático e informático Holandés.

Dijkstra nació el 11 de mayo de 1930 en Rotterdam, Holanda, hijo de un químico y una matemática. Estudio física 

y matemáticas en la Univ. de Leyden  terminando en 1951. Más tarde, un doctorado en física teórica en la misma universidad en 1956, seguido de un Ph.D. en 1959 en la Univ. de Amsterdam. En 1952 comenzó a trabajar en el Centro Matemático de Amsterdam donde aprendió a programar, siendo el primer programador en Holanda. En 1962 pasó a ser profesor en la Univ. 

Tecnológica de Eindhoven hasta 1984. En paralelo, desde 1973 a 1984 fue investigador para Burroughs. Finalmente, en 1984 

aceptó la cátedra Schlumberger en la Univ. de Texas at Austin, hasta que jubiló en 1999. Finalmente, el mes pasado, 

enfermo de cáncer, murió en Nuenen, Holanda. Dijkstra se casó en 1957 con Maria Debets (más conocida como Ria) y tuvo tres hijos: Marcus, Femke y Rutger, el único que siguió sus pasos en la computación. 

A fines de los años 1950 fue uno de los principales diseñadores del lenguaje de programación ALGOL.

Se destacó tambien en teoría de grafos donde descubrió el algoritmo que lleva su nombre para hallar el camino más corto entre dos vértices de un grafo dirigido con pesos no negativos en sus aristas.

En el campo de la programación estructurada, demostró el Teorema de Dijkstra según el cual todo programa escrito en un lenguaje de programación imperativo puede obtenerse mediante la combinación secuencial de estructuras de decisión y repetición. Definió también la notación de comandos custodiados (guarded commands) para razonar sobre programas no-determinísticos.

En 1972 recibió el Premio Turing.

Su estilo incisivo provocó numerosos debates en el ambiente profesional; se pueden mencionar su suscinta condena del salto incondicional (La sentencia Go To considerada como perjudicial) o su empeño en enseñar Ciencias de la Computación como un capítulo de las matemáticas aplicadas.

[Edgser Dijkstra].Recuperado  de : http://www.tugurium.com/gti/images/D/Dijkstra_Edsger_Wybe.jpg,09 de septiembre de 20012.

Edgser Dijkstra,[en linea]: http://enciclopedia.us.es/index.php/Edsger_Dijkstra, 09 de septiembre de 2012

Edgser Dijkstra,[en linea]: http://users.dcc.uchile.cl/~rbaeza/inf/dijkstra.html, 09 de septiembre de 2012.