Tarea 4. Boletín electrónico

Tarea 4

Tarea 3. Video de la Programación Entera

Tarea 3. Guión de video

Tarea 3. Guión de video

Tarea 2 Redes de Optimización‎

Tarea 2

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.

Su trabajo ha puesto la base de casi toda la investigación en flujos de grafos. El artículo de Ford y de Fulkerson (1956) con el problema de flujo máximo estableció el famoso teorema del flujo máximo - mínimo corte.

Se puede considerar un grafo como una red de flujo. Donde un nodo fuente produce o introduce en la red cierta cantidad de algún tipo de material, y un nodo sumidero lo consume. Cada arco, por tanto, puede considerarse como un conducto que tiene cierta capacidad de flujo. De igual modo que en redes eléctricas (Leyes de Kirchhoff), la suma de flujos entrantes a un nodo, debe ser igual a la suma de los salientes (principio de conservación de energía), excepto para el nodo fuente y el nodo sumidero.

Por tanto, el problema de flujo máximo se enuncia como: ¿cuál es la tasa a la cual se puede transportar el material desde el nodo fuente al nodo sumidero, sin violar las restricciones de capacidad?. Este algoritmo se puede usar para resolver modelos de: transporte de mercancías (logística de aprovisionamiento y distribución), flujo de gases y líquidos por tuberías, componentes o piezas en líneas de montaje, corriente en redes eléctricas, paquetes de información en redes de comunicaciones, tráfico ferroviario, sistema de regadíos, etc.

Una red de flujo es un grafo dirigido G=(V,E) donde cada arco (u,v) perteneciente a E el número de arcos del grafo; tiene una capacidad no negativa. Se distinguen dos nodos: la fuente o nodo s, y el sumidero o nodo t. Si existen múltiples fuentes y sumideros, el problema se puede simplificar añadiendo una fuente común y un sumidero común. Este algoritmo depende de tres conceptos principales:

Un camino de aumento, es una trayectoria desde el nodo fuente s al nodo sumidero t que puede conducir más flujo.

La capacidad residual es la capacidad adicional de flujo que un arco puede llevar c_f (u,v) = c(u,v) - f(u,v).

Teorema de Ford-Fulkerson (1962): En cualquier red, el flujo máximo que fluye de la fuente al destino es igual a la capacidad del corte mínimo que separa a la fuente del destino.

El algoritmo es iterativo, se comienza con f(u,v)=0 para cada par de nodos y en cada iteración se incrementa el valor del flujo buscando un camino de aumento. El proceso se repite hasta no encontrar un camino de aumento.

Referencias:

• "Algoritmo_ford_fulkerson â Grafos -???? Software Para La construccià ³ n, Edicià ³ n Anà ¡lisis Y De Grafos". Algoritmo_ford_fulkerson â???? Grafos . Np, nd Web. 17 de septiembre 2012. <http://arodrigu.webs.upv.es/grafos/doku.php?id=algoritmo_ford_fulkerson>.
• "Delbert Ray Fulkerson." - Wikipedia, La Enciclopedia Libre. N.p., n.d. Web. 17 Sept. 2012. <http://es.wikipedia.org/wiki/Delbert_Ray_Fulkerson>.

Imagen obtenida: 

• N.p., n.d. Web. 17 Sept. 2012. <http://arodrigu.webs.upv.es/grafos/lib/exe/fetch.php?media=delbertrayfulkerson_foto.jpg>.

Lester Randolph Ford Jr.

Lester Randolph Ford, Jr. (nacido el 23 de septiembre 1927, Houston ) es un americano matemático especializado en redes de flujo problemas, uno de los pioneros en el campo de la programación de flujos en grafos. Él es el hijo del matemático Lester R. Ford, padre (quién también es un matemático distinguido) .

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 ha desarrollado el algoritmo de Bellman-Ford para encontrar los caminos más cortos en grafos que tienen bordes negativamente ponderados.

 L. R. Ford Sr es elogiado por su ejemplar trabajo en matemáticas al inventar una interpretación geométrica absolutamente maravillosa de la serie de Farey. 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. Fue redactor de American Mathematical Monthly, de 1942-1946, y el presidente de Mathematical Association of America, 1947-1948. Ford Sr. y Ford Jr. son co-autores de Automorphic Functions cuál fue publicado cerca por McGraw-Hill en 1963.

Mientras trabajó en RAND CORPORATION, Ford Jr publicó numerosos artículos que no solo establecieron la base de los flujos de red sino también la futura investigación en este campo. En 1962 Priceton University Press publicó su libro Flow in Networks con D. R. Fulkerson como co-autor. Este libro contiene todo su trabajo sobre redes.

Referencias:

