Unidad 2. Participación 3

Encuentre la trayectoria más corta del nodo 1 al nodo 6

Resolviendo por el metodo de Dijkstra:

La trayectoria más corta del nodo 1 al nodo 6 es: 1-2-4-6 con un costo de 31

Unidad 2. Participación 2

 Se tiene una red de comunicaciones entre dos estaciones 1 y 7. Las probabilidades de que un enlace de la red funcione sin fallar se muestran en la siguiente tabla. Los mensajes se mandan de la estación 1 a la estación 7 y el objetivo es determinar la ruta que maximice la probabilidad de una buena transmisión.

Plantear la red y resolver como un problema de ruta más corta.

Red:

Resolviendo por el método de Dijkstra

La ruta que maximice la probabilidad de una buena transmisión será: 1-2-4-3-6-7 y la probabilidad es de 0.52326

Unidad 2. Participación 1

1. Las distancias en millas entre ciudades de Indiana: Gary, Fort Wayne, Evansville, Terre Haute y South Bend, se muestran en la siguiente tabla. Es necesario construir un sistema estatal de carreteras que una todas estas ciudades. Suponga que por razones políticas no es necesario construir una carretera a Gary y Fort ¿Cuál es la longitud mínima de la carretera requerida?

Planteando la red:

Resolviendo por Prim, obtenemos la siguiente red:

Las lineas marcadas por naranja son las carreteas que se deben construir , y el costo será de 414

Lester Randolph Ford, Jr.

Fecha y lugar de nacimiento: nacido el 23 de septiembre 1927, Houston

Trabajos: Se 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. 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.

Conocido por: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, 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.


Referencias
http://en.wikipedia.org/wiki/L._R._Ford,_Jr.
http://arodrigu.webs.upv.es/grafos/doku.php?id=algoritmo_bellman_ford

Delbert Ray Fulkerson

Fecha y lugar de nacimiento: 14 de agosto de 1924 en Estados Unidos

Estudios: Recibió su Ph.D. en la Universidad de Wisconsin-Madison en 1951

Trabajos: En 1956, su importante artículo científico fue publicado. 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

Conocido por: 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

Fecha de muerte: 10 de enero de 1976

Referenciashttp://es.wikipedia.org/wiki/D._R._Fulkerson

Robert W. Floyd

Fecha y lugar de nacimiento: Nacio en Nueva York el 8 de junio de 1936

Estudios: 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

Trabajos: 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

Conocido por: 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

Fecha de muerte: 25 de septiembre de 2001

Referencias
http://es.wikipedia.org/wiki/Robert_W._Floyd
http://histsoc.stanford.edu/pdfmem/Floyd_Robert.pdf

Video del Problema de Asignación

http://www.youtube.com/watch?v=vJQUh6Qv6Bw