Не могли бы вы поделиться годной литературой по данному вопросу? А то кроме 6-строчного определения в книгt Карпова "Теория автоматов" я ничего не нашёл.

задан 19 Май '13 18:31

изменен 22 Май '13 15:22

Angry%20Bird's gravatar image


9125

Допустим, Вы знаете определение, а также умеете по заданной функции строить такое дерево. (Функция при этом может быть задана формулой, таблицей, или как-то ещё.) Чего именно Вам хотелось бы сверх этого?

(19 Май '13 19:05) falcao

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

(19 Май '13 19:10) Error
10|600 символов нужно символов осталось
1

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

Если есть таблица, то формулой ничего задавать не нужно. Допустим, функция от трёх переменных, и строки таблицы идут в стандартном порядке: 000, 001, 010, 011, 100, 101, 110, 111. Тогда у дерева в этом же порядке идут листья, то есть значения функции из последнего столбца переносятся чисто механически в таком же порядке. Если не требуется делать упрощений, то это сразу приводит к результату.

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

ссылка

отвечен 19 Май '13 19:25

Значит 8 листьев ? Вот только как это изобразить графически ?

(19 Май '13 23:20) Error

Если функция от $%n$% переменных, то листьев будет $%2^n$%, то есть при $%n=3$% получается их $%8$%. Изображаются деревья стандартно -- обычно "корень" расположен сверху, и они растут как "корневая система", то есть "листья" расположены внизу. По крайней мере, я их именно так предпочитаю рисовать, хотя иногда изображают и по-другому. Рисунок может выглядеть так: от точки вверху отходят два отрезка вниз -- один влево, другой вправо. От концов этих отрезков снова происходит ветвление на два направления, чтобы левая половина не пересекалась с правой, и так далее -- на несколько уровней вниз.

(19 Май '13 23:59) falcao

@Error: да, на три уровня вниз, и внизу должно оказаться 8 точек (листьев), около которых пишутся значения функции -- нули или единицы. Смысл при этом такой: если нам надо быстро найти, скажем, $%f(1,0,1)$%, то 0 означает "влево", а 1 -- "вправо". От верхнего корня дерева по отрезкам мы идём в нижнем направлении, отклоняясь при этом вправо-влево-вправо, выходим на одну из нижних точек, и смотрим, что около него написано. Это и будет значение функции.

(20 Май '13 21:22) falcao

Но разве мы получаем не бинарную диаграмму решений ?

(26 Май '13 14:22) Error

БДР -- это похожая вещь, но это несколько более общее понятие. В одном случае рисуется именно дерево, а в другом может быть (ациклический) граф более общего вида. Вот тут можно сравнить картинки для одного и другого.

(26 Май '13 19:34) falcao

Вот про правила сокращения не понятно, если я создам топик, где задам вопрос как строить БДР, вы объясните ?

(26 Май '13 19:53) Error

@Error: отдельный вопрос создать можно, но здесь есть одна принципиальная трудность. Дело в том, что про большинство функций в каком-то смысле можно сказать, что схемы представления для них принципиально неулучшаемы. Упрощать что-то удаётся обычно лишь в простых "модельных" примерах. Это значит, что рекомендации могут относиться лишь к частным случаям, но тогда эти случаи нужно описать, то есть задать конкретные функции, для которых хотелось бы иметь удобные упрощённые схемы.

(26 Май '13 20:17) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×150
×31

задан
19 Май '13 18:31

показан
2230 раз

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

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

по почте:

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

по RSS:

Ответы

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

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