(7 оценок, среднее: 4,71 из 5)
Загрузка...
Учебная работа. Контрольная работа: Унификация алгебраических выражений
Введение
1. задачка унификации
2. Преобразование выражения в префиксную форму
3. Определение классов для реализации метода
4. Операции класса
4.1 Операция выполнения унификации (
)
4.2 Операция проверки применимости продукций(
)
4.3 Операция подмены вольных переменных (
)
5. Операции класса
5.1 Операция проверки применимости (
)
6. Операции класса
6.1 Операция проверки применимости (
)
Выводы
Литература
Введение
Тема курсовой работы по дисциплине «Проектирование умственных систем» — «Унификация алгебраических выражений».
Целью исследования дисциплины является подготовка профессионалов в области автоматизации сложноформализуемых задач. Задачей исследования дисциплины является приобретение познаний о базовых методах, используемых при построении систем искусственного ума, также способов разработки программных приложений, реализующих эти системы.
Принципное отличие умственных систем от всех остальных систем автоматизации заключается в наличии базы познаний о предметной среде, в какой решается задачка. Неинтеллектуальная система при отсутствии каких-то входных данных прекращает решение задачки, умственная же система недостающие данные извлекает из базы познаний и решение делает.
По А. Н. Колмогорову, неважно какая вещественная система, с которой можно довольно длительно дискуссировать трудности науки, литературы и искусства, владеет умом. Такое определение указывает, что данная дисциплина находится во связи фактически со всеми учебными дисциплинами. Тем не наименее, следует выделить связи со последующими дисциплинами: «Программирование», «Математический анализ«, «Линейная алгебра и аналитическая геометрия», «Дискретная математика», «Логическое программирование», «Экспертные системы«, «Интерфейсы умственных систем».
1. задачка унификации
Формально задачка записывается последующим образом: для данной аксиомы Т в форме продукции вида
Н Þ С,
где Н – догадка;
С – заключение, и некого выражения Е нужно проверить, можно ли создать Н и Е стопроцентно схожими методом поочередных подстановок вольных переменных в Е. Если выражение Е при помощи подстановок вольных переменных удается привести к виду Н, то Е можно поменять выражением С. Опосля этого в выражении С вольные переменные подменяют надлежащими им фрагментами из выражения Е.
к примеру, для продукции (аксиомы)
)2
=
2
2
начальное выражение
2
+ √3)2
при помощи вольных переменных
и
можно конвертировать к виду
2
)2
. Фрагмент выражения
)2
стопроцентно совпадает с левой частью продукции, как следует заместо него можно подставить правую часть продукции. В итоге будет получено выражение
2
2
2
Для окончания преобразования нужно вольные переменные
и
поменять надлежащими им фрагментами выражения Е. совсем будет получено:
2
2
√3 + (√3)2
.
Базовая мысль метода связана с процедурой просмотра выражения: сначала делается попытка применить какую-либо продукцию ко всему выражению; если не удается применить ни одну продукцию, выбирается фрагмент выражения и проверяется применимость продукций к этому фрагменту и т.д.. Выполнение процедуры унификации прекращается, когда уже никакая продукция не быть может использована ни к какому подвыражению. Для исследования либо разработки метода унификации комфортно представлять выражение и продукции в виде деревьев. Для приведенного выше примера деревья продукций и выражения будут иметь вид:
Набросок
1 —метод унификации делает обход дерева выражения, начиная с корня дерева. Для еще одного узла дерева производятся последующие деяния:
— производится проверка на совпадение операции из узла дерева выражения Е с операцией в корне левой части очередной продукции Т. Если совпадают, то производится переход к последующему шагу. В неприятном случае, по окончании просмотра всех продукций, производится переход к последующему узлу дерева выражения Е;
— если в левой части продукции операндами операции являются переменные, то им сопоставляются ветки дерева выражения Е, отходящие от узла с совпавшей операцией (так, как показано на рисунке);
— фрагмент дерева выражения Е, соответственный левой части продукции, заменяется деревом из правой части продукции (см. набросок 2);
Набросок 2
-Выражение Е опосля подмены фрагмента на правую часть выражения
— в приобретенном дереве выражения Е производится подмена вольных переменных сопоставленными фрагментами начального дерева (см. набросок 3).
Набросок
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)опять провести сопоставление ценностей и избрать действие в согласовании с таблицей.
Если очередной знак в выражении закрывающая скобка, а на верхушке стека операций открывающая скобка, то удалить открывающую скобку из стека и перейти к последующему символу в выражении.
Работа метода завершается, если при следующем воззвании стек операций оказывается пустым. На верхушке стека операндов будет находиться ссылка на выражение в префиксной форме.
Деяния метода иллюстрируются таблицей, в какой показываются состояния стеков и иная информация опосля выполнения методом еще одного шага для выражения
. знак
употребляется как признак конца(дна) стека либо входной строчки.
Таблица 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 (- md))
$+
$(+ a b) (/ c (- md))
$
<
Выделение тройки:
(+ (+ ab) (/ c (- md)))
$
$(+ (+ a b)(/ c (- md)))
$
Конец работы
3. Определение классов для реализации метода
На рисунке 4 приведена диаграмма классов для реализации метода унификации, на которой показана структура вызовов операций классов. Числа над линиями указывают вероятную последовательность вызовов. В рассматриваемой реализации метода предполагается, что выражение представлено в префиксной форме. Описываться будут лишь те структуры данных и операции, которые соединены с принципом работы метода унификации.
Набросок 4
— Диаграмма классов для метода унификации
В рассматриваемом примере реализации метода унификации основную структурную единицу задает класс Lisp_item. имя класса показывает на то, что проводится объект (константу, переменную либо тройку – выражение, состоящее из операции и 2-ух операндов). При этом, хоть какой из операндов быть может экземпляром класса
Таблица 3
— Предназначение операций класса
имя операции
Описание
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 – перечень вольных переменных
Для задания продукций (подстановок), применяемых для унификации выражений, применяется класс
. В согласовании с определением продукции атрибутами класса являются
и
При всем этом и левая, и правая части могут представлять произвольные выражения и задаются как объекты класса
Таблица 4
— Предназначение операций класса
имя операции
Описание
primenima(Lisp_item E, ref ArrayList SV)
Описывает применимость левой части продукции к данному выражению. Е – унифицируемое выражение; SV – создаваемый перечень вольных переменных.
zamena(ArrayListSV)
Делает подмену вольных переменных в правой части успешно примененной продукции.
Для работы с выражением в префиксной форме предназначен класс
. Атрибуты этого класса предусмотрены для определения главных частей и признаков выражения в префиксной форме:
– знак операции;
– ценность операции;
– операция является функцией;
,
– операнды.
Таблица 5
— Предназначение операций класса
имя операции
Описание
primenima(Lisp_item E,
ref ArrayList SV)
Описывает применимость тройки из левой части продукции к тройке данного выражения. Е – унифицируемое выражение; SV – создаваемый перечень вольных переменных.
4. Операции класса
4.1 Операция выполнения унификации (
)
Деяния данной операции определяются схемой на рисунке 5 и складываются из последующего. Сначала проверяется применимость продукций ко всему выражению.
Если удается успешно применить какую-либо продукцию из данного перечня, то производится выход. В неприятном случае, операция унификации (
) вызывается для всякого из операндов выражения.
4.2 Операция проверки применимости продукций(
)
Деяния данной операции определяются схемой на рисунке 6 и складываются из последующего. Организуется цикл просмотра перечня продукций.
Для очередной продукции из перечня (
) вызывается операция проверки применимости продукции (
). Если операция возвращает настоящее части продукции.
Если же ни одной продукции применить не удалось, то ворачивается неверное
4.3 Операция подмены вольных переменных (
)
Деяния данной операции определяются схемой на рисунке 7 и складываются из последующего. Состав выполняемых действий зависит от типа обрабатываемого элемента выражения.
В случае константы никаких действий не производится.
В случае обычный переменной производится ее поиск в перечне вольных переменных, опосля чего же она заменяется подходящим фрагментом выражения. Если обрабатываемый элемент является тройкой (операция и два операнда), то данная операция подмены (
) вольных переменных производится для всякого из операндов тройки.
5. Операции класса
5.1 Операция проверки применимости (
)
Деяния данной операции определяются схемой на рисунке 8 и складываются из последующего. Сначала производится проверка соответствия типов левой части продукции и унифицируемого выражения. При несовпадении производится выход с возвратом значения
. При совпадении типов последующие деяния определяются типом левой части продукции.
Если левая часть – константа, то производится сопоставление значений констант из левой части продукции и данного выражения. Итог сопоставления ворачивается как итог выполнения операции.
Если левая часть продукции – переменная, то формируется элемент перечня вольных переменных и помещается в перечень. Для задания частей перечня вольных переменных употребляется класс
, атрибутами которых являются:
– имя вольной переменной;
— фрагмент выражения, соответственный переменной (тип Lisp_item).
Если левая часть – тройка, то производится выделение выражений тройки из левой части продукции и унифицируемого выражения, опосля чего же вызывается операция класса
для проверки применимости тройки из продукции к тройке из выражения (
).
Рисунок5 -Схемаалгоритмаоперации
Набросок
6 — Схема метода операции
Набросок
7 — Схема метода операции
Набросок
8 — Схема метода операции
6. Операции класса
6.1 Операция проверки применимости (
)
Деяния данной операции определяются схемой на рисунке 9 и складываются из последующего. Тройка из продукции будет считаться успешно примененной к тройке из унифицируемого выражения, если, во-1-х, совпадают операции троек; во-2-х, правила применимости производятся для первых и вторых операндов троек.
При совпадении операций троек, анализируется тип первого операнда.
В случае константы производится сопоставление значений констант, стоящих на месте первого операнда в сравниваемых тройках. При несовпадении – производится выход.
Если 1-ый операнд переменная, то ей сопоставляется 1-ый операнд из тройки унифицируемого выражения и заносится в перечень вольных переменных.
Если 1-ый операнд тройка, то для этого объекта вызывается описываемая операция
При неудачном окончании данной нам операции производится выход из операции со значением
.
Так как в тройке может отсутствовать 2-ой операнд (к примеру, функции с одним аргументом, либо одноместные операции типа (
)), то если это подтверждается, то работа операции заканчивается со значением
. Если же 2-ой операнд находится, то до этого всего проверяется вероятное условие совпадения первого и второго операндов.
Если же в тройке из продукции операнды различны, то производится обработка второго операнда. Метод обработки аналогичен методу обработки первого операнда.
Набросок 9, лист 1- Схема метода операции
Набросок 9, лист 2.
Выводы
Таковым образом, процесс унификации выражения складывается из 3-х поочередно выполняемых шагов:
.
Что касается крайнего преобразования, то оно реализуется в виде легкой рекурсивной процедуры.
Литература
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-технологии. Практическая работа в RationalRose. – М.: ЗАО «Издательство БИНОМ», 2001.
15
. Новичков А. Действенная разработка программного обеспечения с внедрением технологий и инструментов компании RATIONAL. – http://www.interface.ru
16. Selic B., RumbaughJ. Внедрение UML при моделировании сложных систем настоящего времени. — http://www.interface.ru.
]]>