Дэн Уиллард

и Эдвард Уиллард
и Эдвард Уиллард
	Портрет Дэна Э. Уилларда для вручения Президентской премии Университета Олбани 2008 года за выдающиеся достижения в области исследований.
Рожденный	19 сентября 1948 г. ; Нью-Йорк , Нью-Йорк, США
Умер	23 января 2023 г. ; Олбани, Нью-Йорк , США
Альма-матер	Гарвардский университет (доктор философии)
	Научная карьера
Поля	Информатика
Учреждения	SUNY Олбани
Диссертация	Алгоритмы поиска в базе данных, ориентированные на предикаты (1979)
Докторантура	Джеральд Сакс

И Эдвард Уиллард (19 сентября 1948 г.) ^{[ 3 ]} – 21 января 2023 г. ^{[ 4 ]}) — американский учёный-компьютерщик и логик, профессор информатики в Университете Олбани .

Образование и карьера

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

Взносы

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

Диссертация Уилларда 1978 года по поиска по диапазону структурам данных ^{[ документ 2 ]} был одним из предшественников техники дробного каскадирования , ^{[ 8 ]} и на протяжении 1980-х годов Уиллард продолжал работать над соответствующими проблемами структуры данных. Помимо продолжения работы над поиском дальности, он провёл важную раннюю работу над проблемой поддержания порядка . ^{[ документ 3 ]} и изобрел x-fast trie и y-fast trie — структуры данных для хранения и поиска наборов небольших целых чисел с низкими требованиями к памяти. ^{[ документ 4 ]}

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

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

Избранные публикации

