Dan Willard - Dan Willard

Dan Edward Willard je americký počítačový vědec a logik a je profesorem počítačové vědy na Univerzita v Albany.

Vzdělání a kariéra

Willard absolvoval vysokoškolské studium matematiky na Univerzita Stony Brook, kterou ukončil v roce 1970. Pokračoval postgraduálním studiem matematiky na Harvardská Univerzita, získal magisterský titul v roce 1972 a doktorát v roce 1978. Po odchodu z Harvardu pracoval v Bell Labs čtyři roky před nástupem na fakultu v Albany v roce 1983.^[1]

Příspěvky

Ačkoli je Willard nejcitovanější publikací, která je vycvičena jako matematik a zaměstnána jako počítačový vědec evoluční biologie. V roce 1973 s biologem Robert Trivers, Willard zveřejnil Trivers - Willardova hypotéza, že samice savců mohly ovládat poměr pohlaví jejich potomků a že by bylo vývojově výhodné, aby zdravější ženy nebo ženy s vyšším stavem měly více potomků mužů a aby ženy s méně zdravým či nižším stavem měly více potomků.^{[papír 1]} V té době kontroverzní, zejména proto, že pro tuto kontrolu nenavrhoval žádný mechanismus, byla tato teorie později ověřena pozorováním,^[2] a byl nazýván „jedním z nejvlivnějších a nejcitovanějších článků evoluční biologie 20. století“.^[3]

Práce Willarda z roku 1978 vyhledávání rozsahu datové struktury^{[papír 2]} byl jedním z předchůdců techniky částečné kaskádování,^[4] a v průběhu 80. let Willard pokračoval v práci na souvisejících problémech s datovou strukturou. Kromě toho, že pokračoval v práci na vyhledávání dosahu, udělal důležitou ranou práci na problém s údržbou objednávky,^{[papír 3]} a vynalezl x-rychlá trie a y-rychlá trie, datové struktury pro ukládání a vyhledávání souborů malých celých čísel s nízkými nároky na paměť.^{[papír 4]}

V počítačové vědě je Willard nejlépe známý pro svou práci s Michael Fredman počátkem 90. let 20. století celočíselné třídění a související datové struktury. Před jejich výzkumem to bylo dlouho známo srovnávací třídění požadovaný čas ${ displaystyle Theta (n log n)}$ třídit sadu ${ displaystyle n}$ položky, ale že rychlejší algoritmy byly možné, pokud lze předpokládat, že klíče, podle kterých byly položky tříděny, jsou celá čísla střední velikosti. Například řazení klíčů v rozsahu od ${ displaystyle 1}$ na ${ displaystyle N}$ mohlo být dosaženo včas ${ displaystyle O (n (1 + { tfrac { log N} { log n}}))}$ podle třídění radix. Předpokládalo se však, že algoritmy pro třídění celých čísel budou nutně mít časově závislé v závislosti na ${ displaystyle N}$a bylo by nutně pomalejší než srovnávací třídění pro dostatečně velké hodnoty ${ displaystyle N}$. Ve výzkumu původně oznámeném v roce 1990 Fredman a Willard tyto předpoklady změnili zavedením transdichotomický model výpočtu. V tomto modelu ukázali, že třídění celých čísel lze provést včas ${ displaystyle O (n { tfrac { log n} { log log n}})}$ algoritmem s použitím jejich fúzní strom datová struktura jako a prioritní fronta.^{[papír 5][5]} V návaznosti na tuto práci Fredman a Willard také ukázali, že podobné zrychlení lze použít i na další standardní algoritmické problémy, včetně minimální kostry a nejkratší cesty.^{[papír 6]}

Od roku 2000 se Willardovy publikace primárně týkaly sebeověřující teorie: systémy logiky, které byly ve srovnání s běžněji studovanými systémy dostatečně oslabeny, aby se zabránilo Gödelovy věty o neúplnosti od podání žádosti o ně. V rámci těchto systémů je možné dokázat, že samotné systémy jsou logicky konzistentní, aniž by tato dedukce vedla k protikladu sebe sama, kterou Gödelova věta implikuje pro silnější systémy.^{[papír 7]} V předtisku shrnující jeho dílo práce v této oblasti spekuloval Willard, že tyto logické systémy budou mít význam při vývoji umělé inteligence které mohou přežít potenciální vyhynutí lidstva, důsledně uvažovat a rozpoznat jejich vlastní důslednost.^[6]

Vybrané publikace

Reference