 |
Определение классов для реализации алгоритма
|
|
|
|
На рисунке 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 – операция является функцией; op 1, op 2 – операнды.
Таблица 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.
Поскольку в тройке может отсутствовать второй операнд (например, функции с одним аргументом, или одноместные операции типа (not x)), то если это подтверждается, то работа операции завершается со значением 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 for accelerating 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, IEEE Computer 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. Буч Г. Объектно-ориентированный анализ и проектирование с примерами приложений на С++. - http://www.nexus.odessa.ua/files/books/booch.
13. Аджиев В. MS: корпоративная культура разработки ПО – http:// www.osp.ru
14. Трофимов С.А. Case-технологии. Практическая работа в Rational Rose. – М.: ЗАО "Издательство БИНОМ", 2001.
15. Новичков А. Эффективная разработка программного обеспечения с использованием технологий и инструментов компании RATIONAL. – http://www.interface.ru
16. Selic B., Rumbaugh J. Использование UML при моделировании сложных систем реального времени. - http://www.interface.ru.
|
|
|
