¿Quien invento el algoritmo de Kruskal?

JOSEPH B. KRUSKAL

Joseph B. Kruskal  (29 de enero de 1928 – Maplewood, Nueva Jersey, 19 de septiembre de 2010) fue un matemático y estadístico estadounidense.

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

El objetivo del algoritmo de Kruskal es construir un árbol (subgrafo sin ciclos) formado por arcossucesivamente seleccionados de mínimo peso a partir de un grafo con pesos en los arcos.

Un árbol (spanning tree) de un grafo es un subgrafo que contiene todos sus vértices o nodos. Un grafo puede tener múltiples árboles. Por ejemplo, un grafo completo de cuatro nodos (todos relacionados con todos) tendría 16 árboles.

La aplicación típica de este problema es el diseño de redes telefónicas. Una empresa con diferentes oficinas, trata de trazar líneas de teléfono para conectarlas unas con otras. La compañía telefónica le ofrece esta interconexión, pero ofrece tarifas diferentes o costes por conectar cada par de oficinas. Cómo conectar entonces las oficinas al mínimo coste total.

La formulación del MST también ha sido aplicada para hallar soluciones en diversas áreas (diseño de redes de transporte, diseño de redes de telecomunicaciones - TV por cable, sistemas distribuidos, interpretación de datos climatológicos, visión artificial - análisis de imágenes - extracción de rasgos de parentesco, análisis de clusters y búsqueda de superestructuras de quasar, plegamiento de proteínas, reconocimiento de células cancerosas, y otros).

Otra aplicación menos obvia es que el árbol de coste total mínimo puede ser usado como solución aproximada al problema del viajante de comercio, el cual es NP-completo. La manera formal de definir este problema es encontrar la trayectoria más corta para visitar cada punto al menos una vez. Nótese que si se visitan todos los puntos exactamente una vez, lo que se tiene es un tipo especial de árbol. En el ejemplo anterior, 12 de los 16 árboles son trayectorias de este tipo. Si se tiene una trayectoria que visita algunos vértices más de una vez, siempre se puede soltar algunos nodos del árbol. En general el peso del árbol total mínimo es menor que el del viajante de comercio, debido a que su minimización se realiza sobre un conjunto estrictamente mayor. Existen diferentes algoritmos y maneras de usar el árbol de coste total mínimo para encontrar la solución al problema del viajante de comercio (con resultados cercanos al óptimo)

Joseph B. Kruskal [en línea] Recuperado de: http://es.wikipedia.org/wiki/Joseph_Kruskal Consulta: Septiembre 16, 2012

Joseph B. Kruskal [en línea] Recuperada de: http://tinyurl.com/chl7o3t Consulta: Septiembre 16, 2012

¿Quien invento el algoritmo de PRIM?

ROBERT C. PRIM

Robert C. Prim (n 1921, Sweetwater, Estados Unidos) es un matemático e ingeniero informático.

En 1941 se licenció en ingeniería eléctrica en la Universidad de Princeton. Más tarde, en 1949 recibe su doctorado en matemáticas en la misma universidad. Trabajó en dicha universidad desde 1948 hasta 1949 como investigador asociado.

En plena Segunda Guerra Mundial, Prim trabajó como ingeniero para General Electric. Desde 1944hasta 1949 fue contratado por la United States Naval Ordnance Lab como ingeniero y más tarde como matemático. En los laboratorios Bell, trabajó como director de investigación matemática desde 1958hasta 1961. Allí Prim desarrolló el conocido Algoritmo de Prim. Después de su estancia en los laboratorios Bell, Prim pasó a ser vicepresidente de investigación en Sandia National Laboratories.

Durante su carrera en los laboratorios Bell, Robert Prim junto a su compañero Joseph Kruskal desarrolló dos algoritmos diferentes para encontrar los árboles abarcadores mínimos en un grafo ponderado. El algoritmo que lleva su nombre fue originalmente descubierto por el matemático Vojtech Jarnik y más tarde e independientemente por Prim en 1957. Dos años más tarde fue redescubierto por Edsger Dijkstra.

Robert C. Prim [en línea] Recuperado de: http://es.wikipedia.org/wiki/Robert_C._Prim Consulta: Semptiembre 16, 2012

Robert C. Prim [imagen]. Recuperada de: http://tinyurl.com/8qk2sd4 Consulta: Semptiembre 16, 2012

Biografía de Dijkstra

EDSGER DIJKSTRA

(Róterdam, Países Bajos, 11 de mayo de 1930 - Nuenen, Países Bajos,6 de agosto de 2002) fue un científico de la computación de los Países Bajos. Dijkstra estudió física teórica en la Universidad de Leiden. 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.

Entre sus contribuciones a las ciencias de la computación está la solución del problema del camino más corto, también conocido como el algoritmo de Dijkstra, la notación polaca inversa y el relacionadoalgoritmo shunting yard, THE multiprogramming system, el algoritmo del banquero y la construcción delsemá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. El algoritmo de Dijkstra es usado en la ruta más corta primero (SPF) que es usado en el protocolo de enrutamiento Open Shortest Path First (OSPF). También se le debe la autoría de la expresión "Crisis del software", aparecida en su libro The Humble Programmer y usada ampliamente en la famosa reunión de la OTAN de 1968 sobre desarrollo del software. Recibió el Premio Turing en 1972.

Era conocido por su baja opinión de la sentencia GOTO en programación, que culminó en 1968 con el artículo Go To Statement Considered Harmful (La sentencia Goto considerada perjudicial), visto como un paso importante hacia el rechazo de la expresión GOTO y de su eficaz reemplazo por estructuras de control tales como el bucle while. El famoso título del artículo no era obra de Dijkstra, sino de Niklaus Wirth, entonces redactor de Comunicaciones del ACM. Dijkstra era un aficionado bien conocido de ALGOL, y trabajó en el equipo que desarrolló el primer compilador para este lenguaje. En ese mismo año creó el primer sistema operativo con estructura jerárquica, de niveles o capas. Fue denominado THE(Technische Hogeschool, Eindhoven) que se utilizó con fines didácticos.

