Реферат: Унификация алгебраических выражений

Содержание

Введение

1. Задачаунификации2. Преобразованиевыражения в префиксную форму3. Определениеклассов для реализации алгоритма4. Операциикласса Lisp_item4.1 Операциявыполнения унификации (unifikacia)4.2 Операцияпроверки применимости продукций(Primen_prod)4.3 Операциязамены свободных переменных (zamena)5. Операциикласса podst5.1 Операцияпроверки применимости (primenima)6. Операциикласса trojka6.1 Операцияпроверки применимости (primenima)Выводы

Литература

Введение

Тема курсовой работы по дисциплине «Проектированиеинтеллектуальных систем» — «Унификация алгебраических выражений».

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

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

По А. Н. Колмогорову, любаяматериальная система, с которой можно достаточно долго обсуждать проблемынауки, литературы и искусства, обладает интеллектом. Такое определениепоказывает, что данная дисциплина находится во взаимосвязи практически со всемиучебными дисциплинами. Тем не менее, следует подчеркнуть связи со следующимидисциплинами: «Программирование», «Математический анализ», «Линейнаяалгебра и аналитическая геометрия», «Дискретная математика», «Логическоепрограммирование», «Экспертные системы», «Интерфейсыинтеллектуальных систем».

 

1. Задачаунификации

Формально задача записываетсяследующим образом: для данной теоремы Т в форме продукции вида

Н Þ С,

где Н – гипотеза;

С – заключение, и некотороговыражения Е необходимо проверить, можно ли сделать Н и Е полностью идентичнымипутем последовательных подстановок свободных переменных в Е. Если выражение Е спомощью подстановок свободных переменных удается привести к виду Н, то Е можнозаменить выражением С. После этого в выражении С свободные переменные заменяютсоответствующими им фрагментами из выражения Е.

Например, для продукции (теоремы) (a+ b)2 = a2+ 2ab+ b2 исходное выражение x2+ (y+ √3)2 с помощью свободных переменных a= y и b= √3можно преобразовать к виду x2+ (a+ b)2. Фрагмент выражения (a+ b)2 полностью совпадает с левой частьюпродукции, следовательно вместо него можно подставить правую часть продукции. Врезультате будет получено выражение x2+ a2+ 2ab+ b2. Для завершения преобразования необходимо свободныепеременные a и bзаменить соответствующими им фрагментами выражения Е.окончательно будет получено: x2+ y2+ 2y√3 + (√3)2 .

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

/>

Рисунок1 -Представление продукции и выражения в виде дерева (­ -символ операции возведения встепень)

На рисунке одинаковыми цветнымипрямоугольниками выделены совпадающие фрагменты деревьев продукции и выражения;штрихпунктирными линиями – соответствие между свободными переменными ифрагментами дерева выражения.

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

- выполняетсяпроверка на совпадение операции из узла дерева выражения Е с операцией в корнелевой части очередной продукции Т. Если совпадают, то выполняется переход кследующему шагу. В противном случае, по окончании просмотра всех продукций,выполняется переход к следующему узлу дерева выражения Е;

- если в левойчасти продукции операндами операции являются переменные, то им сопоставляютсяветви дерева выражения Е, отходящие от узла с совпавшей операцией (так, какпоказано на рисунке);

- фрагмент деревавыражения Е, соответствующий левой части продукции, заменяется деревом изправой части продукции (см. рисунок 2);

/>

Рисунок2 -Выражение Е после замены фрагмента на правую часть выражения

- в полученномдереве выражения Е выполняется замена свободных переменных сопоставленнымифрагментами исходного дерева (см. рисунок 3).

/>

Рисунок3 -Выражение Е после замены свободных переменных соответствующимифрагментами

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

(­(+ ab) 2) => (+ (­a2) (+ (* 2 (* ab)) (­b2)) );

(+ (­x2) (­(+ y(√ 3)) 2)).

 

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

 

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))) $ Конец работы

 

3. Определение классов для реализации алгоритма

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

/>

Рисунок4 — Диаграмма классов для алгоритма унификации

