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 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.
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ático checo 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 la historia 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 algoritmo de Prim había sido realmente descubierto independientemente mucho antes por el matemático checo Vojtech Jarnik (1897-1970), quien hizo importantes contribuciones a las matemáticas, además de su trabajo en los árboles. La historia completa de las circunstancias de interés de Kruskal y de Prim en el problema del árbol de expansión mínimo costo se debe a problemas en la fijación de precios "servicios de línea arrendada" por el sistema Bell.
El algoritmo de Kruskal descubrió que para encontrar un árbol de expansión mínimo costo es muy atractivo, aunque sí requiere una prueba de que siempre produce un árbol óptimo. (El algoritmo análogo para el problema del viajante no siempre produce un óptimo global.) Además, en el inicio, el algoritmo de Kruskal requiere la clasificación de los pesos de todos los bordes del gráfico para el cual se busca un coste del árbol de expansión mínima. Esto requiere que la memoria del ordenador se utiliza para almacenar esta información. Dadas las capacidades de los ordenadores en el algoritmo de Kruskal tiempo de no satisfacer las necesidades de los clientes del sistema de Bell. Se le ocurrió a Robert Prim, colega de Kruskal en los Laboratorios Bell, que podría ser posible encontrar una alternativa al algoritmo de Kruskal (aunque matemáticamente trabajo de Kruskal era muy atractivo), que respondía a las necesidades de los clientes del sistema de Bell. Él tuvo éxito en hacer esto y al observar que su método funciona para los gráficos con los lazos en el costo entre los bordes y con pesos negativos.
Los tres de los algoritmos debido a Borůvka, Kruskal y Prim. son "codiciosos" algoritmos es decir, dependen de hacer algo que es localmente óptima (mejor), que "milagrosamente" resulta ser globalmente óptima.
Algoritmo de Prim trabaja recogiendo, a partir de cualquier vértice, un borde más barata en ese vértice, la contratación de esa ventaja para un nuevo single "super-vértice" y repetir el proceso. El algoritmo de Kruskal funciona mediante la adición de los bordes con el fin de sujetos más peso a la condición de que ningún ciclo de bordes se crea. (Una de las ventajas del algoritmo de Prim es que ningún control especial para asegurarse de que un ciclo no se forma es necesario.) Algoritmo Borůvka (que para trabajar en su forma más simple requiere que todos los bordes tienen pesos distintos) funciona haciendo que cada vértice agarrar más un borde. Si la estructura resultante no es un árbol, a continuación, los componentes obtenidos se contraen y se repite el proceso. Los detalles de estos algoritmos se describen a continuación mediante un ejemplo simple.
Nacimiento:1897.
Lugar de Nacimiento: Austrian Empire Bohemia Prague
Muerte: 1970-09-22.Czechoslovakia Prague.
Educacion:
estudió en la Universidad Charles en Praga.
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 fue Jarnik teoría de números. Uno de los problemas que trabajó extensivamente en estuvo relacionada con el problema del círculo de Gauss. Sea R (r) denota el número de puntos (m, n), con m, n ∈ Z contenida en un círculo de centro O, radio r. Existe una constante C y un número k con
| R (r) - πr2 | <Crk.Sea d el valor mínimo 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 Landau y 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 especial con la desigualdad de Minkowski para 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.Carácter Jarnik se describe en [1]: -
Jarnik era un maestro excepcional que fue capaz de transmitir su entusiasmo por las matemáticas a sus alumnos. ... su profunda erudición humana, su tacto y su carácter humano puro como resultado un profundo respeto y admiración de todos los que le han conocido personalmente.Además de ser un editor de Acta Arithmetica desde el inicio de la revista, Jarnik estuvo activo en la organización de la enseñanza universitaria y la investigación científica a través de Checoslovaquia. Fue honrado por muchas sociedades científicas, en particular, de ser elegido miembro de la Academia Checoslovaca de Ciencias.
0 comentarios: