Logical view for construction-synthesis model of data structures

Logical view for construction-synthesis model of data structures

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...

Повний опис

Збережено в:
Бібліографічні деталі
Дата:2025
Автори: Shynkarenko, V.I., Ilman, V.M., Zabulula, G.V.
Формат: Стаття
Мова:Russian
Опубліковано: PROBLEMS IN PROGRAMMING 2025
Теми:
UDC 004.422+510.23+510.25+510.54+512.567
Онлайн доступ:https://pp.isofts.kiev.ua/index.php/ojs1/article/view/688
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Problems in programming
Завантажити файл: Pdf

Репозитарії

Problems in programming
id pp_isofts_kiev_ua-article-688
record_format ojs
resource_txt_mv ppisoftskievua/a2/3d072ebaae2b240cb7cd6e18ca7a68a2.pdf
spelling pp_isofts_kiev_ua-article-6882025-04-09T22:22:32Z Logical view for construction-synthesis model of data structures Конструкционно-продукционная модель структур данных на логическом уровне Shynkarenko, V.I. Ilman, V.M. Zabulula, G.V. UDC 004.422+510.23+510.25+510.54+512.567 УДК 004.422+510.23+510.25+510.54+512.567 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.Prombles in programming 2014; 2-3: 10-16 Разработана обобщенная конструктивно-продукционная структура, которая аккумулирует возможности различных грамматик и грамматико-подобных систем по формированию конструкций с элементов различной природы. Отличительная особенность формируемых конструкций заключается в применении аппарата атрибутов к элементам, их связям, частям конструкций, конструкций в целом. Рассматривается специализация обобщенной конструкционно-продукционной структуры по формированию структур данных на логическом уровне. Приведена конкретизация конструкционно-продукционной структуры на примере логической структуры BMP-файлов.Prombles in programming 2014; 2-3: 10-16 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-04-09 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/688 PROBLEMS IN PROGRAMMING; No 2-3 (2014); 10-16 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 2-3 (2014); 10-16 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 2-3 (2014); 10-16 1727-4907 ru https://pp.isofts.kiev.ua/index.php/ojs1/article/view/688/740 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution Problems in programming
baseUrl_str https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date 2025-04-09T22:22:32Z
collection OJS
language Russian
topic
UDC 004.422+510.23+510.25+510.54+512.567
spellingShingle
UDC 004.422+510.23+510.25+510.54+512.567
Shynkarenko, V.I.
Ilman, V.M.
Zabulula, G.V.
Logical view for construction-synthesis model of data structures
topic_facet
UDC 004.422+510.23+510.25+510.54+512.567

