mamografias

Universidad Nacional Experimental
De los Llanos Occidentales
“Ezequiel Zamora”
Barinas-Barinas

Bachiller:
 Lisney Hernández
Prof: C.I.V 23.914.642
 Yolimar Nadal Nádales
Carrera: Ing. En Informática
Subproyecto: Estructuras Discretas


Barinas, Mayo de 2012
INTRODUCCIÓN
El siguiente trabajo tiene comoobjetivo comprender la importancia del estudio de los algoritmos de Dikjstra, para lo cual es necesario realizar un recorrido por distintas nociones de esta disciplina, con el fin de acercarnos un poco a su naturaleza.
Posteriormente, analizaremos que es lo que cuenta la historia; fechas, hechos, o procesos, dado que este debate que se ha sostenido durante siglos en la humanidad, nosotros nopretendemos llegar a una respuesta absoluta, sino que entregar algunos elementos que permitan al lector profundizar en el tema y obtener sus propias conclusiones.
A continuación, realizaremos una apreciación más profunda del sentido de los teoremas de Dikjstra, y teoremas de Grafos, para ver si la historia que conocemos es el único pasado posible. En caso de no ser así, ¿qué es lo que permanece fuerade lo que conocemos?
Finalmente veremos la intervención del azar en la historia y de la historia en el azar.
 
ALGORITMO DE DIJKSTRA
Un famoso teorema, demostrado por Egsger Dijkstra en los años sesenta, demuestra que todo programa puede escribirse utilizando únicamente las tres instrucciones de control siguientes:
• El bloque secuencial de instrucciones, instrucciones ejecutadassucesivamente.
• La instrucción condicional alternativa, de la forma "IF condición THEN instrucción-1 ELSE instrucción-2".
o Si la condición se cumple, se ejecutará "instrucción-1".
o En caso contrario, se ejecuta "instrucción-2".
o Abreviadamente, esta instrucción se suele llamar IF-THEN-ELSE.
• El bucle condicional "WHILE condición DO instrucción", que ejecuta la instrucción repetidamentemientras la condición se cumpla.
o En su lugar, se puede utilizar también la forma "UNTIL condición DO instrucción", que ejecuta la instrucción hasta que la condición se cumpla. Los dos bucles se diferencian entre sí porque en la forma WHILE la condición se comprueba al principio, por lo que es posible que la instrucción no se ejecute ni una sola vez.
o En cambio, en la forma UNTIL la condición secomprueba al final del bucle, por lo que la instrucción se ejecuta siempre al menos una vez.
Los programas que utilizan sólo estas tres instrucciones de control básicas o sus variantes (como los bucles FOR o la instrucción condicional CASE), pero no la instrucción GOTO, se llaman estructurados.
La "programación estructurada" (llamada también "programación sin GOTO") se convirtió durante losaños setenta en la forma de programar más extendida.
A pesar de todo, la mayoría de los lenguajes conservan la instrucción GOTO y las etiquetas de las instrucciones, para utilizarla en casos muy especiales, aunque normalmente se desaconseja su uso.
Entre los lenguajes de alto nivel, PASCAL, C, y ADA pueden considerarse especializados en programación estructurada, y aunque todos ellos permitenutilizar la instrucción GOTO, se desaconseja su uso. El algoritmo de Dijkstra, también llamado algoritmo de caminos mínimos, es un algoritmo para la determinación del camino más corto dado un vértice origen al resto de vértices en un grafo con pesos en cada arista. Su nombre se refiere a Edsger Dijkstra, quien lo describió por primera vez en 1959.
La idea subyacente en este algoritmo consiste en irexplorando todos los caminos más cortos que parten del vértice origen y que llevan a todos los demás vértices; cuando se obtiene el camino más corto desde el vértice origen, al resto de vértices que componen el grafo, el algoritmo se detiene. El algoritmo es una especialización de la búsqueda de costo uniforme, y como tal, no funciona en grafos con aristas de costo negativo (al elegir siempre el...