Контрольная работа: Унификация алгебраических выражений
Содержание
Введение
1. Задача унификации
2. Преобразование выражения в префиксную форму
3. Определение классов для реализации алгоритма
4. Операции класса Lisp _ item
4.1 Операция выполнения унификации (unifikacia )
4.2 Операция проверки применимости продукций(Primen _ prod )
4.3 Операция замены свободных переменных (zamena )
5. Операции класса podst
5.1 Операция проверки применимости (primenima )
6. Операции класса trojka
6.1 Операция проверки применимости (primenima )
Выводы
Литература
Введение
Тема курсовой работы по дисциплине "Проектирование интеллектуальных систем" - "Унификация алгебраических выражений".
Целью изучения дисциплины является подготовка специалистов в области автоматизации сложноформализуемых задач. Задачей изучения дисциплины является приобретение знаний о фундаментальных алгоритмах, применяемых при построении систем искусственного интеллекта, а также методов разработки программных приложений, реализующих эти системы.
Принципиальное отличие интеллектуальных систем от любых других систем автоматизации заключается в наличии базы знаний о предметной среде, в которой решается задача. Неинтеллектуальная система при отсутствии каких-либо входных данных прекращает решение задачи, интеллектуальная же система недостающие данные извлекает из базы знаний и решение выполняет.
По А. Н. Колмогорову, любая материальная система, с которой можно достаточно долго обсуждать проблемы науки, литературы и искусства, обладает интеллектом. Такое определение показывает, что данная дисциплина находится во взаимосвязи практически со всеми учебными дисциплинами. Тем не менее, следует подчеркнуть связи со следующими дисциплинами: "Программирование", "Математический анализ", "Линейная алгебра и аналитическая геометрия", "Дискретная математика", "Логическое программирование", "Экспертные системы", "Интерфейсы интеллектуальных систем".
1. Задача унификации
Формально задача записывается следующим образом: для данной теоремы Т в форме продукции вида
Н Þ С,
где Н – гипотеза;
С – заключение, и некоторого выражения Е необходимо проверить, можно ли сделать Н и Е полностью идентичными путем последовательных подстановок свободных переменных в Е. Если выражение Е с помощью подстановок свободных переменных удается привести к виду Н, то Е можно заменить выражением С. После этого в выражении С свободные переменные заменяют соответствующими им фрагментами из выражения Е.
Например, для продукции (теоремы) ( a + b )2 = a 2 + 2 ab + b 2 исходное выражение x 2 + ( y + √3)2 с помощью свободных переменных a = y и b = √3 можно преобразовать к виду x 2 + ( a + b )2 . Фрагмент выражения ( a + b )2 полностью совпадает с левой частью продукции, следовательно вместо него можно подставить правую часть продукции. В результате будет получено выражение x 2 + a 2 + 2 ab + b 2 . Для завершения преобразования необходимо свободные переменные a и b заменить соответствующими им фрагментами выражения Е. окончательно будет получено: x 2 + y 2 + 2 y √3 + (√3)2 .
Фундаментальная идея алгоритма связана с процедурой просмотра выражения: вначале делается попытка применить какую-либо продукцию ко всему выражению; если не удается применить ни одну продукцию, выбирается фрагмент выражения и проверяется применимость продукций к этому фрагменту и т.д.. Выполнение процедуры унификации прекращается, когда уже никакая продукция не может быть применена ни к какому подвыражению. Для изучения или разработки алгоритма унификации удобно представлять выражение и продукции в виде деревьев. Для приведенного выше примера деревья продукций и выражения будут иметь вид:
Рисунок 1 -Представление продукции и выражения в виде дерева ( -символ операции возведения в степень)
На рисунке одинаковыми цветными прямоугольниками выделены совпадающие фрагменты деревьев продукции и выражения; штрихпунктирными линиями – соответствие между свободными переменными и фрагментами дерева выражения.
Алгоритм унификации выполняет обход дерева выражения, начиная с корня дерева. Для очередного узла дерева выполняются следующие действия:
- выполняется проверка на совпадение операции из узла дерева выражения Е с операцией в корне левой части очередной продукции Т. Если совпадают, то выполняется переход к следующему шагу. В противном случае, по окончании просмотра всех продукций, выполняется переход к следующему узлу дерева выражения Е;
- если в левой части продукции операндами операции являются переменные, то им сопоставляются ветви дерева выражения Е, отходящие от узла с совпавшей операцией (так, как показано на рисунке);
- фрагмент дерева выражения Е, соответствующий левой части продукции, заменяется деревом из правой части продукции (см. рисунок 2);
Рисунок 2 -Выражение Е после замены фрагмента на правую часть выражения
- в полученном дереве выражения Е выполняется замена свободных переменных сопоставленными фрагментами исходного дерева (см. рисунок 3).
Рисунок 3 -Выражение Е после замены свободных переменных соответствующими фрагментами
Таким образом, выполнение унификации предполагает построение дерева выражения. В наибольшей степени заданию выражения в форме дерева соответствует префиксная форма записи. Например, рассмотренные выше продукция и выражение в префиксной форме будут иметь следующий вид:
( (+ a b ) 2) => (+ ( a 2) (+ (* 2 (* a b )) ( b 2)) );
(+ ( x 2) ( (+ y (√ 3)) 2)).
В каждой скобке присутствуют два или три элемента: знак операции или имя функции и один или два операнда. Операции соответствуют узлам дерева, а операнды – ветвям дерева. Такая фиксированная структура упрощает построение алгоритма унификации, но требует введения алгоритма преобразования выражения, заданного в инфиксной записи, в префиксную форму записи.
2.Преобразование выражения в префиксную форму
--> ЧИТАТЬ ПОЛНОСТЬЮ <--