دان ويلارد

كان دان إدوارد ويلارد (19 سبتمبر 1948 ^{[ 3 ]} - 21 يناير 2023 ^{[ 4 ]} ) عالم حاسوب ومنطقي أمريكي، وأستاذ علوم الحاسوب في جامعة ألباني .

أكمل ويلارد دراسته الجامعية في الرياضيات في جامعة ستوني بروك ، وتخرج عام 1970. ثم تابع دراساته العليا في الرياضيات في جامعة هارفارد ، وحصل على درجة الماجستير عام 1972 ودرجة الدكتوراه عام 1978. بعد مغادرته هارفارد، عمل في مختبرات بيل لمدة أربع سنوات قبل انضمامه إلى هيئة التدريس في ألباني عام 1983. ^{[ 5 ]}

على الرغم من تدريبه كرياضي وعمله كعالم حاسوب، إلا أن أكثر منشورات ويلارد استشهادًا تقع في مجال علم الأحياء التطوري . ففي عام 1973، نشر ويلارد ، بالاشتراك مع عالم الأحياء روبرت تريفرز ، فرضية تريفرز-ويلارد ، التي تنص على أن إناث الثدييات قادرة على التحكم في نسبة الجنس في نسلها، وأن من مصلحة الإناث الأكثر صحة أو ذات المكانة الاجتماعية الأعلى إنجاب عدد أكبر من الذكور، بينما من مصلحة الإناث الأقل صحة أو ذات المكانة الاجتماعية الأدنى إنجاب عدد أكبر من الإناث. ^{[ الورقة البحثية 1 ]} أثارت هذه النظرية جدلًا واسعًا في ذلك الوقت، لا سيما لعدم اقتراحها أي آلية لهذا التحكم، إلا أنها ثبتت صحتها لاحقًا من خلال الملاحظة، ^{[ 6 ]} ووُصفت بأنها "إحدى أكثر الأوراق البحثية تأثيرًا واستشهادًا في علم الأحياء التطوري في القرن العشرين". ^{[ 7 ]}

كانت أطروحة ويلارد لعام 1978 حول هياكل بيانات البحث النطاقي ^{[ الورقة البحثية 2 ]} من أوائل الأعمال التي سبقت تقنية التتالي الجزئي ^{[ 8 ]} ، وخلال ثمانينيات القرن العشرين، واصل ويلارد العمل على مشاكل هياكل البيانات ذات الصلة. إلى جانب استمراره في العمل على البحث النطاقي، أنجز أعمالًا مبكرة هامة حول مشكلة الحفاظ على الترتيب [ ^{الورقة البحثية 3 ]} ، وابتكر هياكل البيانات "شجرة البحث السريعة x" و " شجرة البحث السريعة y" ، ^وهي هياكل بيانات لتخزين مجموعات الأعداد الصحيحة الصغيرة والبحث فيها بمتطلبات ذاكرة منخفضة ^{[ الورقة البحثية 4 ] .}

في مجال علوم الحاسوب، يشتهر ويلارد بعمله مع مايكل فريدمان في أوائل التسعينيات على فرز الأعداد الصحيحة وهياكل البيانات ذات الصلة. قبل بحثهما، كان من المعروف منذ فترة طويلة أن فرز المقارنة يتطلب وقتًا${\displaystyle \Theta (n\log n)}$لفرز مجموعة من${\displaystyle n}$العناصر، ولكن يمكن استخدام خوارزميات أسرع إذا أمكن افتراض أن المفاتيح التي يتم فرز العناصر بناءً عليها هي أعداد صحيحة ذات حجم متوسط. على سبيل المثال، فرز المفاتيح في النطاق من${\displaystyle 1}$ل${\displaystyle N}$يمكن إنجاز ذلك في الوقت المناسب${\displaystyle O(n(1+{\tfrac {\log N}{\log n}}))}$باستخدام فرز الجذر . ومع ذلك، كان يُفترض أن خوارزميات فرز الأعداد الصحيحة سيكون لها بالضرورة حد زمني يعتمد على${\displaystyle N}$وسيكون بالضرورة أبطأ من فرز المقارنة بالنسبة للقيم الكبيرة بما فيه الكفاية لـ${\displaystyle N}$في بحث أُعلن عنه لأول مرة عام 1990، غيّر فريدمان وويلارد هذه الافتراضات من خلال تقديم نموذج الحوسبة العابرة للثنائية . في هذا النموذج، أظهرا أنه يمكن فرز الأعداد الصحيحة في وقت${\displaystyle O(n{\tfrac {\log n}{\log \log n}})}$باستخدام خوارزمية تعتمد على بنية بيانات شجرة الاندماج كقائمة انتظار ذات أولوية . ^{[ الورقة 5 ] [ 9 ]} وفي متابعة لهذا العمل، أظهر فريدمان وويلارد أيضًا إمكانية تطبيق تحسينات مماثلة على مسائل خوارزمية قياسية أخرى، بما في ذلك الأشجار الممتدة الدنيا وأقصر المسارات . ^{[ الورقة 6 ]}

بعد عام 2000، انصبّت منشورات ويلارد بشكل أساسي على النظريات ذاتية التحقق : وهي أنظمة منطقية أُضعفت بشكل كافٍ، مقارنةً بالأنظمة الأكثر شيوعًا، لمنع تطبيق نظريات عدم الاكتمال لغودل عليها. ضمن هذه الأنظمة، يُمكن إثبات اتساقها المنطقي، دون أن يؤدي هذا الاستنتاج إلى التناقض الذاتي الذي تُشير إليه نظرية غودل بالنسبة للأنظمة الأقوى. ^{[ الورقة 7 ]} في ورقة بحثية أولية تُوجز مجمل أعماله في هذا المجال، تكهّن ويلارد بأن هذه الأنظمة المنطقية ستكون ذات أهمية في تطوير ذكاء اصطناعي قادر على النجاة من الانقراض المُحتمل للبشرية، والتفكير بشكل متسق، والتعرف على اتساقها الذاتي. ^{[ 10 ]}