автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Синтез эффективных математических моделей дискретной обработки данных на основе алгебраической и понятийной декомпозиции предметной области

РОССИЙСКАЯ АКАДЕМИЯ НАУК Институт проблем управления им. В.А. Трапезникова

2 2 ФЕВ 2007

На правах рукописи Выхованец Валерий Святославович

СИНТЕЗ ЭФФЕКТИВНЫХ МАТЕМАТИЧЕСКИХ МОДЕЛЕЙ

ДИСКРЕТНОЙ ОБРАБОТКИ ДАННЫХ НА ОСНОВЕ АЛГЕБРАИЧЕСКОЙ И ПОНЯТИЙНОЙ ДЕКОМПОЗИЦИИ ПРЕДМЕТНОЙ ОБЛАСТИ

Специальность 05.13.11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Специальность 05.13.15 Вычислительныемашины и системы

Автореферат диссертации на соискание ученой степени доктора технических наук

Москва 2007

003053244

Работа выполнена в Институте проблем управления им. В. А. Трапезникова РАН

Научный консультант:

доктор технический наук В. Д. Малюгин

Официальные оппоненты: доктор технических наук В. Н. Вагин доктор технических наук Н. Н. Иванов доктор технических наук И. Ф. Чебурахин

Ведущая организация: Московский государственный технический университет им. Н. Э. Баумана.

Защита состоится 19 марта 2007 г. в 11 часов на заседании Диссертационного совета Д002.226.03 Института проблем управления им. В.А.Трапезникова РАН по адресу: 117997, г.Москва, ул. Профсоюзная, 65. Тел. +(495) 335-9329.

С диссертацией можно ознакомиться в библиотеке Института проблем управления им. В. А. Трапезникова РАН и в сети Интернет по адресу http://www.vykhovanets.ru.

Автореферат разослан 7 февраля 2007 г.

Ученый секретарь диссертационного совета, д-р. техн. наук

Е. В. Юркевич

Общая характеристика работы

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

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

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

Объектом исследования является процесс обработки данных, реализуемый вычислительными средствами дискретного действия.

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

Решаемые задачи. Общей задачей, решаемой в диссертации, является получение эффективных математических моделей дискретной обработки данных. Частными задачами, вытекающими из общей, являются:

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

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

1 Здесь под концептуализацией понимается метод моделирования, при котором совокупность известных фактов или представлений относительно предметной области истолковывается с помощью знаков и операций над ними, или с помощью языков Согласно определения Грубера [Л1], онтология есть точная (формальная) спецификация результатов концептуального моделирования

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

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

Методика исследования основана на формально-логическом и концептуально-онтологическом моделировании. Формально-логическое моделирование осуществляется при алгебраической декомпозиции дискретных функций, а концептуально-онтологическое — путем формальной спецификации результатов понятийного анализа предметной области. Как в первом, так и во втором случае ищутся декомпозиционные схемы, позволяющие получать эффективные математические модели дискретной обработки данных.

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

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

-выполнен количественный и качественный анализ порождающей способности аналитических конструкций формул;

-обоснована методика алгебраического синтеза дискретных функций и найдены точные оценки сложности синтезируемых формул при конечной размерности задачи;

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

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

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

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

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

Реализация результатов. Результаты и положения диссертации приняты к использованию в ЗАО «ЛАНИТ» (понятийный анализ, элементы системы контекстного программирования) и внедрены в учебный процесс РГТУ им. К. Э. Циолковского (алгебраический синтез, контекстная технология), о чем имеются акты: ЗАО «ЛАНИТ» - акт об использовании результатов диссертационного исследования при выполнении государственного контракта 698ДК-МФ-03 по разработке проектно-сметной документации для создания систем инженерного обеспечения территориальных органов Федерального казначейства путем автоматической генерации документов на основе понятийного моделирования; РГТУ им. К. Э. Циолковского -акт о внедрении результатов диссертационной работы в учебный процесс на кафедре «Испытание летательных аппаратов» по дисциплинам «Организация ЭВМ и систем» и «Программные средства автоматизации».

Апробация работы. Результаты диссертационного исследования докладывались на международных конференциях «Современные методы цифровой обработки сигналов в системах измерения, контроля, диагностики и управления» (Минск, 1998), «Математические методы в образовании, науке и промышленности» (Тирасполь, 1999, 2001), конференции по телекоммуникациям (Одесса, 1999), по проблемам управления (Москва, 1999, 2003 и 2006), на конференции «Цифровая обработка сигналов и ее применение» (Москва, 1999, 2002, 2003), «Идентификация систем и задачи управления» (Москва, 2000, 2003), «Проблемы управления безопасностью сложных систем» (Москва, 2000), «Распознавание образов и обработка информации» (Минск, 2001), «Параллельные вычисления и задачи управления» (Москва, 2001), «Автоматизация проектирования дискретных устройств» (Минск, 2001, 2003), на конференции, посвященной 100-летию со дня рождения члена-корреспондента АН СССР М. А. Гаврилова (Москва, 2003); на семинарах «Логическое моделирование» (Москва, 2005) и «Проблемы искусственного интеллекта» (Москва, 2006).

Публикации. По теме диссертации опубликовано 50 работ общим объемом 25,2 печатных листа, в том числе 8 статей в журналах из перечня ВАК. Под руководством автора и по тематике исследования защищена одна кандидатская диссертация.

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и пяти приложений. Объем диссертации 320 страниц.

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

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

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

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

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

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

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

Дискретная обработка. Для кодирования данных выберем в качестве универсального множество целых чисел = {...,-1,0,1,...}. Когда необходимо задать конечное множество из к элементов будем использовать подмножество Л^ этого множества, = {0,1,..., к -1}.

