11.2.2. Пример работы GPS

Важно различать очень общие идеи решения задач „в стиле GPS“ и реализации этих идей в конкретных GPS-программах. Фактически был создан целый ряд важных вариантов GPS, в работе

которых есть некоторые интересные различия. Мы сейчас детально познакомимся с работой программы на примере, рассмотренном Эрнстом и Ньюэллом (1969). Это наполнит некоторым конкретным содержанием наше абстрактное изложение.

Задача состоит в нахождении алгебраической формы для

На рис. 11.5 показано дерево, соответствующее выражению, которое нужно проинтегрировать. Целевым объектом является любое выражение, не содержащее знак Определены два класса операторов: дифференцирование и интегрирование. Внутри каждого класса задан ряд возможных изменений входной — выходной формы. Например, правило интегрирования

можно изобразить с помощью изменений в дереве (рис. 11.6). Другие изменения формы при интегрировании и дифференцировании

Таблица 11.3 (см. скан)

(кликните для просмотра скана)

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

Правила (4а) — (4г) применяются непосредственно программой везде, где можно, без проведения анализа целей и средств.

Определены два класса различий: символьные различия и множественные различия. Речь идет о символьных различиях, когда символы в сравниваемых позициях деревьев двух выражений не совпадают. Относительная важность различных возможных типов символьных различий (т. е. или или ) также была установлена вне программы. Множественное различие существует, когда в двух выражениях, которые нужно проинтегрировать, различны количества сомножителей. В матрице операторов и различий зафиксировано, что интегрированию соответствует уменьшение символьных различий, а дифференцированию — множественных различий. Ясно, что это — ни единственные, ни обязательно наиболее подходящие различия, которые можно использовать для сравнения алгебраических выражений. Однако в данном случае их оказывается достаточно.

Исходная цель:

Это порождает цель

Поскольку операция интегрирования соответствует этому виду различий, новой целью будет

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

формы оператора проинтегрировать и была выбрана та, которая ближе всего к нашему выражению. Это дало

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

С этим связано дифференцирование, поэтому целью становится

Рассмотрены различные формы дифференцирования и выбрана операция

Это правило применимо и дает Подставляя и производя необходимые преобразования, получаем

Поскольку цель достигнута, переходим к пользуясь при этом окончательным результатом из (5), который содержит выражение в форме Цель можно достичь, получая

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