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

Размещено на http://www.allbest.ru/

УДК 004.422+510.23+510.25+510.54+512.567

Днепропетровский национальный университет железнодорожного транспорта им. академика В.Лазаряна 49010, Днепропетровск, ул. акад. Лазаряна, 2

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

В.И. Шинкаренко, В.М. Ильман, Г.В. Забула

e-mail: shinkarenko_vi@ua.fm, zabulus12@gmail.com

Аннотация

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

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

Annotation

Developed generalized constructive-synthesizing structures that accumulate scope of various grammars and grammar-like systems intended to produce constructions consist of different elements. Distinctive feature of produced constructions is attribute applying framework for elements, their connections, construction parts and entire constructions. Specialization of generalized constructive-synthesizing structure to produce data structure on the logical level considered. Concretization of generalized constructive-synthesizing structure for logical structure of BMP-file shown.

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

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

На основе анализа известных модификаций классических грамматик: матричных [5], индексных [6, 7], разнообразных графических [6, 8-10], стохастических [9], программных [11, 6, 12], атрибутивных [5], деревьев [9], и других разработана обобщенная конструктивно-продукционная структура. Учтены так же возможности грамматико-подобных систем, таких как R-системы [13], L-системы [10], которые, по сути, являются модификациями грамматик, хотя не представляются грамматическими средствами.

Обобщенная конструктивно-продукционная структура

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

Определение 1. Обобщенной конструктивно-продукционной структурой (ОКПС) назовем:

(1)

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

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

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

Аксиома 1. Носитель структуры состоит из конструктивных элементов с набором атрибутов.

У каждого элемента может быть свой набор атрибутов.

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

Аксиома 2. Обязательными атрибутами элементов носителя являются:

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

- атрибуты, связанные с семантикой.

- атрибут со значением «терминал» или «нетерминал».

Атрибуты, связанные с семантикой и местоположением кроме конкретных значений, могут иметь значения «не определено» и «любое»;

Наличие набора атрибутов у элемента носителя будем обозначать как (идентификатор с атрибутом ), а то, что является атрибутом идентификатора - . Набор атрибутов задается кортежем длины - . Таким образом носитель - .

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

Аксиома 2 устанавливает наличие взаимно-однозначного соответствия между элементом и идентифицирующим атрибутом. Можно считать, что элемент обладает идентифицирующим атрибутом или идентификатор имеет атрибут «элемент» («значение»).

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

Следствие 1. Из аксиомы 2 имеем свойства пустого элемента :

; ; ; ; ; .

Следствие 2.

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

- согласно аксиомам 1, 2 можно выделить подмножества носителя: - терминалов, - нетерминалов;

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

, , ,.

Аксиома 3. , .

Определение 2. Два элемента равны , если и равны по идентификатору , если .

Аксиома 4. В множестве должно быть выделено множество начальных нетерминалов .

Замечание. Как правило [8, 14, 9] множество начальных нетерминалов состоит из одного элемента .

Подаксиоматика сигнатуры.

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

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

Сигнатура состоит из множества операций: - связывания, - подстановки и вывода, - операций над атрибутами, а также отношения подстановки - «». .

Свойства подмножеств сигнатуры. , .

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

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

В классических формальных грамматиках [8, 14, 9] используется одна бинарная операция связывания (конкатенации) над элементами терминального и нетерминального алфавитов. В специализированных грамматиках используются разнообразные операции связывания: по условию [6-9], многоместные [6, 8, 9, 15], графических элементов [6, 9] и др.

Пусть - произвольная -местная операция связывания из множества с набором атрибутов .

Аксиома 7. Для операции справедливо .

Определение 3. Будем называть формой с набором атрибутов :

для ;

, если ;

, если - формы.

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

Аксиома 8. Носитель расширяется сконструированными формами.

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

Определение 4. Если , то назовем подформами формы , что будем обозначать .

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

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

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

Свойства операций связывания:

- ;

- .

Свойство вложенности множеств: и .

Подаксиоматика подстановки и вывода. Подстановки и выводы в грамматиках предназначены для выделения из свободных языков формальных языков. Существует большое разнообразие операций подстановки и вывода в различных грамматических средствах [5, 6, 8-13, 15].