Обработку данных представим дискретной функцией /, заданной на множестве = N|C(¡ хх...х Л^ и принимающей значения на множестве , где х — знак декартова произведения. Будем говорить, что функция имеет значность kf и зависит от п переменных х0, Х[, ..., хп_\ со значностями к0, к\, ..., кп_\ соответственно. При дискретной обработ-

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

Рассмотрим две крайние формы описания дискретной обработки: регулярную и нерегулярную. Нерегулярные формы получают в результате декомпозиции общего вида [Л2], когда дискретная функция / , зависящая от переменных X, на каждом шаге представляется как композиция функций g и И,

где X', X" - подмножества X. Декомпозиция завершается, когда g и И непосредственно реализуются вычислительным средством. Синтез нерегулярных форм без заранее заданной декомпозиционной схемы2 практически нереализуем, т.к. связан с перебором большого числа вариантов.

Регулярные формы основаны на алгебраической декомпозиции [48], осуществляемой в алгебре из двух операций + и х,

АЛ = а, (X"),

где 0,, а, - некоторые функции, которые будем называть частичными. Частным видом алгебраической декомпозиции является решающее разложение функции, применяемое при построении диаграмм решений и логических программ [ЛЗ]:

где 0, - система решающих функций, а, - остаточные функции, \ — знак разности множеств. В случае, когда X' = X и X" = 0, имеем спектральную форму [Л4],

ЯХ) = ^в,{Х) ха,, где в, - система спектральных функций, а, - коэффициенты разложения.

Алгебраическая декомпозиция. Найдем условия, при которых алгебраическая декомпозиция существует. Разделим множество переменных Х = {х0,х1,...,х„^]} на два непересекающихся множества X'= {х'0,х[,...,х'„'_^} и X" = с числом переменных п и

п" соответственно. Представим функцию /, заданную вектором значений длины т, зависящей от двух переменных х' и х" со значностями к' и к",

*' = Цк; = П*}> к"= = *'*' = «•

7=0 (х,еХ') 7=0

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

2 Здесь под декомпозиционной схемой понимается совокупность ограничений на вид функций g,h и множества переменных А" , X', которые сокращают перебор вариантов

Разложим / по некоторой системе функций в, (/ = 0,к' -1),

/(*'.*•) = (*>««(*")■ (1)

1=0 _

При подстановке в (1) значений переменной х' = 0,к' — 1 ползаем систему алгебраических уравнений

ДО,*") = 0о(О)хао(х") + ...+ 0*'-1(О)хя*'-1(*");

Л1,Л = 0о(1)хао(х') +...+

: : : : '2-)

Дк'-\,х") = в0(к'-1)ха0(х") +...+ ^(¿'-»х^мОО,

из которой требуется найти а, (/ = ОД' -1). В матричном виде система (2) представляется так:

Р = ОхА ( А = Охр), (3)

где Р и А - матрицы функции и коэффициентов размерности к'хк", О и О - квадратные матрицы прямого и обратного преобразования размерности к'хк' с элементами = 0,0') и =&,(у) соответственно. Столбцы матрицы Э являются векторами частичных функций в,, а строки А - векторами частичных функций а,.

Существует несколько алгебр, позволяющих разрешить систему (2) относительно неизвестных функций а,(х") . Такие алгебры будем называть образующими3.

Алгебра логики. Рассмотрим алгебру Л/, =(Лг^.,+,х) и потребуем существование таких элементов а и т Фа , что

а + а=а, ст+а=а, аха=а, тха = а для всех а е Л^ . Элемент а назовем нулем, а т — единицей алгебры .

Определение 1. Матрицей перестановок Р^- порядка к' называется квадратная матрица, состоящая из нулей а и единиц г и имеющая в каждой строке (столбце) ровно по одной единице.

Теорема 1. Произвольная функция / представима в ^ разложением (1), если и только если Р является матрицей перестановок. Тогда О = Ог и О х О = Е, где Е — единичная матрица, Т — операция транспонирования.

Мультипликативная алгебра. Определим образующую алгебру = (^к > +>х). У которой операции удовлетворяют условиям алгебры Кь, а умножение дополнительно образует группу = (Л^ \ а, х) на множестве А^ без нулевого элемента а . Последнее означает, что для любого элемента а е См существует обратный ему элемент а, такой, что ах а'' = т .

3 Известно, что разложение (1) возможно в полях и целостных кольцах (коммутативных кольцах с единицей и без делителей нуля) Следовательно, перечисленные алгебры являются образующими

Определение 2. Мономиальной матрицей М^ порядка к' называется квадратная матрица, получаемая перестановкой строк (столбцов) диагональной матрицы с элементами (1, Фа .

Теорема 2. Произвольная функция / представима в Ям разложением (1), если и только если О является мономиальной. Тогда О = Ог и ОхЭ = Е, где Е - единичная матрица, а О получается из Б заменой ненулевых элементов на обратные в группе О^.

Аддитивная алгебра. Пусть ЯА = где операции сложе-

ния и умножения удовлетворяют условиям алгебры , а сложение таково, что образует коммутативную группу СА = (Л^, +), т.е. для любого элемента аеб^ существует противоположный ему элемент -а, такой, что а + (-а) = ст .

Определение 3. Порядком элемента а группы СА называется минимальное натуральное число са > 0, для которого сД-а = а + а + ... + а = а,

" 1-V-'

са

где и — нейтральный (нулевой) элемент группы СА.

Для определенности положим 0-а = сг и -Я■ я = Я • (-а) для любого Я е 2 , где 2 - множество целых чисел.

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

Заметим, что циклический порядок группы (3А равен наименьшему простому числу кроме единицы, являющемуся делителем ее порядка [Л5, с. 19].

Лемма 3. В произвольной группе 0А уравнение вида Х-а = Ь, где Я € 2, а,Ье вА, имеет единственное решение тогда и только тогда, когда циклический порядок группы больше | Я |.

Определение 5. Биполярной матрицей Ък> порядка к' называется квадратная матрица, состоящая из нулей а, .единиц т и минус единиц -г алгебры ЯА.

Определение 6. Матрицей, сопряженной биполярной матрице В^', называется такая матрица , которая получена из В^ заменой нулей, единиц и минус единиц ЯА на нули, единицы и минус единицы кольца целых чисел Яу = \2, +, х).

Теорема 4. Произвольная функция / представима в ЯА разложением (1), если и только если О является биполярной, и модуль определителя А сопряженной ей матрицы не равен нулю и меньше циклического порядка группы йА. Тогда А • А = , где О - матрица алгебраических дополнений О, вычисленная в кольце целых чисел .

Умножение из КА применяется только при вычислении функции, для нахождения частичных функций используется циклическая сумма.

Фундаментальная алгебра. Пусть Яр=(Ик,+,у), где операции сложения и умножения образуют поле и, тем самым, удовлетворяют усло-

виям алгебр Яь, Ям и ЯА . Известна следующая теорема [Л5].

Теорема 5. Произвольная функция / представима в Яр разложением (1), если и только если определитель О е Яр- отличен от нуля. Тогда 0 = 0"' и ОхО = Е, где О ' -матрица, обратная О 4.

Сигнатуры образующих алгебр. Элемент а называется инвертирующим (слева и справа) на множестве Ма с , если уравнения а + х = Ь и х + а = Ь имеют единственные решения относительно х е Л^ для всех Ъ е №. Элемент а называется обращающим (слева) на множестве №, если уравнение ахх-Ь имеет единственное решение относительно х для всех Ь € №. Элемент а называется вырожденным (слева) на множестве №, если элемент х = а*Ь может быть найден (выражен, определен) при любом наперед неизвестном Ь е №. Такие элементы Ь будем называть свободными. Вырожденный элемент а называется нейтральным, если Ъ~ ахЬ, константным - если с = ахЬ и с не зависит от Ь, нулеобра-зующим - если а = а х Ъ для всех Ъ . Элемент а называется неделимым (слева) на множестве N°, если уравнение Ьу.х = а не имеет решений относительно х при любом ¿ёЛ'".

В табл. 1 приведены свойства специальных элементов алгебр.

Таблица!. Сигнатуры образующих алгебр

Алгебра Сложение Умножение

Логики Ч ст+ст =сг, с -инвертирующий ф - вырожденный (фха = а), т -обращающий

Мультипликативная Ям ф - вырожденный (фха = ст ), А^ \ ст - обращающие

Аддитивная Ка Ир. - инвертирующие, ассоциативность, коммутативность ф - вырожденный, т -обращающий

Фундаментальная Яр- ф - неделимый на Ык \ и , ассоциативность, коммутативность, дистрибутивность по сложению

Из таблицы находим, что операция сложения в аддитивной и фундаментальной алгебре образует коммутативную (абелеву) группу на множестве Л^ с нейтральным элементом о . Фундаментальная алгебра включает поле (к > 0 ) или коммутативное кольцо без делителей нуля (к = 0 ). В фундаментальной алгебре элемент т становится нейтральным по умножению, а нулеобразующий элемент ф вырождается в и . В остальных алгеб-

4 Теорема 5 справедлива на целостном кольце. При конечном числе элементов целостное кольцо изоморфно конечному полю [Л5, с 25], следовательно, носитель кольца - счетное множество Мй. Теорема справедлива и на коммутативных кольцах без делителей нуля, т к для разложения (1) существование единицы не является необходимым

pax элементы ф и а могут различаться.

В аддитивной алгебре возможно различное вырождение ф иг, но, в любом случае, требуется, чтобы хотя бы одно вырождение существенным образом зависело от свободного элемента. Частными случаями аддитивной алгебры являются униполярная и биполярная алгебры. Униполярная алгебра имеет традиционное вырождение элементов: фхх = ст , txi = x. В биполярной алгебре элемент ф вырождается иначе: ф х х = -х, где -х - элемент, противоположный х. В общем случае возможно существование еще одного вырожденного элемента - минус единицы: -тхх = —х.

Для существования матрицы Q и использования матричного аппарата обратного дискретного преобразования (3) на операции образующих алгебр накладываются дополнительные ограничения. В алгебре логики а должен быть равен ф и являться нейтральным по сложению, а г - нейтральным по умножению. В мультипликативной алгебре умножение должно иметь обратную операцию на множестве Nk \ а . В аддитивной и фундаментальной алгебре в дополнительных требованиях нет необходимости. Отношения между алгебрами показаны на рис. 1а.

R,

R

■м

R*

Ra

а)

б)

Рис. 1. Классы образующих алгебр и частичных функций Функциональная полнота. По своей сути разложение (1) позволяет свести вычисление произвольной функции / к вычислению функций в, и а, меньшей сложности (с меньшей длиной вектора), а теоремы разложения определяют условия, при которых базис {+,х, {9,}, < а>} обладает функциональной полнотой, где {в,} - система фундаментальных к'-функций, а < а > - класс, включающий все к" -функции5.

Определение 7. Система частичных функций {0,} называется фундаментальной, если сложение и умножение функций для всех значений переменных коммутативно, ассоциативно, и выполняется закон дистрибутивности умножения функций относительно их сложения, т.е. при

5 Здесь под ¿-функцией понимается произвольная дискретная функция, задаваемая вектором значений длины к

* е {+, х}, для любых /, ], ? и всех х, у, г

е1{х)*е]{у)=в]{у)*в1{ху, в,(х) * (6^*0,(2)) = (01(х)*0^у))*в1(2)-, в, (X) X (0, (У) + 0, (2)) = (0, (X) X (У)) + (0, (X) X 0, (7)).

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

Классы функций. Из отсутствия ограничений на а, следует, что четыре основных типа образующих алгебр порождают четыре класса частичных функций вi (табл. 2).

Таблица 2. Классы частичных функций

Класс функций Двузначные Многозначные

Унимодальные Алгебры логики Мультипликативные алгебры

Мультимодальные Аддитивные алгебры Фундаментальные алгебры

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

Классы частичных функций находятся в отношении включения друг в друга (рис. 16). Самый обширный класс Бр представлен мультимодаль-ными многозначными функциями и включает в себя два пересекающихся класса: класс мультимодальных двузначных функций 3А и класс унимодальных многозначных функций 5м. Пересечение последних образует класс унимодальных двузначных функций Типичные представители распространенных на практике систем приведены в табл. 3.

ТаблицаЗ. Системы частичных функций

Класс функций Двузначные Многозначные

Унимодальные Дизъюнктивные Конъюнктивные Литеральные Интервальные

Мультимодальные униполярные Жегалкина Рида-Маллера Теоретико-числовые Полиномиальные

Мультимодальные биполярные Радемахера Уолша Хаара Виленкина-Крестенсона

Синтез формул. Покажем на примере синтез формульного пред-

10

ставления дискретной функции в алгебре ЯА . Операции сложения и умножения зададим матрицами

"о 1 2 з" "о 1 2 з"

1 2 3 0 0 0 1 1

, х =

2 3 0 1 0 0 0 0

_3 0 1 2_ 0 0 0 0

где + - сумма по модулю 4, образующая абелеву группу на множестве с нулем а = 0 и циклическим порядком 2, а х - операция логического сдвига (ахЬ есть сдвиг Ъ на а двоичных разрядов влево) с ф = 3 и обращающим элементом г = 0.

Пусть функция определена векторами значений Р и значностей К, Я = [322102312103103020020220], К = [2232], т.е. зависит от переменных X = {х0,х1,х2,х$} со значностями к0 = 2, = 2, к2 = 3 и ¿з = 2 . Запишем (1) при X' = и X" = {х0,х2},

/ = в0 (х') х а0 (х") + 01 (х') х а{ (х") + 02 (*') х а2 (х") + в} (V) х а3 (х") . Зададим систему частичных функций биполярной матрицей О и найдет,! на кольце целых чисел определитель А и алгебраические дополнения й сопряженной ей матрицы О:

1 0 0 О] Г 1 0 0 0"

110 0 —- -110 0

, А =1, 0 = 10 10 -10 10

10 0 1] [-1 0 0 1. Так как циклический порядок группы больше А, то в соответствии с теоремой 4 система функций О функционально полная. Тогда

3 2 0 2 2 0"

2 13 113 1 0 2 0 0 2'

3 2 0 2 2 0

где • — операция циклической суммы, А — матрица коэффициентов, Т -матрица_функции, найденная для заданного разделения переменных. Умножая й и Т относительно сложения и циклической суммы, находим А • А , а затем, на основании леммы 3, и А :

3 2 0 2 2 0" 3 3 3 3 3 3 2 2 2 2 2 2' 0 0 0 0 0 0 В итоге имеем искомую формулу функции,

11

г Ф ф ф

т X ф ф

т ф т ф

г ф ф т

А А = Р Т =

10 0 0 -110 0 -10 10 -10 0 1

Д-А =

3 2 0 2 2 0

3 3 3 3 3 3

2 2 2 2 2 2

0 0 0 0 0 0

У У ~2~ "0"

т 2 3 ~ф 2 ~Ф 0

т У ' V 0 х" + Т 3 ф г'* 2 Ф г'х 0

т Л Л 2 ф Л * 3 X Л Л 2 Ф Л А 0

т 2 0 ф. 3 _3 ф. 2 2 г 0 0

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

У

х +

У У У

0 х'хЗ + 3 х'х2 + 3

3 0 3

3 3 0

х'хО =

(х0,х2) +

(*1>*з)>

и, представив частичные функции от двух переменных операциями о0 и , имеем

ДЛО = *о

"3 0 2 О 2

2 2 0 х2 + Х1 _3 0

х3 - *0 °0 х2 +Д!:1 °1 ХЪ •■

где х[у„ ]г = ух: - бинарная операция, задаваемая матрицей [уу ].

Из примера видно, что при алгебраической декомпозиции по виду Т можно оценить эффективность формульного представления, которое будет более компактно, если при прочих равных условиях Т содержит большее число одинаковых или линейно-зависимых строк6.

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

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

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

М-1

ДА') = 10,(Х')ха,(Х"), (4)

/=0

где М — количество слагаемых, М < к'. Сложность разложения определим количеством слагаемых М. Под сложностью представления Ь будем понимать количество операций, необходимых для вычисления функции по формуле (4).

Алгебраическая декомпозиция близка преобразованию Карунена-Лоэва [Л6, с. 182], где разложение осуществляется по собственным векторам ковариационной матрицы функции и, тем самым, обеспечивается наилучшее (оптимальное) приближение функции в среднеквадратическом смысле и достигается наименьшая сложность разложения. В этом случае частичные функции вычисляются с некоторой степенью свободы, а их количество равно числу ненулевых собственных значений ковариационной матрицы. Воспользуемся оставшимися степенями свободы для достижения наименьшей сложности представления функции.

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

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

е(Х)=<0 х0 о0 <, хх о1...°„_2 <„-1 Х„-1, (5)

где <J - произвольные унарные (бинарные) операции. После тождественных преобразований (5) имеем ее каноническую форму

в(х) = х,в °0 °1 °2 ■•• V-2 . (6)

также заданную с точностью до расстановки скобок, но уже не содержащую унарных операций и несущественных переменных (п' < п).

Бесскобочная конструкция. Подсчитаем количество различных функций , порождаемых бесскобочным вариантом конструкции (6). Для этого рассмотрим бинарные операции от двух переменных со значностями ко , ¿1 и найдем количество порождаемых ими функций N0{к,ка,к{) знач-ности к . Общее число функций равно ккс,к' и

7=0

где множитель С^ - число сочетаний из к элементов по ], который учи-

тывает функции значности ] , принимающие значения не на всем множестве Л^, а на различных его подмножествах из у элементов. Отсюда получаем рекуррентное выражение для И0 (к, к0, ку),

лго(0Д0Д1) = 0, = - х'с/здДоД,). (7)

7=0

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

к„-1

к-1

АГ0-*(1, к0, кО = 1, к0, ко = П (* ' - 0 ■- I С(А>?и, к0, ко . (8)

г=0 7=1

Для подсчета количества функций , порождаемых конструкцией (6) используем систему рекуррентных уравнений,

ЛЪО^/ДоЛ) = ЗД/ДоЛ).

к Гг

г к

1=1

(9)

ЛГ9(А:ДоД1,"-А-1) = оДъ-А-1>>

7=1

Из (7) и (8) следует

Л*о<*.-1 > (к, к0,к1)<^(к,к0,к1) <кк°к> ,

*

а с учетом (9) получаем оценку для лУе при п > 2,

к "2 <ЛГв(*.*ьЛ>-Л-1)<* -1 ■ (Ю)

Оценка (10) допускает достаточно простую содержательную интерпретацию: верхняя граница степеней свободы аналитической конструкции меньше суммарной площади операций, а нижняя граница определяется при более чем существенной зависимости операций от правого операнда, что эквивалентно вычеркиванию одной строки у каждой операции, кроме нулевой (рис. 2).

Вместо неравенств (10) будем использовать равенство

я-1

Щ(к,к0,к1,...,к„_1) = к , (11)

где а — порождающая способность аналитической конструкции, 0<а <1.

х\

х2

Х0

* * * *

°0

* * ... * * * ... *

°1

ХП-1

* * ... * * * ... *

°п-2

->0(Х)

Рис. 2. Бесскобочная аналитическая конструкция Вычисление а осуществим по формуле 1о

а = к-

и-1

Е \

7=2

(12)

где А, - значности переменных в порядке их вхождения в формулу, Л^ -количество порождаемых функций, найденное путем решения (9).

На рис. 3 показана зависимость порождающей способности а от ко-

личества переменных п. а

0,750 0,725 0,700 0,675 0,650 0,625 0,600 0,575

\

N к = 2

а, > 0,708

\ к = 3 а,! *0,578

к = 4 .щ = 0,577

5 10 15 20 25 30 35 40 п

Рис. 3. Порождающая способность бесповторных формул

С ростом п параметр а асимптотически стремиться к некоторой величине ак, которую назовем предельной порождающей способностью. Из (9) с учетом (12) находим

1.

ак=к--1оёк П". ,

к ,=0 г + 1 Зависимость ак от к показана на рис. 4.

5 10 15 20 25 30 35 40 к Рис. 4. Предельная порождающая способность Скобочная конструкция. Если конструкция (6) является скобочной, то для подсчета количества функций на каждом уровне вложенности скобок применим представление:

в(х)=0о(*о)°о адь ...«,-2 .

где в, — некоторые подформулы в скобках, зависящие от переменных из подмножеств X,- со значностями К, (рис. 5).

ОД) 02(Х2) О^(Х^)

О0(Х0)

* * . . * * * . . * * * . . *

* * . . * —> * * . . * ... * * . . #

* * . * * * . * * * . . *

■ в(Х)

°0 °1 °5-2

Рис. 5. Скобочная аналитическая конструкция

Если - количество функций, порождаемых подформулой

в1, а к§,к{) - количество операций при их более чем существенной

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

= Е"тг А'е (/, (/, к,),

7=1

Так как к0, < к0, к{), то

16

ЛГе(*,АГ0,л:,,!) < .

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

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

п-1

Ы1(к,к0,к1,...,к„_1)<к '=» ' .

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

Спектральная декомпозиция. Синтезируем формульное представление функции путем ее разложения в спектральном базисе {в,}:

М-1

/(*)=! 0,(Х)ха1. (14)

1=0

Функции, порождаемые бесповторной аналитической конструкцией, образуют множество линейно-независимых классов. Внутри класса функции преобразуются друг в друга путем умножения на ненулевые константы. Следовательно, в один класс включаются функции, которые могут быть преобразованы друг в друга умножением элементов матрицы последней операции на ненулевую константу. В фундаментальной алгебре таких констант к -1, в аддитивной алгебре - одна или две7.

Пусть в разложении (14) при М <т , где т - длина вектора значений /, различные комбинации спектральных функций в,, взятые из различных классов, порождают различные функции8. Тогда для порождения всех функций необходимо, чтобы

м

*т = 1С^(*-1)г, (15)

,=1 '

где Ыс = М0/(к -1) - число классов функций, порождаемых конструкцией

7 Полное использование комбинаторных возможностей бесповторной аналитической конструкции возможно только в аддитивной и фундаментальной алгебрах В других алгебрах конструкция является избыточной и не влияет на эффективность синтеза [40,42]

8 Допущение о том, что различные линейные комбинации частичных функций порождают различные функции основано на следующих соображениях. Известно [Л7], что количество невырожденных матриц размерности тхт значности к равно -1), отсюда доля невырожденных матриц с различающимися столбцами от общего их числа всегда больше некоторого параметра ^ > 0,5, который быстро стремится к единице с ростом т Учет параметра х не изменяет получаемые оценки

(6). Из (15) получаем

ТМ{к_Х)мМм <кт < (к-1)мN2*,

а после логарифмирования с учетом (10) имеем оценку Ма и Мг при спектральной декомпозиции в аддитивной и фундаментальной алгебре соответственно:

п-1 я-1

, . п*. , п*.

Ма =—------^-, М,=—--^-, (16)

(=0 г=0

где ¡3 - поправочный коэффициент для учета начальных условий,

к —а

Тогда для максимального количества операций Ь, необходимых для представления произвольной функции от п переменных со значностями £0 , кх,..., кп_1, из (16) следует

и-1

П*,

Кк,к0,кь...,к„_ 0= " -= (17)

а±к,-р 1=0

где С - константа, характеризующая аналитическую конструкцию,

1 2

С = —----. (18)

" г=0

Из (15) получаем точное и оценочное значение доли функций 8 , имеющих меньшую чем Ь сложность,

М( 1-е)

I С'К(к-1)г

«(да) = ----< к~гт, (19)

кт

где £ - доля слагаемых, на которую уменьшается сложность разложения.

Из (17) и (19) следует, что при спектральной декомпозиции количество ненулевых коэффициентов М и число операций Ь в синтезируемой формуле удовлетворяют асимптотическим оценкам:

1, (20) 2 п 2 к~ак к

где--знак асимптотического равенства, — предельная порождающая

способность аналитической конструкции, к - средняя значность переменных. Более того, для любого е > 0 доля функций 8 , для которых

18

м <(1 -£)%-,

2 п

меньше чем к~гт и стремится к нулю с ростом т.

Алгебраическая декомпозиция. Найдем сложность алгебраического разложения (4) при произвольном разделении переменных. Для этого в качестве первого приближения системы частичных функций {в,} выберем столбцы матрицы функции Т размерности к'у. к" (рис.6).

"06 в 02 03 Ф Ф т ф ф Ф~ "00 в 02 0з"

% в 02 03 Ф Ф ф т ф Ф 06 02 03

06 в 02 03 Ф Ф ф ф г Ф 00 в 02 03

06 в 02 03 Ф Ф ф ф Ф т 06 в 02 03

% в 02 03 Ф Ф ф" ~ф" "Ф "Ф 06 02 03

% в 02 0з Ф Ф ф ф Ф Ф. 06 е 02 03

Рис. 6. Алгебраический синтез: б/ - элементы линейно-независимых столбцов функции; ф - нулеобразующий элемент; т - единичный элемент

Для формирования {в,} возможно использование различных линейных комбинаций столбцов Т. Количество таких комбинаций равно кк -1, что позволяет сформировать произвольную систему функций, в том числе и представимую формулами с наименьшим числом операций. При уменьшении к" количество слагаемых в разложении уменьшается. В пределе имеем спектральное разложение. Однако, в общем случае разлагаемая функция не имеет бесповторного представления. Следовательно, существует некоторое минимальное к", при котором система {б,} все еще предста-вима бесповторными формулами.

Так как при достаточно большом к" < к' частичные функции могут быть произвольными, представим их как спектральное разложение некоторой неизвестной функции. Тогда из (16) следует условие, при котором гарантируется представимость системы из к" частичных функций длины к' бесповторными формулами, а сложность решающего разложения М станет равна к" :

¡=о

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

п'-1

(21)

М'-\ М"~ 1 М-1

(=0 7=0 7=0

где М = Л/М", М' = к", в[ и - бесповторные бесскобочные конструкции, в, - бесповторные скобочные формулы, состоящие из двух бесскобочных подформул. Из (16) и (21) получаем:

п-1

. п*.

-------'=°--— . (22)

М--

0к-ау

2 п'-1

Найдем разделение переменных, которое обеспечивает наименьшую сложность разложения. Для этого сформулируем задачу поиска условного экстремума (22):

п'-\ п'~1 7=0 7=0

• т = (к -а){± к[ - р')Ц к"/ (23)

7=0 7=0

7=0 7=0

где 5 и /и — константы, первое и второе тождество задает зависимость переменных, а последнее выражение определяет целевую функцию. Решение (23) методом неопределенных множителей Лагранжа выявляет следующую связь между значностями переменных9: п'-1 п"-\

7=0 7=0

где ¡л - некоторая константа, не зависящая от разделения переменных. Полагая ц(2п" -1) = рп, получаем

77—1

Л Г1. п"-\ Ъ,, и —1

п —--' р1*;)«^-—.

(к-а)2 Д,^ п /=0 7=0 к + [1 п

м=-

Ы-Р'-РТ-р'*1

7=0

где р - параметр, характеризующий разделение переменных. Для оценки /.I используем условие (21), заданное при одинаковых значностях переменных,

9 Решение (23) получено при условии £ к\ » (3'

20

^щЛ{к-а)кп

-:-•

п-1

На рис. 7 приведена зависимость оптимального значения р от количества переменных п при их одинаковой значности. Заметим, что р стремиться к нулю с ростом п. Р

0,40 0,35 0,30 0,25 0,20 0,15 0,10 0,05

к = 2

\

к = Ъ

к = 5

10 15 20 25 30 35 40 45 п Рис. 7. Оптимальное разделение переменных

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

С = -

1

к-а

^ 1 «-1 у-1 42

" г=0

(24)

7=0

где С - константа, характеризующая аналитическую конструкцию, а -порождающая способность, у - количество скобок или количество ступеней декомпозиции, 2 < у < 1о§2 п -1, - поправки начальной порождающей способности подформул, р - параметр разделения переменных.

С увеличением глубины вложенности скобок оценка (24) ухудшается, а наименьшая сложность достигается при у = 2 . Из (24) находим:

1 2

М~С,

2 т

Ь~С2-

СК =

к — ак к

причем для любого е > 0 доля функций <5 , для которых"

(25)

10 Сложность алгебраического разложения может быть уменьшена только за счет спектрального разложения коэффициентов Полагая к" <4т , из (19) получаем искомую долю функций.

М<(1-£)с1~ 11

Ь<{\-Е)С1-п

- Г~ 1

стремится к нулю с ростом т как к еу/т . Зависимость Сх от значности

образующей алгебры к показана на рис. 8.

с2

30 0,6

0,5 0,4 0,3 0,2 0,1

23456 7 8 9 £ Рис. 8. Зависимость Ст от значности алгебры к Из (25) следует асимптотическая оценка количества операций, необходимых для представления произвольной булевой функции,

4 2" 2"

Ц")--т— * 0,5986—,

(1 + к^23)2 " п

которая согласуется с оценкой количества команд (операторов и условных переходов), полученной при программной реализации логической обработки данных [Л8]. Заметим, что программная реализация имеет ту же природу, что и аппаратурная [Л3].

Эффективность модели. Установлено, что почти все дискретные функции реализуются со сложностью

и-1

4 П*,

I =--¡-^2-, (26)

п^к-а) 1 ("¿¿г_2/3)2_р2

П г=0

где к — значность образующей алгебры ( к > ку), а — порождающая способность аналитической конструкции ( 0 < а < 1), /3 — начальная порождающая способность (¡3 «к), р - параметр разделения переменных (0<р <0,3).

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

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

Формула (26) позволяет по объему обрабатываемых данных и количеству операций V оценить эффективность произвольной дискретной обработки данных, а в случае, если количество операций V будет меньше Ь, определить и степень минимизации математической модели, равную отношению Ь к И.

Алгебраический синтез. Алгебраический синтез осуществим при алгебраической декомпозиции функции путем оптимального разделения переменных X на два непересекающихся множества X' и X" таких, что 1 (п'-1 и"-1 4 ~~ — ~ Роит'

7=0

а искомая формула ищется в виде

м-1

/=0

где и Л, - частичные функции, задаваемые бесповторными бесскобочными формулами, а М таково, что обеспечивается выполнение условия (26).

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

Однако трудоемкость алгоритмов алгебраического синтеза, как это имеет место и при разложении по Карунену-Лоэву, достаточно высока. Это объясняется отсутствием ограничений на степени свободы декомпозируемых функций и является следствием абстрагирования общей теории декомпозиции от содержательных представлений о решаемой задаче.

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

ределенные надежды на возможность автоматизации такого поиска.

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

Суть подхода заключается в том, что мышление рассматривается как способность сведения многоэкстремальной задачи, которую можно решать только методом перебора, к градиентной, одноэкстремальной [Л9]. Последнее есть следствие специфического отражения окружающего мира в сознании человека, благодаря которому он решает задачу на основе обобщений и ассоциаций, двигаясь к эффективному результату по прогнозируемому градиенту эмоциональной оценки ситуации.

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

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

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

Сущность определим как устойчивое и уникальное представление предметной области, воспринимаемое некоторой совокупностью признаков. Признак, как именованная сущность, характеризуется множеством своих проявлений (значений) и имеет некоторую проблемную интерпретацию (семантическую роль). Признаки будем воспринимать как элементарные сущности, с точностью до которых осуществляется описание предметной области.

Понятие представим множеством сущностей, объединенных на основе общности своих признаков. Понятия будем именовать и задавать схемой, интенсионалом и экстенсионалом. Имя, или знаковое представление понятия, является языковой единицей, несущей некоторый смысл — в семантическом плане, или обозначает некоторую конкретную сущность - в синтаксическом плане. Схему понятия зададим набором признаков, на ко-

24

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

Сущности различаются с помощью признаков. Множество допустимых значений понятия-признака образует его экстенсионал или домен, а интенсионал вырождается в семантическую роль. В пределе, когда у понятия единичный объем, имеем именованную сущность, т.е. имена могут использоваться не только для обозначения понятий, но и для обозначения сущностей. Таким образом, под сущностью следует понимать понятие, имеющее единичный объем. В итоге, понятие будем рассматривать как общую категорию, а сущность и признак - как ее частные случаи.

Структура понятия. Обычно понятие используется не в абсолютном, а в некотором относительном смысле, называемом прагматикой. Прагматика понятия выявляется при знании проблематики предметной области. Если понятие рассматривать как вместилище всех своих смыслов, то проблематика конкретизирует семантику понятия до его прагматики. В итоге имеем шестиугольник (рис. 9), включающий треугольник Фреге Сущность - Имя - Понятие, объясняющий образование понятия, и треугольник Проблематика - Прагматика - Семантика, выражающий содержательную интерпретацию понятия в некоторой проблемной области.

Абстрагирование понятий. Абстрагирование - форма мышления, при которой происходит образование понятия. При абстрагировании между понятиями выявляются отношения независимости, дифференциации и интеграции (рис. 10). Понятия независимы, если их признаки не пересекаются. Если у двух понятий имеются общие признаки, то наблюдается диффе-

Рис. 9. Структура понятия

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

Известны следующие абстракции [Л11]: обобщение (специализация), типизация (конкретизация), агрегация (декомпозиция) и ассоциация (индивидуализация). Обобщение и типизация, и обратные им специализация и конкретизация, выражают общность понятий, проявляющуюся при дифференциации. Агрегация и ассоциация, и обратные им декомпозиция и индивидуализация раскрывают интеграцию понятий.

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

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

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

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

а) независимость б) дифференциация в) интеграция Рис. 10. Пространство признаков

ция - порождение понятия на основе объединения схем агрегируемых понятий и декартового произведения их экстенсионалов. При декомпозиции понятие-агрегат разделяется на входящие в него агрегированные понятия.

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

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

В отличие от семантической сети и онтологии11, где на понятиях задаются различные типы отношений, несущие различную семантическую нагрузку, понятийная структура определена множеством понятий с четырьмя видами отображений, единственное назначение которых — показать способ образования понятий. Понятийная структура близка расширенной модели данных «сущность-связь» (ЕЕЛ-модель)1 , однако в ЕЕЯ-модели элементами являются не понятия, а типы данных, причем для детализации модели используется трудно формализуемая семантическая разметка в виде дополнительных нотаций и ограничений.

Пример понятийной структуры приведен на рис. 11. Заметим, что даже для такой предметной области как «Числа» в зависимости от проблематики можно определить несколько понятийных структур.

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

Теорема 6 (обобщение). Произвольная понятийная структура может быть тождественно преобразована к виду, содержащему не более чем по одному обобщению для каждого включенного в нее понятия.

Теорема 7 (типизация). Произвольная понятийная структура может быть тождественно преобразована к виду, содержащему одинако-

11 Количество различных типов отношений между понятиями в семантических сетях может превышать 200 fJI 10]

12 Модель определена на множестве типов данных, между которыми установлены отношения обобщения, типизации, ассоциации и агрегации [Л 11]

вые схемы у всех типизируемых понятии и соответствующих им понятии-типов'3.

Теорема 8 (агрегация). Для непротиворечивости понятийной структуры необходимо и достаточно единственности агрегации у каждого понятия-агрегата.

Теорема 9 (ассоциация). Для непротиворечивости понятийной структуры необходимо и достаточно непустого пересечения схем ассоциируемых понятий у каждого понятия-ассоциации.

Действительное

Мнимая

Комплексное ч ______* ►Действительная

• - - обобщение О— типизация ♦— агрегация ♦ - - ассоциация

Рис. 11. Примгр понятийной структуры

Понятийный анализ. Понятийный анализ определим как методику построения и верификации понятийной структуры. Основными этапами понятийного анализа являются:

- выявление существенных признаков у сущностей предметной области с учетом заданной проблематики;

- сопоставление выявленных сущностей и определение их общих и различающихся признаков;

- образование новых или определение (переопределение) уже существующих понятий;

- создание понятийной структуры на основе дифференциации и интеграции признаков;

- вычисление схем понятий и задание ключей - для типизации, и связей - для ассоциации;

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

Схемы понятий вычислим по следующей рекуррентной процедуре:

13 В [Л12] абстракция типизации изначально определяется на множестве понятий, имеющих одинаковую схему Однако исходная форма описания понятия-типа может не удовлетворять этому требованию

- схема простого понятия состоит из этого понятия;

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

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

Таблица 4. Сравнение понятийного и объектного анализа

Понятийный анализ Объектный анализ

Сущность (единичное понятие): Объект:

- обладает уникальностью; - различается признаками; - выражает смысл. — обладает идентичностью; — имеет состояние; — проявляет поведение.

Признак (элементарное понятие): Свойство (атрибут):

отличает одну сущность от другой; имеет имя, домен и семантическую роль принимает различные значения и характеризует состояние объекта.

Понятие: Класс:

множество сущностей, образованное на основе абстрагирования. множество объектов, имеющих общую структуру и общее поведение.

Спецификация понятия-. Спецификация класса:

- имя (уникальность), схема (признаки); - интенсионал (содержание); - экстенсионал (состав). — имя (идентичность); — свойства (состояние); — методы (поведение).

Взаимосвязь понятий: Взаимосвязь классов:

- обобщение (есть некоторый); - агрегация (есть часть); - ассоциация (есть участник); - типизация (есть экземпляр). - общее и частное (наследование); - целое и часть (агрегация); - зависимость (ассоциация).

Обобщение (расширенная типизация): Наследование:

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

Агрегация: Агрегация:

соединение сущностей интегрируемых понятий. отношения целого и части, приводящие к иерархии объектов.

Ассоциация (ограниченная агрегация): Ассоциация:

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

Типизация: Виртуальные классы:

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

Понятийная структура: Диаграммы:

множество понятий с отображениями абстрагирования. иерархия классов, диаграммы состояний и поведения объектов.

Из табл. 4 видно, что понятийный анализ является некоторым обобщением объектного. Заметим, что результаты понятийного анализа легко формализуются и могут быть подвергнуты элементарной проверке на пол-

ноту и непротиворечивость.

Контекстная технология. Формализованное описание предметной области получим путем построения ее понятийной модели. В качестве программы будем использовать понятийную модель, дополненную описанием решения одной или нескольких прикладных задач:

Программа = Понятийная модель + Решение задачи. В понятийной модели выделим три части: понятийную структуру, синтаксис форм выражения понятий и семантику каждой такой формы:

Понятийная модель = Структура + Синтаксис + Семантика. Понятийную структуру и синтаксис понятий опишем на декларируемом в контекстной технологии метаязыке, а описание семантики и решаемых задач выполним на специализированном предметной языке, определяемом в понятийной модели.

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

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

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

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

Метаязык контекстной технологии зададим грамматикой:

1 program model [situation] [program]

2 model -ь essences [model]

3 essences différenciation notion [integration] [intension]

4 différenciation '(' [notions] ')'

5 integration -> '(' [notions] ')'

6 notions —> notion [alias] [notions]

7 intension —> sentence [intension]

8 sentence syntax semantic

9 syntax item [parse] [compile] [syntax]

10 item -> notion [alias] | lexeme [alias]

11 alias —> terms'"

12 lexeme term | pattern

13 term "• [terms]

14 pattern "" [ferms]""

15 semantic pragmatic [semantic]

16 pragmatic [aspecQ'{[text]

17 parse —>• ■<' [text] •>'

18 compile [aspect] T [text] T

19 situation —У [aspect] '<' [text] '>'

20 text phrase [text]

21 phrase -> terms | [aspect]'{text

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

Текст программы. Программа program состоит из понятийной модели model и ситуаций situation (правило 1). В модели определяется язык, на котором в ситуационной части описывается решение прикладной задачи. Понятийная модель model является законченным фрагментом определения специализированного языка, а ситуация situation может содержать полное решение задачи, если в приведенных ранее фрагментах модели определяемый язык задан полностью, или часть решения, когда язык определен в объеме некоторого подязыка, достаточного для описания только этой части.

Понятийная модель. Понятийная модель model состоит из описаний сущностей предметной области essences (правило 2). Сущностям присваивается имя notion нетерминального понятия определяемого языка, а само понятие задается как дифференциация différenciation и интеграция intégration ранее определенных понятий notions (правила 3-6).

Для указания на отсутствие у понятия абстракций используются пустые круглые скобки (правила 4, 5). В этом случае понятие считается обобщенным от «пустого» понятия empty или агрегирующим понятие empty. Для выражения перекрестных и рекурсивных связей между понятиями возможно их предварительное объявление, которое не включает описание содержания понятия intension (правило 3).

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

31

противном случае, differentiation выражает обобщение. Определение исходного понятия для сущности из экстенсионала понятия-типа осуществляется через ключ и описывается в конструкциях sentence типизируемых понятий.

Конструкция integration позволяет выразить агрегацию или ассоциацию (правило 5). Если интенсивная понятия, задаваемый описанием его содержания intension, ограничивает вхождение сущностей интегрируемых понятий в экстенсионал образуемого понятия, то реализуется ассоциация. В противном случае интеграция выражает агрегацию. Переход от сущностей одного из ассоциированных понятий к другим таким сущностям осуществляется через связь и описывается предложениями sentence ассоциированных понятий.

Интенсионалы понятий. Содержание понятия intension состоит из предложений sentence (правило 7). Предложения служат для определения интенсионала понятия и содержат как формы его выражения syntax, так и семантическую интерпретацию semantic (правило 8). С каждым предложением связывается понятие-результат, именем notion которого названы описываемые сущности (правило 3), определяемые предложением полностью -когда больше нет предложений с тем же понятием-результатом, или частично - если такие предложения имеются (правило 7).

Синтаксис предложения syntax выражается последовательностью элементов item: понятий notion и лексем lexeme (правило 9). Лексема является терминальным понятием определяемого языка. Для выражения лексем используются как терм term, так и множества термов, задаваемых на языке регулярных выражений в виде шаблонов pattern (правила 12-14). Для ссылок на отдельные элементы item применяются алиасы (правила 6, 11).

Средства расширения. Предложение sentence является правилом вывода грамматики определяемого языка с тем отличием, что в его состав введены конструкции parse и compile (правило 9). Конструкция parse (правило 17) служит для расширения метаязыка и подлежит компиляции и исполнению при метаязыковом разборе предложения. Конструкция compile (правило 18) используется для реализации компилятора специализированного языка, компилируется и сохраняется в структуре предложения для исполнения во время распознавании этого предложения в тексте.

Прагматика. Семантику понятий будем задавать в виде текста, построенного по правилам определяемого языка. Для этого каждое предложение sentence дополним описанием его семантики semantic, которую выразим множеством прагматик pragmatic (правила 8, 15). Текст прагматики pragmatic компилируется в императив - некоторую последовательность действий, которую система программирования выполняет всякий раз, когда понятие выражается этим предложением (правило 16). По своей сути императивы - единицы вызова целевой вычислительной платформы, в то время как синтаксис предложения - описание структуры таких вызовов.

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

32

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

Аспекты. Понятийная структура может быть общей для нескольких задач. Предусмотрим возможность задания для каждого предложения одной или нескольких прагматик (правило 15), которые будем именовать (правило 16) и называть аспектами aspect. В итоге любой текст на специализированном языке может задавать решение целого класса задач, а его конкретизация осуществляться указанием на одну из определенных прагматик (правила 16, 19,21).

Контекстные условия. Контекстные условия в метаязыке задаются для понятий notion, аспектов aspect и лексем lexeme, а места их задания в грамматике метаязыка выделены курсивом (правила 3, 13, 14, 16).

Имена понятий notion как терминальных понятий метаязыка объявляются при описании сущностей essences (правило 3). После такого объявления эти имена могут появляться в списке notions (правила 4, 5) и как элементы item при определении синтаксиса syntax (правила 9,10).

Аспекты aspect являются именами прагматик pragmatic (правило 16), назначение которых - определение именованных семантических интерпретации фрагментов текста phrase (правило 21) и текстов в описании семантики semantic, грамматического разбора parse, компиляции compile и ситуации situation (правила 16-19).

Лексемы lexeme задаются в виде термов term и шаблонов pattern (правило 12) и используются для выражения терминальных понятий terms определяемого языка (правила 13, 14). Лексемы сохраняются не в таблице идентификаторов, как это было для понятий и аспектов, а непосредственно в структуре определяемого предложения sentence.

Имена понятий notion являются терминальными понятиями метаязыка и одновременно нетерминальными понятиями определяемого языка. Имена аспектов aspect являются терминальными понятиями как метаязыка, так и определяемого языка. Лексемы lexeme и алиасы alias являются терминальными понятиями определяемого языка и метаязыка соответственно.

Демонстрационный пример. Рассмотрим понятийную модель предметной области «Исчисление высказываний»: 0 Variable

"[A-Za-z][A-Za-zO-9]*" [...]{} 0 Constant

'false' [ asm{ mov eax, 0; push eax } ] { } 'true' [ asm{ mov eax, -1 ; push eax} ] {} bit[ asm{mov eax, 1, push eax} ] {} (Variable) Logic

Variable [ asm{ pop ebx; mov eax, [ebx]; push eax } ] { }

33

Integer [ asm{ pop eax; cmp eax, 0, je m; mov eax, -1, m: push eax} ]

bit[ asm{ pop eax; and eax, 1; push eax } ] {} '('Boolean')'{} (Constant Logic) Negation

'not' Logic [ asm{ pop eax; not eax; push eax } ] {} (Negation) Conjunction Negation 'and' Negation

[ asm{ pop eax; pop edx; and eax, edx; push eax } ] { } (Conjunction) Disjunction

Conjunction 'a" 'or' Conjunction 'b' {not a and not b} (Disjunction) Boolean

Disjunction 'a' 'imp' Disjunction { not a or b }, где Constant именует простое понятие «логическая константа», a Variable -«пропозиционная переменная». Другие понятия являются сложными: Logic обозначает понятие «логическое значение», Negation - «отрицание», Conjunction - «конъюнкция», Disjunction - «дизъюнкция», Boolean - «высказывание». Constant, Logic, Negation, Conjunction и Disjunction являются частными случаями Boolean. Однако выражение этих частных случаев осуществляется по-разному. Negation получено обобщением Logic и Constant, т.е. Logic и Constant является конкретизацией Negation.

Семантика языка исчисления высказываний определена низкоуровневыми средствами. Для доступа к данным и организации их временного хранения использован аппаратный стек, а для хранения переменных - память произвольного доступа с линейной организацией. В предложении "[А-Za-z][A-Za-zO-9]*" текст компиляции (не показан) описывает создание переменной путем включения ее имени в некоторую таблицу идентификаторов и выделения памяти требуемого объема. Логические константы 'false' и 'true' реализованы как занесение нуля и минус единицы на вершину стека. Переменная определена адресом ячейки памяти. Для получения значения переменной Variable ее адрес извлекается из стека, а содержимое адресуемой ячейки заносится в стек. Для преобразования целого числа в булево значение использовано предложение Integer. Предложение '(' Boolean ')' {} не нуждается в императиве, так как его роль - задание приоритета выражений, заключенных в круглые скобки.

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

Семантика последних двух предложений выражена на уже определенном к тому времени специализированном предметном подязыке, для

34

чего использованы известные тождества: aw b = â &b и а ^ b = â v b, где a - алиас первого понятия предложения, b - второго.

Текст ситуационной части <(not х or у) and z> приведет к вычислению этого выражения при арифметическом кодировании логических значений, a bit < (not х or у) and z > - при битовом. В рассмотренной понятийной модели возможно задание других прагматик, например, для выполнения вычислений в нечеткой логике. Тогда текст fuzzy < (not х or у) and z >, где fuzzy - аспект нечетких вычислений, будет интерпретирован как нечеткое высказывание.

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

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

Семантическое замыкание. Предметный язык служит для описания не только ситуационной части (text в правиле 19), но и для задания семантики предложений и описания самого процесса грамматического разбора и компиляции (text в правилах 7, 17, 18). Тем самым достигается синтаксическая и семантическая замкнутость понятийной модели, позволяющая использовать для обработки перечисленных выше текстов одни и те же средства.

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

Синтаксически-управляемые схемы. Рассмотрим дифференцирование выражений, включающих целочисленные константы, переменную х, функции sin и cos, а также алгебраические операции: изменение знака -, сложение +, вычитание -, умножение *. Свяжем с каждым предложением два перевода, формируемые прагматикой по умолчанию и именованной прагматикой dif. Неименованная прагматика указывает на то, что выражение не дифференцируется, а именованная - что выражение необходимо продифференцировать. Таким образом, формальная производная некоторой строки s - это dif{s}. Процесс перевода опишем так:

0 Expression (String) " [0-9]+ " 'n

{n}

dif {'0'}

{'x'} dif {'1'} '(' Expression')' 'exp' {'(' & exp &')'} dif {•('& dif {exp }&')'} 'sin' 'C Expression 'exp'')' {'sinC & exp &')'}

dif {'cos(' & exp & ')*(' & dif { exp} & ')'} 'cos''(' Expression 'exp'')' {'cos(' & exp &')'}

dif {'-sin(' & exp & ')*(' & dif {exp} &')'} '-' Expression 'exp' {'-' & exp } dif {'-' & dif { exp }} Expression 'ехрГ '*' Expression 'exp2' { expl & w & exp2 }

dif {•(*& expl & '*' & dif { exp2} &'+'& dif { expl } & '*' & exp2 &')"} Expression 'ехрГ "+ | -" 'oper' Expression 'exp2' {expl & oper & exp2 }

dif {'(' & dif { expl } & oper & dif { exp2 } &')'}, где знаком & обозначена конкатенация строк, определенная при описании понятия String (в примере не показано). Текст ситуационной части dif { sin(5*cos(x)) - х*х } будет переведен так:

(cos(5*cos(x))*(5* - sin(x)*(1) + 0*cos(x)*(1))-(x*1 + 1*х). Для тождественных преобразований выражений, получаемых после дифференцирования, возможно определение прагматики с именем equ. В результате ее применения имеем: -5*(cos(5*cos(x))*sin(x))-2*x.

Атрибутные грамматики. Реализуем трансляцию текстового представления числа, заданного в формате с фиксированной запятой, в его двоичный эквивалент. Семантика такой задачи традиционно описывается атрибутной грамматикой. Дня выражения числа Fixed введем два дополнительных понятия: Integer (целая часть) и Fraction (дробная). Понятию Integer припишем атрибут int, равный значению целой части числа, а понятию Fraction - атрибут frac, равный его дробной части. Атрибуты сопоставим сущностям выражаемых понятий. В итоге имеем следующую понятийную модель:

(Number) Integer () "[0-9]" 'digit' { digit}

"[0-9]" 'digit' Integer 'int' {int * 10 + digit} (Float) Fraction 0

"[0-9]" 'digit' { digit}

Fraction 'frac' "[0-9]" 'digit' { digit + frac /10 }

0 Fixed (Integer Fraction)

Integer 'inf '.' Fraction 'frac' {int + frac /10}, где использованы понятия Number и Float, при описании которых определяются необходимые арифметические операции. В отличие от атрибутных грамматик, не имеющих средств для задания порядка вычисления атрибутов, в рассматриваемом примере порядок вычисления атрибутов определен выразительными средствами метаязыка. Так для вычисления синтезируемого атрибута int понятие Integer определено как подлежащее грамматическому разбору слева направо, а для вычисления наследуемого атрибута frac понятие Fraction подвергается разбору справа налево.

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

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

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

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

Контекстное сопоставление. Пусть имеется структура данных, которую назовем текущим контекстом и реализуем в виде стека контекста (рис. 12). Текущий контекст содержит последовательность понятий, которые уже распознаны, а соответствующий этим понятиям текст извлечен из входного потока. Таким образом, в каждый момент времени контекстный анализатор имеет некоторое текущее состояние, определяемое состоянием стека контекста и текущей позицией во входном потоке.

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

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

Стек контекста Стек исполнения

( Модель ]

Понятие

Понятие 2

Предложение

Контекст

Лексема

Разбор

Инперативы

Понятие 1 -^-

_У_

Сущность 2

Сущность 1

—т—

V

Контекстный анализатор

"7Г

Виртуальная машина

Текст

Входной поток

/V

м

Локальная 1

Возврат 1

Локальная память Рис. 12. Архитектура системы программирования Структурное распознавание. После выявления применимого предложения наступает этап разбора оставшейся его части, которая еще не сопоставлена входному потоку. Для этого контекстный анализатор запоминает свое состояние и выполняет просмотр вперед при пустом контексте.

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

Если все элементы области разбора сопоставлены входному потоку, то предложение считается распознанным, контекст предложения в стеке

контекста замещается на его понятие-результат, а полученное состояние входного потока объявляется текущим.

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

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

Конверторы. Метаязык контекстной технологии позволяет определять предложения вида sentence -» notions, не имеющие лексем и состоящие из одного контекста. Такие предложения будем называть конверторами. Конверторы задают денотационную форму выражения понятия, в то время как предложения, состоящие только из лексем, - сигнификативную. Контекстное сопоставление и структурное распознавание следует осуществлять с учетом конверторов, устанавливающих эквивалентность одного или нескольких понятий другому.

Неоднозначные грамматики. При разнесенном грамматическом разборе возможен анализ текста, порождаемого неоднозначными грамматиками. Для учета неоднозначности контекстный анализатор перед началом структурного распознавания сохраняет свое состояние (создает точку отката назад) и начинает разбор предложения. Если в некотором состоянии анализатора не найдено применимых предложений, то восстанавливается сохраненное последним состояние (производится откат назад) и анализируется следующее предложение.

Описанная процедура осуществляется рекурсивным вызовом анализатора всякий раз, когда начинается распознавание нового предложения. Учитывая то, что понятийная модель предназначена для описания предметной области непротиворечивым образом, количество неоднозначностей в тексте не должно быть большим. Если неоднозначностей будет много, то предусмотрим некоторое критическое количество точек отката назад. Тогда при достижении этого количества делается вывод о недостаточной проработке понятийной модели.

Специальные лексемы. В контекстной технологии используются лексемы специального вида, инициирующие грамматический разбор «пустого» понятия empty и любого понятия, ранее объявленного в понятийной модели.

Грамматический разбор empty задается лексемой вида" (две одинарные кавычки) и используется в том случае, когда из входного потока необходимо извлечь текст, не выражающий никакого понятия. Когда необходимо выражать суждения о понятиях, например в предложении «Фраза X выражает понятие Y», разбор и извлечение из входного потока произвольного понятия задается лексемой "" (две двойные кавычки). В этом случае алиас лексемы принимает значение имени распознанного понятия.

Контекстность языка. При использовании «пустого» понятия empty выразительные возможности определяемого языка становятся эквивалентными контекстным языкам, так как появляется возможность использовать укорачивающие правила вида empty -> а , где а - некоторая непустая строка. Контекстная зависимость языка следует из эквивалентности контекстных и укорачивающих грамматик [Л13] и служит одним из оснований для названия разработанной технологии контекстной.

Аксиома. Для разрыва бесконечной рекурсии, связанной с предложениями типа «Сущность есть сущность», в контекстной технологии предусмотрены специальные средства. В качестве примера рассмотрим предложение для записи в область кода числа, например, байта: 0 0 "[0-9А-F][0-9A-F]" {}, где декларируется понятие empty и определяется предложение, выражающее это понятие. Так как рассматриваемое предложение первое, то не существует средств для задания его семантики.

Для разрешения описанной проблемы будем использовать следующее соглашение (аксиому): «пустые» квадратные скобки реализуют запись в императив того значения, которое задается элементом предложения, после которого эти скобки указаны.

С учетом аксиомы переопределим первое предложение так: '#' "[0-9А-F][0-9A-F]" [ ] { }. Этого уже достаточно для задания семантики всех других предложений понятийной модели. Запись в область кода двоичных данных является частной интерпретацией аксиомы.

Для генерации некоторого промежуточного (текстового) представления возможно, например, такое определение: ""'[л']+" []"'{}, которое реализует запись в область кода мнемонического обозначения команды виртуальной машины или строки целевого языка программирования. В рассмотренном примере текст, подлежащий записи, заключается в обратные одинарные кавычки и может содержать произвольные знаки.

Организация системы. Система контекстного программирования может быть представлена как состоящая из следующих частей (рис. 13): входной поток Stream, лексический анализатор Token с препроцессором Text и словарем макроопределений Vocabulary, синтаксический анализатор Parser, семантический анализатор Analyzer, виртуальные машины Engine и понятийная модель Cognition.

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

после компиляции происходит его выполнение. Лексический анализатор Token предназначен для контекстного выделения лексем. При его реализации предусматривается сохранение (восстановление) состояния входного потока, препроцессора Text и словаря макроопределений Vocabulary.

Stream

Token

Text

Vocabulary

\f

Parser

/V

w"

-5> V Analyzer Engine

WEI

Cognition

Рис. 13. Структура системы программирования

Основное назначение синтаксического анализатора Parser - грамматический разбор той части текста, которая описывается грамматикой метаязыка. Другая часть текста, выраженная на определяемом языке, обрабатывается семантическим анализатором Analyzer.

Для выполнения императива может быть использована одна или несколько целевых платформ. Со стороны системы программирования целевая платформа представляется одной или несколькими виртуальными машинами Engine.

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

Императивы. На вход Engine подаются императивы, являющиеся ее единицами вызова. Каждая единица вызова может представляться командами непосредственного исполнения, интерпретируемыми операторами, текстом на входном языке другой системы программирования и т.п. В последних двух случаях виртуальная машина из промежуточного кода императива генерирует его исполняемый код, который в виде идентификатора образа памяти возвращается для сохранения в понятийной модели Cognition и использования при повторном вызове того же императива без повторной генерации исполняемого кода. Допускается существование несколько образов у каждого императива, по одному для каждого типа виртуальных машин.

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

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

Сервисы обратного вызова служат для выполнения действий, которые активируются из области кода специальными командами:

- сервис компиляции — для записи в текущий компилируемый императив данных различных типов;

- информационный сервис — для доступа к данным, сохраненным в понятийной модели;

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

- сервис контекстных условий - для определения предложений динамической семантики;

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

Сервисы прямого вызова предназначены для переопределения стандартных действий, выполняемых системой в интерфейсных точках:

- жизненного цикла сущности (декларация, создание, извлечение, передача, возврат, копирование, уничтожение);

- генерации кода (запись вызова императивов, определение эпилога и пролога таких вызовов, доступ к сущностям-аргументам);

- активации (перед вызовом и после вызова виртуальных машин).

В экспериментальной части работы выполнено исследование прототипа системы контекстного программирования и получено подтверждение основных положений понятийного анализа и контекстной технологии.

В Приложении 1 описана методика синтеза полиномиальных и неполиномиальных форм частичных функций алгебраической декомпозиции.

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

В Приложении 3 приведен пример эффективного решения средствами контекстной технологии задачи управления лифтом.

В Приложении 4 приведен пример реализации исчисления предикатов первого порядка.

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

Полученные результаты

1) Обобщена теория алгебраической декомпозиции дискретных функций на основе объединения алгебраических методов, разделительной декомпозиции и ортогональных разложений в широком спектре алгебраических систем. В частности:

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

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

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

2) Разработан метод синтеза эффективных моделей дискретной обработки данных при двухступенчатой алгебраической декомпозиции дискретных функций, базирующаяся на следующих результатах:

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

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

- получены точные, приближенные и асимптотические оценки сложности синтезируемых формул и показано, что количество операций, необходимое для представления дискретных функций, не хуже известных наилучших оценок;

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

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

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

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

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

4) Создана контекстная технология обработки данных на основе отражения понятийной структуры предметной области в понятиях создаваемого специализированного предметного языка, а получаемые при понятийном анализе декомпозиционные схемы — в его языковых конструкциях. Для реализации системы контекстного программирования:

- доказано, что выразигельные возможности языковых средств контекстной технологии обработки данных эквивалентны формализму контекстных грамматик;

-разработан метод разнесенного грамматического разбора, позволяющий выполнять эффективный анализ текста, порожденного, в том числе и неоднозначными и контекстными грамматиками;

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

Список публикаций по теме диссертации

1. Выхованец В. С. Многократные параллельные логические вычисления //Информационно-управляющие системы и специализированные вычислительные устройства для обработки и передачи данных: Тез. докл. всероссийской конф. Махачкала, 1996. С. 105-106.

2. Выхованец В. С. Вычислительные средства и комплексы // Учебно-методическое пособие. Тирасполь, 1996. Ч. 2. 90 с.

3. Выхованец В. С. Многократные параллельные логические вычисления // Вестник Приднестровского университета. Тирасполь, 1997. №2. С. 64-74.

4. Выхованец В. С. Дискретное преобразование Фурье и его применение при логических вычислениях / Приднестровский гос.-корпорат. унив. им. Т.Г. Шевченко. Тирасполь, 1997. 18 с. Деп. в ВИНИТИ 05.06.97, № 1852-В97.

5. Выхованец В С., Выхованец О. Д. Параллельная парадигма в программировании и ее использование в языках высокого уровня // Вестник Приднестровского университета. Тирасполь, 1997. № 2. С. 74-79.

6. Выхованец В. С. Кратные логические вычисления и их применение в управлении, обработке информации и других областях / Приднест-

44

ровский гос.-корпорат. унив. им. Т.Г. Шевченко. Тирасполь, 1997. 18 с. Деп. в ВИНИТИ 05.06.97, № 1851-В97.

7. Выховаиец В. С., Малюгин В. Д. Спектральные методы в логическом управлении // Тр. 2-й Межд. науч.-техн. конф. «Современные методы цифровой обработки сигналов в системах измерения, контроля, диагностики и управления». Минск, 1998. С. 56-59.

8. Выхованец В. С. Кратные логические вычисления и их применение при моделировании дискретных объектов / Автореферат дис. на соиск. уч. ст. канд. техн. наук. М., 1998. 23 с.

9. Выхованец В. С., Малюгин В. Д. Кратные логические вычисления //Автоматика и телемеханика. 1998. №6. С. 163-171.

10. Выхованец В. С. Булевы мультипликативные формы // Тез. докл. Межд. науч.-практ. конф. «Математические методы в образовании, науке и промышленности». Тирасполь, 1999. С. 52-53.

И. Выхованец В. С. Контекстная технология программирования // Тр. 4-ой Межд. науч.-техн. конф. по телекоммуникациям (Телеком-99). Одесса, 1999. С. 116-119.

12. Vykhovanets V. S. The generalized multiplicative forms // Тез. докл. Межд. конф. по проблемам управления. М., 1999. Т. 3. С. 319-321.

13. Выхованец В. С. Обработка сигналов в дискретных базисах на основе обобщенных полиномиальных форм //Докл. 2-й Межд. конф. «Цифровая обработка сигналов и ее применение». М., 1999. Т. 2. С. 372-377.

14. Vykhovanets V. S. Digital signal processing on basis of generalized polynomial forms // Proc. 2nd Int. Conf. «Digital signal processing and its applications». Moscow, 1999. Vol. 2. PP. 378-379.

15. Выхованец В. С. Обобщенные полиномиальные формы // Радиоэлектроника. Информатика. Управление. 1999. № 2. С. 55-59.

16. Выхованец В. С. Параллельные вычисления во времени // Автоматика и телемеханика. 1999. № 12. С. 155-165.

17. Выхованец В. С. Структурная организация кратных вычислений // Матер, межвузовской науч.-техн. конф. «Управляющие и вычислительные системы. Новые технологии». Вологда, 2000. С. 139-140.

18. Выхованец В. С. Асимптотические оценки при идентификации дискретных объектов // Матер. Межд. конф. «Идентификация систем и задачи управления» М., 2000. Электрон, опт. диск. ISBN 5-201-09605-0.

19. Выхованец В. С. Асимптотические оценки в многозначной логике // Матер, юбилейной конф. профессорско-преподавательского состава, посвященной 70-летию Приднестровского государственного университета им. Т.Г. Шевченко. Тирасполь, 2000. С. 264-270.

20. Выхованец В. С Технология безопасного программирования // Тез. докл. 8-й Межд. конф. «Проблемы управления безопасностью сложных систем». М., 2000. Т. 2. С. 89-91.

21. Выхованец В. С. Кратные вычисления в современных высокопроизводительных системах обработки данных // Вестник Приднестровско-

го университета. 2000. № 1-2 (12). С. 99-110.

22. Иосенкин В. Я., Выхованец В. С. Технология контекстного программирования в экономике и бизнесе // Матер, межвузовской науч.-техн. конф. «Управляющие и вычислительные системы. Новые технологии». Вологда, 2001. С. 180-181.

23. Иосенкин В. Я., Выхованец В. С. Контекстное программирование в моделировании // Матер, межд. науч.-практ. конф. «Моделирование. Теория, методы и средства». Новочеркасск, 2001. Ч. 7. С. 49-51.

24. Выхованец В. С. О вычислимости конечных полей // Матер, межд. науч.-прак. конф. «Математическое моделирование в образовании, науке и производстве». Тирасполь, 2001. С. 475-477.

25. Иосенкин В. Я., Выхованец В. С. Формализация семантики искусственных языков // Матер, межд. науч.-практ. конф. «Математическое моделирование в образовании, науке и производстве». Тирасполь, 2001. С. 477-479.

26. Иосенкин В. Я., Выхованец В. С. Технология контекстного программирования в телекоммуникационных системах // Тр. 2-ой Межд. науч.-практ. конф. «Современные информационные и электронные технологии». Одесса: Друк, 2001. С. 118-119.

27. Vykhovanets V. S. Algebraic Systems for Digital Signal Processing // Proc. 6th Int. Conf. "Pattern Recognition and Information Processing". Mink, 2001. Vol. 2. PP. 93-99.

28. Иосенкин В. Я., Выхованец В. С. Применение технологии контекстного программирования для решения больших прикладных задач // Тр. Межд. конф. «Параллельные вычисления и задачи управления». М., 2001. С. (4)-121-139. Электрон, опт. диск. ISBN 5-201-09559-3.

29. Vykhovanets V. S. Fundamental Theorems for Polynomial Representation of Discrete Functions // Proc. 4th Int. Conf. "Computer-Aided Design of Discrete Devices". Mink, 2001. Vol. 1. PP. 69-76.

30. Выхованец В. С. Спектральные методы в логической обработке данных // Автоматика и телемеханика. 2001. № 10. С. 28-53.

31. Выхованец В. С. Аддитивная алгебра в цифровой обработке сигналов // Докл. 4-й Межд. конф. и выставки «Цифровая обработка сигналов и ее применение». М., 2002. Т. 2. С. 255-258.

32. Vykhovanets V. S. Additive Algebra for Digital Signal Processing // Proc. 4th Int. Conf. and Exhib. on Digital Signal Processing and its Applications. Moscow, 2002. Vol. 2. PP. 258-260.

33. Иосенкин В.Я., Выхованец В. С. Контекстная модель технологического процесса предприятия // Тр. 2-ой Межд. конф. «Идентификация систем и задачи управления». М., 2003. С. 859-871. Электрон, опт. диск. ISBN 5-201-14948-0.

34. Выхованец В. С. Хааро-подобные системы сигналов // Докл. 5-й Межд. конф. и выставки «Цифровая обработка сигналов и ее применение». М., 2003. Т. 2. С. 279-283.

35. Vykhovanets V. S. Haar-Like Systems of Signals // Proc. 5th Int. Conf. and Exhib. on Digital Signal Processing and its Applications. Moscow,

2003. Vol. 2. PP. 283-285.

36. Выхованец В. С. Факторизация полиномиальных форм // Тез. докл. 2-ой Межд. конф. по проблемам управления. М., 2003. Т. 2. С. 108.

37. Выхованец В. С., Иосенкин В. Я. Высокоуровневая форма синтеза систем управления // Тез. докл. 2-ой Межд. конф. по проблемам управления. М., 2003. Т. 2. С. 109.

38. Выхованец В. С., Малюгин В. Д. Мультипликативные формы и их применение при логических вычислениях // Тез. докл. 2-ой Межд. конф. по проблемам управления. М., 2003. Т. 2. С. 110-111.

39. Выхованец В. С., Иосенкин В. Я. Компиляция знаний, представленных на языке ESSE // Тез. докл. 2-ой Межд. конф. по проблемам управления. М., 2003. Т. 2. С. 165.

40. Выхованец В. С., Малюгин В. Д. Аппаратная и программная реализация мультипликативных форм // Теория и практика логического управления: Тез. докл. Межд. конф., посвященной 100-летию со дня рождения чл.-кор. АН СССР М. А. Гаврилова. М., 2003. С. 79-81.

41. Выхованец В. С. Алгебраическая декомпозиция дискретных функций в аддитивной алгебре // Теория и практика логического управления: Тез. докл. Межд. конф., посвященной 100-летию со дня рождения чл.-кор. АН СССР М. А. Гаврилова. М, 2003. С. 81-84.

42. Выхованец В. С., Малюгин В. Д. Мультипликативная алгебра и ее применение в логической обработке данных // Проблемы управления.

2004. № 3. С. 67-77.

43. Выхованец В. С. Полиномиальная факторизация спектральных базисов // Тр. 5-й Межд. конф. «Автоматизация проектирования дискретных устройств». Минск, 2004. Т. 2. С. 71-79.

44. Выхованец В. С. Полиномиальная факторизация спектральных базисов // Автоматика и телемеханика. 2004. № 12. С. 3-14.

45. Vykhovanets V. S. Additive algebra for signal and image processing // Proc. of SPIE. 2005. Vol. 5822. PP. 94-97.

46. Выхованец В. С., Иосенкин В. Я. Понятийный анализ и контекстная технология программирования //Проблемы управления. 2005. №4. С. 2-11.

47. Выхованец В. С. Разнесенный грамматический разбор // Проблемы управления. 2006. № 3. С. 32-43.

48. Выхованец В. С. Алгебраическая декомпозиция дискретных функций // Автоматика и телемеханика. 2006. № 3. С. 20-56.

49. Выхованец В. С. Оптимальный синтез логического управления // Тез. докл. 3-й Межд. конф. по проблемам управления. М., 2006. Т. 2. С. 106.

50. Выхованец В. С. Верификация результатов понятийного анализа //Тез. докл. 3-й Межд. конф. по пробл. управления. М., 2006. Т. 1. С. 105.

В журналах из перечня ВАК опубликовано 8 работ: [9], [16], [30],

47

[42], [44], [46], [47], [48].

Личный вклад автора в совместные публикации

[5] - зависимость эффективности программ от парадигмы программирования, [7, 9] - кратные вычисления в форме совместного описания систем функций на множестве наборов, [22, 23,25,26,28, 33, 37,39] -методология понятийного анализа и контекстная технология, [38,40]-существование алгебраической декомпозиции.

Диссертации, выполненные под научным руководством автора

Д1. Иосенкин В.Я. Технология контекстного программирования и ее применение. М.: Институт проблем управления, 2004.

Цитированная литература

Л1 Gruber T. R. A Translation Approach to Portable Ontologies // Knowledge Acquisition. 1993. Vol. 5. No 2. PP. 199-220.

Л2. Semon W. L Characteristic Numbers and Their Use in the Decomposition of Switching Functions // Proc. ACM. 1952. Vol. 17. PP. 273-280.

ЛЗ. Кузнецов О. П. О программной реализации логических функций и автоматов // Автоматика и телемеханика. 1977. № 7. С. 163-174. № 9. С. 137-149.

Л4. КарповскийМ.Г., Москалев Э.С. Реализация частично определенных функций алгебры логики с помощью разложения в ортогональные ряды // Автоматика и телемеханика. 1970. № 8.

Л5. Лидл Л., Нидеррайтер Г. Конечные поля: В 2-х т. Т. 1. М.: Мир,

1988.

Л6. Ахмед Н., Pao К. Р. Ортогональные преобразования при обработке цифровых сигналов. М.: Связь, 1980.

Л7. Артин Э. Геометрическая алгебра. М.: Наука, 1969.

Ш. Кузьмин В.А. Оценка сложности реализации функций алгебры логики простейшими видами бинарных программ // Методы дискретного анализа в теории кодов и схем. Новосибирск, 1976. Вып. 29. С. 24-36.

Л9. Шамис А. Л. Поведение, восприятие, мышление: проблемы создания искусственного интеллекта. М.: Едиториал УРСС, 2005.

RIO. Поспелов Д. А. Ситуационное управление: теория и практика. М.: Наука, 1986.

Л11. BrodieM. L., Mylopoulos J., Schmidt J. W. On Conceptual Modeling. New York: Springer-Verlag, 1984.

Л12. Макетирование, проектирование и реализация диалоговых информационных систем / Под ред. Е. И. Ломако. М.: Финансы и статистика, 1993.

Л13. Кузнецов О. П., Адельсон-Велъский Г. М. Дискретная математика для инженера. М.: Энергоатомиздат, 1988.

Подписано в печать 02.01.2007 г. Формат 60 х 90/16. Объем 3.0 п.л. Тираж 100 экз. Заказ № 2501071

Оттиражировано в ООО «Полиграф-Сервис» Св. о регистрации № 1057748169159 от 12 сентября 2005 года ИНН 7725548326