В рассматриваемом примере реализацииалгоритма унификации основную структурную единицу задает класс Lisp_item. Имя класса указывает на то, что проводится аналогияс понятием символа языка LISP.Суть заключается в том, что в LISPсимвол может обозначать константу, переменную, список, функцию или выражение,которое можно обрабатывать. Чтобы конкретизировать, что задает экземпляр классаLisp_item, в его состав вводится атрибут typ. Атрибут itmбудет задавать ссылку на объект (константу, переменнуюили тройку – выражение, состоящее из операции и двух операндов). Причем, любойиз операндов может быть экземпляром класса Lisp_item.

Таблица 3 — Назначениеопераций класса Lisp_item

Имя операции Описание

unifikacia(ArrayList sp,

ref ArrayList SV, TextBox tbox)

Выполняет унификацию данного экземпляра Lisp_item, где sp – список продукций (подстановок); SV – формируемый список свободных переменных; tbox – компонента для вывода текстовых сообщений.

Primen_prod(ArrayList sp, ref ArrayList SV,

 TextBox tbox)

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

Для задания продукций (подстановок),используемых для унификации выражений, применяется класс podst. В соответствии с определениемпродукции атрибутами класса являются left_part и right_part. При этом и левая, и правая части могут представлятьпроизвольные выражения и задаются как объекты класса Lisp_item.

Таблица 4 — Назначениеопераций класса podst

Имя операции Описание primenima(Lisp_item E, ref ArrayList SV) Определяет применимость левой части продукции к заданному выражению. Е – унифицируемое выражение; SV – формируемый список свободных переменных. zamena(ArrayList SV) Выполняет замену свободных переменных в правой части удачно примененной продукции.

Для работы с выражением в префикснойформе предназначен класс trojka. Атрибуты этого класса предназначены для определения основных элементови признаков выражения в префиксной форме: operation – символ операции; priority – приоритет операции; is_func – операция является функцией; op1, op2 – операнды.

Таблица 5 — Назначениеопераций класса trojka

Имя операции Описание

primenima(Lisp_item E,

 ref ArrayList SV)

Определяет применимость тройки из левой части продукции к тройке заданного выражения. Е – унифицируемое выражение; SV – формируемый список свободных переменных.

 

4. Операции класса Lisp_item 4.1 Операция выполнения унификации (unifikacia)

Действия данной операции определяютсясхемой на рисунке 5 и складываются из следующего. Вначале проверяетсяприменимость продукций ко всему выражению.

Если удается удачно применитькакую-либо продукцию из заданного списка, то выполняется выход. В противномслучае, операция унификации (unifikacia) вызывается для каждого из операндов выражения.

4.2 Операция проверки применимостипродукций(Primen_prod)

Действия данной операции определяютсясхемой на рисунке 6 и складываются из следующего. Организуется цикл просмотрасписка продукций.

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

Если же ни одной продукции применитьне удалось, то возвращается ложное значение.

4.3 Операция замены свободныхпеременных (zamena)

Действия данной операции определяютсясхемой на рисунке 7 и складываются из следующего. Состав выполняемых действийзависит от типа обрабатываемого элемента выражения.

В случае константы никаких действийне выполняется.

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

 

5. Операции класса podst 5.1 Операция проверки применимости (primenima)

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

Если левая часть – константа, товыполняется сравнение значений констант из левой части продукции и заданноговыражения. Результат сравнения возвращается как результат выполнения операции.

Если левая часть продукции –переменная, то формируется элемент списка свободных переменных и помещается всписок. Для задания элементов списка свободных переменных используется класс sv_perem, атрибутами которых являются:

nm_sv – имя свободной переменной;

fragment — фрагмент выражения, соответствующийпеременной (тип Lisp_item).

Если левая часть – тройка, товыполняется выделение выражений тройки из левой части продукции иунифицируемого выражения, после чего вызывается операция класса trojka для проверки применимости тройки изпродукции к тройке из выражения (primenima).

/>

Рисунок5 -Схема алгоритма операции Lisp_item.unifikacia

/>

Рисунок6 — Схема алгоритма операции Lisp_item.Primen_prod

/>

Рисунок7 — Схема алгоритма операции Lisp_item.zamena

 

 

/>

