Jakie jest pierwsze użycie „drzew” w informatyce?

18

Mam małe pytanie historyczne, a mianowicie, jak głosi tytuł, szukam wczesnych zastosowań drzew (jako struktury danych, drzewa wyszukiwania, cokolwiek) w informatyce.

data-structures reference-request trees history john_leo
źródło
2
Jest prawdopodobne wcześniejsze użycie tego terminu w kontekście teorii grafów.
Juho,
Prawdopodobnie od samego początku . Masz na myśli tego rodzaju drzewa.
200_sukces

Odpowiedzi:

13

Wikipedia twierdzi, że pierwsze użycie drzewa w matematyce miało Cayley w 1857 roku.

Ponieważ wykorzystanie w informatyce jest zaczerpnięte bezpośrednio z matematyki, bardziej fundamentalne wydaje się pytanie, kiedy powstały. O ile informatycy pierwotnie nie nazwali drzew czymś innym, pierwszy informatyk, który użył „drzewa”, nie wydaje się bardziej znaczący niż, powiedzmy, pierwszy Australijczyk, który użył „drzewa”.

David Richerby
źródło
Cayley prawdopodobnie wymyślił słowo „drzewo”, ale drzewa były już używane (np. Przez Kirchhoffa). W XIX wieku matematycy tak naprawdę nie przejmowali się algorytmami (niektóre wyjątki tutaj). W tych pracach drzewa zdecydowanie nie były wykorzystywane jako struktura danych, podobnie jak drzewo wyszukiwania.
A.Schulz,
11

Według TAOCP Donalda Knutha, t. 1, str. 459 następujące artykuły można uznać za jeden z pierwszych występów drzew w CS.

  • HG Kahrimanian, Różnicowanie analityczne za pomocą komputera cyfrowego , Sympozjum nt. Programowania automatycznego, 6–14, 1952
  • KE Iverson i LR Johnson, raporty z badań IBM Corp. RC-390, RC-603 , 1961
  • AJ Perils i C. Thornton, Threaded trees , CACM 3, 195–204, 1960

Sprawdź TAOCP, aby uzyskać więcej informacji i więcej referencji.

A.Schulz
źródło
Dzięki, to wygląda bardzo obiecująco. Czy drugie odniesienie ma tytuł? Nie mam pod ręką TAOCP, pójdę później do biblioteki.
john_leo,
4
Jest to argument władzy, który może faktycznie zadziałać, biorąc pod uwagę, że Knuth jest uważnym zbieraczem referencji.
Raphael
INVERSON, KE Notacja programowa dla drzew. Raport z badań R - 390, II3M Research Center (styczeń 1961). To stąd: dl.acm.org/citation.cfm?id=366828, co również może być dobrym odniesieniem.
KWillets,
@Raphael Dosłownie napisał książkę o informatyce, prawda?
corsiKa
6

Izajasz: „„ I wyjdzie pręt z łodygi Jessego, a gałąź wyrosnie z jego korzeni ”

Drzewo jako model danych dla informacji genealogicznych jest rzeczywiście bardzo starożytne.

Michael Kay
źródło
2
„... w informatyce ”.
Raphael
@Raphael Fair point, choć prawdopodobnie jest to struktura danych, która jest z pewnością informatyką pod inną nazwą.
David Richerby,
3
Skłaniam się ku poglądowi Dijkstry, że informatyka dotyczy struktur danych i algorytmów i ma niewiele wspólnego z komputerami.
Michael Kay,
4

Znalazłem ten artykuł w (BCS) Computer Journal z 1960 r .:

PF Windley: Drzewa, lasy i przestawianie.

Wprowadza pojęcie „drzew”, krótko opisane przez Douglasa (1959) „[Sandy Douglas]” i przypisane Berners-Lee „[Conway Berners-Lee, ojciec Tima].

Co ciekawe, jego drzewa są botanicznie dokładniejsze niż współczesne drzewa CS, ponieważ mają korzenie na dole, a nie na górze!

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

Przypadkowo ostatnim cytatem w artykule jest artykuł, którego Windley jest współautorem Tony'ego Rowlanda Jonesa i „LF Kay”, co jest błędnym błędem dla LR Kay, mojego ojca, który kierował UCCA, centralnym systemem rekrutacji na uniwersytety w UK.

List Conwaya BL do Computer Journal komentujący ten artykuł oraz odpowiedź Windleya są podzielone między strony 174 i 184 następującego wydania:

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

Michael Kay
źródło
3

Rachunek Lambda sięga lat 30. XX wieku. Jego gramatyka jest wczesnym zastosowaniem drzew, szczególnie abstrakcyjnych drzew składniowych. Każdy termin LC jest drzewem. Zmienne to węzły liści. Zarówno abstrakty, jak i terminy aplikacji składają się z innych terminów, dlatego nie są węzłami typu liść.

Nie wiem, kiedy po raz pierwszy terminy LC były uważane za drzewa. Jednak wczesne dowody obejmujące LC wymagały analizy przypadków, podobnie jak robią to teraz programiści piszący programy, aby przejść AST.

Jake Mitchell
źródło