ダン・ウィラード

ダン・エドワード・ウィラード
ダン・エドワード・ウィラード
	2008 年アルバニー大学学長優秀研究賞受賞者のダン E. ウィラード氏の肖像画。
生まれる	1948年9月19日; ニューヨーク市、ニューヨーク州、米国
死亡	2023年1月23日; アルバニー、ニューヨーク州、米国
母校	ハーバード大学（博士号）
	科学者としてのキャリア
フィールド	コンピュータサイエンス
機関	ニューヨーク州立大学アルバニー校
論文	述語指向データベース検索アルゴリズム (1979)
博士課程の指導教員	ジェラルド・サックス

ダン・エドワード・ウィラード（1948年9月19日^[3] - 2023年1月21日^{[4] ）は、アメリカのコンピュータ科学者、論理学者であり、}オールバニー大学のコンピュータサイエンスの教授であった。

教育とキャリア

ウィラードはストーニーブルック大学で数学の学士号を取得し、1970年に卒業した。その後ハーバード大学で数学の大学院課程に進み、1972年に修士号、1978年に博士号を取得した。ハーバード大学を離れた後、ベル研究所で4年間働き、1983年にアルバニー大学の教授陣に加わった。^[5]

貢献

数学者として訓練され、コンピュータ科学者として働いていたにもかかわらず、ウィラードの最も引用されている出版物は進化生物学に関するものである。1973年、ウィラードは生物学者ロバート・トリヴァースとともに、トリヴァース・ウィラード仮説を発表した。これは、雌の哺乳類は子孫の性比を制御でき、より健康または地位の高い雌がより多くの雄の子孫を産み、より不健康または地位の低い雌がより多くの雌の子孫を産むことが進化的に有利であるというものである。^[論文1]この理論は、特にこの制御のメカニズムを提案していなかったため、当時は物議を醸したが、後に観察によって検証され、^[6]「20世紀の進化生物学で最も影響力があり、最も引用されている論文の1つ」と呼ばれている。^[7]

ウィラードの 1978 年の学位論文である範囲検索データ構造に関する研究^{[論文 2] は}、分数カスケーディングの手法の前身の 1 つであり^[8]、1980 年代を通じてウィラードは関連するデータ構造の問題に取り組み続けました。範囲検索の研究を続けるとともに、彼は順序維持問題に関する重要な初期の研究を行い^{[論文 3]}、メモリ要件の少ない小さな整数の集合を格納および検索するためのデータ構造であるx 高速トライとy 高速トライを発明しました^{[論文 4] 。}

コンピュータサイエンスにおいて、ウィラードは1990 年代初頭にマイケル・フレッドマンと行った整数ソートおよび関連データ構造に関する研究で最もよく知られています。彼らの研究以前から、比較ソートでは項目セットのソートに時間がかかるものの、項目をソートするキーが中程度のサイズの整数であると想定できれば、より高速なアルゴリズムが可能であることは長い間知られていました。たとえば、からまでの範囲のキーのソートは、基数ソートによって100 分以内に実行できます。しかし、整数ソートアルゴリズムはに依存する時間制限を必然的に持ち、が十分に大きいの値に対しては必然的に比較ソートよりも遅くなると想定されていました。1990 年に最初に発表された研究で、フレッドマンとウィラードはトランス二分法計算モデルを導入することでこれらの想定を変更しました。このモデルでは、彼らは、融合木データ構造を優先キューとして使用したアルゴリズムによって整数ソートを 100 分以内に実行できることを示しました。^[論文5]^[9]この研究のフォローアップとして、フレッドマンとウィラードは、同様の高速化が最小全域木や最短経路を含む他の標準的なアルゴリズムの問題にも適用できることを示しました。^[論文6] $\Theta (n\log n)$ $n$ $1$ $N$ $O(n(1+{\tfrac {\log N}{\log n}}))$ $N$ $N$ $O(n{\tfrac {\log n}{\log \log n}})$

2000 年以降、ウィラードの出版物は主に自己検証理論に関するものであった。これは、より一般的に研究されているシステムと比較して、ゲーデルの不完全性定理を適用できないほど十分に弱められた論理システムである。これらのシステムでは、システム自体が論理的に一貫していることを証明することが可能であり、この推論はゲーデルの定理がより強力なシステムに対して示唆する自己矛盾につながることはない。^{[論文 7]}この分野での彼の研究成果をまとめたプレプリントで、ウィラードは、これらの論理システムは、人類の絶滅の可能性を生き延び、一貫して推論し、自身の一貫性を認識できる人工知能の開発に重要になると推測した。^[10]

主な出版物

^ Trivers, RL ; Willard, DE (1973)、「子孫の性比を変化させる親の能力の自然選択」、Science、179 (4068): 90–2、Bibcode :1973Sci...179...90T、doi :10.1126/science.179.4068.90、JSTOR 1734960、PMID 4682135、S2CID 29326420。
^ Willard, DE (1978)、「述語指向データベース検索アルゴリズム」、博士論文、ハーバード大学。
^ Willard, Dan E. (1982)、「動的環境における高密度シーケンシャルファイルの維持」、Proc. 14th ACM Symposium on Theory of Computing (STOC '82)、pp. 114–121、doi :10.1145/800070.802183、S2CID 15400034。
^ Willard, Dan E. (1983)、「対数対数最悪ケース範囲クエリは空間Θ( N )で可能」、Information Processing Letters、17 (2): 81–84、doi :10.1016/0020-0190(83)90075-3、MR 0731126。
^ Fredman, Michael L. ; Willard, Dan E. (1993)、「融合木による情報理論的限界の超越」、Journal of Computer and System Sciences、47 (3): 424–436、doi :10.1016/0022-0000(93)90040-4、MR 1248864。
^ Fredman, Michael L. ; Willard, Dan E. (1994)、「最小全域木と最短経路のためのトランス二分アルゴリズム」、Journal of Computer and System Sciences、48 (3): 533–551、doi : 10.1016/S0022-0000(05)80064-9。
^ ウィラード、ダン E. (2001)、「自己検証公理システム、不完全性定理および関連する反射原理」、Journal of Symbolic Logic、66 (2): 536–596、doi :10.2307/2695030、JSTOR 2695030、MR 1833464、S2CID 2822314。

参考文献

^ 述語指向データベース検索アルゴリズム。2024年2月4日取得
^ ウィラード、ダン、数学系譜プロジェクト、2024年2月4日閲覧
^ ウィラード、ダン・E.、米国議会図書館、 2024年2月3日閲覧; 生年月日はウィラード博士論文の著作権ページから引用。
^ "ダン・ウィラード死亡記事 (2023) - ニューヨーク州アルバニー - アルバニー・タイムズ・ユニオン"、Legacy.com 、 2023-03-22取得
^ 履歴書 Archived 2009-05-09 at the Wayback Machine、アクセス日2013-06-04。
^ シンプソン、MJA; シンプソン、AE (1982)、「アカゲザルの母親の出生性比と社会的地位」、ネイチャー、300 (5891): 440–441、Bibcode :1982Natur.300..440S、doi :10.1038/300440a0、PMID 7144897、S2CID 4234180。
^ マシューズ、ポール (2011)、「人間にトリヴァース・ウィラード効果を誘発する心理的近接メカニズムはあるか? 死亡率プライミング後の子供の望ましい性別構成を調べるインターネット実験の結果」(PDF)、社会、生物学、および人間問題、76 (2): 11–23^{[永久リンク切れ‍ ]}。
^ デ・バーグ、M.;ヴァン・クレフェルト、M. Overmars, MH州; Schwarzkopf, O. (2008)、Computational Geometry: Algorithms and Applications (3rd ed.)、Springer-Verlag、p. 116、ISBN 9783540779735。
^ ピーターソン、アイヴァース（1991年6月29日）、「障壁を破る「融合木」の計算：コンピュータが情報をソートする速度を速めるアルゴリズム」、サイエンスニュース。
^ ウィラード、ダン E. (2018)、ヒルベルトの無矛盾性プログラムの目標と第 2 不完全性定理を分ける溝について、arXiv : 1807.04717

[6] Trivers, RL ; Willard, 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] Willard, DE (1978)、「述語指向データベース検索アルゴリズム」、博士論文、ハーバード大学。

