Robert Floyd

ROBERT FLOYD

Vida:

Nació el 8 de junio de 1936 en la ciudad de Nueva York. Falleció el 25 de septiembre de 2001.

Educación y trabajo:

Floyd culminó bachillerato a los 14 años. Sus padres se trasladaron  más de una docena de veces antes de que el fuera   a la universidad,un niño prodigio, había leído todos los libros que caían en sus manos, recibió una beca para entrar en la Universidad de Chicago a los 15 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.

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».

Aportaciones:

Una de sus aportaciones mas importante y por el que hoy es conocido es el diseño del algoritmo de Floyd, que de manera eficiente encuentra todos los caminos más cortos en un gráfico, y el trabajo en el análisis. En un documento aislado que introdujo el concepto importante de difusión de errores para las imágenes de la representación, también llamado Floyd-Steinberg tramado (a pesar de que distinguidos tramado de difusión). Fue pionero en el campo de verificación de programas con afirmaciones lógicas con el artículo de 1967 asignar significados a los programas. Esta fue una importante contribución a lo que más tarde se convirtió en la lógica de Hoare.

REFERENCIAS

http://en.wikipedia.org/wiki/Robert_W._Floyd

http://www.ithistory.org/honor_roll/honor-roll-alpha.php?navletter=F

http://resources.metapress.com/pdf-review.axd?code=pv215ulwl4679m54&size=largest

Vídeo (Tarea2)

Problema de asignación. 

Biografía de Dijkstra

Edsger Wybe Dijkstra

Vida:

Dijkstra nació el  11 de mayo de 1930 en Rotterdam, Holanda y murió el 6 Agosto 2002, Texas. Su padre era un químico que trabajaba como profesor de química y el superintendente, y su madre una matemática.

Educación y trabajo:

En 1945, a la edad de 15 años, Dijkstra decidió que le gustaría estudiar Derecho.Ingreso a la Universidad de Leiden estudió matemáticas y física teórica en la. En 1951, tomó un curso de programación de tres semanas para los equipos electrónicos de la Universidad de Cambridge, un curso que con el tiempo cambiaría su vida. En marzo de 1952, cuando aún estaba en la escuela, Dijkstra comenzó a trabajar a tiempo parcial como programador de computadoras en el Centro Matemático en Amsterdam. . Terminó con los requisitos para su carrera de Física en 1956 y comenzó a perseguir su interés en la programación con el Centro de Matemáticas. en 1957, su profesión fue declarado oficialmente como "físico teórico". Trabajó como investigador para Burroughs Corporation a principios de los años 1970. En la Universidad de Texas en Austin, Estados Unidos, ocupó el Schlumberger Centennial Chair in Computer Sciences. Se retiró en 2000.

Aportaciones:

Su aportación mas importante y por la que es conocido es el algoritmo que lleva su nombre que creó mientras fue empleado con el Centro de Matemáticas, o llamado también  "El camino más corto.”, mismo que  se dice descubrió gracias a un problema de determinar la ruta más corta entre dos puntos en un mapa del ferrocarril. Otras aportaciones importantes como la notación polaca inversa y el relacionado algoritmo shunting yard, THE multiprogramming system, el algoritmo del banquero y la construcción del semáforo para coordinar múltiples procesadores y programas. Otro concepto debido a Dijkstra, en el campo de la computación distribuida, es el de la auto-estabilización, una vía alternativa para garantizar la confiabilidad del sistema.

Referencias

http://es.wikipedia.org/wiki/Edsger_Dijkstra

http://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra

http://www.dcc.uchile.cl/~rbaeza/inf/dijkstra.html

http://mictlan.utm.mx/html/jaws/html/index9775.html?page/grafosdijkstra

http://www.bookrags.com/biography/edsger-wybe-dijkstra-wcs/

Algoritmo de PRIM

El algoritmo de Prim 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 cuyas aristas están etiquetadas.

El algoritmo  consiste en encontrar 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 por Dijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de Jarnik.

Pseudo código del algoritmo:

La idea básica consiste en añadir, en cada paso, una arista de peso mínimo a un árbol previamente construido. Más explícitamente:
   Paso 1. Se elige un vértice u de G y se considera el árbol S={u}
   Paso 2. Se considera la arista e de mínimo peso que une un vértice de S y un vértice que no es de S, y se hace S=S+e
  Paso 3. Si el nº de aristas de T es n-1 el algoritmo termina. En caso contrario se vuelve al paso 2

Referencia:

http://www.dma.fi.upm.es/gregorio/grafos/PrimKruskal/prim/prim.html

http://es.wikipedia.org/wiki/Algoritmo_de_Prim

Guion del vídeo (tarea 2)

El guion esta en esta dirección:

https://docs.google.com/present/view?id=dcthbn88_0hrhxjmfj

Tabla resumen: Problema de Asignación

P7. Problema de Maximización

Unidad 1 M. Transporte y Asignación

Participación 7

Problema de Maximización

Dos plantas abastecen a tres clientes con suministros médicos. Las GANANCIAS unitarias, junto con los suministros y demandas se dan en la siguiente tabla:

	1	2	3	Oferta
1	$55	$65	$80	35
2	$10	$15	$25	50
Demanda	10	10	10

1.       ¿Cómo cambian los criterios de los métodos que generan solución inicial?

Esquina Noroeste:

Este método se usa tal cual es, sin cambio alguno.

Costos Mínimos:

El criterio que cambia en éste método es el primer paso en lugar de tomar la casilla de costo mínimo se toma la casilla de mayor costo (en este caso mayor ganancia).

Vogel:

El único criterio cambiante es para obtener las penalizaciones se hace la diferencia entre los ganancias máximas. Y se usa el procedimiento normal.

2.       ¿Qué criterio se utilizaría para determinar la variable de entrada?

Usando el método de multiplicadores con la diferencia de que ahora se usará la variable no básica más negativa.

3.        ¿Cómo es el criterio de la variable de salida?

Es el mismo que se usa al minimizar.

4.       Encontrar la solución óptima.

Para obtener la solución óptima se usa el método de Vogel con los cambios mencionados anteriormente.

Los resultados del problema son:

      X11=10

      X12=10

      X13=10

      Máx Z=2000

Interpretación del resultado:

De la planta 1 se enviarán 10 suministros al cliente 1, 10 suministros al cliente 2 y 10 suministros al cliente 3, quedando así las demandas satisfechas.