laboratorio

INTRODUCCIÓN

Los algoritmos devoradores son algoritmos que toman decisiones, partiendo de los datos que tienen disponibles, ignorando las consecuencias quo tales decisiones pueda tener. Esta característica los hace sencillos de diseñar e implementar. Poseen los siguientes elementos característicos:

Conjunto de candidatos: Son los posibles elementos que pueden ser considerados. Algunos deellos serán seleccionados mientras que otros rechazados.
Función de solución: Verifica si con los elementos seleccionados ya se ha completado la solución.
Función de factibilidad: verifica si hay posibilidad de completar la solución apoyándose en los elementos seleccionados.
Función de selección: permite elegir el candidato más prometedor. Generalmente existe una relación directa con la funciónobjetivo relacionada con la función objetivo.
Los Algoritmos Voraces, se emplean en problemas de optimización en los cuales se pretende maximizar o minimizar algún valor. La codificación de un algoritmo voraz se caracteriza por tener un bucle, denominado bucle voraz.
Algunos algoritmos voraces:
El algoritmo de Kruskal.
El algoritmo de Prim.











ALGORITMO DE PRIM
Concepto: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.
En otras palabras, el algoritmo 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. Por esta razón, el algoritmo es también conocido como algoritmoDJP o algoritmo de Jarnik.
ROBERT C. PRIM

Nacimiento: 1921.
Lugar de Nacimiento: Sweetwater, Estados Unidos. 
Muerte:-

Educación: 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.

Curriculum: 
En plena Segunda GuerraMundial, Prim trabajó como ingeniero para General Electric. Desde 1944 hasta 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 1958 hasta 1961. Allí Prim desarrolló el conocido Algoritmo de Prim. Después de su estancia en los laboratorios Bell, Prim pasó a servicepresidente de investigación en Sandia National Laboratories.
Historia:
En la literatura de libros de texto y la investigación que se desarrolló sobre lo Kruskal y Prim. consumado que se perdió en gran medida que otros habían trabajado en este problema antes. En particular, se pasa por alto que la mayoría de los periódicos, tanto de Prim y Kruskal, se hizo referencia a la labor del matemáticocheco Otakar Borůvka (1899-1995). Trabajo Borůvka de fecha a 1926 y su algoritmo para el problema del árbol de expansión mínimo coste es diferente de la de cualquiera de Kruskal o Prim! Por otra parte, el algoritmo Borůvka es muy elegante y merece tanta atención como la de Prim y Kruskal. Su trabajo fue publicado en checo (un documento con un resumen en alemán). Los últimos trabajos sobre lahistoria del problema al coste del árbol de expansión mínima muestra que hubo una serie de descubrimientos independientes de los algoritmos y las ideas involucradas, lo cual no es sorprendente a la luz de la importancia teórica de codicioso (hacer una elección mejor a nivel local) y los algoritmos aplicado muchos problemas que pueden ser atacados mediante las matemáticas involucradas. Por ejemplo, el...