УДК 004.422+510.23+510.25+510.54+512.567
format Article
author Shynkarenko, V.I.
Ilman, V.M.
Zabulula, G.V.
author_facet Shynkarenko, V.I.
Ilman, V.M.
Zabulula, G.V.
author_sort Shynkarenko, V.I.
title Logical view for construction-synthesis model of data structures
title_short Logical view for construction-synthesis model of data structures
title_full Logical view for construction-synthesis model of data structures
title_fullStr Logical view for construction-synthesis model of data structures
title_full_unstemmed Logical view for construction-synthesis model of data structures
title_sort logical view for construction-synthesis model of data structures
title_alt Конструкционно-продукционная модель структур данных на логическом уровне
description 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.Prombles in programming 2014; 2-3: 10-16
publisher PROBLEMS IN PROGRAMMING
publishDate 2025
url https://pp.isofts.kiev.ua/index.php/ojs1/article/view/688
work_keys_str_mv AT shynkarenkovi logicalviewforconstructionsynthesismodelofdatastructures
AT ilmanvm logicalviewforconstructionsynthesismodelofdatastructures
AT zabululagv logicalviewforconstructionsynthesismodelofdatastructures
AT shynkarenkovi konstrukcionnoprodukcionnaâmodelʹstrukturdannyhnalogičeskomurovne
AT ilmanvm konstrukcionnoprodukcionnaâmodelʹstrukturdannyhnalogičeskomurovne
AT zabululagv konstrukcionnoprodukcionnaâmodelʹstrukturdannyhnalogičeskomurovne
first_indexed 2025-07-17T10:08:28Z
last_indexed 2025-07-17T10:08:28Z
_version_ 1850411932394192896
fulltext Теоретичні та методологічні основи програмування © В.И. Шинкаренко, В.М. Ильман, Г.В. Забула, 2014 10 ISSN 1727-4907. Проблеми програмування. 2014. № 2–3. Спеціальний випуск УДК 004.422+510.23+510.25+510.54+512.567 КОНСТРУКЦИОННО-ПРОДУКЦИОННАЯ МОДЕЛЬ СТРУКТУР ДАННЫХ НА ЛОГИЧЕСКОМ УРОВНЕ В.И. Шинкаренко, В.М. Ильман, Г.В. Забула Днепропетровский национальный университет железнодорожного транспорта им. академика В. Лазаряна 49010, Днепропетровск, ул. акад. Лазаряна, 2 E-mail: shinkarenko_vi@ua.fm, zabulus12@gmail.com Разработана обобщенная конструктивно-продукционная структура, которая аккумулирует возможности различных грамматик и грамматико-подобных систем по формированию конструкций с элементов различной природы. Отличительная особенность формируемых конструкций заключается в применении аппарата атрибутов к элементам, их связям, частям конструкций, конструкций в целом. Рассматривается специализация обобщенной конструкционно-продукционной структуры по формированию структур данных на логическом уровне. Приведена конкретизация конструкционно-продукционной структуры на примере логической структуры BMP-файлов. 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. Обобщенной конструктивно-продукционной структурой (ОКПС) назовем: ,,,  MC (1) где M – носитель структуры,  – сигнатура, состоящая из множеств возможных имен многоместных опера- ций и отношений: связывания, подстановки, вывода и вспомогательных операций;  – конструктивная аксио- матика, которая включает множество определений, аксиом, правил, свойств, инструкций и пр. Множества M и  определяется аксиоматикой. Выделим в аксиоматике  семантически завершенные части – подаксиоматики: носителя грамматиче- ской структуры, сигнатуры, операций связывания, подстановки и вывода. Рассмотрим отдельно каждую подак- сиоматику. Подаксиоматика носителя грамматической структуры. Чтобы не усложнять структуру формализаци- ей относительно ее атрибутики будем считать, что имеет место следующие аксиомы. Аксиома 1. Носитель M структуры C состоит из конструктивных элементов с набором атрибутов. У каждого элемента может быть свой набор атрибутов. Атрибуты могут быть связаны как со статическими свойствами элементов (такими как цвет, объем и т. п.), так и динамическими (способность перемещаться определенным образом и т. п.), а также составными свойствами (например, в терминах объектно-ориентированного программирования объект представляется набором свойств и методов, при этом свойства в свою очередь могут быть объектами). mailto:shinkarenko_vi@ua.fm mailto:zabulus12@gmail.com Теоретичні та методологічні основи програмування 11 Аксиома 2. Обязательными атрибутами элементов носителя являются:  идентифицирующий атрибут – имя, указатель местоположения, набор этих или других свойств;  атрибуты, связанные с семантикой.  атрибут со значением «терминал» или «нетерминал». Атрибуты, связанные с семантикой и местоположением кроме конкретных значений, могут иметь значе- ния «не определено» и «любое»; Наличие набора атрибутов iw у элемента носителя im будем обозначать как iw m i (идентификатор im с атрибутом iw ), а то, что jiw является атрибутом идентификатора im – ii mw j  . Набор атрибутов задается кор- тежем длины k –  kiiii wwww ,,, 21  WWWW k  21 . Таким образом носитель – }{ iw mM i  . Здесь и далее идентифицирующие атрибуты (по местоположению) будем обозначать индексом справа, другие атрибуты – индексом слева. Аксиома 2 устанавливает наличие взаимно-однозначного соответствия между элементом и идентифици- рующим атрибутом. Можно считать, что элемент обладает идентифицирующим атрибутом или идентификатор имеет атрибут «элемент» («значение»). В формальных теориях элементы носителя принято обозначать их идентифицирующим атрибутом, т.е. под обозначением m понимается идентификатор элемента носителя, а не сам элемент (значение). В дальней- шем изложении будем обозначать: m – идентификатор элемента, m – элемент с идентификатором m . Следствие 1. Из аксиомы 2 имеем свойства пустого элемента  : jj iii www  ),,,,,,(   ;   ),,( iw ; mm  ;   ; M ; }{}{ iwi mm i  . Следствие 2.  }{ iw m i – мультимножество по идентификаторам с различными атрибутами;  согласно аксиомам 1, 2 можно выделить подмножества носителя: I iiw tT i 1}{  – терминалов, J jjw j N 1}{   – нетерминалов;  значение атрибута терминал/нетерминал будем определять по принадлежности к множеству T или N ;  MNT  , NT  , T , N . Аксиома 3. iW , ki ,,1 . Определение 2. Два элемента Mmm jwiw ji , равны jwiw mm ji  , если jiji wwmm  & и равны по идентификатору jwiw mm ji  , если ji mm  . Аксиома 4. В множестве N должно быть выделено множество начальных нетерминалов NU  . Замечание. Как правило [8, 14, 9] множество начальных нетерминалов состоит из одного элемента }{U . Подаксиоматика сигнатуры. Аксиома 5. Сигнатура состоит из имен операций, обладающих набором атрибутов. Произвольная операция сигнатуры представляется как v , где  kvvvv ,,, 21  VVVV k  21 ( – набор атрибутов из множества V ). Сигнатура  состоит из множества операций:  – связывания,  – подстановки и вывода,  – опера- ций над атрибутами, а также отношения подстановки – « ». }{,,,  . Свойства подмножеств сигнатуры. ;;    ,  . Аксиома 6. Обязательным атрибутом операций сигнатуры является интерпретация – правила и порядок ее выполнения. Подаксиоматика операций связывания. Операции связывания элементов ОКПС связывают отдельные элементы в конструкции или их части. В классических формальных грамматиках [8, 9, 14] используется одна бинарная операция связывания (конкатенации) над элементами терминального и нетерминального алфавитов. В специализированных грамма- тиках используются разнообразные операции связывания: по условию [6–9], многоместные [6, 8, 9, 15], графи- ческих элементов [6, 9] и др. Пусть  – произвольная k -местная операция связывания из множества  с набором атрибутов  . Аксиома 7. Для операции  справедливо  . Определение 3. Будем называть формой l lw с набором атрибутов lw : ),,,( 21 210 kwwww mmml kl  для Mmiwi  ; jww ml jl  , если ),,,,,,( 0   jw ml j  ; Теоретичні та методологічні основи програмування 12 ),,,( 21 210 kwwww llll kl  , если kwww lll k ,,, 21 21  – формы. Из определения 3 следует, что операция связывания применяется как к элементам носителя так и к фор- мам, сконструированных с ее помощью на основе элементов носителя. Аксиома 8. Носитель M расширяется сконструированными формами. В классических алгебраических операциях результат операции не содержит никаких информативных признаков об операндах. Определение 3 выделяет класс операций, результат которых содержит информацию об операндах. Определение 4. Если ),,,( 21 210 kwwww llll kl  , то kwww lll k ,,, 21 21  назовем подформами формы l lw , что будем обозначать ll li wiw  . Определение 5. Формы, в которых отсутствуют нетерминальные элементы, будем называть конструкци- ями и обозначать lw, , где  – определяющий форму атрибут. Определение 6. Назовем множество всех форм, конструируемых на носителе этой структуры операция- ми связывания, свободным множеством форм **)( FNT  . Определение 7. Свободным множеством конструкций формальной структуры назовем все допустимые конструкции, сформированные на носителе структуры операциями связывания *T . Свойства операций связывания:    ),,,(: 0 lWw lw ;  ,,,(,),,,,,,(:, 2121 210210  mmlmmmmmlll wwjwkwhwqwwwiwjwiw jkqiji   jwiwkwqwhw llmmm jikqh ),,,  . Свойство вложенности множеств: ** FTT C  и *FN  . Подаксиоматика подстановки и вывода. Подстановки и выводы в грамматиках предназначены для выделения из свободных языков формальных языков. Существует большое разнообразие операций подстановки и вывода в различных грамматических средствах [5, 6, 8-13, 15]. Будем различать отношение подстановки и операцию подстановки. Определение 8. Отношение постановки – двуместное отношение с атрибутами ),( jwiw ll jip . Аксиома 9. Обязательный атрибут отношения подстановки – атрибут доступности d . Замечание. В грамматиках отношение подстановки принято обозначать в инфиксной форме ji ll  и в классических грамматиках всегда d =1. Для наглядности будем придерживаться аналогичных обозначений jwiw ll jpi  . Определение 9. Пусть 26431 21654321 ,,,   mwmwwwww lllllls mmm   – последователь- ность отношений подстановки или s , и ,),,,,,(),,,,( 2,2,22,121,1,21,11 2 2 21 1 1  k k k k wwwwwwg   ),,,( ,,2,1 nknn k n n n n www  – последовательность операций над атрибутами. Назовем правилом продукции gsp ,: . Здесь  – произвольная операция над атрибутами (  ). Множество правил продукций будем обозначать },:{ iii gs . Определение 10. Пусть задана форма ),,,,,( 21 210 kwhwwww lllll khl  и доступное отношение под- становки ),( qwhw ll qhp такое, что ll lh whw  , тогда результатом трехместной операции подстановки ),,(* * llll lqhpl wqwhww  будет форма ),,,,,( 21 * 210 * kwqwwww lllll kql  , где  . Определение 11. Двухместная операция частичного вывода ),(|* * ll lpl ww  ( | ) заключается в:  выборе одного из доступных правил подстановки rrr gsp ,: с отношениями подстановки rs ;  выполнении на его основе операций подстановки;  выполнении операций над атрибутами rg в соответствующей последовательности. Замечание 1. Выполнение операций над атрибутами rg – часть операции частичного вывода. Один из атрибутов операций над атрибутами определяет последовательность выполнения операций над атрибутами: в начале операции частичного вывода или после его окончания, перед поиском подформы hw l h в l lw , при срав- нении подформ (для сравнения атрибутов), перед удалением hw l h из формы l lw , после удаления, перед встав- кой qw l q на место hw l h в форме l lw без hw l h , после вставки (после операции подстановки). Теоретичні та методологічні основи програмування 13 Замечание 2. Выбор правила из числа доступных может быть произвольным, а может задаваться неко- торыми условиями, алгоритмами или атрибутами. Замечание 3. При пустом отношении подстановки могут выполняться только операции над атрибутами. Замечание 4. Доступность правила определяется атрибутикой правила и аксиоматикой структуры. До- ступность правила может изменяться операциями из rg . Основное назначение конструктивно-продукционных структур – формирование конструкций с допусти- мым структурой составом и связями. Определение 12. Операция полного вывода или просто вывода ( | | ) заключается в пошаговом пре- образовании форм, начиная с начального нетерминала и заканчивая конструкцией, удовлетворяющей условию окончания вывода, что подразумевает циклическое выполнение операций частичного вывода. Операция двух- местная ),(| |* , * ll ll ww   , где Ul lw  . Замечание 1. В результате вывода не всегда может быть сформирована конструкция удовлетворяющая условию окончания вывода. Если на i-1 шаге сформирована форма ),,,,,( 211 210 kwhwwwiw llllf khf   и для 1 iwiw fl fi  нет ни одного доступного правила )( jwiw lls jjpi   и операция частичного вывода невы- полнима, такой вывод будем считать тупиковым. Замечание 2. Операция полного вывода не однозначная. Определение 13. Множество конструкций, которые могут быть сформированы в результате вывода в со- ответствии с аксиоматикой этой структуры, с атрибутами элементов и самой конструкции определенными в результате вывода назовем множеством выводимых (правильных) конструкций )(C структуры C , т.е. UlllCl llll wwww   &),(| |:)( * , * , ** и &),(| |:)( * , * , ** llCl lll www   Ul lw  . Замечание. )(C является многозначная функцией одного аргумента. Каждая конструкция связана с «историей» своего конструирования. Последовательность форм вывода (список вывода) будем представлять kwwwwww fff kfkvvfvf  12211 21  , где Uf fw 1 1 , )(Cfkw kf  . Определение 14. Любая из форм вывода является сентенциальной формой Ff  . Множество сентенциальных F форм включает все начальные, конечные и промежуточные формы опе- рации вывода. Формальная структура для проектирования данных на логическом уровне Рассмотрим специализацию ОКПС для формального представления СД на логическом уровне. Формальной структурой для проектирования СД на логическом уровне, назовем специализированную ОКПС LDC :  LDLDLDLDS MCMC ,,,,  , (2) где S – операция специализации формальных структур (операция выполняется внешним исполнителем),  }{,,, LDLDLDLD ,  "","" LD , 21  LD . }}{}{)({1 isi,m,s,txLD α,Nx,TNTΜ iiiii   , где }{ ix – множество простейших элементов данных, со значением ix , типом it , семантикой is , и необязательным порядковым номером im ; }{ i – множество со- ставных элементов, с семантикой is . Частичная аксиоматика 2 включает аксиомы 10-11 и инструктивные дополнения 1-4. Аксиома 10. Операция связывания терминалов "" обладает свойством симметричности:  jsis xx ii &ji ss  )( ijji xxxx  . Аксиома 11. Операция связывания терминалов "" обладает свойством антисимметричности:  jsis xx ii ji ss  )&( ijji xxxx  . Дополнение 1. Операции связывания имеют атрибут }{ 21 ni ,...,ρ,ρρΡρ  , идентифицирующий опера- цию связывания, n – общее количество групп операций связывания в конкретизированной грамматике. Дополнение 2. Порядок применения операции над атрибутами в процессе выполнения операции частич- ного вывода задается атрибутом }{ 10,tt;t j  , где 0t – операция над атрибутом выполняется перед операци- ей подстановки, 1t – после операции подстановки. Дополнение 3. Операции подстановки имеют атрибут доступности id – доступность операции подста- новки i-го правила продукции, такая что:  falsetrueid ,  . Теоретичні та методологічні основи програмування 14 Дополнение 4. Нетерминалы правил продукции имеют атрибут i – количество элементов в форме. Для интерпретации LDC построим модель исполнителя в виде базовой алгоритмической структуры (БАС): LDALDALDALDALDA VMС ,,,,, ,,,  , где LDAM , – неоднородный носитель, LDA,V – множество образующих алгоритмов, базовых (элементарных) для некоторого исполнителя, LDA,Σ – сигнатура и LDA,Λ – аксиоматика. Носитель WCNTM LDALDA,  )( , , где )( LDA,СΩ все сформированные алгоритмами алгоритмической структуры конструкции; W – множество допустимых значений атрибутов. Множество базовых алгоритмов },{ 0 4 0 3 0 2 0 1 21 ji ji ji ji i i ji ji ll ,ll ll ,ll :A ,A,ZZ AA ,AALDA, |A|A,|A,|AV   и сконструированных ,|{ ,,5 j iqh f fffA W f f f f VAA j i j i }|,| ,7,6  )( ,LDAС :  алгоритм выполнения операции композиции алгоритмов ji ji AA AAA  , 0 1 | ( Y XA | – алгоритм над данными из входного множества X со значениями из множества Y , 0A – образующий алгоритм), )(, ,MSAji СAA  , ji AA  – последовательное выполнение алгоритма jA после алгоритма iA ;  алгоритм условного выполнения i i A AZZA : ,, 0 2 21 | , который заключается в выполнении алгоритма iA при условии 21 ZZ  ;  алгоритм связывания элементов ji ji ll ll A  , 0 3 | , *, Fll ji  , согласно аксиоме 10;  алгоритм связывания элементов ji ji ll ll A  , 0 4 | , *, Fll ji  , согласно аксиоме 11;  алгоритм выполнения операции подстановки j iqh f fllA ,,5 | , SllFff qhji  ,,, спецификация которого за- дана определением 10 аксиоматики ОКПС;  алгоритмы выполнения операций частичного и полного вывода j i f fA ,6 | , j i f fA ,7 | Fff ji , , специфика- ция которых заданы определением 11 и 12 (соответственно) аксиоматики ОКПС;  множество алгоритмов, реализующих операции над атрибутами WV . Аксиоматика алгоритмической структуры LDA, представлена в [19]. Интерпретация формальной структуры проектирования СД на логическом уровне:  LDILDILDILDIILDLDLDLD MCMC ,,, ,,,,  , где I – операция интерпретации; 43,  LDLDI ; );| ||();||();|();|{( ,6,5,,4, 0 33    j i j i j iqh ji ji f f f f f fll ll ll AAAA )}(|,)""|(: ,MSA Y Xii Y Xii CAA i i i i   )}(|,)""|(: ,MSA Y Xii Y Xii CAA i i i i   , 4 . (3) Рассмотрим одну из конкретизаций LDI C на примере логической структуры BMP файла [1, 2]  BMPBMPBMPBMP LLLLKLDILDILDILDI MCMC ,,,, ,,,  , (4) где K операция конкретизации; LDIL MM BMP , ℕ; BMPLDILBMP  , ; }"",":","","","","{" BMP ; 5,  LDILBMP . Частичная аксиоматика 3 : {5     sss p s  001 ; trueg ptt  :: 010  ; cbas cccbbbaaap mstρmstρmstνs  1112   ; true:ν:g ptt  120 ;   sλνS p s 12,13  ;          256 256 0 2130 afalse,z atrue,z :ν;:λ:g ptt ;   sλρsλνs p s 3223,24  ;          256 256 00 33240 afalse,z atrue,z :ν;:λ;:λ:g ptt ;   sλρmstνsλ es eeep 13415  ;  25155 ,, ,ggg  ; Теоретичні та методологічні основи програмування 15 114150 λ:c;mzbzλ:g ep,tt   ; 111251  λ:λg ,tt ;   sλρmstνsλ fs fffp 24526  ;  26166 ,, ,ggg  ; 225160 λ:mc;zbzλ:g fp,tt   ; 122261  λ:λg ,tt ;   sλρνsλ ps pmpsptp 35637  ;  27177 ,, ,ggg  ; 33617 256 0 λ:m;λ:g pp,tt   ; }133271  λ:λg ,tt . Будем считать, что при интерпретации BMPLC частичная аксиоматика 4 включает конструктивные до- полнения 5…7. Дополнение 5. Будем считать, что алгоритмическая структура LDAС , содержит следующие алгоритмы: b aA |8 – алгоритм реализующий присваивания ab : ; c baA ,9 | – сложение bac : ; c baA ,10 | – сравнение bac : ; c baA ,11 | – сравнение bac : . Дополнение 6. При интерпретации (3) операций i имеется );:|( 8 b aA );|( ,9 c baA );|( ,10 c baA )|( ,11 c baA . Дополнение 7. Значения атрибутов семантики приведено в таблице. Таблица Атрибут Значение Атрибут Значение s BMP файл без файлового заго- ловка es цвет пикселя s информационный заголовок BMP 2s индексированный цвет 1s цвет в модели RGB s данные изображения as количество битов на пиксель s индекс цвета пикселей bs ширина изображения s цвета RGB cs высота изображения ps цвет RGB s цвет пикселей fs индекс цвета пикселя На рисунке показана визуализация логической структуры BMP-файла соответствующей структуре моде- ли (4). Данное представление выполнено средствами нотации Джексона [20] с модифицированными связями нетерминал-значение и идентификацией правил подстановки. Рисунок. Логическая структура данных Теоретичні та методологічні основи програмування 16 Выводы Применение средств КПС позволяет формализовать процессы и результат проектирования СД на логиче- ском уровне. Реализация конкретизированной КПС представляет модели логически связанных конкретных элементов данных. Однако логический уровень не предполагает физической реализации данных и связей, т. е. представление данных на физическом носителе и порядка их размещения. В последующих работах предполагается разработка КПС СД на физическом носителе, связывание между собой КПС разных уровней. Как и любая формализация, разрабатываемые КПС, позволяют автоматизировать процесс разработки и совершенствования структур данных, повышать их временную эффективность. 1. Шинкаренко В.И., Забула Г.В. Повышение временной эффективности структур данных в оперативной памяти на основе адаптации // Проблеми програмування. – 2012. – № 2–3. – С. 211–218. 2. Шинкаренко В.И., Забула Г.В. Применение генетического алгоритма в задачах адаптации структур данных // Искусственный интел- лект. – 2012. – 3. – С. 323–331. 3. Цейтлин Г.Е. Алгоритмические алгебры структур данных и многоуровневое проектирование программ // Программирование. – 1986. – № 3. – С. 8–16. 4. Акуловский В.Г. Алгебра для описания данных в композиционных схемах алгоритмов // Проблеми програмування. – 2012. – № 2–3. – С. 234-240. 5. Андон Ф.И., Дорошенко А.Е., Цейтлин Г.Е., Яценко Е.А. Алгеброалгоритмические модели и методы параллельного программирова- ния. – Киев: Академпериодика, 2007. – 634 с. 6. Фу К. Структурные методы распознавания образов. – М.: Мир, 1977. – 318 с. 7. Ахо А. Индексные грамматики – расширение контекстно-свободных грамматик // Сб. «Языки и автоматы». – М.: Мир, 1975. – С. 130–165. 8. Павлюк О.В., Савчинський Б.Д. Ефективний синтаксичний аналіз та розпізнання структурованих зображень // Управляющие системы и машины. – 2005. – № 5. – С. 13–24. 9. Ту Дж., Гонсалес Р. Принципы распознавания образов. – М.: Мир, 1978. – 411 с. 10. Prusinkiewicz P., Lindenmayer A. The algorithmic beauty of plants. New York etc.: Springer, Cop. 1990. – XII. – 228 p. 11. Братчиков И.Л. Синтаксис языков программирования. – М.: Наука, 1975. – 232 с. 12. Розенкранц Д. Программные грамматики и классы формальных языков. // Сборник переводов по вопросам информационной теории и практики, ВИНИТИ, 1970. – № 16. – С. 117–146. 13. Лисовик Л.П., Карнаух Т.А. Об одном методе задания фрактальных множеств // Кибернетика и системный анализ. – 2009. – № 3. – С. 42–50. 14. Хантер Р. Основные концепции компиляторов. – М.; СПб. ; К.: Издательский дом "Вильямс", 2002. – 252 с. 15. Шлезингер М.И., Главач В. Десять лекций по статистическому и структурному распознаванию. – Киев: Наук. думка, 2004. – 546 с. 16. Шинкаренко В.И. Экспериментальные исследования алгоритмов в программно-аппаратных средах : монография. – Д.: Изд-во Днепро- петр. нац. ун-та ж.-д. трансп. им. акад. В. Лазаряна, 2009. – 279 с. 17. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т. 1: Синтаксический анализ. – М.: Мир, 1978. – 612 с. 18. Пратт Т., Зелковиц М. Языки программирования, разработка и реализация. – СПб.: Питер, 2002. – 688 с. 19. Шинкаренко В.И., Ильман В.М., Скалозуб В.В. Структурные модели алгоритмов в задачах прикладного программирования Часть I. Формальные алгоритмические структуры // Кибернетика и системный анализ. – 2009. – № 3. – С. 3–14. 20. Зиглер К. Методы проектирования программных систем: Пер. с англ. – М.: Мир, 1985. – 328 с.

Схожі ресурси