Рисунок8 — Схема алгоритма операции podst.primenima

 

6. Операции класса trojka 6.1 Операция проверки применимости (primenima)

Действия данной операции определяютсясхемой на рисунке 9 и складываются из следующего. Тройка из продукции будетсчитаться удачно примененной к тройке из унифицируемого выражения, если,во-первых, совпадают операции троек; во-вторых, правила применимости выполняютсядля первых и вторых операндов троек.

При совпадении операций троек,анализируется тип первого операнда.

В случае константы выполняетсясравнение значений констант, стоящих на месте первого операнда в сравниваемыхтройках. При несовпадении – выполняется выход.

Если первый операнд переменная, то ейсопоставляется первый операнд из тройки унифицируемого выражения и заносится всписок свободных переменных.

Если первый операнд тройка, то дляэтого объекта вызывается описываемая операция primenima. При неудачном завершении этой операции выполняетсявыход из операции со значением false.

Поскольку в тройке можетотсутствовать второй операнд (например, функции с одним аргументом, илиодноместные операции типа (notx)),то если это подтверждается, то работа операции завершается со значением true. Если же второй операндприсутствует, то прежде всего проверяется возможное условие совпадения первогои второго операндов.

Если же в тройке из продукцииоперанды различны, то выполняется обработка второго операнда. Алгоритмобработки аналогичен алгоритму обработки первого операнда.

/>

Рисунок 9,лист 1- Схема алгоритма операции trojka.primenima

/>

Рисунок 9, лист 2.

Выводы

Таким образом, процесс унификациивыражения складывается из трех последовательно выполняемых этапов:

 

преобразование выражения в инфикснойформе в выражение в префиксной форме Þунификация выражения в префикснойформе Þпреобразование результата унификации из префиксной формы в инфиксную форму.

Что касается последнегопреобразования, то оно реализуется в виде несложной рекурсивной процедуры.

Литература

1. Уоссермен Ф., Нейрокомпьютернаятехника, — М., Мир, 1992.

2. Горбань А.Н. Обучение нейронных сетей.- М.: ПараГраф, 1990

3. Горбань А.Н., Россиев Д.А.Нейронные сети на персональном компьютере. — Новосибирск: Наука, 1996

4. Gilev S.E., Gorban A.N., Mirkes E.M. Several methods foraccelerating the training process of neural networks in pattern recognition //Adv. Modelling & Analysis, A. AMSE Press. – 1992. – Vol.12, N4. – P.29-53

5. С. Короткий. Нейронные сети: алгоритм обратного распространения.

6. С. Короткий, Нейронные сети:обучение без учителя. Artificial Neural Networks: Concepts and Theory, IEEEComputer Society Press, 1992.

7. Заенцев И. В. Нейронные сети:основные модели./Учебное пособие к курсу «Нейронные сети» длястудентов 5 курса магистратуры к. электроники физического ф-та ВоронежскогоГосударственного университета – e-mail: ivz@ivz.vrn.ru

/>8. Лорьер Ж.Л. Системы искусственногоинтеллекта. – М.: Мир, 1991. – 568 с.

9. Искусственный интеллект. – В 3-х кн. Кн. 2. Модели и методы:Справочник/ Под ред. Поспелова Д. А. – М.: Радио и связь, 1990. – 304 с.

10. Бек Л. Введение в системное программирование.- М.: Мир, 1988.

11. Шлеер С., Меллор С. Объектно-ориентированныйанализ: моделирование мира в состояниях. – К.: Диалектика, 1993. – 240 с.

12. Буч Г. Объектно-ориентированныйанализ и проектирование с примерами приложений на С++. — www.nexus.odessa.ua/files/books/booch.

13. Аджиев В. MS: корпоративнаякультура разработки ПО – www.osp.ru

14. Трофимов С.А. Case-технологии. Практическая работа в Rational Rose. – М.: ЗАО «Издательство БИНОМ», 2001.

15. Новичков А. Эффективная разработкапрограммного обеспечения с использованием технологий и инструментов компанииRATIONAL. – www.interface.ru

16. Selic B., Rumbaugh J. Использование UML при моделировании сложных системреального времени. — www.interface.ru.