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 algoritmo DJP o algoritmo de Jarnik.
Referencias
Wikipedia Enciclopedia libre. ALGORITMO DE
PRIM [en línea] [Fecha de consulta: 16, Septiembre 2012]. Disponible en: <http://es.wikipedia.org/wiki/Algoritmo_de_Prim>
Vojtech Jarnik estudió en la
Universidad Charles en Praga. Después
de graduarse fue nombrado como asistente en la Universidad Charles. En 1923 se trasladó a la Universidad
de Göttingen para trabajar con Edmund
Landau . Al regresar a su puesto en Praga en
1924, se fue de nuevo a visitar a Göttingen en la sesión 1927/28, cuando
trabajó con Landau .
Jarnik
fue nombrado catedrático de matemáticas en la Universidad Charles de Praga, en
1928. Ocupó este cargo hasta que
se retiró en 1968 después de haber enseñado en la Universidad para un total de
47 años.
El
tema principal de la investigación Jarnik era la teoría de
números . Uno de los problemas que trabajó
extensivamente en estuvo relacionada con el Gauss problema
círculo. Que R ( r ) denota el número de puntos ( m , n),
con m , n ∈ Z contenida en
un círculo centro O , el radio r . Existe
una constante C y un número k con
| R ( r ) - π r 2 | < Cr k .
Sea d
el mínimo valor de k. Gauss demostró en
1837 que d <= 1. Sierpinski mejorado la desigualdad para d <= 2/3 en 1904. Landau también hizo contribuciones
importantes y en 1915 Hardy y Landau demostró que d > 1 / 2. En 1923 se demostró que d <2/3.
Jarnik
y Landau estudiado el mismo problema de las
curvas y superficies que no sean círculos. Aquí
uno está interesado en la diferencia entre el número de puntos reticulares
dentro de la superficie cerrada y el volumen encerrado por la superficie. Jarnik mostró que, para ciertas curvas
cerradas el término de error tiene d = 2/3. Se estudió el problema para el caso
particular de la elipsoide en una serie de documentos.
Otra
área de la teoría de números que Jarnik interesado fue aproximación
diofántica . Escribió artículos sobre este tema que
abarca los años 1928 a 1969. Durante
la década 1939-49, escribió una serie de artículos que tratan de la geometría
de los números, en el trato particular con Minkowski desigualdad 's de los cuerpos
convexos.
Alrededor
de 60 de los 90 Jarnik los documentos fueron escritos sobre teoría de números. Muchos de los otros fueron escritos en
funciones de una variable real, especialmente durante los años 1933-1936, donde
estudióDini derivados y
derivados aproximadas de funciones continuas. También
escribió sobre la reorganización de las series infinitas, series
trigonométricas y otras áreas de análisis.
Referencias
Biography Vojtech Jarnik
[en línea] [Fecha de consulta: 16, Septiembre 2012]. Disponible en: <http://wwwhistory.mcs.st-andrews.ac.uk/Biographies/Jarnik.html/>
Vojtech Jarnik. [Imagen]. [Fecha de consulta: 16, Septiembre
2012]. Disponible en: <http://www-history.mcs.st-andrews.ac.uk/PictDisplay/Jarnik.html>
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 desde1948 hasta 1949 como investigador asociado.
En plena Segunda Guerra Mundial, 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 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.
Referencias
Biography Robert C. Prim
[en línea] [Fecha de consulta: 16, Septiembre 2012]. Disponible en <http://es.wikipedia.org/wiki/Robert_C._Prim>
Robert C. Prim . [Imágen]. [Fecha de consulta: 16, Septiembre
2012]. Disponible en: < http://optimientedin.blogspot.mx >
No hay comentarios:
Publicar un comentario