Функциональные грамматики и логико-математическое моделирование

Ширапов Д.Ш.,

Кравченко В.А.,

Чимитов Д.Н.,

Восточно-Сибирский государственный университет технологий и управления,

г. Улан-Удэ

Под логико-математической моделью системы понимается совокупность математических отношений, связывающих характеристики состояния рассматриваемой системы с её параметрами, исходной информацией и начальными условиями. Прикладное значение логико-математической модели заключается в её эффективной трансформации в предметно-математическую модель в виде программы для ЭВМ, осуществляющей компьютерное моделирование системы.

Наиболее распространенным способом логико-математического моделирования является дедуктивный синтез. Согласно нему, логико-математическое моделирование имеет несколько этапов:

1)      формулировка задачи моделирования в логическом виде;

2)      доказательство решения задачи моделирования в виде логического вывода;

3)      построение логико-математической модели из доказательства решения задачи;

4)      программная реализация модели.

Для формулировки задачи (этап 1) необходимо выбрать способ представления знаний о предметной области, для доказательства решения и построения модели (этапы 2 и 3) – математический аппарат логического вывода, а для программной реализации – язык программирования.

В классических работах [1], [2] логико-математическое моделирование имеет прикладное название «концептуальное программирование». Для представления знаний используются семантические сети, основанные на атрибутных грамматиках; для доказательства решения и построения модели – интуиционистская логика, а для программной реализации – специально созданный язык программирования УТОПИСТ.

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

Рассмотрим преимущества метода функциональных грамматик над методом атрибутных грамматик.

1. Формулировка задачи моделирования

В общем виде задача логико-математического моделирования может быть задана совокупностью трёх множеств:

множеством понятий и отношений предметной области, составляющих базу знаний:

множеством входных переменных задачи, характеризующих исходные знания о модели:

множеством выходных переменных задачи, характеризующих цель моделирования:

Если задача моделирования разрешима, то её можно представить в виде:

Таким образом, для формулировки задачи моделирования необходимо выбрать способ представления знаний, на основе которого строится база знаний K и задаются параметры I и Q.

Функциональные грамматики впервые описаны в работе [3]. Они являются дальнейшим развитием атрибутных грамматик. Преимущества функциональных грамматик над атрибутными грамматиками и другими методами при описании языков программирования было показано в монографии [3]. Данный сравнительный анализ вполне применим и при описании баз знаний K, так как технически реализованная база знаний представляет собой модуль либо на имеющемся, либо на специально созданном языке программирования.

Кроме того, в [3] были указаны такие недостатки атрибутных грамматик, как неполнота, сложность описания, отсутствие ясности в описании семантики, низкие способности обнаружения ошибок и освещения деталей.

Методы представления знаний и задач с помощью функциональных грамматик рассматриваются в [4] и [5].

2. Доказательство решения задачи моделирования

Для доказательства решения задачи моделирования необходимо представить задачу моделирования в виде:

где B – оператор логического вывода.

Решение существует только тогда, когда оператор B может быть выражен в виде совокупности простейших операций B_i, принадлежащих базе знаний K:

В классических работах [1] и [2] для доказательства решения используется аппарат интуиционистской логики, поэтому решение представляет собой последовательную декомпозицию оператора B:

В методе функциональных грамматик для доказательства решения используется лямбда- исчисление. Поэтому решение задачи представляет собой последовательно-параллельную декомпозицию оператора B:

Последовательно-параллельная декомпозиция является более подробной, а её компоненты B_ij – более простыми, чем при последовательной декомпозиции. Это позволяет упростить базу знаний и последующую реализацию логико-математической модели. Кроме того, последовательно-параллельная декомпозиция открывает путь к применению параллельных процессов при программной реализации модели.

3. Логико-математическая модель и её программная реализация

В результате последовательной декомпозиции логико-математическая модель представляет собой последовательность правил вывода:

Реализация такой логико-математической модели является программой на императивном языке программирования, состоящей из программных блоков B_ij. В работах [1] и [2] в качестве такого языка использовался язык УТОПИСТ.

Последовательно-параллельная декомпозиция позволяет получить логико-математическую модель в виде суперпозиции функций:

где  – элементарные функции базы знаний K, определяющие операции B_ij.

Реализация логико-математической модели в виде суперпозиции функций представляет собой программу на функциональном языке программирования.

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

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

В результате сравнения метода функциональных грамматик с классическим методом логико-математического моделирования на разных стадиях дедуктивного синтеза был выявлен ряд преимуществ:

1. Функциональные грамматики более адекватно и гибко могут быть использованы при составлении базы знаний K.

2. Последовательно-параллельная декомпозиция является более подробной и позволяет использовать распараллеливание процессов при вычислительных процессах.

3. Функции f_j более просты, чем правила вывода B_i, и могут быть реализованы независимо друг от друга.

4. Суперпозиция функций является готовой программой в отличие от последовательности правил, которая требует извлечение программы из логико-математической модели.

Список литературы:

1.  Тыугу Э.Х. Концептуальное программирование – М.: Наука, 1984. – 256 с.

2.  Кахро М.И., Калья А.П., Тыугу Э.Х. Инструментальная система программирования ЕС ЭВМ (ПРИЗ). ­– М.: Финансы и статистика, 1988. – 181 с.

3.  Тузов В.А. Математическая модель языка. – Л.: Изд-во Ленингр. ун-та, 1984. – 176 с.

4.  Кравченко В.А. Моделирование поиска решения с помощью функциональных грамматик // Вестник Бурятского государственного университета. – Улан-Удэ: Изд-во Бурятского госуниверситета,  2012. №9. с. 33-41.

5.  Кравченко В.А., Ширапов Д.Ш. Построение баз знаний для решения задач методом функциональных грамматик // Вестник Бурятского государственного университета. – Улан-Удэ: Изд-во Бурятского госуниверситета,  2015. №X. С. 96-102.