Edsger Dijkstra

Nació el 11 de mayo de 1930 en Nuenen, Países Bajos y murió el  6 de agosto de 2002.

Fue un científico de la computación holandés.

Estudio física teórica en la Universidad de Leiden. Trabajó como investigador para Burroughs Corporation.

Entre sus contribuciones a la informática está la solución del problema del camino más corto, también conocido como el algoritmo de Dijkstra, 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.

Era conocido por su baja opinión de la sentencia GOTO en programación. Respecto a su caracter á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".

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. 

Referencias:

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

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.

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

El algoritmo incrementa continuamente el tamaño de un árbol, comenzando por un vértice inicial al que se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima. Esto significa que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya pertenecen al árbol.

Referencias:

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

Guión

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

Partcipación 10. Publicación de algun ejercicio.

Ejercicio 1.

Plantear modelo de programación y tabla de transporte.

 

Modelo de programación:

min z = X13 + 4X14 + 3X23 + 2X24 + X34 + 3X43 + 6X35 + 5X45 + 8X46 + X56

s.a

X13 + X14 <= 100

X23 + X24 <= 200

X13 + X23 + X43 =X43 + X35

X14 + X24 + X34 =X43 + X45 +X46

X35 + X45 = 150 + X56

X46 + X56 =150

Xij >= 0

Tabla de transporte:

	3	4	5	6	F
1	1	4	M	M	0	100
2	3	2	M	M	0	200
3	0	1	6	M	0	300
4	3	0	5	8	0	300
5	M	M	0	1	0	300
	300	300	150	150	300

Participación 8. Publicación de algun ejercicio.

Ejercicio 1.

1. Hay tres refinerías con capacidad diarias de 6, 5 y 8 millones de galones, respectivamente, que abastecen a tres áreas de distribución cuyas demandas diarias son 4, 8 y 7 millones de galones, respectivamente. La gasolina se transporta por una rede de oleoductos a las tres áreas de distribución. El costo de transporte es de 10 centavos por 1000 galones por milla de oleoducto. En la siguiente tabla se ven las distancias entre refinerías y las áreas de distribución. La refinería 1 no está conectada con el área de distribución 3.

Refinería \ Área de Distribución	1	2	3
1	120	180	--
2	300	100	80
3	200	250	120

 Solución:

min z= 1000(120X11 + 180X12 + 300X21 + 100X22 + 80X23 + 200X31 + 250X32 + 120X33)

	V1=120	V2=180	V3=50
U1=0	120 4	180 2	M -M	6
U2=30	300 -150	100 110	80 5	8
U3=70	200 -10	250 6	120 2	2
	4	8	7

Donde min z= 1000(2980) =29800

La solución es $29,800