 |
Преобразование выражения в префиксную форму
|
|
|
|
Задача унификации
Преобразование выражения в префиксную форму
Определение классов для реализации алгоритма
4. Операции класса Lisp _ item
4.1 Операция выполнения унификации (unifikacia)
4.2 Операция проверки применимости продукций(Primen _ prod)
4.3 Операция замены свободных переменных (zamena)
5. Операции класса podst
5.1 Операция проверки применимости (primenima)
6. Операции класса trojka
6.1 Операция проверки применимости (primenima)
Выводы
Литература
Введение
Тема курсовой работы по дисциплине "Проектирование интеллектуальных систем" - "Унификация алгебраических выражений".
Целью изучения дисциплины является подготовка специалистов в области автоматизации сложноформализуемых задач. Задачей изучения дисциплины является приобретение знаний о фундаментальных алгоритмах, применяемых при построении систем искусственного интеллекта, а также методов разработки программных приложений, реализующих эти системы.
Принципиальное отличие интеллектуальных систем от любых других систем автоматизации заключается в наличии базы знаний о предметной среде, в которой решается задача. Неинтеллектуальная система при отсутствии каких-либо входных данных прекращает решение задачи, интеллектуальная же система недостающие данные извлекает из базы знаний и решение выполняет.
По А. Н. Колмогорову, любая материальная система, с которой можно достаточно долго обсуждать проблемы науки, литературы и искусства, обладает интеллектом. Такое определение показывает, что данная дисциплина находится во взаимосвязи практически со всеми учебными дисциплинами. Тем не менее, следует подчеркнуть связи со следующими дисциплинами: "Программирование", "Математический анализ", "Линейная алгебра и аналитическая геометрия", "Дискретная математика", "Логическое программирование", "Экспертные системы", "Интерфейсы интеллектуальных систем".
|
|
|
Задача унификации
Формально задача записывается следующим образом: для данной теоремы Т в форме продукции вида
Н Þ С,
где Н – гипотеза;
С – заключение, и некоторого выражения Е необходимо проверить, можно ли сделать Н и Е полностью идентичными путем последовательных подстановок свободных переменных в Е. Если выражение Е с помощью подстановок свободных переменных удается привести к виду Н, то Е можно заменить выражением С. После этого в выражении С свободные переменные заменяют соответствующими им фрагментами из выражения Е.
Например, для продукции (теоремы) (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)).
В каждой скобке присутствуют два или три элемента: знак операции или имя функции и один или два операнда. Операции соответствуют узлам дерева, а операнды – ветвям дерева. Такая фиксированная структура упрощает построение алгоритма унификации, но требует введения алгоритма преобразования выражения, заданного в инфиксной записи, в префиксную форму записи.
|
|
|
Преобразование выражения в префиксную форму
Это преобразование является частным случаем задачи трансляции выражений. Неформальное определение алгоритма заключается в следующем.
Алгоритмом используется два стека: стек операндов и стек операций. Строка с выражением сканируется слева направо. Если очередным элементом выражения является операнд – константа или переменная, - то он безусловно заносится в стек операндов. Если очередной элемент выражения открывающая скобка, то она безусловно заносится в стек операций. Закрывающая скобка вызывает действия, задаваемые в третьей строке таблицы.
Если очередной элемент выражения операция или скобка, то действия определяются в зависимости от соотношения приоритетов данной операции и операции на вершине стека операций (таблица 1). Обозначения: Op(E) – очередная операция из выражения Е; Op(stack) – операция на вершине стека операций. Значения приоритетов и количество операндов в операциях определяются с помощью справочника операций. Соблюдаются следующие соглашения о приоритетах:
- приоритет открывающей скобки из выражения выше приоритета любой операции на вершине стека;
- приоритет любой операции из выражения выше приоритета открывающей скобки на вершине стека операций;
- приоритет любой операции на вершине стека выше приоритета закрывающей скобки из выражения.
Таблица 1 - Связь между соотношением приоритетов операций и действиями алгоритма
| Op(E) Ä Op(stack) | Описание действий |
| > | 1)Op(E) занести в стек операций; 2)перейти к следующему элементу выражения Е |
| = | 1)сформировать тройку: - операция - с вершины стека операций; - один или два операнда - с вершины стека операндов; 2)ссылку на тройку поместить на вершину стека операндов; 3)Op(E) занести в стек операций; 4)перейти к следующему элементу выражения Е |
| < | 1)сформировать тройку: - операция - с вершины стека операций; - один или два операнда - с вершины стека операндов; 2)ссылку на тройку поместить на вершину стека операндов; 3)снова провести сравнение приоритетов и выбрать действие в соответствии с таблицей. |
|
|
|
Если очередной символ в выражении закрывающая скобка, а на вершине стека операций открывающая скобка, то удалить открывающую скобку из стека и перейти к следующему символу в выражении.
Работа алгоритма заканчивается, если при очередном обращении стек операций оказывается пустым. На вершине стека операндов будет находиться ссылка на выражение в префиксной форме.
Действия алгоритма иллюстрируются таблицей, в которой отображаются состояния стеков и другая информация после выполнения алгоритмом очередного шага для выражения a + b + c /(m - d). Символ $ используется как признак конца(дна) стека или входной строки.
Таблица 2 - Состояния основных структур алгоритма
| Стек операций | Стек операндов | Символ входной строки | Соотно-шение приори-тетов | Описание |
| $ | $ | a | ||
| $ | $a | + | > | |
| $+ | $a | b | ||
| $+ | $ab | + | = | Выделение тройки: (+ a b) |
| $+ | $(+ a b) | c | ||
| $+ | $(+ a b)c | / | > | |
| $+/ | $(+ a b)c | ( | > | |
| $+/( | $(+ a b)c | m | ||
| $+/( | $(+ a b)cm | - | > | |
| $+/(- | $(+ a b)cm | d | ||
| $+/(- | $(+ a b)cmd | ) | < | Выделение тройки: (- m d) |
| $+/( | $(+ a b)c(- m d) | ) | Удаление скобки | |
| $+/ | $(+ a b)c(- m d) | $ | < | Выделение тройки: (/ c (- m d)) |
| $+ | $(+ a b) (/ c (- m d)) | $ | < | Выделение тройки: (+ (+ a b) (/ c (- m d))) |
| $ | $(+ (+ a b) (/ c (- m d))) | $ | Конец работы |
|
|
|