Desde los años 1970, el principal interés de Dijkstra fue la verificación formal. La opinión que prevalecía entonces era que uno debe primero escribir un programa y seguidamente proporcionar una prueba matemática de su corrección. Dijkstra objetó que las pruebas que resultan son largas e incómodas, y que la prueba no da ninguna comprensión de cómo se desarrolló el programa. Un método alternativo es la derivación de programas, «desarrollar prueba y programa conjuntamente». Uno comienza con una especificación matemática del programa que se supone va a hacer y aplica transformaciones matemáticas a la especificación hasta que se transforma en un programa que pueda ser ejecutado. El programa que resulta entonces es sabido correcto por la construcción. Muchos de los últimos trabajos de Dijkstra tratan sobre las maneras de hacer fluida la argumentación matemática.

Respecto a su carácter árido y ácido, conocidas son su oposición a la instrucción GOTO y al lenguaje BASIC ("mutila la mente más allá de toda recuperación"). Alan Kay expuso que "en informática, la arrogancia se mide en nanodijkstras ".

Dijkstra murió el 6 de agosto de 2002 después de una larga lucha contra el cáncer

Edsger Dijkstra [en línea] Recuperado de: http://es.wikipedia.org/wiki/Edsger_Dijkstra Consultado: Septiembre 16, 2012

Edsger Dijkstra [imagen] Recuperada de: http://www.cs.utexas.edu/~EWD/EWDwww.jpg Consultado: Septiembre 16, 2012

Biografía de Floyd

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

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

  

Robert W. Floyd [en línea] Recuperado de: http://es.wikipedia.org/wiki/Robert_W._Floyd Consulta: Septiembre 16, 2012

Robert W. Floyd [imagen] Recuperada de: http://tinyurl.com/9xs9ey8 Consulta: Septiembre 16, 2012

Tarea 1 - Triptico

Hola!!! que tal... aquí les dejo el  URL de mi Tarea 1 (Triptico)

https://docs.google.com/document/pub?id=1E637tjlc6vdSAcoSHSP6xsEJ__zPFFR1OrhOrkCuRbc

Participación 7 - Problema de Maximización

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. ¿Cómo cambian los criterios de los métodos que generan solución inicial?

• Esquina Noroeste: Como sabemos en este método no se toman en cuenta los costos por lo tanto no habrá ningún cambio al aplicarle el método en un problema de maximización.

Aplicando el método de Esquina Noroeste al ejemplo anterior tenemos: 

con un valor de Z= 1500

• Costos Mínimos:  Para este método en los problemas de minimización utilizamos el costo mínimo, pero en este caso como estamos trabajando con un problemas de maximización se busca el "mayor beneficio".

Aplicando el método de costos mínimos tenemos:

Z= 1500

• Vogel: Al aplicar el método de vogel en un problemas de maximización, para obtener el valor de la penalizaciones se obtiene usando le diferencia entre los mayores beneficios y eligiendo el numero mayor que se obtuvo en las penalizaciones, para elegir la casilla se usa la de mayor beneficio.

Aplicando el método de vogel al ejemplo, tenemos:

Z= 1500

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

Como sabemos se obtiene con el método de multiplicadores

Para obtener la variable de entrada en problemas de minimización, se utiliza el coeficiente mas POSITVO que se obtuvo en las celdas.

Para el caso de maximizacion, se usa el mismo criterio solo que ahora en lugar de ser el coeficiente mas positivo sera el mas NEGATIVO.

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

Se obtiene la variable de salida usando el mismo criterio para un problema de minimizacion, el cual consite en θ=min{xij│xij-θ y xij  básica} 

Aplicando el metodo al problema tenemos: 

Para elegir la variable de entrada en este caso en un problema de maximización, se elige el coeficiente mas negativo, como vemos los valores 15, 20 y 35 son todos positivos lo que quiere decir que no hay variable de entrada, por lo tanto es la solución es la optima.  

Como resultado tenemos: 

William R. Vogel

William R. Vogel

William R. Vogel murió Jueves, 26 de agosto 2010, en el Mercy Hospice, Johnston, después de una larga y valiente lucha contra el cáncer.

Bill nació en Sac City, Iowa, el 15 de noviembre de 1941, a Roy y Vogel Minnie. Creció en una granja al oeste de Wall Lake, Iowa, y se graduó en 1959 como mejor alumno. Asistió a la AIB durante un año, y luego sirvió en la Reserva del Ejército durante seis años, y luego trabajó en un banco en Storm Lake por un año. Él y Karaan se casaron 13 de septiembre 1964 y vivió en Storm Lake por un año, luego se mudó a Des Moines en 1966. Trabajó en la Northwestern Bell / Qwest por 25 años, y en Principal Financial de 12 años como analista de telecomunicaciones. Después de su jubilación a los 62 años, vivió la vida al máximo, manteniendo su superficie de cultivo y algunos otros. Él y Karaan viajado, y llevó a la familia en los viajes a Florida.

Después de unirse a la Iglesia Luterana de la Esperanza, se unió el grupo de hombres y disfrutamos del compañerismo y la amistad de todos. Le encantaba jugar al golf y tenía varios trofeos.

Referencia: 

"William R. Vogel." Obituary. N.p., n.d. Web. 26 Aug. 2012. <http://hosting-24625.tributes.com/show/William-R.-Vogel-89227895>.