Dan Willard

För järnvägschefen, se Daniel Willard .

Dan Edward Willard (död januari 2023) var en amerikansk datavetare och logiker och professor i datavetenskap vid universitetet i Albany .

Utbildning och karriär

Willard gjorde sina grundstudier i matematik vid Stony Brook University och tog examen 1970. Han fortsatte med studier i matematik vid Harvard University , tog en magisterexamen 1972 och en doktorsexamen 1978. Efter att ha lämnat Harvard arbetade han på Bell Labs för fyra år innan han började på Albany-fakulteten 1983.

Bidrag

Även om han är utbildad som matematiker och anställd som datavetare, är Willards mest citerade publikation inom evolutionsbiologi . År 1973 publicerade Willard tillsammans med biologen Robert Trivers Trivers–Willard-hypotesen , att däggdjurshonor kunde kontrollera könsförhållandet mellan sina avkommor och att det skulle vara evolutionärt fördelaktigt för friskare honor eller honor med högre status att få fler manliga avkommor och för mindre friska eller lägre status honor för att få fler kvinnliga avkommor. Kontroversiell vid den tiden, särskilt för att den inte föreslog någon mekanism för denna kontroll, validerades denna teori senare genom observation, och den har kallats "en av de mest inflytelserika och mycket citerade artiklarna från 1900-talets evolutionära biologi".

Willards examensarbete från 1978 om avståndssökningsdatastrukturer var en av föregångarna till tekniken för fraktionerad kaskad , och under hela 1980 - talet fortsatte Willard att arbeta med relaterade datastrukturproblem. Förutom att fortsätta att arbeta med intervallsökning, gjorde han tidigt ett viktigt arbete med orderunderhållsproblemet och uppfann x-fast trie och y-fast trie , datastrukturer för lagring och sökning av uppsättningar av små heltal med låga minneskrav.

Inom datavetenskap är Willard mest känd för sitt arbete med Michael Fredman i början av 1990-talet om heltalssortering och relaterade datastrukturer. Innan deras forskning hade det länge varit känt att jämförelsesortering krävde tid $\Theta (n\log n)$ för att sortera en uppsättning av $n$ objekt, men att snabbare algoritmer var möjliga om nycklarna med vilka objekten sorterades kunde antas vara heltal av måttlig storlek. Till exempel kan sortering av nycklar i intervallet från $1$$O(n(1+ {\tfrac {\log N}{\log n}}))$ N $\displaystyle N}$ utföras i tiden genom radixsortering . Det antogs dock att heltalssorteringsalgoritmer nödvändigtvis skulle ha en tidsgräns beroende på ${\displaystyle N} ,$ och nödvändigtvis skulle vara långsammare än jämförelsesortering för tillräckligt stora värden på $N$ . I forskning som ursprungligen tillkännagavs 1990 ändrade Fredman och Willard dessa antaganden genom att introducera den transdikotoma beräkningsmodellen. I den här modellen visade de att heltalssortering kunde göras i tid $O(n{\tfrac {\log n}{\log \log n}})$ av en algoritm som använder deras fusionsträddatastruktur som en prioritetskö . I en uppföljning av detta arbete visade Fredman och Willard också att liknande hastighetshöjningar kunde tillämpas på andra standardalgoritmiska problem, inklusive minsta spännträd och kortaste vägar .

Sedan 2000 har Willards publikationer i första hand handlat om självverifierande teorier : logiksystem som har försvagats tillräckligt, jämfört med mer allmänt studerade system, för att förhindra Gödels ofullständighetsteorem från att tillämpas på dem. Inom dessa system är det möjligt att bevisa att systemen i sig är logiskt konsistenta, utan att denna deduktion leder till den självmotsägelse som Gödels sats innebär för starkare system. I ett förtryck som sammanfattar sitt arbete på detta område, spekulerade Willard att dessa logiska system kommer att vara viktiga för att utveckla artificiell intelligens som kan överleva mänsklighetens potentiella utplåning, resonera konsekvent och känna igen sin egen konsistens.