У меня есть семантическое дерево, из которого я хочу получить БДР. Открываю книгу и там описан алгоритм, но первый же пункт мне не понятен

Выбрасывание дублирующих значений функции.

Что именно подразумевается под этим?

Моё семантическое дерево

alt text

задан 26 Май '13 20:19

изменен 27 Май '13 14:41

Angry%20Bird's gravatar image


9125

10|600 символов нужно символов осталось
2

Эта фраза означает, что у построенного семантического дерева внизу есть много узлов, соответствующих одному и тому же значению функции. А именно, там половина нулей и половина единиц. Вместо этого заводим один узел, помеченный нулём, и один узел, помеченный единицей. Все нижние рёбра, которые шли раньше к узлам с меткой 0, будут теперь идти к одному Нулевому Узлу, и аналогично для метки 1 и одного Единичного Узла. При этом, конечно, получится уже не дерево, а граф более общего вида.

То же самое можно было бы описать так: отождествим все нижние вершины, помеченные нулём, сделав из них одну, а также все нижние вершины, помеченные единицей.

Добавление. Ваш пример совсем простой. Это функция $%f(x,y,z)=z$%, зависящая только от $%z$%. Итог там будет такой: все вершины типа $%y$% склеиваются, все вершины типа $%z$% тоже склеиваются. А $%z$% в кружочке соединена двумя стрелочками с нулевым и единичным узлом. Новый граф будет иметь 5 узлов.

ссылка

отвечен 26 Май '13 20:31

изменен 26 Май '13 20:37

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×105

задан
26 Май '13 20:19

показан
909 раз

обновлен
26 Май '13 20:37

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru