Dan Edward Willard es un científico informático y lógico estadounidense, y es profesor de informática en la Universidad de Albany .
Educación y carrera
Willard realizó sus estudios de pregrado en matemáticas en la Universidad de Stony Brook , donde se graduó en 1970. Luego realizó estudios de posgrado en matemáticas en la Universidad de Harvard , donde obtuvo una maestría en 1972 y un doctorado en 1978. Después de dejar Harvard, trabajó en Bell Labs para cuatro años antes de unirse a la facultad de Albany en 1983. [1]
Contribuciones
Aunque se formó como matemático y se empleó como científico informático, la publicación más citada de Willard es sobre biología evolutiva . En 1973, con el biólogo Robert Trivers , Willard publicó la hipótesis de Trivers-Willard , que las hembras de mamíferos podían controlar la proporción de sexos de su descendencia, y que sería evolutivamente ventajoso para las hembras más sanas o de mayor estatus tener más descendencia masculina y por menos hembras sanas o de menor estatus para tener más descendencia femenina. [artículo 1] Controvertido en ese momento, especialmente porque no propuso ningún mecanismo para este control, esta teoría fue posteriormente validada mediante la observación, [2] y ha sido llamada "uno de los artículos más influyentes y más citados de la biología evolutiva del siglo XX". ". [3]
El trabajo de tesis de Willard de 1978 sobre estructuras de datos de búsqueda de rango [artículo 2] fue uno de los predecesores de la técnica de cascada fraccionada , [4] ya lo largo de la década de 1980 Willard continuó trabajando en problemas relacionados con la estructura de datos. Además de continuar trabajando en la búsqueda de rangos, realizó un trabajo temprano importante en el problema de mantenimiento de pedidos , [documento 3] e inventó el trie x-fast y el y-fast trie , estructuras de datos para almacenar y buscar conjuntos de números enteros pequeños con requisitos de memoria bajos. [documento 4]
En ciencias de la computación, Willard es mejor conocido por su trabajo con Michael Fredman a principios de la década de 1990 sobre clasificación de enteros y estructuras de datos relacionadas. Antes de su investigación, se sabía desde hace mucho tiempo que la clasificación por comparación requería tiempo para ordenar un conjunto de ítems, pero que los algoritmos más rápidos eran posibles si las claves por las cuales se clasificaban los ítems pudieran suponerse como números enteros de tamaño moderado. Por ejemplo, ordenar claves en el rango de a podría lograrse a tiempo por clasificación de radix . Sin embargo, se asumió que los algoritmos de ordenación de enteros necesariamente tendrían un límite de tiempo dependiendo de, y sería necesariamente más lento que la clasificación de comparación para valores suficientemente grandes de . En una investigación anunciada originalmente en 1990, Fredman y Willard cambiaron estos supuestos al introducir el modelo de computación transdicotómico . En este modelo, demostraron que la ordenación de números enteros se podía hacer a tiempomediante un algoritmo que utiliza su estructura de datos de árbol de fusión como una cola de prioridad . [artículo 5] [5] En un seguimiento de este trabajo, Fredman y Willard también demostraron que se podrían aplicar aceleraciones similares a otros problemas algorítmicos estándar, incluidos los árboles de expansión mínimos y las rutas más cortas . [documento 6]
Desde 2000, las publicaciones de Willard se han centrado principalmente en teorías de autoverificación : sistemas de lógica que se han debilitado lo suficiente, en comparación con los sistemas más comúnmente estudiados, para evitar que los teoremas de incompletitud de Gödel se apliquen a ellos. Dentro de estos sistemas, es posible probar que los propios sistemas son lógicamente consistentes, sin que esta deducción conduzca a la auto-contradicción que implica el teorema de Gödel para sistemas más fuertes. [artículo 7] En un preimpreso que resume su obra de trabajo en esta área, Willard ha especulado que estos sistemas lógicos serán de importancia en el desarrollo de inteligencias artificiales que puedan sobrevivir a la extinción potencial de la humanidad, razonar consistentemente y reconocer su propia consistencia. [6]
Publicaciones Seleccionadas
- ^ Trivers, RL ; Willard, DE (1973), "Selección natural de la capacidad de los padres para variar la proporción de sexos de la descendencia", Science , 179 (4068): 90-2, Bibcode : 1973Sci ... 179 ... 90T , doi : 10.1126 / science .179.4068.90 , JSTOR 1734960 , PMID 4682135.
- ^ Willard, DE (1978), Algoritmos de búsqueda de bases de datos orientadas a predicados , Ph.D. tesis, Universidad de Harvard.
- ^ Willard, Dan E. (1982), "Mantenimiento de archivos secuenciales densos en un entorno dinámico", Proc. XIV Simposio ACM sobre Teoría de la Computación (STOC '82) , págs. 114-121, doi : 10.1145 / 800070.802183.
- ^ Willard, Dan E. (1983), "Las consultas de rango logarítmico del peor caso son posibles en el espacio Θ ( N )", Information Processing Letters , 17 (2): 81–84, doi : 10.1016 / 0020-0190 (83 ) 90075-3 , MR 0731126.
- ^ Fredman, Michael L .; Willard, Dan E. (1993), "Superando el límite de la teoría de la información con árboles de fusión", Journal of Computer and System Sciences , 47 (3): 424–436, doi : 10.1016 / 0022-0000 (93) 90040-4 , MR 1248864.
- ^ Fredman, Michael L .; Willard, Dan E. (1994), "Algoritmos trans-dicotómicos para árboles de expansión mínimos y rutas más cortas", Journal of Computer and System Sciences , 48 (3): 533–551, doi : 10.1016 / S0022-0000 (05) 80064 -9.
- ^ Willard, Dan E. (2001), "Sistemas de axiomas autoverificables, el teorema de incompletitud y principios de reflexión relacionados", Journal of Symbolic Logic , 66 (2): 536–596, doi : 10.2307 / 2695030 , MR 1833464.
Referencias
- ^ Curriculum vitae , consultado el 4 de junio de 2013.
- ^ Simpson, MJA; Simpson, AE (1982), "Proporciones de sexo al nacer y rango social en madres de monos rhesus", Nature , 300 : 440–441, Bibcode : 1982Natur.300..440S , doi : 10.1038 / 300440a0.
- ^ Mathews, Paul (2011), "¿Existe un mecanismo psicológico próximo para inducir un efecto Trivers-Willard en humanos? Resultados de un experimento en Internet que analiza la composición sexual deseada de los niños después de la preparación de la mortalidad" (PDF) , Sociedad, Biología y Asuntos humanos , 76 (2): 11–23[ enlace muerto permanente ] .
- ^ de Berg, M .; van Kreveld, M .; Overmars, MH ; Schwarzkopf, O. (2008), Geometría computacional: Algoritmos y aplicaciones (3ª ed.), Springer-Verlag, p. 116, ISBN 9783540779735.
- ^ Peterson, Ivars (29 de junio de 1991), "Computación de 'árboles de fusión' para derribar barreras: un algoritmo que acelera la rapidez con la que las computadoras pueden clasificar la información" , Science News.
- ^ Willard, Dan E. (2018), Acerca del abismo que separa los objetivos del programa de coherencia de Hilbert del segundo teorema de incompletitud , arXiv : 1807.04717