Apa penggunaan awal "pohon" dalam ilmu komputer?

18

Saya punya sedikit pertanyaan sejarah, yaitu, seperti judulnya, saya mencari kegunaan awal pohon (sebagai struktur data, pohon pencarian, apa pun) dalam ilmu komputer.

data-structures reference-request trees history john_leo
sumber
2
Kemungkinan ada penggunaan istilah sebelumnya dalam konteks teori grafik.
Juho
Mungkin sejak awal . Oh, Anda berarti bahwa jenis pohon.
200_sukses

Jawaban:

13

Wikipedia mengatakan bahwa penggunaan pertama pohon dalam matematika adalah oleh Cayley pada tahun 1857.

Karena penggunaan dalam ilmu komputer diambil langsung dari matematika, tampaknya lebih mendasar untuk bertanya kapan mereka berasal di sana. Kecuali jika para ilmuwan komputer awalnya menyebut pohon sebagai sesuatu yang lain, ilmuwan komputer pertama yang menggunakan "tree" tampaknya tidak lebih penting daripada, katakanlah, orang Australia pertama yang menggunakan "tree".

David Richerby
sumber
Cayley mungkin menciptakan kata "pohon", tetapi pohon telah digunakan sebelumnya (misalnya, oleh Kirchhoff). Pada abad ke-19 ahli matematika tidak terlalu peduli tentang algoritma (beberapa pengecualian di sini). Pohon jelas tidak digunakan sebagai struktur data seperti pohon pencarian dalam karya-karya ini.
A.Schulz
11

Menurut TAOCP Donald Knuth, Vol. 1, hal. 459 makalah-makalah berikut dapat dianggap sebagai salah satu penampakan pertama pohon di CS.

  • HG Kahrimanian, Diferensial Analitik dengan Komputer Digital , Simposium Pemrograman Otomatis, 6–14, 1952
  • KE Iverson dan LR Johnson, laporan penelitian IBM Corp., RC-390, RC-603 , 1961
  • AJ Perils dan C. Thornton, Pohon berulir , CACM 3, 195–204, 1960

Lihatlah TAOCP untuk informasi lebih lanjut dan lebih banyak referensi.

A.Schulz
sumber
Terima kasih, itu terlihat sangat menjanjikan. Apakah referensi kedua memiliki judul? Saya tidak memiliki TAOCP, saya akan pergi ke perpustakaan nanti.
john_leo
4
Ini adalah argumen oleh otoritas yang mungkin benar-benar berfungsi, mengingat bahwa Knuth dikenal sebagai pengumpul referensi yang sangat rajin.
Raphael
INVERSON, KE Notasi pemrograman untuk pohon. Laporan Penelitian R - 390, II3M Research Center (Jan 1961). Itu dari sini: dl.acm.org/citation.cfm?id=366828 yang juga bisa menjadi referensi yang bagus.
KWillets
@ Raphael Dia benar-benar menulis buku tentang ilmu komputer, kan ...
corsiKa
6

Yesaya: "" Dan akan keluar tongkat dari batang Isai, dan sebuah ranting akan tumbuh dari akarnya "

Pohon sebagai model data untuk informasi silsilah memang sangat kuno.

Michael Kay
sumber
2
"... dalam ilmu komputer ."
Raphael
@Raphael Fair point, meskipun ini bisa dibilang sebuah struktur data, yang merupakan ilmu komputer dengan nama lain.
David Richerby
3
Saya cenderung pada pandangan Dijkstra bahwa ilmu komputer adalah semua tentang struktur data dan algoritma, dan sangat sedikit hubungannya dengan komputer.
Michael Kay
4

Saya menemukan makalah ini di Jurnal Komputer (BCS) untuk tahun 1960:

PF Windley: Pohon, hutan, dan penataan ulang.

Dia memperkenalkan konsep "pohon", "dijelaskan secara singkat oleh Douglas (1959)" [Sandy Douglas] "dan dikaitkan dengan Berners-Lee" [Conway Berners-Lee, ayah Tim].

Menariknya pohon-pohonnya secara botani lebih akurat daripada pohon-pohon CS modern, karena mereka memiliki akar di bagian bawah daripada di atas!

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

Secara kebetulan, kutipan terakhir dalam makalah ini adalah sebuah makalah yang ditulis bersama Windley dengan Tony Rowland Jones dan "LF Kay", yang merupakan salah cetak untuk LR Kay, ayah saya, yang kemudian menjalankan UCCA, sistem Penerimaan Universitas pusat di Inggris.

Sebuah surat dari Conway BL kepada Computer Journal mengomentari makalah ini, dan jawaban dari Windley, terbagi antara halaman 174 dan 184 dari masalah berikut:

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

Michael Kay
sumber
3

Tanggal kalkulus Lambda kembali ke tahun 1930-an. Tata bahasanya adalah aplikasi awal pohon, khususnya pohon sintaksis abstrak. Setiap istilah LC adalah pohon. Variabelnya adalah simpul daun. Istilah abstraksi dan aplikasi terdiri dari istilah lain, sehingga keduanya merupakan simpul non-daun.

Saya tidak tahu kapan istilah LC pertama kali dianggap sebagai pohon. Namun, bukti awal yang melibatkan LC memerlukan analisis kasus, seperti yang dilakukan oleh programer yang menulis program untuk menjalankan AST sekarang.

Jake Mitchell
sumber