Robert W. Floyd

Nació el 8 de Junio de 1936 en Nueva York, Estados Unidos de América.

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

Bibliografia:

• Hispavista. Disponible en: http://biografia.cine.hispavista.com/n206240-robert-floyd. (Consultado 23 de Septiembre del 2011)
• Wikipwdia. Disponible en: http://es.wikipedia.org/wiki/Robert_W._Floyd. (Consultada 23 de Septiembre del 2011)

Tarea 2: Problema de Asignacion

Edsger Wybe Dijkstra

Edsger Wybe Dijkstra

"El esfuerzo de utilizar las máquinas para emular el pensamiento humano siempre me ha parecido bastante estúpido. Preferiría usarlas para emular algo mejor." E.W.Dijkstra.

Nació el 11 de Mayo de 1930 en Rotterdam, Holanda.

De joven, asistió a la escuela secundaria de Rotterdam. Él quería estudiar Derecho y asi poder representar a los Paises Bajos en las Naciones Unidas. Pero, en 1948 realizó los exámenes finales de su etapa en la escuela secundaria y saco notas excelentes en matemáticas, física, química y biología, y tanto sus padres como sus profesores intentaron persuadirle para que se decantara por una carrera de ciencias. Finalmente, decidió estudiar física teórica en la Universidad de Leyden.

Tres años después, en 1951, Dijkstra vio un anuncio de la Universidad de Cambridge sobre un curso de tres semanas que trataba la programación en computadores. Se interesó mucho por este curso y decidió apuntarse, ya que lo veía como una oportunidad esta actividad, que consideraba muy ligada a su campo, la física teórica.

Dijkstra completó sus estudios en física teórica en la Universidad, graduándose en 1956. También en 1956, el Centro de Matemáticas de Amsterdam, en el que trabajaba completó la construcción de una nueva computadora y quería hacer una demostración pública. Para ello, Dijkstra, plateó el problema de encontrar el camino mas corto entre dos ciudades de los Países Bajos, Publicó su algoritmo que ha perdurado hasta nuestros días, y conocido popularmente como " el algoritmo de Dijkstra" ( o algoritmo de caminos mínimos).

También en 1959 fue galardonado con el doctorado de la Universidad de Amsterdam por su tesis La comunicación con un equipo automático.

Dijkstra también colaboró con el equipo de desarrollo del lenguaje de programación ALGOL-60. Hizo varias contribuciones importantes: la introducción explícita de la recursividad y la noción de "pila". Dijkstra, junto con uno de sus colegas en el Centro de Matemáticas, escribió el primer compilador de ALGOL-60, que se completó en agosto de 1960.

Muere el 06 de Agosto del 2002

Bibliografia:

• http://es.wikipedia.org/wiki/Edsger_Dijkstra
• http://enciclopedia.us.es/index.php/Edsger_Dijkstra
• http://histinf.blogs.upv.es/2010/10/28/dijkstra/

Algunos Videos:

Guión de un video de una aplicación de un problema de asignación

	Imágenes a colocar	Texto a colocar	Sonido o Efectos	Segundos
Introducción		Problema de asignación	*Grabación 1  *Muse - Resistance	50seg
Planteamiento		Planteamiento. xij = Persona i hace el trabajo j Min Z = 50x11 + 46x12 + 42x13 + 40x14 + 51x21 +48x22 + 44x23 +47x32 +45x33 +  45x34 Sujeto a  x11 + x12 + x13 + x14 ≤ 2 x21 + x22 + x23 ≤ 2 x32 + x33 + x34 = 1 x11 + x21 = 1 x12 + x22 + x32 = 1 x13 + x23 + x33 = 1 x14 + x34 = 1                 xij ≥ 0	*Grabación 2 *Grabación 3 *Muse - Resistance	80seg.
Resolución		Resolución	*Grabación 4 *Muse - Resistance	1.20seg
Interpretación		Resultados. Min Z = 182	*Grabación 5 *Muse - Neutron Star Collision	20seg
Créditos de imágenes, voces, música y producción		Voces: Jonatan Méndez, Maria Cruz, Fernando López y Saúl Martínez Producción: Jonatan Méndez, Maria Cruz y Saúl Martínez	*Grabación 6 *Muse - Neutron Star Collision	30seg

*Grabación 1: Problema de asignación.

Los Húngaros Denes König y Jeno Egerváry iniciaron con el desarrollo de un método para la solución del problema de asignación. Harold Kuhn creó el método Húngaro con los trabajos de König y Egerváry.

Problema de asignación es un caso especial del problema de transporte en el que lo que se asigna son recursos para realizar tareas. Los asignados no solo pueden ser personas, sino también maquinas, vehículos, plantas, periodos de trabajo, etc.

Debe de cumplir con:

1. El número de asignados debe ser igual al número de tareas, a cada trabajador se le asigna una tarea, cada tarea debe ser realizada por un trabajador, existen costos relacionados C_ij , el objetivo es determinar cómo asignar los trabajadores a las tareas al menor costo. 
2. Es un modelo de programación binario, es decir, que solo toma valores de cero y uno.

*Grabación 2: Se resolverá el siguiente ejercicio:

Una compañía recibe ofertas para cuatro trabajos de construcción. Tres personas realizaron ofertas en relación con los trabajos. Sus ofertas en miles de dólares se dan en la tabla. La persona 1 puede realizar un trabajo pero las personas 2 y 3 pueden llevar a cabo dos tareas. Determinar la asignación de costo mínimo de personas a trabajos.

La tabla es la siguiente.

*Grabación 3: El modelo de programación lineal es este.