^ Триверс, РЛ ; Уиллард, DE (1973), «Естественный отбор способности родителей изменять соотношение полов в потомстве», Science , 179 (4068): 90–2, Bibcode : 1973Sci...179...90T , doi : 10.1126/science .179.4068.90 , JSTOR 1734960 , PMID 4682135 , S2CID 29326420 .
^ Уиллард, DE (1978), Алгоритмы поиска в базе данных, ориентированные на предикаты , доктор философии. диссертация, Гарвардский университет .
^ Уиллард, Дэн Э. (1982), «Поддержание плотных последовательных файлов в динамической среде», Proc. 14-й симпозиум ACM по теории вычислений (STOC '82) , стр. 114–121, doi : 10.1145/800070.802183 , S2CID 15400034 .
^ Уиллард, Дэн Э. (1983), «Лог-логарифмические запросы диапазона наихудшего случая возможны в пространстве Θ( N )», Information Processing Letters , 17 (2): 81–84, doi : 10.1016/0020-0190(83 )90075-3 , МР 0731126 .
^ Фредман, Майкл Л .; Уиллард, Дэн Э. (1993), «Преодоление теоретико-информационной связи с объединенными деревьями», Journal of Computer and System Sciences , 47 (3): 424–436, doi : 10.1016/0022-0000(93)90040-4 , МР 1248864 .
^ Фредман, Майкл Л .; Уиллард, Дэн Э. (1994), «Трансдихотомические алгоритмы для минимальных остовных деревьев и кратчайших путей», Журнал компьютерных и системных наук , 48 (3): 533–551, doi : 10.1016/S0022-0000(05)80064 -9 .
^ Уиллард, Дэн Э. (2001), «Самопроверяющиеся системы аксиом, теорема о неполноте и связанные с ней принципы отражения», Журнал символической логики , 66 (2): 536–596, doi : 10.2307/2695030 , JSTOR 2695030 , MR 1833464 , S2CID 2822314 .

Ссылки

^ Алгоритмы поиска в базе данных, ориентированные на предикаты. , получено 4 февраля 2024 г.
^ Уиллард, Дэн , Проект математической генеалогии , получено 4 февраля 2024 г.
^ Уиллард, Дэн Э. , Библиотека Конгресса , получено 3 февраля 2024 г .; Дата рождения взята со страницы авторских прав докторской диссертации Уилларда.
^ «Некролог Дэна Уилларда (2023) - Олбани, Нью-Йорк - Albany Times Union» , Legacy.com , получено 22 марта 2023 г.
^ Биографические данные. Архивировано 9 мая 2009 г. на Wayback Machine , по состоянию на 4 июня 2013 г.
^ Симпсон, MJA; Симпсон, AE (1982), «Соотношение полов при рождении и социальный ранг у матерей-резусов», Nature , 300 (5891): 440–441, Bibcode : 1982Natur.300..440S , doi : 10.1038/300440a0 , PMID 7144897 , S2CID 4234180 .
^ Мэтьюз, Пол (2011), «Существует ли психологический непосредственный механизм, вызывающий эффект Триверса-Уилларда у людей? Результаты интернет-эксперимента по изучению желаемого полового состава детей после прайминга смертности» (PDF) , Общество, биология, & Человеческие дела , 76 (2): 11–23. ^{[ постоянная мертвая ссылка ]}.
^ де Берг, М.; ван Кревелд, М.; Овермарс, Миннесота ; Шварцкопф, О. (2008), Вычислительная геометрия: алгоритмы и приложения (3-е изд.), Springer-Verlag, p. 116, ISBN 9783540779735 .
^ Петерсон, Иварс (29 июня 1991 г.), «Вычисление «слитых деревьев» для разрушения барьеров: алгоритм, который ускоряет скорость сортировки информации компьютерами» , Science News .
^ Уиллард, Дэн Э. (2018), О пропасти, отделяющей цели программы согласованности Гильберта от второй теоремы о неполноте , arXiv : 1807.04717

[6] Триверс, РЛ ; Уиллард, DE (1973), «Естественный отбор способности родителей изменять соотношение полов в потомстве», Science , 179 (4068): 90–2, Bibcode : 1973Sci...179...90T , doi : 10.1126/science .179.4068.90 , JSTOR 1734960 , PMID 4682135 , S2CID 29326420 .

[9] Уиллард, DE (1978), Алгоритмы поиска в базе данных, ориентированные на предикаты , доктор философии. диссертация, Гарвардский университет .

[11] Уиллард, Дэн Э. (1982), «Поддержание плотных последовательных файлов в динамической среде», Proc. 14-й симпозиум ACM по теории вычислений (STOC '82) , стр. 114–121, doi : 10.1145/800070.802183 , S2CID 15400034 .

[12] Уиллард, Дэн Э. (1983), «Лог-логарифмические запросы диапазона наихудшего случая возможны в пространстве Θ( N )», Information Processing Letters , 17 (2): 81–84, doi : 10.1016/0020-0190(83 )90075-3 , МР 0731126 .

[13] Фредман, Майкл Л .; Уиллард, Дэн Э. (1993), «Преодоление теоретико-информационной связи с объединенными деревьями», Journal of Computer and System Sciences , 47 (3): 424–436, doi : 10.1016/0022-0000(93)90040-4 , МР 1248864 .

[15] Фредман, Майкл Л .; Уиллард, Дэн Э. (1994), «Трансдихотомические алгоритмы для минимальных остовных деревьев и кратчайших путей», Журнал компьютерных и системных наук , 48 (3): 533–551, doi : 10.1016/S0022-0000(05)80064 -9 .

[16] Уиллард, Дэн Э. (2001), «Самопроверяющиеся системы аксиом, теорема о неполноте и связанные с ней принципы отражения», Журнал символической логики , 66 (2): 536–596, doi : 10.2307/2695030 , JSTOR 2695030 , MR 1833464 , S2CID 2822314 .

[1] Алгоритмы поиска в базе данных, ориентированные на предикаты. , получено 4 февраля 2024 г.

[2] Уиллард, Дэн , Проект математической генеалогии , получено 4 февраля 2024 г.

[3] Уиллард, Дэн Э. , Библиотека Конгресса , получено 3 февраля 2024 г .; Дата рождения взята со страницы авторских прав докторской диссертации Уилларда.

[4] «Некролог Дэна Уилларда (2023) - Олбани, Нью-Йорк - Albany Times Union» , Legacy.com , получено 22 марта 2023 г.

[cv-5] Биографические данные. Архивировано 9 мая 2009 г. на Wayback Machine , по состоянию на 4 июня 2013 г.

[7] Симпсон, MJA; Симпсон, AE (1982), «Соотношение полов при рождении и социальный ранг у матерей-резусов», Nature , 300 (5891): 440–441, Bibcode : 1982Natur.300..440S , doi : 10.1038/300440a0 , PMID 7144897 , S2CID 4234180 .

[8] Мэтьюз, Пол (2011), «Существует ли психологический непосредственный механизм, вызывающий эффект Триверса-Уилларда у людей? Результаты интернет-эксперимента по изучению желаемого полового состава детей после прайминга смертности» (PDF) , Общество, биология, & Человеческие дела , 76 (2): 11–23. ^{[ постоянная мертвая ссылка ]}.

[10] де Берг, М.; ван Кревелд, М.; Овермарс, Миннесота ; Шварцкопф, О. (2008), Вычислительная геометрия: алгоритмы и приложения (3-е изд.), Springer-Verlag, p. 116, ISBN 9783540779735 .

[14] Петерсон, Иварс (29 июня 1991 г.), «Вычисление «слитых деревьев» для разрушения барьеров: алгоритм, который ускоряет скорость сортировки информации компьютерами» , Science News .

[17] Уиллард, Дэн Э. (2018), О пропасти, отделяющей цели программы согласованности Гильберта от второй теоремы о неполноте , arXiv : 1807.04717

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ бумага 1 ]

[ 6 ]

[ 7 ]

[ документ 2 ]

[ 8 ]

[ документ 3 ]

[ документ 4 ]

[ документ 5 ]

[ 9 ]

[ документ 6 ]

[ документ 7 ]

[ 10 ]

Базы данных авторитетного контроля
Международный	ЯВЛЯЮТСЯ ВИАФ WorldCat
Национальный	Соединенные Штаты Нидерланды Норвегия
академики	ЦиНии ДБЛП