[11] Willard, Dan E. (1982)、「動的環境における高密度シーケンシャルファイルの維持」、Proc. 14th ACM Symposium on Theory of Computing (STOC '82)、pp. 114–121、doi :10.1145/800070.802183、S2CID 15400034。

[12] Willard, Dan E. (1983)、「対数対数最悪ケース範囲クエリは空間Θ( N )で可能」、Information Processing Letters、17 (2): 81–84、doi :10.1016/0020-0190(83)90075-3、MR 0731126。

[13] Fredman, Michael L. ; Willard, Dan E. (1993)、「融合木による情報理論的限界の超越」、Journal of Computer and System Sciences、47 (3): 424–436、doi :10.1016/0022-0000(93)90040-4、MR 1248864。

[15] Fredman, Michael L. ; Willard, Dan E. (1994)、「最小全域木と最短経路のためのトランス二分アルゴリズム」、Journal of Computer and System Sciences、48 (3): 533–551、doi : 10.1016/S0022-0000(05)80064-9。

[16] ウィラード、ダン E. (2001)、「自己検証公理システム、不完全性定理および関連する反射原理」、Journal of Symbolic Logic、66 (2): 536–596、doi :10.2307/2695030、JSTOR 2695030、MR 1833464、S2CID 2822314。

[1] 述語指向データベース検索アルゴリズム。2024年2月4日取得

[2] ウィラード、ダン、数学系譜プロジェクト、2024年2月4日閲覧

[3] ウィラード、ダン・E.、米国議会図書館、 2024年2月3日閲覧; 生年月日はウィラード博士論文の著作権ページから引用。

[4] "ダン・ウィラード死亡記事 (2023) - ニューヨーク州アルバニー - アルバニー・タイムズ・ユニオン"、Legacy.com 、 2023-03-22取得

[cv-5] 履歴書 Archived 2009-05-09 at the Wayback Machine、アクセス日2013-06-04。

[7] シンプソン、MJA; シンプソン、AE (1982)、「アカゲザルの母親の出生性比と社会的地位」、ネイチャー、300 (5891): 440–441、Bibcode :1982Natur.300..440S、doi :10.1038/300440a0、PMID 7144897、S2CID 4234180。

[8] マシューズ、ポール (2011)、「人間にトリヴァース・ウィラード効果を誘発する心理的近接メカニズムはあるか? 死亡率プライミング後の子供の望ましい性別構成を調べるインターネット実験の結果」(PDF)、社会、生物学、および人間問題、76 (2): 11–23^{[永久リンク切れ‍ ]}。

[10] デ・バーグ、M.;ヴァン・クレフェルト、M. Overmars, MH州; Schwarzkopf, O. (2008)、Computational Geometry: Algorithms and Applications (3rd ed.)、Springer-Verlag、p. 116、ISBN 9783540779735。

[14] ピーターソン、アイヴァース（1991年6月29日）、「障壁を破る「融合木」の計算：コンピュータが情報をソートする速度を速めるアルゴリズム」、サイエンスニュース。

[17] ウィラード、ダン E. (2018)、ヒルベルトの無矛盾性プログラムの目標と第 2 不完全性定理を分ける溝について、arXiv : 1807.04717

教育とキャリア

貢献

主な出版物

参考文献

関連するトピック

ニューヨーク市

アルバニー、ニューヨーク州

ハーバード大学

コンピュータサイエンス