Вопрос 58: Представление свободных деревьев кодом Прюфера.

Возьмем какое-нибудь дерево с n вершинами, помеченными различными

числами от 1 до n. Мы сопоставим дереву последовательность длины n-2 из букв x1; x2; …;xn. Последовательность строится индуктивно. Возьмем

в дереве лист с минимальным номером и возьмем в качестве первой буквы

последовательности x с индексом, равным номеру вершины, с которой этот

лист соединен. Затем удалим выбранный лист. Второй буквой будет x с ин-

дексом, равным номеру вершины, с которой соединен минимальный лист в

оставшемся дереве. Этот лист тоже удалим, и будем повторять эту опера-

цию до тех пор, пока не останется дерево из двух вершин (ребро). Получим

как раз последовательность букв длины n-2.

Последовательность удаления вершин в дереве с помеченными вершинами и соответствующая этому дереву последовательность букв – его код Прюфера.

Вопрос 59: Представление упорядоченных деревьев.

Всякое свободное дерево можно ориентировать, назначив один из узлов корнем. Всякое ордерево можно произвольно упорядочить. Всякое упорядоченное дерево можно представить бинарным деревом, проведя правую связь к старшему брату, а левую — к младшему сыну.

Диаграммы упорядоченного и соответствующего ему бинарного деревьев

Из данного представления следует, что множество бинарных деревьев взаимнооднозначно соответствует множеству упорядоченных лесов упорядоченных деревьев.

Вопрос 60: Способы кодирования бинарных деревьев: списочные структуры, упакованные массивы, польская запись.

Кодирование списком. Одна ячейка списка – 3 значения: 1)указатель на сам узел, 2) указатель на левый узел, 3) указатель на правый узел. Таким образом, объем памяти n=3p. Очень удобно восстанавливать исходное упорядоченное дерево.

Упакованные массивы. Все узлы располагаются в массиве, так что все узлы поддерева данного узла располагаются вслед за этим узлом. Вместе с каждым узлом хранится индекс узла, который является последним узлом поддерева данного узла. Дерево Т обычно определяется следующим образом: Т : array [l..p] of record i : info, k : l..p end record. Для этого представления n(р) = 2р.

Польская запись. Первый элемент – указатель на узел, второй – условный код: 0 – нет потомков, 1 – есть левый потомок, 2- есть правый потомок, 3 – есть оба потомка. Наиболее компактная запись, так как тройка в двоичном коде – это 11. Поэтому общий объем памяти n<=2p. Но ходить по такому дереву сложнее, чем при кодировании списком. Это удобная запись именно для бинарных деревьев.

61.Булевы функции  булева функция – это функция, и аргументы и значение которой принадлежит множеству { 0, 1 }.

Произвольная булева функция задается одним из трех способов: матричным (табличным), геометрическим и аналитическим.При матричном способе булева функция f (х1, ...,хn) задается таблицей истинности, в левой части которой представлены все возможные двоичные наборы длины n, а в правой указывается значение функции на этих наборах.

При геометрическом способе булева функция f (х1, ..., хn) задается с помощью n-мерного куба. В геометрическом смысле каждый двоичный набор у = <y1, y2,...,yn> yi E {0,1} есть n-мерный вектор, определяющий точку n-мерпого пространства. Исходя из этого, все множество наборов, на которых определена функция n переменных, представляется вершинами n-мерного куба. Отмечая точками вершины куба, в которых функция принимает единичное (либо нулевое) значение, получим геометрическое представление функции.  При аналитическом способе булева функция задается формулами, т. е. аналитическими выражениями, построенными на основе операций булевой алгебры.

Замена переменных и суперпозиция Пусть f(x1, x2, ... , xn) - заданная функция алгебры логики. Будем говорить, что функция (y1, y2, ... , yn) получена операцией замены переменных из функции f(x1, x2, ... , xn), если осуществлена подстановка переменных

Пусть имеется функция f(x₁, x₂, ... , x_n) и функци ,

тогда функцию

будем называть суперпозицией функции f(x₁, x₂, ... , x_n) и функций

Другими словами: пусть F = { fj } - набор функций алгебры логики, не обязательно конечный. Функция f называется суперпозицией функций из множества F или функцией над F, если она получена из функции

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

Булева функция y=f(x1,x2 ... xn) существенно зависит от переменной xk, если существует такой набор значений a1,a2 ... ak-1, ak+1, ak+2 ... an, что f(a1,a2 ... ak-1, 0, ak+1, ak+2 ... an) ≠ f(a1, a2 ... ak-1, 1, ak+1, ak+2 ... an).      В этом случае xk называют существенной переменной

 Переменная является несущественной, если ее изменение не изменяет значения функции.