Подскажите литературу по теме.
Что за метод такой multiterm rewriting?

Ещё такой вопрос.
Допустим, у меня математическое выражение представлено деревом (в узлах операторы(унарные и бинарные), в листьях переменные и константы). Получается так, что существует определенное множество различных возможных деревьев, которые будут обозначать одно и то же выражение.

a + b + c

  +       или     +       или     +
 / \             / \             / \
a   +           +   c           +   b
   / \         / \             / \
  b   c       a   b           a   c

a, b, c — вообще говоря выражения, а не переменные

Мне нужно сравнить выражение с шаблоном.
Шаблон:

a + c
представлено деревом так
  +
 / \
a   c

Если просто сравнивать деревья и поддеревья, то обнаружить то что в исходном выражении содержаться выражения подходящие по шаблону можно только в третьем случае(3 вариант дерева).

Как правильно решить эту проблему?

Здравствуйте, maggot, Вы писали:

M>Ещё такой вопрос.
M>Допустим, у меня математическое выражение представлено деревом (в узлах операторы(унарные и бинарные), в листьях переменные и константы). Получается так, что существует определенное множество различных возможных деревьев, которые будут обозначать одно и то же выражение.

Это происходит в случае неоднозначной (ambiguous) грамматики. Надо переписать ее так, чтобы она стала однозначной. Тогда дерево разбора будет уникальным. Правда для некоторых редко встречающихся языков это невозможно (но арифметические выражения к ним не относятся).

Здравствуйте, kl, Вы писали:

kl>Здравствуйте, maggot, Вы писали:

M>>Ещё такой вопрос.
M>>Допустим, у меня математическое выражение представлено деревом (в узлах операторы(унарные и бинарные), в листьях переменные и константы). Получается так, что существует определенное множество различных возможных деревьев, которые будут обозначать одно и то же выражение.

kl>Это происходит в случае неоднозначной (ambiguous) грамматики. Надо переписать ее так, чтобы она стала однозначной. Тогда дерево разбора будет уникальным. Правда для некоторых редко встречающихся языков это невозможно (но арифметические выражения к ним не относятся).
Грамматика однозначная.
Дело в том, что дерево может меняться например в процессе дифференцирования, и некоторого упрощения.

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

Эту проблему можно решить заданием правил преобразования выражений (по сути деревьев).
Задать операциям свойства коммуникативность, ассоциативность, дистрибутивность...
Но в таком случае опять получается, что будут получаться всевозможные деревья.

И я бы действительно так сделал, но мне кажется, что это неэффективно будет работать, поэтому интересуюсь, как такие задачи решать правильно. Например, как их решают в математических пакетах.

Есть ещё способ — представлять коммуникативные ассоциативные операции не бинарно, а операциями над множеством термов.

Здравствуйте, maggot, Вы писали:

M>И проблема состоит в том, что как раз если не рассматривать все возможные деревья, не получится проверить выражение на соответствие шаблону тривиальным способом (просто равенство кусков деревьев).

M>Эту проблему можно решить заданием правил преобразования выражений (по сути деревьев).
M>Задать операциям свойства коммуникативность, ассоциативность, дистрибутивность...
M>Но в таком случае опять получается, что будут получаться всевозможные деревья.

Если Вам НЕизвестен результат упрощения (т.е. цели нет, осуществляется поиск "от данных"), то Вам все равно придется просмотреть все деревья.
Пример a^2 — b^2 — c^2 = (a-b)(a+b) — c^2 = (a-c)(a+c) — b^2 = a^2 + (-(b^2 — c^2))
Как узнать какое из этих преобразований приведет к успеху?

Для устранения проблемы, при "наложении" конкретнего шаблона можно использовать поиск с возвратом (т.е. идти от цели — от шаблона).

P.S. Результат упрощения известен? Если нет, то каков критерий простоты выражения?

Здравствуйте, Beam, Вы писали:

B>Здравствуйте, maggot, Вы писали:

M>>И проблема состоит в том, что как раз если не рассматривать все возможные деревья, не получится проверить выражение на соответствие шаблону тривиальным способом (просто равенство кусков деревьев).

M>>Эту проблему можно решить заданием правил преобразования выражений (по сути деревьев).
M>>Задать операциям свойства коммуникативность, ассоциативность, дистрибутивность...
M>>Но в таком случае опять получается, что будут получаться всевозможные деревья.

B>Если Вам НЕизвестен результат упрощения (т.е. цели нет, осуществляется поиск "от данных"), то Вам все равно придется просмотреть все деревья.
Да, но я имею ввиду такие деревья, которые будут обозначать одно и то же выражение.
Выражение a+b+c+d можно представить разными деревьями

     +                +                     +                        и  т. д.
    / \              / \                   / \
   /   \            a   +                 a   +
  +     +              / \                   / \
 / \   / \            b   +                 +   d
a   b c   d              / \               / \
                        c   d             b   c

То есть я понимаю, что придётся рассматривать все возможные выражения и деревья, которыми они представлены. Но я не хочу рассматривать различные деревья, которые обозначают в точности одинаковые выражения.

B>Пример a^2 — b^2 — c^2 = (a-b)(a+b) — c^2 = (a-c)(a+c) — b^2 = a^2 + (-(b^2 — c^2))
B>Как узнать какое из этих преобразований приведет к успеху?

B>Для устранения проблемы, при "наложении" конкретнего шаблона можно использовать поиск с возвратом (т.е. идти от цели — от шаблона).
Ещё можно одновременно на каждом шаге рассматривать различные ветви преобразований и объединять их в одну если выражения на данной стадии оказываются одинаковыми, чтобы не выполнять одну и ту же работу.