Будем различать отношение подстановки и операцию подстановки.

Определение 8. Отношение постановки - двуместное отношение с атрибутами .

Аксиома 9. Обязательный атрибут отношения подстановки - атрибут доступности .

Замечание. В грамматиках отношение подстановки принято обозначать в инфиксной форме и в классических грамматиках всегда =1. Для наглядности будем придерживаться аналогичных обозначений .

Определение 9. Пусть - последовательность отношений подстановки или , и - последовательность операций над атрибутами. Назовем правилом продукции . Здесь - произвольная операция над атрибутами ().

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

Определение 10. Пусть задана форма и доступное отношение подстановки такое, что , тогда результатом трехместной операции подстановки будет форма , где .

Определение 11. Двухместная операция частичного вывода () заключается в:

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

- выполнении на его основе операций подстановки;

- выполнении операций над атрибутами в соответствующей последовательности.

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

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

Замечание 3. При пустом отношении подстановки могут выполняться только операции над атрибутами.

Замечание 4. Доступность правила определяется атрибутикой правила и аксиоматикой структуры. Доступность правила может изменяться операциями из .

Основное назначение конструктивно-продукционных структур - формирование конструкций с допустимым структурой составом и связями.

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

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

Замечание 2. Операция полного вывода не однозначная.

Определение 13. Множество конструкций, которые могут быть сформированы в результате вывода в соответствии с аксиоматикой этой структуры, с атрибутами элементов и самой конструкции определенными в результате вывода назовем множеством выводимых (правильных) конструкций структуры , т.е. и .

Замечание. является многозначная функцией одного аргумента. Каждая конструкция связана с «историей» своего конструирования.

Последовательность форм вывода (список вывода) будем представлять , где , .

Определение 14. Любая из форм вывода является сентенциальной формой .

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

ФОРМАЛЬНАЯ СТРУКТУРА ДЛЯ ПРОЕКТИРОВАНИЯ ДАННЫХ НА ЛОГИЧЕСКОМ УРОВНЕ

Рассмотрим специализацию ОКПС для формального представления СД на логическом уровне.

Формальной структурой для проектирования СД на логическом уровне, назовем специализированную ОКПС :

,(2)

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

, , .

,

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

Частичная аксиоматика включает аксиомы 10-11 и инструктивные дополнения 1-4.

Аксиома 10. Операция связывания терминалов обладает свойством симметричности: .

Аксиома 11. Операция связывания терминалов обладает свойством антисимметричности: .

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

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

Дополнение 3. Операции подстановки имеют атрибут доступности - доступность операции подстановки i-го правила продукции, такая что: .

Дополнение 4. Нетерминалы правил продукции имеют атрибут - количество элементов в форме.

Для интерпретации построим модель исполнителя в виде базовой алгоритмической структуры (БАС):

,

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

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

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

- алгоритм связывания элементов , , согласно аксиоме 10;

- алгоритм связывания элементов , , согласно аксиоме 11;

- алгоритм выполнения операции подстановки , спецификация которого задана определением 10 аксиоматики ОКПС;

- алгоритмы выполнения операций частичного и полного вывода , , спецификация которых заданы определением 11 и 12 (соответственно) аксиоматики ОКПС;

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

Аксиоматика алгоритмической структуры представлена в [19].

Интерпретация формальной структуры проектирования СД на логическом уровне:

,

где - операция интерпретации; ;

,.(3)

Рассмотрим одну из конкретизаций на примере логической структуры BMP файла [1,2]

, (4)

где - операция конкретизации; ?; ; ; .

Частичная аксиоматика :

; ;

; ;

; ;

; ;

; ;

; ;

; ;

; ;

; ;

; .

Будем считать, что при интерпретации частичная аксиоматика включает конструктивные дополнения 5…7.

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

Дополнение 6. При интерпретации (3) операций имеется .

Дополнение 7. Значения атрибутов семантики приведено в табл. 1.

Таблица 1

Атрибут	Значение	Атрибут	Значение
	BMP файл без файлового заголовка		цвет пикселя
	информационный заголовок BMP		индексированный цвет
	цвет в модели RGB		данные изображения
	количество битов на пиксель		индекс цвета пикселей
	ширина изображения		цвета RGB
	высота изображения		цвет RGB
	цвет пикселей		индекс цвета пикселя

