Quelle est la première utilisation des «arbres» en informatique?

18

J'ai une petite question d'histoire, à savoir, comme le titre l'indique, je recherche les premières utilisations des arbres (comme structure de données, arbre de recherche, etc.) en informatique.

data-structures reference-request trees history john_leo
la source
2
Il y a probablement une utilisation antérieure du terme dans le contexte de la théorie des graphes.
Juho
Probablement depuis le début . Oh, tu veux dire ce genre d'arbres.
200_success

Réponses:

13

Wikipédia dit que la première utilisation de l'arbre en mathématiques a été faite par Cayley en 1857.

L'usage en informatique étant directement emprunté aux mathématiques, il semble plus fondamental de se demander d'où elles proviennent. À moins que les informaticiens aient initialement appelé les arbres autre chose, le premier informaticien à utiliser "arbre" ne semble pas plus important que, disons, le premier Australien à utiliser "arbre".

David Richerby
la source
Cayley a probablement inventé le mot «arbre», mais des arbres ont déjà été utilisés (par exemple, par Kirchhoff). Au XIXe siècle, les mathématiciens ne se souciaient pas vraiment des algorithmes (à quelques exceptions près). Les arbres n'étaient certainement pas utilisés comme structure de données comme un arbre de recherche dans ces travaux.
A.Schulz
11

Selon le TAOCP de Donald Knuth, vol. 1, p. 459 les articles suivants pourraient être considérés comme l'une des premières apparitions d'arbres en CS.

  • HG Kahrimanian, Différenciation analytique par un ordinateur numérique , Symposium sur la programmation automatique, 6-14, 1952
  • Rapports de recherche KE Iverson et LR Johnson, IBM Corp. RC-390, RC-603 , 1961
  • AJ Perils et C. Thornton, Arbres filetés, MCCA 3, 195-204, 1960

Consultez TAOCP pour plus d'informations et plus de références.

A.Schulz
la source
Merci, cela semble très prometteur. La deuxième référence a-t-elle un titre? Je n'ai pas TAOCP à portée de main, j'irai à la bibliothèque plus tard.
john_leo
4
C'est un argument de l'autorité qui peut réellement fonctionner, étant donné que Knuth est connu pour être un collecteur de références très diligent.
Raphael
INVERSON, KE Une notation de programmation pour les arbres. Rapport de recherche R-390, Centre de recherche II3M (janvier 1961). C'est d'ici: dl.acm.org/citation.cfm?id=366828 qui pourrait également être une bonne référence.
KWillets
@Raphael Il a littéralement écrit le livre sur l'informatique, n'est-ce pas ...
corsiKa
6

Ésaïe: "" Et il sortira une verge de la tige d'Isaï, et une branche jaillira de ses racines "

L'arbre comme modèle de données pour les informations généalogiques est en effet très ancien.

Michael Kay
la source
2
"... en informatique ."
Raphael
@Raphael Fair point, bien qu'il s'agisse sans doute d'une structure de données, qui est ténuement informatique par un autre nom.
David Richerby
3
J'ai tendance à penser que Dijkstra considère que l'informatique concerne uniquement les structures de données et les algorithmes, et a très peu à voir avec les ordinateurs.
Michael Kay
4

J'ai trouvé cet article dans le (BCS) Computer Journal pour 1960:

PF Windley: Arbres, forêts et réaménagement.

Il introduit le concept d '"arbres", "décrit brièvement par Douglas (1959)" [Sandy Douglas] "et attribué à Berners-Lee" [Conway Berners-Lee, père de Tim].

Fait intéressant, ses arbres sont botaniquement plus précis que les arbres CS modernes, en ce sens qu'ils ont la racine en bas plutôt qu'en haut!

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

Par coïncidence, la dernière citation de l'article est celle d'un article que Windley a co-écrit avec Tony Rowland Jones et "LF Kay", qui est une faute de frappe pour LR Kay, mon père, qui a ensuite dirigé l'UCCA, le système central d'admission des universités au Royaume-Uni.

Une lettre de Conway BL au Computer Journal commentant ce document et une réponse de Windley sont réparties entre les pages 174 et 184 du numéro suivant:

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

Michael Kay
la source
3

Le calcul lambda remonte aux années 1930. Sa grammaire est une application précoce des arbres, en particulier des arbres à syntaxe abstraite. Chaque terme LC est un arbre. Les variables sont les nœuds feuilles. Les termes d'abstraction et d'application sont constitués d'autres termes, ce sont donc des nœuds non foliaires.

Je ne sais pas quand les termes LC ont d'abord été considérés comme des arbres. Cependant, les premières preuves impliquant LC nécessitaient une analyse de cas, un peu comme ce que les programmeurs écrivant des programmes pour parcourir les AST font maintenant.

Jake Mitchell
la source