B>P.S. Результат упрощения известен? Если нет, то каков критерий простоты выражения?
Результат упрощения неизвестен.
Критерии могут быть различные, а именно:
1) Какая нибудь нормальная форма. Пока не важно какая — придумаю.
2) Минимальное количество операций.

Можете какие нибудь книжки, которые есть в сети посоветовать?

Здравствуйте, maggot, Вы писали:

M>Да, но я имею ввиду такие деревья, которые будут обозначать одно и то же выражение.
M>Выражение a+b+c+d можно представить разными деревьями

M>

M>     +                +                     +                        и  т. д.
M>    / \              / \                   / \
M>   /   \            a   +                 a   +
M>  +     +              / \                   / \
M> / \   / \            b   +                 +   d
M>a   b c   d              / \               / \
M>                        c   d             b   c
M>

M>То есть я понимаю, что придётся рассматривать все возможные выражения и деревья, которыми они представлены. Но я не хочу рассматривать различные деревья, которые обозначают в точности одинаковые выражения.

С точки зрения упрощения выражения это совершенно разные выражения.
Уже приводил пример. Уточню немного.

a^2 - b^2 - c^2 = (a-b)(a+b) - c^2            c^2
---------------   ---------------- = (a+b) - -------  (упрощение 1)
   (a-b)               (a-b)                  (a-b)
     
a^2 - b^2 - c^2 = (a-c)(a+c) - b^2             b^2
---------------   ---------------- = (a+c) - -------  (упрощение 2)
   (a-c)               (a-c)                  (a-c)

Можно представить a^2 — b^2 — c^2 = (a^2 — b^2) — c^2 (вариант 1), а можно a^2 — b^2 — c^2 = (a^2 — c^2) — b^2 (вариант 2)
Так вот "вариант 1" сработает в дальнейшем в "упрощение 1" и не сработает в "упрощение 2".

Но заранее неизвестно, что сработает. Поэтому придется пробовать оба варианта.

M>Ещё можно одновременно на каждом шаге рассматривать различные ветви преобразований и объединять их в одну если выражения на данной стадии оказываются одинаковыми, чтобы не выполнять одну и ту же работу.

Спорно. По тем же причинам.

M>Критерии могут быть различные, а именно:
M>1) Какая нибудь нормальная форма. Пока не важно какая — придумаю.
M>2) Минимальное количество операций.

Не определившись с критериями, будет трудно придумать эвристики. А без эвристик ... ну сами понимаете

M>Можете какие нибудь книжки, которые есть в сети посоветовать?

Нет. Смотрите что-нибудь по темам Symbolic computation, Automated theorem proving, ну и вообще AI

Здравствуйте, maggot, Вы писали:

M>Подскажите литературу по теме.
M>Что за метод такой multiterm rewriting?

в забугорном интернете море информации по этому вопросу.
запрос в google, например, Simplifying Algebraic Expressions

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, maggot, Вы писали:

M>>Подскажите литературу по теме.
M>>Что за метод такой multiterm rewriting?

А>в забугорном интернете море информации по этому вопросу.
А>запрос в google, например, Simplifying Algebraic Expressions

Там в основном про то как тыкнуть на кнопку или написать команду в каком-нибудь математическом пакете, чтобы он упростил выражение. А мне нужен алгоритм.

Я так понимаю, задача решается методом term rewriting, и мне надо что то курить по этой теме.

Здравствуйте, maggot, Вы писали:

M>Я так понимаю, задача решается методом term rewriting, и мне надо что то курить по этой теме.

Переписывание (wikipedia рус)
Rewriting (wikipedia eng)

Citeseerx
Ищите term rewriting, rewriting, term rewriting system

Здравствуйте, maggot, Вы писали:

M>

M>a + b + c

M>  +       или     +       или     +
M> / \             / \             / \
M>a   +           +   c           +   b
M>   / \         / \             / \
M>  b   c       a   b           a   c
M>

M>a, b, c — вообще говоря выражения, а не переменные

M>Мне нужно сравнить выражение с шаблоном.
M>Шаблон:
M>

M>a + c
M>представлено деревом так
M>  +
M> / \
M>a   c
M>

Что значит сравнить выражение с шаблоном ? Шаблон должен содержаться как поддерево в дереве с учетом возможных преобразований деревьев ?

Если я тебя правильно понял, то вот мои соображения по теме.

Все зависит от того какие операции могут встречаться в твоем выражении и от их свойств. Если только сложение, то поскольку действует коммутативные и ассоциативные свойства решение элементарно -- просто представляем исходное выражение не в виде дерева, а в некой канонической форме, в виде списка слагаемых. Как-то так -- SUM(a,b,c). Твой шаблон будет чем-то в вроде SUM(a,c). В итоге надо просто отыскать элементы второго списка слагаемых в первом.

Если имеются более сложные комбинации операций, то тут тоже можно попробовать отыскать каноническую форму исходных выражений. На самом деле вопросами поиска такой канонической формы занимается раздел computer sciense, кототрый называют переписыванием формул (переписыванием термов, term rewriting). Правда, классическая задача переписывания формул несколько отличается от твоей. В классической задаче даны два выражения и набор эквационных спецификациях, характеризующие свойства операций. Например

a + b = b + a
a + (b+c) = (a+b)+c
a* 1 = a
a* 0 = 0
a + 0 = a
...
и т.д.

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

Но в целом задача близка к твоей. Можешь поковырять в эту сторону. Ищи в гугле "переписывание формул", "переписывание термов", "term rewriting". Есть кое-что по теме в книге про графы. Кстати, если что-нибудь полезное найдешь, скажи мне.