Was ist die früheste Verwendung von "Bäumen" in der Informatik?

18

Ich habe eine kleine geschichtliche Frage, nämlich, wie der Titel sagt, ich suche nach frühen Verwendungen von Bäumen (als Datenstruktur, Suchbaum, was auch immer) in der Informatik.

data-structures reference-request trees history john_leo
quelle
2
Es gibt wahrscheinlich eine frühere Verwendung des Begriffs im Kontext der Graphentheorie.
Juho
Vermutlich von Anfang an . Oh, du meinst diese Art von Bäumen.
200_success

Antworten:

13

Wikipedia sagt, dass Cayley 1857 zum ersten Mal einen Baum in der Mathematik verwendete.

Da der Gebrauch in der Informatik direkt der Mathematik entnommen ist, erscheint es grundlegender, zu fragen, wann sie dort entstanden sind. Sofern Informatiker Bäume ursprünglich nicht anders nannten, scheint der erste Informatiker, der "Baum" verwendet, nicht bedeutender zu sein als beispielsweise der erste Australier, der "Baum" verwendet.

David Richerby
quelle
Cayley hat wahrscheinlich das Wort "Baum" geprägt, aber Bäume wurden schon früher verwendet (z. B. von Kirchhoff). Im 19. Jahrhundert interessierten sich Mathematiker nicht wirklich für Algorithmen (einige Ausnahmen hier). Bäume wurden in diesen Arbeiten definitiv nicht als Datenstruktur wie ein Suchbaum verwendet.
A.Schulz,
11

Nach Donald Knuths TAOCP, Vol. 1, pg. 459 Die folgenden Arbeiten können als eine der ersten Erscheinungen von Bäumen in CS angesehen werden.

  • HG Kahrimanian, Analytische Differenzierung durch einen Digitalcomputer , Symposium über automatische Programmierung, 6–14, 1952
  • KE Iverson und LR Johnson, IBM Corp. Research Reports RC-390, RC-603 , 1961
  • AJ Perils und C. Thornton, Threaded trees , CACM 3, 195–204, 1960

Weitere Informationen und Referenzen finden Sie in TAOCP.

A.Schulz
quelle
Danke, das sieht sehr vielversprechend aus. Hat die zweite Referenz einen Titel? Ich habe TAOCP nicht zur Hand, ich gehe später in die Bibliothek.
john_leo
4
Dies ist ein Argument der Behörde, das möglicherweise tatsächlich funktioniert, da Knuth als sehr sorgfältiger Sammler von Referenzen bekannt ist.
Raphael
INVERSON, KE Eine Programmiernotation für Bäume. Forschungsbericht R - 390, II3M Forschungszentrum (Jan. 1961). Das ist von hier: dl.acm.org/citation.cfm?id=366828, was auch eine gute Referenz sein könnte.
KWillets
@Raphael Er hat buchstäblich das Buch über Informatik geschrieben, oder ...
corsiKa
6

Jesaja: "Und es wird ein Stab aus dem Stamm Isais hervorkommen, und ein Zweig wird aus seinen Wurzeln wachsen."

Der Baum als Datenmodell für genealogische Informationen ist in der Tat sehr alt.

Michael Kay
quelle
2
"... in der Informatik ."
Raphael
@Raphael Fair point, obwohl es sich wohl um eine Datenstruktur handelt, bei der es sich häufig um Informatik unter einem anderen Namen handelt.
David Richerby
3
Ich neige zu der Ansicht von Dijkstra, dass es in der Informatik nur um Datenstrukturen und Algorithmen geht und dass sie sehr wenig mit Computern zu tun hat.
Michael Kay
4

Ich fand diesen Artikel im (BCS) Computer Journal für 1960:

PF Windley: Bäume, Wälder und Neuordnung.

Er führt den Begriff "Bäume" ein, der von Douglas (1959) kurz "[Sandy Douglas]" beschrieben und Berners-Lee [Conway Berners-Lee, Vater von Tim] zugeschrieben wird.

Interessanterweise sind seine Bäume botanisch genauer als moderne CS-Bäume, da sie die Wurzel eher unten als oben haben!

http://comjnl.oxfordjournals.org/content/3/2/84.full.pdf+html?sid=a1c02733-1497-49e9-b308-a05c1dcca1df

Zufälligerweise handelt es sich bei dem letzten Zitat um ein Papier, das Windley gemeinsam mit Tony Rowland Jones und "LF Kay" verfasst hat. Dies ist ein Druckfehler für LR Kay, meinen Vater, der später die UCCA, das zentrale Zulassungssystem der Universität, leitete im Vereinigten Königreich.

Ein Brief von Conway BL an das Computer Journal mit Kommentaren zu diesem Artikel und eine Antwort von Windley sind auf die Seiten 174 und 184 der folgenden Ausgabe aufgeteilt:

http://comjnl.oxfordjournals.org/content/3/3/174.full.pdf+html http://comjnl.oxfordjournals.org/content/3/3/175.full.pdf+html

Michael Kay
quelle
3

Lambda-Kalkül stammt aus den 1930er Jahren. Seine Grammatik ist eine frühe Anwendung von Bäumen, insbesondere abstrakten Syntaxbäumen. Jeder LC-Term ist ein Baum. Variablen sind die Blattknoten. Sowohl Abstraktions- als auch Anwendungsbegriffe bestehen aus anderen Begriffen, sodass sie keine Blattknoten sind.

Ich weiß nicht, wann LC-Begriffe zuerst als Bäume gedacht wurden. Die frühen Beweise mit LC erforderten jedoch eine Fallanalyse, ähnlich wie es Programmierer tun, die Programme für Lauf-ASTs schreiben.

Jake Mitchell
quelle