Дэн Уиллард - Dan Willard
Дэн Эдвард Уиллард - американский ученый-компьютерщик и логик, профессор компьютерных наук в университете Олбани .
Образование и карьера
Уиллард учился на бакалавриате по математике в Университете Стоуни-Брук , который окончил в 1970 году. Он продолжил аспирантуру по математике в Гарвардском университете , получив степень магистра в 1972 году и докторскую степень в 1978 году. После ухода из Гарварда он работал в Bell Labs на за четыре года до поступления на факультет в Олбани в 1983 году.
Взносы
Несмотря на то, что Уиллард получил образование математика и работал в качестве ученого-информатика, наиболее цитируемая публикация Уилларда посвящена эволюционной биологии . В 1973 году вместе с биологом Робертом Трайверсом Уиллард опубликовал гипотезу Трайверса-Уилларда, согласно которой самки млекопитающих могут контролировать соотношение полов в своем потомстве и что для более здоровых самок или самок с более высоким статусом было бы эволюционно выгодно иметь больше потомков мужского пола и с меньшими затратами. здоровые самки или самки с более низким статусом, чтобы иметь больше потомков женского пола. Эта теория вызывала споры в то время, особенно потому, что не предлагала никакого механизма для этого контроля, но позже была подтверждена наблюдениями и была названа «одной из самых влиятельных и часто цитируемых статей эволюционной биологии 20 века».
Тезисная работа Уилларда 1978 года по структурам данных с поиском по диапазону была одним из предшественников техники дробного каскадирования , и на протяжении 1980-х Уиллард продолжал работать над проблемами связанных структур данных. Он не только продолжал работать над поиском по диапазону, но и на раннем этапе проделал важную работу по проблеме поддержания порядка и изобрел x-fast trie и y-fast trie , структуры данных для хранения и поиска наборов небольших целых чисел с низкими требованиями к памяти.
В области информатики Уиллард наиболее известен своей работой с Майклом Фредманом в начале 1990-х годов над целочисленной сортировкой и связанными структурами данных. До их исследования было давно известно, что сортировка сравнением требует времени для сортировки набора элементов, но что более быстрые алгоритмы были бы возможны, если бы ключи, по которым сортировались элементы, можно было принять как целые числа умеренного размера. Например, сортировка ключей в диапазоне от до может выполняться во времени с помощью сортировки по основанию . Однако предполагалось, что алгоритмы целочисленной сортировки обязательно будут иметь временную привязку в зависимости от и обязательно будут медленнее, чем сортировка сравнения для достаточно больших значений . В исследовании, первоначально объявленном в 1990 году, Фредман и Уиллард изменили эти предположения, представив трансдихотомическую модель вычислений. В этой модели они показали, что целочисленную сортировку можно выполнять вовремя с помощью алгоритма, использующего структуру данных их дерева слияния в качестве очереди с приоритетом . В продолжение этой работы Фредман и Уиллард также показали, что подобное ускорение может быть применено к другим стандартным алгоритмам, включая минимальные остовные деревья и кратчайшие пути .
С 2000 года публикации Уилларда в основном касались самопроверяющихся теорий : систем логики, которые были достаточно ослаблены по сравнению с более широко изучаемыми системами, чтобы теоремы Гёделя о неполноте не применялись к ним. В рамках этих систем можно доказать, что сами системы логически непротиворечивы, без этого вывода, ведущего к внутреннему противоречию, которое теорема Гёделя влечет для более сильных систем. В препринте, обобщающем его работы в этой области, Уиллард высказал предположение, что эти логические системы будут иметь важное значение для развития искусственного интеллекта, который сможет пережить потенциальное вымирание человечества, последовательно рассуждать и признавать свою непротиворечивость.