Дэн Уиллард

Дэн Эдвард Уиллард - американский ученый-компьютерщик и логик, профессор информатики в университете Олбани .

Образование и карьера [ править ]

Уиллард учился на бакалавриате по математике в Университете Стоуни-Брук , который окончил в 1970 году. Он продолжил учебу в аспирантуре по математике в Гарвардском университете , получив степень магистра в 1972 году и докторскую степень в 1978 году. После ухода из Гарварда он работал в Bell Labs на за четыре года до поступления на факультет Олбани в 1983 году. ^[1]

Вклады [ править ]

Несмотря на то, что Уиллард получил образование математика и работал специалистом по информатике, наиболее цитируемая публикация Уилларда относится к эволюционной биологии . В 1973 году вместе с биологом Робертом Триверсом Уиллард опубликовал гипотезу Трайверса-Уилларда, согласно которой самки млекопитающих могут контролировать соотношение полов в своем потомстве и что для более здоровых самок или самок с более высоким статусом было бы эволюционно выгодно иметь больше потомков мужского пола и за меньшие деньги. здоровые самки или самки с более низким статусом, чтобы иметь больше потомков женского пола. ^{[paper 1]} Эта теория вызывала споры в то время, особенно потому, что не предлагала никакого механизма для этого контроля, но позже была подтверждена наблюдениями ^[2]и его назвали «одной из самых влиятельных и часто цитируемых статей эволюционной биологии 20 века». ^[3]

1978 Дипломная работа Уилларда на диапазон поиска структур данных ^{[бумага 2]} был один из предшественников в технике фракционного каскадирования , ^[4] и в течение 1980 - х годов Уиллард продолжал работу по смежным проблемам структуры данных. А также продолжает работу по поиску расстояния, он сделал важные ранние работы по проблеме порядка обслуживания , ^{[бумага 3]} и изобрел й-быстро синтаксическое дерево и у-быстро синтаксическое дерева , структуры данных для хранения и поиска множества небольших целых чисел низкие требования к памяти. ^{[бумага 4]}

В области информатики Уиллард наиболее известен своей работой с Майклом Фредманом в начале 1990-х годов над целочисленной сортировкой и связанными структурами данных. До их исследования было давно известно, что сортировка сравнением требует времени для сортировки набора элементов, но что более быстрые алгоритмы были бы возможны, если бы ключи, по которым сортировались элементы, можно было принять как целые числа умеренного размера. Например, сортировка ключей в диапазоне от до может выполняться во времени с помощью сортировки по основанию . Однако предполагалось, что алгоритмы целочисленной сортировки обязательно будут иметь временную привязку в зависимости от${\ Displaystyle \ Theta (п \ журнал п)}$${\ displaystyle n}$${\ displaystyle 1}$${\ displaystyle N}$${\ Displaystyle О (п (1 + {\ tfrac {\ log N} {\ log n}}))}$${\ displaystyle N}$, и обязательно будет медленнее, чем сортировка сравнения для достаточно больших значений . В исследовании, первоначально объявленном в 1990 году, Фредман и Уиллард изменили эти предположения, представив трансдихотомическую модель вычислений. В этой модели они показали, что целочисленную сортировку можно выполнять вовремя с помощью алгоритма, использующего структуру данных их дерева слияния в качестве очереди с приоритетом . ^{[paper 5] [5]} В продолжение этой работы Фредман и Уиллард также показали, что подобное ускорение может быть применено к другим стандартным алгоритмам, включая минимальные остовные деревья и кратчайшие пути . ^{[бумага 6]}${\ displaystyle N}$${\ Displaystyle О (п {\ tfrac {\ журнал п} {\ журнал \ журнал п}})}$

С 2000 года публикации Уилларда в первую очередь касались самопроверяющихся теорий : систем логики, которые были достаточно ослаблены по сравнению с более широко изучаемыми системами, чтобы теоремы Гёделя о неполноте не применялись к ним. В рамках этих систем можно доказать, что сами системы логически непротиворечивы, без этого вывода, ведущего к внутреннему противоречию, которое теорема Гёделя влечет для более сильных систем. ^{[статья 7]} В препринте, обобщающем его работы в этой области, Уиллард высказал предположение, что эти логические системы будут иметь важное значение для развития искусственного интеллекта.которые могут пережить потенциальное вымирание человечества, последовательно рассуждать и осознавать свою непротиворечивость. ^[6]

Избранные публикации [ править ]

Ссылки [ править ]