На рис. 1 приведена визуализация логической структуры BMP-файла соответствующей структуре модели (4). Данное представление выполнено средствами нотации Джексона [20] с модифицированными связями нетерминал-значение и идентификацией правил подстановки.

Рис.1. Логическая структура данных.

Выводы

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

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

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

Литература

Шинкаренко В. И. Повышение временной эффективности структур данных в оперативной памяти на основе адаптации / В. И. Шинкаренко, Г. В. Забула // Проблеми програмування. - 2012. - № 2-3. - С. 211-218.

Шинкаренко В.И. Применение генетического алгоритма в задачах адаптации структур данных. / В. И. Шинкаренко, Г. В. Забула // Искусственный интеллект. - 2012. - 3. - С. 323-331.

Цейтлин Г.Е. Алгоритмические алгебры структур данных и многоуровневое проектирование программ // Программирование. - 1986. - № 3. - С. 8 - 16.

Акуловский В.Г. Алгебра для описания данных в композиционных схемах алгоритмов // Проблеми програмування. - 2012. - № 2-3. - С. 234-240.

Андон Ф.И., Дорошенко А.Е., Цейтлин Г.Е., Яценко Е.А. Алгеброалгоритмические модели и методы параллельного программирования. - К.: Академпериодика, 2007. - 634 с.

Фу К. Структурные методы распознавания образов. - М.: Мир, - 1977. - 318 с.

Ахо А. Индексные грамматики - расширение контекстно-свободных грамматик. // Сб. «Языки и автоматы». - М.: Мир, 1975. - С. 130-165.

Павлюк О.В., Савчинський Б.Д. Ефективний синтаксичний аналіз та розпізнання структурованих зображень // Управляющие системы и машины. - 2005. - № 5. - С. 13-24.

Ту Дж., Гонсалес Р. Принципы распознавания образов. - М.: Мир, 1978. - 411 с.

Prusinkiewicz P., Lindenmayer A. The algorithmic beauty of plants. New York etc. : Springer, Cop. 1990. - XII. - 228p.

Братчиков И.Л. Синтаксис языков программирования. - М.: Наука, 1975. - 232 с.

Розенкранц Д. Программные грамматики и классы формальных языков. // Сборник переводов по вопросам информационной теории и практики, ВИНИТИ, 1970. - № 16. - С. 117-146.

Лисовик Л.П., Карнаух Т.А. Об одном методе задания фрактальных множеств // Кибернетика и системный анализ. - 2009. - № 3. - С. 42-50.

Хантер Р. Основные концепции компиляторов. - М. ; СПб. ; К. : Издательский дом "Вильямс", 2002. - 252 с.

Шлезингер М.И., Главач В. Десять лекций по статистическому и структурному распознаванию. - Киев: Наук. думка, 2004. - 546 с.

Шинкаренко В. И. Экспериментальные исследования алгоритмов в программно-аппаратных средах : монография / В. И. Шинкаренко. - Д.: Изд-во Днепропетр. нац. ун-та ж.-д. трансп. им. акад. В. Лазаряна, 2009. - 279 с.

Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1: Синтаксический анализ. - М.: Мир, 1978. - 612 с.

Пратт Т., Зелковиц М. Языки программирования, разработка и реализация. - СПб.: Питер, 2002. - 688 с.

Шинкаренко В. И., В. М. Ильман, В. В. Скалозуб Структурные модели алгоритмов в задачах прикладного программирования Часть I. Формальные алгоритмические структуры // Кибернетика и системный анализ. - 2009. - № 3. - С. 3-14.

Зиглер К. Методы проектирования программных систем: Пер. с англ. - М.: Мир, 1985. - 328 с., ил.

Шинкаренко В.І., Ільман В.М., Забула Г.В.

Конструкційно-продукційна модель структур даних на логічному рівні.

Контакт: Шинкаренко Виктор Иванович

shinkarenko_vi@ua.fm

056-373-15-35

063-489-49-15

Размещено на Allbest.ru

...