Dana Willarda

Dla dyrektora kolei, patrz Daniel Willard .

Dan Edward Willard (zm. Styczeń 2023) był amerykańskim informatykiem i logikiem, profesorem informatyki na Uniwersytecie w Albany .

Edukacja i kariera

Willard ukończył studia licencjackie z matematyki na Uniwersytecie Stony Brook , które ukończył w 1970 r. Następnie ukończył studia matematyczne na Uniwersytecie Harvarda , uzyskując tytuł magistra w 1972 r. i doktorat w 1978 r. Po opuszczeniu Harvardu pracował w Bell Labs dla cztery lata przed dołączeniem do wydziału Albany w 1983 roku.

Składki

Chociaż z wykształcenia był matematykiem i pracował jako informatyk, najczęściej cytowaną publikacją Willarda jest biologia ewolucyjna . W 1973 roku, wraz z biologiem Robertem Triversem , Willard opublikował hipotezę Triversa-Willarda , że ​​samice ssaków mogą kontrolować proporcje płci swojego potomstwa i że byłoby ewolucyjnie korzystne dla zdrowszych lub posiadających wyższy status samic mieć więcej męskiego potomstwa i za mniej zdrowe lub o niższym statusie samice mają więcej potomstwa płci żeńskiej. Teoria ta, kontrowersyjna w tamtym czasie, zwłaszcza dlatego, że nie proponowała żadnego mechanizmu tej kontroli, została później potwierdzona obserwacjami i została nazwana „jednym z najbardziej wpływowych i najczęściej cytowanych artykułów biologii ewolucyjnej XX wieku”.

Praca doktorska Willarda z 1978 r. Na temat struktur danych przeszukiwania zakresu była jednym z poprzedników techniki kaskadowania ułamkowego , a przez całe lata 80. Willard kontynuował pracę nad powiązanymi problemami ze strukturą danych. Oprócz kontynuowania pracy nad przeszukiwaniem zakresu, wykonał ważną wczesną pracę nad problemem utrzymania porządku i wynalazł x-fast trie i y-fast trie , struktury danych do przechowywania i wyszukiwania zestawów małych liczb całkowitych z niskimi wymaganiami dotyczącymi pamięci.

W informatyce Willard jest najbardziej znany ze swojej pracy z Michaelem Fredmanem na początku lat 90. nad sortowaniem liczb całkowitych i powiązanymi strukturami danych. $aby$ wiadomo było, że $posortować$ porównawcze , zestaw ale szybsze byłyby możliwe, gdyby można było założyć, że klucze, według których sortowano pozycje, są liczbami całkowitymi o umiarkowanym rozmiarze. Na przykład sortowanie kluczy w zakresie od do $Displaystyle$$N}$ można przeprowadzić w czasie ${\tfrac {\log N}{\log n}})}}$${\ Displaystyle O (n (1 + 1$ przez sortowanie radix . Założono jednak, że algorytmy sortowania liczb całkowitych musiałyby mieć ograniczenie czasowe w zależności od $i$$byłyby$ wolniejsze niż sortowanie porównawcze dla wystarczająco dużych wartości . W badaniach pierwotnie ogłoszonych w 1990 roku Fredman i Willard zmienili te założenia, wprowadzając transdychotomiczny model obliczeń. $całkowitych$ przeprowadzić przez algorytm wykorzystujący ich strukturę danych drzewa fuzyjnego jako kolejkę priorytetową . W ramach kontynuacji tej pracy Fredman i Willard wykazali również, że podobne przyspieszenia można zastosować do innych standardowych problemów algorytmicznych, w tym minimalnych drzew rozpinających i najkrótszych ścieżek .

Od 2000 roku publikacje Willarda dotyczyły przede wszystkim samoweryfikujących się teorii : systemów logiki, które zostały wystarczająco osłabione w porównaniu z częściej badanymi systemami, aby uniemożliwić zastosowanie do nich twierdzeń Gödla o niezupełności . W ramach tych systemów można udowodnić, że same systemy są logicznie spójne, bez dedukcji prowadzącej do wewnętrznej sprzeczności, którą twierdzenie Gödla implikuje dla silniejszych systemów. W przeddruku podsumowującym jego dorobek w tej dziedzinie Willard spekulował, że te systemy logiczne będą miały znaczenie w rozwoju sztucznej inteligencji , która może przetrwać potencjalne wyginięcie ludzkości, konsekwentnie rozumować i rozpoznawać własną spójność.