Дерево; его смысл и значение

[commator]

все сильнее убеждаюсь, что Дональд Кнут вовсе не просто так изложил “теорию деревьев” именно так, как он ее изложил.

Не отвлекайтесь.

Здесь не вообще деревья или дерево обсуждаются, а вполне определенное Дерево, описанное, например, в книге

Грэхем Р., Кнут Д., Паташник О.
Конкретная математика.
http://www.px-pict.com/10/4/4/13.html

А также выясняется его возможные значение и смысл для теории музыки.
“Фича” этого бесконечного бинарного дерева заключается в определенной разметке его вершин рациональными отношениями.

[Математик]

Не отвлекайтесь.

Отвлечения нет. Дело в том, что Дерево Штерна-Броко (ДШБ) определяется через понятие бинарного дерева:

Давайте вдумаемся в смысл написанного у Грэхема Р., Кнута Д., Паташника О.
“Всю совокупность вставок можно представить в виде бесконечного бинарного дерева, верхние уровни которого выглядят так …:”
http://www.px-pict.com/10/4/4/13.html

Не понимая, что такое “бинарное дерево”, невозможно понять, что такое Дерево Штерна-Броко (ДШБ).
Грэхем Р., Кнут Д., Паташник О. смогли так определить ДШБ только потому, что в их головах уже существовала к тому времени идея бинарного дерева, известная им по разнообразным своим воплощениям. Одним из таких воплощений и является упомянутое мною выше “Древо Порфирия”.

Кстати говоря, посмотрите на рисунок на титульном листе книги Н. Нильсона “Искусственный интеллект”:
http://www.px-pict.com/9/7/4/1/02.html

Это ли не перст указующий, какие деревья нам нужны?

[Математик]

Еще один пример воплощения идеи корневого дерева в Computer Science:
http://www.px-pict.com/9/7/3/3/7/5.html

Запомним вот это:
“ …чаще всего информация организовывается в виде дерева с целью быстрого нахождения данных”.

[Математик]

Я не против использования “костыликов”, если они оказываются полезными.

И с этой целью предложил в свое время возвести вокруг собственно Дерева Штерна – Броко (ДШБ) вспомогательные “строительные леса”:
http://forum.arbuz.uz/index.php?showtopic=1795&st=20
(постинг от 4 дек 2006 г. )

Но при этом нужно четко понимать, что эти “строительные леса” есть все же не более чем полезные вспомогательные конструкции и что:

“Честное” Дерево Штерна – Броко изображено на сайте mathworld:

Возможно, Вам будет полезно посмотреть на изображение Дерева на сайте mathworld:
http://mathworld.wolfram.com/Stern-BrocotTree.html

Его ростом управляют (если ограничиться рассмотрением только отношений, “висящих” на самом Дереве и не привлекать к исползованию какие-либо дополнительные отношения, на самом Дереве не “висящие”) упомянутые мною выше операции V и H:

С учетом этого обстоятельства дополнил прежнее изображение ДШБ на странице:
http://www.px-pict.com/10/4/4/2.html

соответствующим “честным вариантом” (он изображен внизу указанной страницы).

[Математик]

С учетом этого обстоятельства дополнил прежнее изображение ДШБ на странице:
http://www.px-pict.com/10/4/4/2.html

соответствующим “честным вариантом” (он изображен внизу указанной страницы).

Если работать с “честным” вариантом ДШБ и пытаться “вытянуть в линию” висящие на нем рациональные отношения в соответствии с их естественным упорядочением по величине, то мы должны будем пройти это бинарное дерево “во внутреннем порядке”:
http://www.px-pict.com/9/7/1/2/4/1.html

На это обстоятельство я уже указывал здесь:
“Известно, что узлы дерева можно вытянуть в линию разными способами. Приведенное выше упорядочение цепочек (понимаемых как метки узлов дерева) соответствует прохождению узлов дерева способом, который в цитированной выше книге Ахо именуется “прохождением бинарного дерева во внутреннем порядке” (с. 69)”.
“На первый взгляд может показаться, что числа на SB-tree расположены несколько хаотично: действительно, как упорядочить их по величине? Но при чуть более глубоком анализе выясняется: а вы пройдите это дерево во внутреннем порядке и числа чудесным образом упорядочатся по величине (в приведенном выше двуязычном словаре последовательность чисел при движении сверху вниз образует строго возрастающую последовательность)”.
“Это показывает, что древесное упорядочение внутри множества положительных рациональных чисел является не случайным, но тесно связанным с их существенными свойствами”.
http://forum.arbuz.uz/index.php?showtopic=1795&st=10

[Математик]

Кстати говоря, посмотрите на рисунок на титульном листе книги Н. Нильсона “Искусственный интеллект”:
http://www.px-pict.com/9/7/4/1/02.html

Это ли не перст указующий, какие деревья нам нужны?

Воистину, перст.
Достаточно бросить взгляд на “семантическое дерево”:
http://www.px-pict.com/9/6/2/4/2/1/8.html

Сам Н. Нильсон еще в своей первой книге сделал попытку по возможности доходчиво изложить совокупность идей и понятий, приведших в конце концов к “логическому программированию”, в связи с задачами искусственного интеллекта:
http://www.px-pict.com/9/6/2/4/2/1.html

Порфирий отдыхает …

Вглядываясь в “Древо Порфирия”:
http://www.px-pict.com/9/6/2/6/1/2/7.html

все сильнее убеждаюсь, что Дональд Кнут вовсе не просто так изложил “теорию деревьев” именно так, как он ее изложил.