La red aparece ya balanceada, puesto que las Personas 2 y 3 pueden ser asignados a dos trabajos, es por eso que colocamos un par de nodos extra que significa la opción de poder asignarle a una persona 2 trabajos, puesto que el problema es de asignación: solo una persona puede ser asignado a un trabajo y viceversa. Entonces ficticiamente tenemos 5 Personas y 4 trabajos, eso implica que el trabajador 2 o 3 realizaran solo un trabajo y el otro 2, por lo tanto debemos añadir un trabajo ficticio.

La tabla de transporte es la siguiente.

Se muestra 5 renglones y 5 columnas por lo antes dicho, en el costo del renglón 1 columna 5 se le colocara M porque el problema dice que la Persona 1 debe forzosamente hacer un trabajo.

Se usará el método Húngaro para la resolución del problema.

*Grabación 4: 

Al comienzo del método debemos de encontrar el costo menor de cada renglón y restárselo respectivamente. En nuestro caso esos números son: en el renglón 1 es el número 40, en el 2, 3, 4 y 5 es el 0;  y el resultado lo anotamos en otra tabla. Después buscamos el costo menor en las columnas de la nueva tablas y se lo restamos respectivamente. En nuestro ejemplo son: en la columna 1 es el 10, en la 2 es el 6, en la 3 es el 2 y en las columnas 4 y 5 es el 0; y volvemos a escribir los resultados en una nueva tabla, a esta se llama Matriz Reducida.

Una vez obtenida esta matriz, a esta le trazamos líneas que cubran la mayor cantidad de ceros con la mínima cantidad de líneas. En nuestro caso trazamos una línea que cubra todo el renglón 1 y toda la columna 5 y con esto cubrimos la mayor cantidad de ceros.

Como todavía el número de líneas hechas no es igual al número de renglones, elegimos el costo menor de toda la tabla discriminando los costos que estén en alguna línea y después se lo restamos a los costos que no estén en las líneas y se los sumamos a los costos que se encuentren en las intercesiones de líneas. En nuestro caso ese valor es el 41.

Una vez haciendo lo anterior volvemos a cubrir con el menor número de líneas el mayor número de ceros. En nuestro caso, ahora quedarían las líneas en el renglón 1 y las columnas 1, 2 y 5. Entonces ahora tenemos 4 líneas, por lo tanto buscamos el costo mas pequeño de la tabla que no esté en las líneas; este es el 1.

Una vez restado el 1 volvemos a trazar las líneas, y ahora nos quedan en los renglones 1, 2 y 3 y en las columnas 2 y 5. Por lo tanto ya tenemos 5 líneas, solo nos queda asignar los trabajos.

Elegimos el única cero que este en la columna o renglón (si hay más de uno elegir indistintamente), en nuestro caso elegimos el que se encuentra en la columna 4 y tachamos los ceros que se encuentren en su renglón y columna. Ahora buscamos otro cero que se encuentre solo, en nuestro caso no hay, entonces elegimos indistintamente; elegimos el que se encuentra en la columna 1 renglón 2 y tachamos los ceros que se encuentren en su renglón y columna.

Otra vez buscamos algún cero que se encuentre solo, entonces elegimos el de la columna 3 renglón 3 y tachamos los que se encuentren en su renglón y columna. Después elegimos un cero que se encuentre solo, y volvemos a encontrar que no hay, entonces elegimos indistintamente, nosotros elegimos el del renglón 4 columna 2. Por ultimo solo nos queda un cero y es el de la columna 5 renglón 5.

*Grabación 5: Viendo la tabla concluimos que a la Persona 1 se le asignara el trabajo 4, a la Persona 2 se le asignara el trabajo 1 y 3, y por ultimo a la Persona 3 se le asignara el trabajo 2. Esta asignación costara 182.

*Grabación 6:

Voces: Jonatan Méndez Lopez, María Cruz Hernandez, Saúl Martínez Chavelas.

Producción: Jonatan Méndez Lopez, María Cruz Hernandez, Saúl Martínez Chavelas.

Música: Neutron Star Collision, Muse. Resistance, Muse.

Facultad de estudios superiores Acatlán. Septiembre del 2011.

Vídeo:

Transporte y Asignación: Método de Mínimos Costes

Método de Mínimos Costes

Pasos del método:

1. Hay que identificar las celdas con los costos mínimos. Si encuentras el mismo costo mínimo mas de una ves escoges arbitrariamente la casilla.
2. De la celda escogida comparamos el número de la oferta y la demanda, escogemos el menor y se lo asignas a la casilla, restamos ese número a la oferta y a la demanda.
3. La oferta o demanda que quede en 0 se cancelará el renglón o columna. Y para elegir el costo mínimo siguiente no se toma en cuenta las celdas canceladas.
4. Se repite los pasos anteriores hasta que solo quede una columna o renglón. Cuando suceda esto, se llegara al termino del método y se le asignara el valor de la oferta o demanda (es el mismo valor si esta equilibrado).

	1	2	3	4	Oferta
1	8	6	10	9	50
2	9	12	13	7	35
3	14	9	16	5	40
Demanda	20	45	30	30

Solución:

	1	2	3	4
1	8 5	6 45	10	9	50	5	0
2	9 5	12	13 20	7	35	20	0
3	14	9	16 10	5 30	40	10	0
	20	45	30	30
	15	0	10	0
	0		0

Z=880

¿Cuál es la diferencia entre el método de la esquina noroeste y de mínimos costos?

• La esquina noroeste solo toma como punto de inicio alguna de las 4 esquinas de la tabla de transporte, él método de costos mínimos inicia en la casilla del menor costo.
• Al no tomar en cuenta el costo de la casilla a escoger, el método de la esquina noroeste puede asignar una casilla con un costo alto; mientras que el de costos mínimos toma en cuenta los costos y se ve claro la ventaja en la solución inicial.

                                                                 Z=1,090       Esquina Noroeste

                                                                 Z=880          Costos Mínimos