Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
VDM-123.doc
Скачиваний:
2
Добавлен:
01.07.2025
Размер:
6 Мб
Скачать
☆

Способ задания д.Функций

Определение. Информационное бинарное дерево – это бесконечное ориентированное дерево:

  1. у которого некоторая вершина отмечена и называется корнем;

  2. и з каждой вершины выходят ровно 2 ребра.

Все слова множества удобно задавать с помощью информационного бинарного дерева, перенумеруя ребра: левое - 0, правое – 1.

Но нам надо еще указать значение функции. Пусть , определяется последовательностью , где Тогда для задания д.функции с помощью информационного дерева нужно у каждого ребра через запятую написать значение соответствующей функции следующим образом:

Таким образом, если есть некоторая д.функция , то она однозначно задает некоторое информационное дерево и наоборот: .

Рассмотрим примеры, взятые выше:

1. 2.

3.

Вес детерминированной функции

Обозначение: Пусть имеется информационное дерево с корнем и некоторая вершина . Рассмотрев поддерево дерева , начиная от вершины , мы получим новое информационное дерево .

Определение. Пусть даны два информационных дерева и с корнями и соответственно, которые являются поддеревьями . Тогда , если , т.е. 2 дерева эквивалентны, если они задают одну и ту же функцию.

Свойство, следующее из предыдущего определения:

Если , тогда между этими информационными деревьями существует изоморфизм, который сохраняет пометки.

Определение (ключевое). Пусть и - ее информационное дерево. Тогда весом д.функции называется максимальное число попарно неэквивалентных поддеревьев дерева . Вес д.функции обозначим через .

Рассмотрим в примерах, взятых выше, каков вес д.функций:

Здесь , т.к. любое поддерево этого дерева эквивалентно самому дереву .

  1. Здесь аналогично примеру 1 .

Здесь , но , и какое бы мы поддерево не взяли, оно будет эквивалентно либо , либо , значит, .

Ограниченно-детерминированные функции

Определение. Ограниченно-детерминированной функцией (или о.д.функцией) называется такая д.функция, которая имеет конечный вес.

Множество всех о.д.функций обозначим через .

Из примеров 1 - 3, взятых выше, следует, что все три д.функции являются о.д.функциями.

Теперь приведем пример д.функции, не являющейся о.д.функцией.

Пример 6.

Рассмотрим бесконечную периодическую последовательность , где , но , т.к. она бесконечна. Рассмотрим функцию - такое, что . Очевидно, что есть д.функция. Она задает следующее информационное дерево :

Заметим, что на всех ребрах одного уровня значения функции одинаковы и они равны значению соответствующей позиции бесконечной периодической последовательности . Т.к. в последовательности на каждом последующем шаге число нулей увеличивается на 1, то в попарно неэквивалентных поддеревьев будет бесконечно много, т.е. .

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]