[Математик]

Дело в том, что Дерево Штерна-Броко (ДШБ) определяется через понятие бинарного дерева:
Не понимая, что такое “бинарное дерево”, невозможно понять, что такое Дерево Штерна-Броко (ДШБ).
Грэхем Р., Кнут Д., Паташник О. смогли так определить ДШБ только потому, что в их головах уже существовала к тому времени идея бинарного дерева, известная им по разнообразным своим воплощениям. Одним из таких воплощений и является упомянутое мною выше “Древо Порфирия”.

Можно еще и так это дело повернуть.
В “традиционной логике” есть метод “определения при помощи ближайшего рода и видового отличия”:
“… определение заключается в указании рода даного понятия с присоединением видового различия его. Это в логике принято обозначать при помощи формулы: “Definitio fit per genus et differentiam specificam”, т. е. определение совершается при помощи рода и видового различия.”
“Другие в этой формуле прибавляют к genus термин proximum: “Definitio fit per genus proximum et differentiam specificam”, т. е. “определение совершается при помощи ближайшего рода и видового различия”, желая этим указать на то, что следует пользоваться ближайшим родовым понятием”

Проф. Г. И. Челпанов.
Учебник логики.
ОГИЗ, 1946, с. 26.
(От издательства: учебник логики профессора Московского Университета Г. И. Челпанова (1862 – 1936) в настоящем издании воспроизводится с некоторыми сокращениями и исправлениями по тексту 10-го издания 1918 года.)
---------------------------------------------

В определени ДШБ можно считать понятие “бинарное дерево” родовым понятием, а его “фичу”:

“Фича” этого бесконечного бинарного дерева заключается в определенной разметке его вершин рациональными отношениями.

– видовым отличием.

Не понимая части этого определения (т. е. того, что является “бинарным деревом”), мы не сможем правильно понять и определение в целом (т. е. не сможем правильно понять, что такое есть Дерево Штерна – Броко, или, сокращенно, ДШБ).

[Математик]

Воистину, перст.
Достаточно бросить взгляд на “семантическое дерево”:
http://www.px-pict.com/9/6/2/4/2/1/8.html

Порфирий отдыхает …

Когда я писал свои посты:

Формализовать эту идею можно, например, при помощи системы SBT, которую я предложил здесь:
http://www.px-pict.com/copies/dxdy/duality/3/3.html

то имел в виду, в частности, рассмотреть тесное и продуктивное взаимодействие этих двух Деревьев (т. е. Дерева Штерна – Броко и Семантического Дерева):
Два Дерева -- две светлых повести. В своей любви, как в невесомости.
Два голоса среди молчания… В небесном храме звезд венчание…
---------------------------------------------------------------

Некоторая дополнительная информация о семантических деревьях:
“Так как обычно существует много, возможно бесконечное число, таких интерпретаций, мы организуем их некоторым систематическим способом. Это можно сделать, используя семантические деревья”.
http://www.px-pict.com/9/7/4/3/4/5.html

О роли теоремы Эрбана в развитии концепции “логического программирования” в лекции Дж. Робинсона:
http://www.px-pict.com/9/7/4/4/1.html

[Математик]

Когда я писал свои посты:
то имел в виду, в частности, рассмотреть тесное и продуктивное взаимодействие этих двух Деревьев (т. е. Дерева Штерна – Броко и Семантического Дерева):

Упомянутые два Дерева – это деревья – великаны (или деревья – маяки), естественным образом порождающие, в свою очередь, более мелкую древесную поросль. Конкретно в контексте Пролога:

В этой связи меня и интересуют идеи “логического программирования”. В частности, язык Пролог (т. е. Программирование в терминах логики):
“Пролог -- это язык программирования, предназначенный для представления и использования знаний о некоторой предметной области. Более точно, предметная область -- это множество объектов вместе со знанием о них, выраженным в виде множества отношений. Эти отношения описывают свойства объектов и связи между ними.
Некоторое множество правил, задающих объекты и отношения, и образует программу на Прологе”.
http://www.px-pict.com/9/7/4/4/2.html

это выливается в следующее:
“Все данные, с которыми имеет дело Пролог, являются деревьями (возможно, бесконечными)...”
http://www.px-pict.com/9/7/4/4/2/4.html

Следует обратить особое внимание на вводимое авторами понятие “рационального бесконечного дерева”:
“Мы ограничимся особым классом бесконечных деревьев -- так называемыми рациональными бесконечными деревьями”.

[Математик]

Не понимая, что такое “бинарное дерево”, невозможно понять, что такое Дерево Штерна-Броко (ДШБ).
Грэхем Р., Кнут Д., Паташник О. смогли так определить ДШБ только потому, что в их головах уже существовала к тому времени идея бинарного дерева, известная им по разнообразным своим воплощениям. Одним из таких воплощений и является упомянутое мною выше “Древо Порфирия”.

Кстати говоря, посмотрите на рисунок на титульном листе книги Н. Нильсона “Искусственный интеллект”:
http://www.px-pict.com/9/7/4/1/02.html

Это ли не перст указующий, какие деревья нам нужны?

Еще один пример воплощения идеи корневого дерева в Computer Science:
http://www.px-pict.com/9/7/3/3/7/5.html

Запомним вот это:
“ …чаще всего информация организовывается в виде дерева с целью быстрого нахождения данных”.

Не забудем и об этом воплощении идеи полного бинарного дерева в музыкальной теории:
http://www.px-pict.com/7/3/2/7/3/17.html