Каково самое раннее использование «деревьев» в информатике?

18

У меня есть небольшой исторический вопрос, а именно, как следует из заголовка, я ищу раннее использование деревьев (в качестве структуры данных, дерева поиска и т. Д.) В компьютерной науке.

data-structures reference-request trees history john_leo
источник
2
Вероятно, более раннее использование этого термина в контексте теории графов.
Юхо
Вероятно, с самого начала . О, вы имеете в виду , что такие деревья.
200_success

Ответы:

13

Википедия говорит, что первое использование дерева в математике было Кейли в 1857 году.

Поскольку использование в информатике взято непосредственно из математики, кажется более фундаментальным спрашивать, когда они возникли там. Если компьютерные ученые изначально не называли деревья чем-то другим, первый ученый, который использовал «дерево», не кажется более значимым, чем, скажем, первый австралиец, который использовал «дерево».

Дэвид Ричерби
источник
Кейли, вероятно, придумал слово «дерево», но деревья использовались ранее (например, Кирхгофом). В 19 веке математики не особо интересовались алгоритмами (за некоторыми исключениями здесь). Деревья определенно не использовались в качестве структуры данных, как дерево поиска в этих работах.
А.Шульц
11

Согласно TAOCP Дональда Кнута, Vol. 1, стр. 459 следующие работы могут рассматриваться как одно из первых появлений деревьев в CS.

  • Х.Г. Кахриманян, Аналитическое дифференцирование с помощью цифрового компьютера , Симпозиум по автоматическому программированию, 6–14, 1952
  • К.Э. Иверсон и Л.Р. Джонсон, исследовательские отчеты IBM Corp. RC-390, RC-603 , 1961
  • AJ Perils и C. Thornton, Резьбовые деревья , CACM 3, 195–204, 1960

Проверьте TAOCP для получения дополнительной информации и большего количества ссылок.

A.Schulz
источник
Спасибо, это выглядит очень многообещающе. У второй ссылки есть заголовок? У меня нет TAOCP под рукой, я пойду в библиотеку позже.
john_leo
4
Это аргумент со стороны авторитета, который действительно может сработать, учитывая, что Кнут известен как очень усердный собиратель ссылок.
Рафаэль
ИНВЕРСОН, К.Е. Программная запись для деревьев. Исследовательский отчет R - 390, Исследовательский центр II3M (январь 1961). Отсюда: dl.acm.org/citation.cfm?id=366828, который также может быть хорошим справочным материалом.
KWillets
@ Рафаэль Он буквально написал книгу по информатике, не так ли ...
corsiKa
6

Исаия: «" И выйдет жезл из стебля Иессея, и ветвь вырастет из его корней "

Дерево как модель данных для генеалогической информации действительно очень древнее.

Майкл Кей
источник
2
"... в информатике ."
Рафаэль
@ Рафаэль Справедливая точка зрения, хотя, возможно, это структура данных, которая является крошечно компьютерной наукой под другим именем.
Дэвид Ричерби
3
Я склоняюсь к мнению Дейкстры о том, что информатика - это все о структурах данных и алгоритмах и имеет мало общего с компьютерами.
Майкл Кей
4

Я нашел эту статью в (BCS) Computer Journal за 1960 год:

PF Windley: деревья, леса и перестановка.

Он вводит концепцию «деревьев», «кратко описанную Дугласом (1959 г.)« [Сэнди Дуглас] »и приписываемую Бернерс-Ли» [Конвей Бернерс-Ли, отец Тима].

Интересно, что его деревья ботанически более точны, чем современные CS-деревья, в том смысле, что они имеют корень снизу, а не сверху!

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

По совпадению, последняя цитата в статье относится к статье, которую Виндли в соавторстве с Тони Роулендом Джонсом и "Л.Ф. Кей", что является опечаткой для Л.Р. Кея, моего отца, который продолжал управлять UCCA, центральной системой приема в университеты. в Соединенном Королевстве.

Письмо Конвея Б.Л. в Компьютерный журнал с комментариями к этому документу и ответ Виндли разбиты на страницы 174 и 184 следующего выпуска:

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

Майкл Кей
источник
3

Лямбда-исчисление восходит к 1930-м годам. Его грамматика является ранним применением деревьев, в частности абстрактных синтаксических деревьев. Каждый термин LC является деревом. Переменные являются листовыми узлами. Термины абстракции и приложения состоят из других терминов, поэтому они являются неконцевыми узлами.

Я не знаю, когда термины LC были впервые восприняты как деревья. Однако ранние доказательства, включающие LC, требовали анализа случаев, во многом как то, что сейчас делают программисты, пишущие программы для обхода AST.

Джейк Митчелл
источник