Eu tenho uma pequena questão histórica, a saber, como o título diz, estou procurando usos iniciais de árvores (como estrutura de dados, árvore de pesquisa, o que for) na ciência da computação.
data-structures
reference-request
trees
history
john_leo
fonte
fonte
Respostas:
A Wikipedia diz que o primeiro uso da árvore em matemática foi por Cayley em 1857.
Como o uso em ciência da computação é retirado diretamente da matemática, parece mais fundamental perguntar quando eles se originaram lá. A menos que os cientistas da computação tenham chamado as árvores de outra coisa, o primeiro cientista da computação a usar "árvore" não parece mais significativo do que, digamos, o primeiro australiano a usar a "árvore".
fonte
De acordo com TAOCP de Donald Knuth, vol. 1, pág. 459 os seguintes artigos podem ser considerados como uma das primeiras aparições de árvores no CS.
Confira TAOCP para mais informações e mais referências.
fonte
Isaías: "" E sairá uma vara da haste de Jessé, e um ramo crescerá das suas raízes "
A árvore como modelo de dados para informações genealógicas é realmente muito antiga.
fonte
Encontrei este artigo no (BCS) Computer Journal de 1960:
PF Windley: Árvores, florestas e reorganização.
Ele introduz o conceito de "árvores", "descrito brevemente por Douglas (1959)" [Sandy Douglas] "e atribuído a Berners-Lee" [Conway Berners-Lee, pai de Tim].
Curiosamente, suas árvores são botanicamente mais precisas do que as árvores CS modernas, na medida em que têm a raiz no fundo e não no topo!
http://comjnl.oxfordjournals.org/content/3/2/84.full.pdf+html?sid=a1c02733-1497-49e9-b308-a05c1dcca1df
Coincidentemente, a última citação no artigo é de um artigo que Windley foi co-autor de Tony Rowland Jones e "LF Kay", que é um erro de impressão para LR Kay, meu pai, que passou a administrar o UCCA, o sistema central de admissões da universidade no Reino Unido.
Uma carta de Conway BL ao Computer Journal comentando este artigo e uma resposta de Windley estão divididas entre as páginas 174 e 184 da seguinte edição:
http://comjnl.oxfordjournals.org/content/3/3/174.full.pdf+html http://comjnl.oxfordjournals.org/content/3/3/175.full.pdf+html
fonte
O cálculo Lambda remonta aos anos 30. Sua gramática é uma aplicação inicial de árvores, especificamente árvores de sintaxe abstrata. Todo termo de LC é uma árvore. Variáveis são os nós das folhas. Os termos de abstração e de aplicação consistem em outros termos, portanto, são nós não-folha.
Não sei quando os termos da LC foram inicialmente considerados árvores. No entanto, as primeiras provas envolvendo LC exigiam análise de caso, bem como o que os programadores que escrevem programas para executar ASTs fazem agora.
fonte