Dan Willard: Amerikanischer Informatiker und Logiker

Dieser Artikel oder nachfolgende Abschnitt ist nicht hinreichend mit Belegen (beispielsweise Einzelnachweisen) ausgestattet. Angaben ohne ausreichenden Beleg könnten demnächst entfernt werden. Bitte hilf Wikipedia, indem du die Angaben recherchierst und gute Belege einfügst.

Januar">21. Januar 2023) war ein amerikanischer Informatiker und Logiker sowie Professor für Informatik an der University at Albany.

Willard absolvierte sein Grundstudium der Mathematik an der Stony Brook University und schloss es 1970 ab. Anschließend studierte er Mathematik an der Harvard University, wo er 1972 einen Master-Abschluss und 1978 einen Doktortitel erwarb. Nachdem er Harvard verlassen hatte, arbeitete er vier Jahre lang bei Bell Labs, bevor er 1983 an die Fakultät von Albany kam.

Obwohl er als Mathematiker ausgebildet und als Informatiker tätig war, ist Willards meistzitierte Veröffentlichung im Bereich der Evolutionsbiologie. Zusammen mit dem Biologen Robert Trivers veröffentlichte Willard 1973 die Trivers-Willard-Hypothese, wonach weibliche Säugetiere das Geschlechterverhältnis ihrer Nachkommen kontrollieren können und es evolutionär vorteilhaft wäre, wenn gesündere oder höher gestellte Weibchen mehr männliche Nachkommen hätten und weniger gesunde oder niedriger gestellte Weibchen mehr weibliche Nachkommen.

In der Informatik ist Willard vor allem für seine Arbeit mit Michael Fredman in den frühen 1990er Jahren über Ganzzahlensortierung und verwandte Datenstrukturen bekannt. Vor ihrer Forschung war schon lange bekannt, dass die Vergleichssortierung für die Sortierung einer Menge von ${\displaystyle n}$  Elementen die Zeit ${\displaystyle \Theta (n\log n)}$  benötigt, dass aber schnellere Algorithmen möglich sind, wenn man davon ausgehen kann, dass die Schlüssel, nach denen die Elemente sortiert werden, ganze Zahlen von mäßiger Größe sind. Zum Beispiel könnte die Sortierung von Schlüsseln im Bereich von ${\displaystyle 1}$  bis ${\displaystyle N}$  in der Zeit ${\displaystyle O(n(1+{\tfrac {\log N}{\log n}}))}$  durch Radix-Sortierung erreicht werden. Man ging jedoch davon aus, dass ganzzahlige Sortieralgorithmen zwangsläufig eine von ${\displaystyle N}$  abhängige Zeitschranke haben und für hinreichend große Werte von ${\displaystyle N}$  zwangsläufig langsamer sind als Vergleichssortierverfahren. In ihren 1990 angekündigten Forschungsarbeiten änderten Fredman und Willard diese Annahmen, indem sie das transdichotome Modell der Berechnung einführten. In diesem Modell zeigten sie, dass die ganzzahlige Sortierung in der Zeit ${\displaystyle O(n{\tfrac {\log n}{\log n}})}$  durch einen Algorithmus durchgeführt werden kann, der ihre Fusionsbaumdatenstruktur als Prioritätswarteschlange verwendet.

Seit dem Jahr 2000 befassen sich Willards Veröffentlichungen in erster Linie mit selbstverifizierenden Theorien: Logiksysteme, die im Vergleich zu allgemeineren Systemen so weit abgeschwächt sind, dass Gödels Unvollständigkeitssätze nicht auf sie anwendbar sind. Innerhalb dieser Systeme ist es möglich zu beweisen, dass die Systeme selbst logisch konsistent sind, ohne dass diese Deduktion zu dem Selbstwiderspruch führt, den der Gödelsche Satz für stärkere Systeme impliziert.