• "LR Ford, Jr." Wikipedia . Wikimedia Foundation, 09 de julio de 2012. Web. 17 de septiembre 2012. <http://en.wikipedia.org/wiki/L._R._Ford,_Jr.>.
• "Algoritmo_bellman_ford â Grafos -???? Software Para La construccià ³ n, Edicià ³ n Anà ¡lisis Y De Grafos". Algoritmo_bellman_ford â???? Grafos . Np, nd Web. 17 de septiembre 2012. <http://arodrigu.webs.upv.es/grafos/doku.php?id=algoritmo_bellman_ford>.
• "OEDKARINA." : Lester Randolph Ford Jr. N.p., n.d. Web. 17 Sept. 2012. <http://oedkarina.blogspot.mx/2011/09/lester-randolph-ford-jr.html>.

Imagen obtenida: 

• N.p., n.d. Web. 17 Sept. 2012. <https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj_Tt9A8hU0e3tkYQN783_d8eCTKX4-BofK8dLhXMUjeYlOHManq6tVBxLQM7yQYlYnid1S3WlRB37aSAcnA_HucXm_BOgWUxLL7RgnUXo5MDEYLPkmJAJk0UxZgGwhlwBrGszxmHgXaMk/s1600/Lester+R+Ford+Jr.jpg>.

Robert W. Floyd

Robert W. Floyd (8 de junio de 1936 - 25 de septiembre de 2001) fue un prominente científico estadounidense en informática.

Nacido en Nueva York , Floyd terminó la escuela a los 14 años. En la Universidad de Chicago, recibió una licenciatura en artes liberales en 1953 a los 17 años y una segunda licenciatura en física en 1958.

Floyd se convirtió en un miembro del personal de la Fundación Armour Research (ahora IIT Research Institute) en el Illinois Institute of Technology en 1950. Convertirse en un operador de la computadora en la década de 1960, comenzó a publicar numerosos trabajos notables y fue nombrado profesor asociado en la Universidad Carnegie Mellon en el momento en que tenía 27 años y se convirtió en profesor titular en la Universidad de Stanford seis años después. Él obtuvo esta posición sin un Ph.D.

Recibió el Premio Turing de la ACM en 1978 "por tener una clara influencia sobre las metodologías para la creación de software eficiente y confiable, y para ayudar a encontrar los siguientes subcampos importantes de la informática: la teoría del análisis , las semántica de los lenguajes de programación , automático programa verificación , automático síntesis de programas , y análisis de algoritmos".

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 un grafo 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 trabajó en estrecha colaboración con Donald Knuth , en particular por lo que el revisor principal para el libro seminal de Knuth El arte de programar ordenadores , y es la persona más citada en este trabajo. Fue el co-autor, junto con Richard Beigel, del libro de texto El lenguaje de las máquinas: una Introducción a la computabilidad y Lenguajes Formales (1994, WH Freeman and Company, ISBN 978-0-7167-8266-7 ). Floyd supervisados ​​7 doctorados.

Floyd se casó y se divorció dos veces, incluso con equipo científico Christiane Floyd , y tenía cuatro hijos. Sus pasatiempos incluyen senderismo y era un ávido backgammon jugador.

En una ocasión estaban atrapados en el aeropuerto O'Hare de Chicago durante horas, esperando nuestro vuelo para salir, debido a una tormenta de nieve. Cuando nos sentamos en nuestra puerta, Bob me preguntó, de manera casual, "¿sabes cómo jugar al backgammon?", Respondí yo conocía las reglas, pero ¿por qué quieres saber? Bob dijo que desde que tuvimos que esperar varias horas tal vez deberíamos jugar algunos juegos, con apuestas pequeñas, por supuesto. Luego buscó en su maletín y sacó un juego de backgammon.

Mi papá me enseñó muchas cosas. Uno de ellos fue a desconfiar de cualquiera que sugiera una partida de billar por dinero, y luego se abre un estuche negro y comienza a atornillar un palo de billar. Me imaginé que este consejo generalizado a todo el que viajaron con su propio set de backgammon. Le dije a Bob que yo no iba a jugar por dinero, ni hablar.Empujó un poco, pero finalmente dijo bien. Procedió en lugar de darme una lección libre en el arte y la ciencia de jugar backgammon.

Yo tenía razón para pasar a jugar con él por dinero en cualquier juego. La lección fue muy divertido. Más tarde me enteré que durante años había estado trabajando en aprender el juego. Él tomó muy en serio a jugar al backgammon, estudió el juego y sus matemáticas, y era un profesional cercano. Creo que fue más que un hobby. Al igual que su investigación, Bob tomó en serio lo que él hizo, y es totalmente coherente que sería genial en backgammon.

Referencias:

• "Robert W. Floyd." - Wikipedia, La Enciclopedia Libre . Np, nd Web. 16 de septiembre 2012. <http://es.wikipedia.org/wiki/Robert_W._Floyd>.
• "Robert W. Floyd." Wikipedia . Wikimedia Foundation, 09 de junio de 2012. Web. 16 de septiembre 2012. <http://en.wikipedia.org/wiki/Robert_W._Floyd>.

Imagen obtenida: 

• Np, nd Web. 16 de septiembre 2012.<http://cs.stanford.edu/system/files/memoriam/hhfffhcc_0.png?1330125978>.