Иерарахические числа – это числа вида [s] a0 . a1 . a2 . … . ai. … .an , где ai– целые положительные числа из множества N = {0, 1, 2, 3…}.
s– символ знака «+» или «-», положительный знак может не указываться.
Например, иерархические числа могут выглядеть так:
0.0.12.48.0 или -2.33.0.0.4 .
Символом, обозначающим множество иерархических чисел, является H.
Прикладное определение десятичных иерархических чисел
Кратко идея иерархических чисел выглядит так. Пусть N – множество целых чисел, включающих 0 и отрицательные элементы. N = {…, -3, -2, -1, 0, 1, 2, 3 , …}. Пусть также есть выделенный символ «.».
Множество A = N ᴗ «.» определяется как алфавит с целыми числами n ∈ N, «ᴗ» –операция объединения множеств, «.» – символ-разделитель уровней, «∈» - теоретико-множественное отношение принадлежности элемента множеству. Тогда грамматика:
h → < n >, h → < n > . <h>
описывает множество бинарных иерархических чисел H с элементами h.
Примеры иерархических чисел: -42.0.1.0.4, 4, -12, 0.1.1.0.
Иерархические числа имеют графическую интерпретацию, в которой соответствуют численным индексам вершин деревьев с одной корневой вершиной n ∈ N. Количество таких деревьев равномощно множеству N, поскольку корневой вершиной любого такого дерева является вершина n, не имеющая в своем написании символа «.».
Спуск в вершину n1 на один уровень вниз от вершины nx производится бинарной операцией «+» (nx + ny = nx . ny ), подъем от вершины n1 . n2 вверх – унарной операцией «--» (n1 . n2 -- = n1, 0-- = 0). Таким образом, любое иерархическое число либо является целым числом, либо начинается с целого числа и содержит в своей структуре целые числа, разделенные точками.
Приведем несколько примеров.
Пусть { n1 , n2 , n3, n4, nx } ⊂ N.
n1 . n2 + n3 . n4 = n1 . n2 . n3 . n4 , n1 . n2 . n3 -- = n1 . n2,
0.nx + 0 = 0.nx.0, 0.0 + 0 = 0.0.0, 0 + -4 = 0.-4, nx -- = nx .
41-- = 41, -33 + 0 = -33.0, -33-- = -33.
Более сложными являются операции {º , ^, ||}.
Операция «º» вычисляет общего предка двух вершин, например:
45.-1.0.0.12 º 45.-1.1.0.12 = 45.-1, 1.-2.14 º -5.3.3.3 = 0.
То есть при отсутствии общего предка результатом операции является 0.
Операция «^» вычисляет путь из одной вершины в другую через общего предка. При этом иерархическое число, идентифицирующее общего предка, опускается, например:
45.-1.0.0.14 ^ 45.-1.1.0.12 = [(45.-1.0.0.14 → 45.-1.0.0 → 45.-1.0 → 45.-1) →
(45.-1.1 → 45.-1.1.0 → 45.-1.1.0.12)] = 14.0.0.1.0.12,
где символом «→» обозначен один шаг перехода по дереву от вершины к вершине.
Наконец, унарная операция «||» вычисляет длину иерархического числа, например:
|14.0.0.1.0.12| = 6 .
Здесь используется свойство алгебры иерархических чисел Н, определяемое как алгебра, объемлющая формальную арифметику целых чисел. Действительно, алгебра целых чисел (арифметика) является частным случаем алгебры H, если доопределить на ней арифметические операции сложения, вычитания и умножения чисел.
После рассмотрения семантики приведенных операций можно задать универсальную арифметическую алгебру иерархических чисел H:
H = < H, Ω >, Ω = {+ (2), --(1), º(2) , ^(2), ||(1)},
где H – множество-носитель, а Ω – сигнатура алгебры, т.е. множество операций.
Операции {+, º , ^} являются бинарными, операции {--, ||} определены как унарные.
Рассмотренную алгебру можно дополнить до алгебраической системы H = < H, Ω, R >, введя множество отношений R = {< , >, ~, = }, где отношения «a > b» и « b < a » соответственно «число a сложней числа b» и «число b короче числа a». Символами «~» (a~b) и «=» (a = b)обозначены отношения соответственно «равенство длин чисел a и b» и полное совпадение чисел.
Рассмотрим алгебру бинарных иерархических чисел.
Пусть B – множество чисел с элементами {0, 1}, n ϵ B (n = 0 или n = 1), пусть также есть выделенный символ «.».
Множество A = B ᴗ «.» ᴗ ᴧ определяется как алфавит с целыми числами из B, где «ᴗ» – операция объединения множеств, а ᴧ – пустой символ. Тогда грамматика:
ĥ → ᴧ, ĥ → h, ĥ → -h,
h → < n >, h → < n > . <h>
описывает множество бинарных иерархических чисел H с элементами h.
Можно привести примеры бинарных иерархических чисел: 0.1.0.0.1 или 1.0.-1.0 .
Бинарные иерархические числа представляют собой численные индексы вершин двух
двоичных деревьев: положительного и отрицательного с одной общей вершиной 0.
Порождение вершины влево от 0 производится бинарной операцией 0+0 = 0.0, порождение вершины вправо - бинарной операцией 0 + 1 = 0.1.
Порождение отрицательных вершин выполняется операцией «-» соответственно:
0-0 = -0.0, 0-1 = -0.1.
Графически это можно представить деревом, распространяющимся в положительную или отрицательную сторону:
Впрочем, использование отрицательных элементов может сделать смысл операций более сложным. Например, порождения трассы «+» может выглядеть так:
0.1 + 1.1 = 0.1.1.1, 0 + 0.1 = 0.0.1
Однако пример 0.0.-1 + 1.1 = 0.0.-1.1.1 свидетельствует о наличии более сложных трасс путешествия по дереву, использующих не только спуск но и локальные подъемы (рисунок 2). Такое применение иерархических чисел будет рассмотрено далее на конкретных примерах.
Операция, обратная порождению, удаление терминальной вершины «--», является унарной:
0.1.1.1-- = 0.1.1, 0.1.0-- = 0.1, 0.-1.-1 -- = 0.-1.-1 .
В графической интерпретации число можно считать абсолютным индексом какой-либо вершины, т.е.начинающимся с вершины дерева 0 или относительным, отображающим путь по дереву от одной из любых вершин к другим вершинам вверх и вниз. Абсолютный индекс всегда начинается с символа 0.
При решении практических задач можно рассматривать только положительную часть алгебры бинарных иерархических чисел. В этом случае операции, претендующие на получение отрицательного индекса, будут иметь результатом 0.
Можно привести еще одну довольно популярную операцию «º», а именно вычисление наиболее общей вершины, что интерпретируется как поиск общего предка двух вершин - аргументов:
0.1.1.1 º 0.1.0 = 0.1.0 º 0.1.1.1 = 0.1
Эта операция генерализации/умножения коммутативна, т.е. a º b = b º a.
Умножение положительного числа на отрицательное всегда равно 0.
Важной операцией является «Ù»
0.1.0 Ù 0.1.1.1 Ù 0.1.0. 0.1. 0.1.1. 0.1.1.1 @ 0.1.1.1 0.1.1. 0.1 0.1.0
Здесь @ - отношение равенства длин двух иерархических чисел.
Однако, такое вычисление приводит к излишне сложному результату.
Заметим, что общим предком для 0.1.1.1 и 0.1.0 является 0.1, с которого начинаются оба числа - аргумента. Вследствие этого, при вычислении операции Ù эти фрагменты опускаются для всех вершин пути из первой вершины во вторую. Это необходимо для получения представления о сложности пути из первой вершины во вторую, не смотря на глубину дерева.
Тогда правильная операция Ù получается так:
0.1.0 Ù 0.1.1.1 = [0.1.]0. [0.1.] [ 0.1.]1. [ 0.1].1.1 = 0.1.1.1
0.1.1.1 Ù 0.1.0 = [0.1.]1.1 [0.1.]1. [0.1] [0.1.]0 = 1.1.1.0
0.1.1.1 @ 1.1.1.0
После рассмотрения семантики приведенных операций можно задать универсальную арифметическую алгебру иерархических чисел H:
H = < H, Ω >, Ω = {+, -, --, º , Ù, ⊕ },
где Ω – сигнатура алгебры, т.е. множество операций. Все операции бинарны, за исключением «--», которая является одноместной. Смысл операции «⊕ » будет рассмотрен позже, на соответствующих примерах.
Рассмотренную алгебру можно дополнить до алгебраической системы H = <H,Ω,R>, введя множество отношений R = {< , >, @ , = }, где отношения « a> b» и « b< a» соответственно «число a сложней числа b» и «число b короче числа a».
Десятичные иерархические числа