Dan Edward Willard (19 de septiembre de 1948 [3] - 21 de enero de 2023 [4] ) fue un científico informático y lógico estadounidense, y profesor de informática en la Universidad de Albany .
Willard realizó sus estudios de pregrado en matemáticas en la Universidad Stony Brook , graduándose en 1970. Continuó sus estudios de posgrado en matemáticas en la Universidad de Harvard , obteniendo una maestría en 1972 y un doctorado en 1978. Después de dejar Harvard, trabajó en Bell Labs durante cuatro años antes de unirse a la facultad de Albany en 1983. [5]
Aunque se formó como matemático y trabajó como científico informático, la publicación más citada de Willard es sobre biología evolutiva . En 1973, junto con el biólogo Robert Trivers , Willard publicó la hipótesis Trivers-Willard , según la cual las hembras de los mamíferos podían controlar la proporción de sexos de su descendencia y que sería evolutivamente ventajoso que las hembras más sanas o de mayor estatus tuvieran más descendencia masculina y que las hembras menos sanas o de menor estatus tuvieran más descendencia femenina. [artículo 1] Esta teoría, que en su momento fue controvertida, especialmente porque no proponía ningún mecanismo para este control, fue validada posteriormente mediante la observación [6] y se la ha denominado "uno de los artículos más influyentes y citados de la biología evolutiva del siglo XX". [7]
El trabajo de tesis de Willard de 1978 sobre estructuras de datos de búsqueda de rangos [documento 2] fue uno de los predecesores de la técnica de cascada fraccionaria [8] y , a lo largo de la década de 1980, Willard continuó trabajando en problemas de estructuras de datos relacionados. Además de seguir trabajando en la búsqueda de rangos, realizó un trabajo temprano importante sobre el problema de mantenimiento de orden [ documento 3] e inventó el trie x-fast y el trie y-fast , estructuras de datos para almacenar y buscar conjuntos de números enteros pequeños con bajos requisitos de memoria [documento 4]
En informática, Willard es más conocido por su trabajo con Michael Fredman a principios de los años 90 sobre ordenamiento de números enteros y estructuras de datos relacionadas. Antes de su investigación, se sabía desde hacía tiempo que el ordenamiento por comparación requería tiempo para ordenar un conjunto de elementos, pero que eran posibles algoritmos más rápidos si se podía suponer que las claves por las que se ordenaban los elementos eran números enteros de tamaño moderado. Por ejemplo, las claves de ordenamiento en el rango de a se podían lograr en el tiempo mediante el ordenamiento por radix . Sin embargo, se suponía que los algoritmos de ordenamiento de números enteros tendrían necesariamente un límite de tiempo en función de , y serían necesariamente más lentos que el ordenamiento por comparación para valores suficientemente grandes de . En una investigación anunciada originalmente en 1990, Fredman y Willard cambiaron estas suposiciones al introducir el modelo transdicotómico de cálculo. En este modelo, demostraron que el ordenamiento de números enteros se podía realizar en el tiempo mediante un algoritmo que utilizaba su estructura de datos de árbol de fusión como una cola de prioridad . [artículo 5] [9] En una continuación 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ínima y las rutas más cortas . [artículo 6]
Después de 2000, las publicaciones de Willard se centraron principalmente en teorías autoverificables : sistemas de lógica que se han debilitado lo suficiente, en comparación con los sistemas más comúnmente estudiados, como para evitar que los teoremas de incompletitud de Gödel se apliquen a ellos. Dentro de estos sistemas, es posible demostrar que los sistemas mismos son lógicamente consistentes, sin que esta deducción conduzca a la autocontradicción que implica el teorema de Gödel para sistemas más fuertes. [artículo 7] En una preimpresión que resume su obra de trabajo en esta área, Willard especuló que estos sistemas lógicos serán importantes para el desarrollo de inteligencias artificiales que puedan sobrevivir a la posible extinción de la humanidad, razonar de manera consistente y reconocer su propia consistencia. [10]
