DS-theory. Presentation of canonical algorithm by means of algorithmic language

This work continues the description of the decomposition scheme as a theoretical model, which makes possible generation of the applied algorithms. The description of the algorithmic language made for show the possibility of algorithms generation is given. One of the factors' group is described,...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2017
1. Verfasser:	Kolesnyk, V.G.
Format:	Artikel
Sprache:	Ukrainian
Veröffentlicht:	Інститут програмних систем НАН України 2017
Schlagworte:	generation of the applied algorithms УДК: 004.424 004.415
Online Zugang:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/124
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Problems in programming

Institution

Problems in programming

id	pp_isofts_kiev_ua-article-124
record_format	ojs
resource_txt_mv	ppisoftskievua/32/5cee13150e2076b1972dde455645c432.pdf
spelling	pp_isofts_kiev_ua-article-1242018-07-23T13:46:01Z DS-theory. Presentation of canonical algorithm by means of algorithmic language DS-теория. Представление канонического алгоритма с помощью алгоритмического языка DS-теорія. Подання канонічного алгоритму за допомогою алгоритмічної мови Kolesnyk, V.G. generation of the applied algorithms УДК: 004.424, 004.415 генерация прикладных алгоритмов УДК: 004.424, 004.415 генерація прикладних алгоритмів УДК: 004.424, 004.415 This work continues the description of the decomposition scheme as a theoretical model, which makes possible generation of the applied algorithms. The description of the algorithmic language made for show the possibility of algorithms generation is given. One of the factors' group is described, i.e. ways of placing the properties on the tape of the abstract type which when is taken into consideration allows to turn canonical algorithm into a real one and applied algorithm, which is the same as turning the decomposition scheme into the program text. The notions of algorithmic primitive and algorithmic joint (operand and operation) as the means for constructing the algorithm are introduced. These notions of algorithms construction are the alternatives for the notional system and methods of structured programming. The notions of functional core, algorithmic frame, functional contents and algorithmic matrix are introduced. Работа является продолжением описания схемы декомпозиции как теоретической модели, обеспечивающая возможность генерации прикладных алгоритмов. Приведено описание алгоритмического языка, предназначенного продемонстрировать возможность генерации алгоритмов. Описана одна из групп факторов – способы размещения свойств на ленте абстрактного типа, учет которой, позволяет превратить канонический алгоритм в реальный прикладной алгоритм или, что то же, превратить схему декомпозиции в текст программы. Вводятся понятия алгоритмического примитива и алгоритмического сочленения (операнда и операции), как средств построения алгоритма. Данные понятия и способ построения алгоритмов – это альтернативная понятийного аппарата и методологии структурного программирования. Вводятся понятия функционального ядра, алгоритмического фрейма, функционального содержания и алгоритмической матрицы. Робота є продовженням опису схеми декомпозиції як теоретичної моделі, яка забезпечує можливість генерації прикладних алгоритмів. Наведено опис алгоритмічної мови, призначеного продемонструвати можливість генерації алгоритмів. Описана одна з груп чинників - способи розміщення властивостей на стрічці абстрактного типу, урахування якої, дозволяє перетворити канонічний алгоритм в реальний прикладний алгоритм або, що те ж, перетворити схему декомпозиції в текст програми. Вводяться поняття алгоритмічного примітиву і алгоритмічного зчленування (операнда і операції), як засобів побудови алгоритму. Ці поняття і спосіб побудови алгоритмів є альтернативою понятійному апарату і методології структурного програмування. Вводяться поняття функціонального ядра, алгоритмічного фрейма, функціонального змісту та алгоритмічної матриці . Інститут програмних систем НАН України 2017-06-13 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/124 PROBLEMS IN PROGRAMMING; No 1 (2015) ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2015) ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2015) 1727-4907 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/124/117 Copyright (c) 2017 ПРОБЛЕМИ ПРОГРАМУВАННЯ
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2018-07-23T13:46:01Z
collection	OJS
language	Ukrainian
topic	generation of the applied algorithms УДК: 004.424 004.415
spellingShingle	generation of the applied algorithms УДК: 004.424 004.415 Kolesnyk, V.G. DS-theory. Presentation of canonical algorithm by means of algorithmic language
topic_facet	generation of the applied algorithms УДК: 004.424 004.415 генерация прикладных алгоритмов УДК: 004.424 004.415 генерація прикладних алгоритмів УДК: 004.424 004.415
format	Article
author	Kolesnyk, V.G.
author_facet	Kolesnyk, V.G.
author_sort	Kolesnyk, V.G.
title	DS-theory. Presentation of canonical algorithm by means of algorithmic language
title_short	DS-theory. Presentation of canonical algorithm by means of algorithmic language
title_full	DS-theory. Presentation of canonical algorithm by means of algorithmic language
title_fullStr	DS-theory. Presentation of canonical algorithm by means of algorithmic language
title_full_unstemmed	DS-theory. Presentation of canonical algorithm by means of algorithmic language
title_sort	ds-theory. presentation of canonical algorithm by means of algorithmic language
title_alt	DS-теория. Представление канонического алгоритма с помощью алгоритмического языка DS-теорія. Подання канонічного алгоритму за допомогою алгоритмічної мови
description	This work continues the description of the decomposition scheme as a theoretical model, which makes possible generation of the applied algorithms. The description of the algorithmic language made for show the possibility of algorithms generation is given. One of the factors' group is described, i.e. ways of placing the properties on the tape of the abstract type which when is taken into consideration allows to turn canonical algorithm into a real one and applied algorithm, which is the same as turning the decomposition scheme into the program text. The notions of algorithmic primitive and algorithmic joint (operand and operation) as the means for constructing the algorithm are introduced. These notions of algorithms construction are the alternatives for the notional system and methods of structured programming. The notions of functional core, algorithmic frame, functional contents and algorithmic matrix are introduced.
publisher	Інститут програмних систем НАН України
publishDate	2017
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/124
work_keys_str_mv	AT kolesnykvg dstheorypresentationofcanonicalalgorithmbymeansofalgorithmiclanguage AT kolesnykvg dsteoriâpredstavleniekanoničeskogoalgoritmaspomoŝʹûalgoritmičeskogoâzyka AT kolesnykvg dsteoríâpodannâkanoníčnogoalgoritmuzadopomogoûalgoritmíčnoímovi
first_indexed	2025-07-17T09:48:47Z
last_indexed	2025-07-17T09:48:47Z
_version_	1838409543038533632
fulltext	Теоретичні та методологічні основи програмування © В.Г. Колесник, 2015 ISSN 1727-4907. Проблеми програмування. 2015. № 1 3 УДК 004.424, 004.415 В.Г. Колесник DS-ТЕОРИЯ. ПРЕДСТАВЛЕНИЕ КАНОНИЧЕСКОГО АЛГОРИТМА С ПОМОЩЬЮ АЛГОРИТМИЧЕСКОГО ЯЗЫКА Работа является продолжением описания схемы декомпозиции как теоретической модели, обеспечива- ющая возможность генерации прикладных алгоритмов. Приведено описание алгоритмического языка, предназначенного продемонстрировать возможность генерации алгоритмов. Описана одна из групп факторов – способы размещения свойств на ленте абстрактного типа, учет которой, позволяет превра- тить канонический алгоритм в реальный прикладной алгоритм или, что то же, превратить схему деком- позиции в текст программы. Вводятся понятия алгоритмического примитива и алгоритмического со- членения (операнда и операции), как средств построения алгоритма. Данные понятия и способ постро- ения алгоритмов – это альтернативная понятийного аппарата и методологии структурного программи- рования. Вводятся понятия функционального ядра, алгоритмического фрейма, функционального со- держания и алгоритмической матрицы. Введение В работе [1] приводится описание теоретической модели, называемой схемой декомпозиции. Там же показано, что схема декомпозиции (DS) имеет алгоритмиче- скую природу. Здесь описаны контур син- теза (КС) и канонический (универсальный) алгоритм (КА) как основные атрибуты схемы декомпозиции. DS-теория [1], неотъемлемой ча- стью которой является DS, как теоретиче- ская модель, создает предпосылки для генерации алгоритмов (не машинного ко- да). Несмотря на то, что КС и КА вполне формализованы, для того, чтобы они были реализованы в практической обработке как программа для компьютера, их необходи- мо представить средствами алгоритмиче- ского строчного языка. В настоящей статье вводится описание алгоритмического язы- ка. Язык предназначен не для практиче- ского программирования, а только для то- го, чтобы продемонстрировать возмож- ность генерации алгоритмов и текст сгене- рированной программы. В работе вводится понятие алго- ритмического примитива, использующий- ся как компонента при построении DS. Описываются свойства алгоритмических примитивов. Приводятся конструкции операторов и предложений на алгоритми- ческом языке, с помощью которых пред- ставляются алгоритмические примитивы. Описываются понятия алгоритмических сочленений как операций над алгоритми- ческими объектами. КА, который может быть построен на основе DS, на пути его преобразова- ния в реальную программу, должен быть доработан с учетом конкретной вычисли- тельной среды, в которой будет функци- онировать программа. Те факторы (ал- горитмически релевантные факторы), ко- торые необходимо учесть, – многообраз- ны и их достаточно много. С точки зрения DS-теории, они собраны в группы. В ста- тье описывается процедура внесения из- менений в КА, порождаемых одной груп- пой факторов – способам размещения Р-данных на А-ленте. Несмотря на то, что алгоритм как результат генерации, представляется с по- мощью алгоритмического языка импера- тивного типа, DS, как описание исходное для генерации, является описанием декла- ративного типа. Сгенерированный алго- ритм по определению отражает порядок вычислений, а описание DS явно этот по- рядок не показывает. В процессе генера- ции алгоритма учитывается порядок обхо- да дерева полной схемы декомпозиции (DPS) сверху вниз и слева направо и бла- годаря этому он появляется в сгенериро- ванном алгоритме. По сути, DS – это объ- ект декларативного программирования, не Теоретичні та методологічні основи програмування 4 имеющий внешнего сходства с традицион- ными языками декларативного програм- мирования [2, 3]. Алгоритмические компоненты DS Далее используется понятие при- митив схемы декомпозиции (ПСД). Про- стейшими элементами, или примитивами, из которых строится схема декомпозиции являются аналитическая алгоритмическая зависимость (ААЗ), синтетические зави- симости (САЗ): первого (САЗ1) и второго вида (САЗ2). Также как ПСД рассматрива- ется механизм декомпозиции (DM). Из ПСД строятся более сложные конструк- ции. Прототипы ПСД – это базовые кон- струкции структурного программирова- ния [4]. САЗ состоит из двух частей: заго- ловка и тела. Заголовок определяет усло- вия начала и условия завершения работы САЗ, а тело выполняет работу с очередной компонентой С-свойства [1]. Пусть два уз- ла связаны ветвью (родственной связью). С ними соотносится некая САЗ. Если САЗ соотносится с узлом родителем, то в спис- ке А-зависимостей, связанных с этим уз- лом, будет выполняться заголовок САЗ, а тело САЗ будет выполняться в списке А-зависимостей связанных с узлом потом- ком. Механизм декомпозиции представ- ляется набором предложений DM = (Sbegin, Sf, Snext, Send), где Sbegin – условие начала декомпозиции, Sf – описание процедуры первого шага декомпозиции, – описание работы с первой частью, Snext – описание процедуры очередного шага декомпози- ции, Send – описание условия завершения декомпозиции. Sbegin, Sf, Send – эти три компоненты называются заголовком ме- ханизма декомпозиции. Snext – эта компо- нента называется телом механизма де- композиции. ААЗ, заголовок САЗ и DM, тело САЗ и DM называются простейшими рас- четными процедурами (ПРП). С листьями и узлами DPS может соотноситься произвольное количество А-зависимостей. Если результат реализа- ции одной А-зависимости исходное данное для реализации другой А-зависимости, то А-зависимости между собой зависимы. При записи таких А-зависимостей должен сохраняться как порядок их перечисления, так и порядок их выполнения. Если поря- док реализации А-зависимостей произ- вольный, то А-зависимости между собой независимы. Возможна ситуация когда расчетная операция, реализующая А-зависимость может быть выполнена только при опре- деленном условии. Это связано с тем, что существует условный тип части объек- та, в момент декомпозиции может отсут- ствовать некоторое Р-свойство. Из-за этого в КС в момент расчета не будет рассчитываться (реализовываться) некото- рая А-зависимость. Такие А-зависимости называются условными. Две условные А-зависимости могут быть связаны. Суть их связи заключается в том, что расчетные процедуры, что их реализуют, выполняются в зависимо- сти от определенного значения некото- рого Р-свойства. Такого рода условных А-зависимостей может быть и более двух. Они называются альтернативными. С узлом DPS, который не является конечным, может быть соотнесено произ- вольное количество ААЗ, заголовков DM, заголовков собственных САЗ. С узлом, ко- торый не является корневым, может быть соотнесено произвольное количество ААЗ, тело САЗ и одно тело DM. Учитывая то, что с каждым из ли- стьев может быть связано произвольное (большое) количество ААЗ, компонентов САЗ и компонентов DM, необходимо вы- полнить предварительную обработку всего набора ПРП. Для этого надо выполнить следующее. 1. Собрать и объединить зависимые ПРП в порядке их взаимной зависимости. После этого обозначить эту алгоритмиче- скую конструкцию (АК) как единое целое. 2. Собрать и скомпоновать услов- ные ПРП. Принцип объединения в том, что у них одинаковое или различные значение одного и того же Эл-свойства. В результате тоже формируется АК, ко- торая должна быть обозначена как еди- ное целое. 3. Собрать и объединить альтерна- Теоретичні та методологічні основи програмування 5 тивные ПРП. В результате тоже формиру- ется АК, которая должна быть обозначена как единое целое. АК и ПРП также как и А- зависимости тоже могут быть условными и безусловными, а также зависимыми или независимыми. Предыдущие два шага повторяются несколько раз. Но анализу и объединению как компоненты подвергаются и ПРП, и АК. Из них могут быть сформированы АК более сложные. Анализ и объединение за- вершится тогда, когда в списке расчетных процедур будут перечислены все, связан- ные с одним узлом DPS и ПРП, и сложные АК, которые независимы друг от друга. Перечень этих независимых ПРП и АК называется алгоритмической конструкци- ей узла (листа) – (АКУ). На DPS на каж- дом узле и листе будет сформирована соб- ственная АКУ. Более точное определение КС зву- чит так: контур синтеза – это перечень АКУ, составленный в процессе обхода DPS сверху вниз и слева направо. Состав- ление КС как перечня АКУ – это первый шаг синтеза конечного алгоритма, который пригоден для обработки в компьютере. Р-свойства и Р-данные В работе [1] предложены определе- ния Эл-свойства, А-свойства, С-свойства и их родового понятия – Р-свойства. С-свойство, состоящее из одного Эл-свойства, называется простым. А- свойство, состоящее из произвольного ко- личества Эл-свойств, называется простым. С-свойство, состоящее из простого А- свойства, называется расширенным. А- свойство, в состав которого входит одно или более простое или расширенное С- свойство, называется расширенным. С-свойство, состоящее из расши- ренного А-свойства, называется сложным. С каждым типом части объекта или самого объекта соотносится только одно А- свойство. Это А-свойство называется главным А-свойством для данного типа части объекта. Главное А-свойство может состоять из промежуточных А-свойств, входящих в главное как компоненты. Про- межуточные могут содержать А-свойств, которые тоже промежуточные. То есть, существует иерархическая структура А- свойств. Р-свойства могут фиксироваться на носителях, доступных для машинной об- работки. В связи с этим наряду со свой- ствами объекта рассматриваются также данные об объекте. Данное об объекте (Р- данное) или данная величина, характери- зующая объект, – это свойство объекта, для которого определен знак, читаемый или воспринимаемый человеком или (и) техническими средствами. Аналогично понятиям С-свойство, Эл-свойство и А- свойство существуют понятия: совокупное данное (С-данное), агрегированное данное (А-данное) и элементарное данное (Эл- данное) и их родовое понятие – Р-данное. Р-свойства и Р-данные соотносятся как с объектом, так и с частями объекта. А-дан- ные могут включать наряду с Эл-данными А-данные и С-данные. С-данные могут со- держать А-данные. Рассматриваются так- же расширенные С-данные и А-данные, сложные С-данные и А-данные и главное А-данное. Каждая часть объекта должна быть поименована. Эл-данное, что содержит идентификатор объекта или части объекта, обязательно должно присутствовать в со- ставе главного А-данного. В составе А-да- нного этот идентификатор называется ключом. Ключ – это обобщенное понятие традиционно понимаемого в обработке файлов и баз данных ключа записи. Кон- кретные числовые, текстовые и прочие значения Р-свойств и Р-данных называют- ся Д-данными. Прототип понятия Д-да- нное в электронной обработке данных – просто данные. Носитель Д-данных Рассматриваются носители Д-дан- ных двух видов: A-память и A-лента. A-па- мять – это обобщенное абстрактное поня- тие оперативной памяти компьютера. До- ступ к Д-данным размещенным в A-памяти реализуется упоминанием имени Р-дан- ного. Понятие “A-память” до предела упрощено и предназначено для модели- рования алгоритмов реализующих А-за- висимости. Теоретичні та методологічні основи програмування 6 A-лента – это абстрактный образ ленты (магнитной или бумажной), состо- ящей из ячеек, вдоль которой движется читающее устройство (A-головка). В этой статье понятие А-ленты усложняется по сравнению с [1]. Допускается, что ячейки А-ленты группируются в записи. Размер записи определяется размером простого А-данного, которое содержится в записи. A-лента может быть разделена на участки, которые больше записей. То есть, суще- ствует иерархическая структура вложен- ных участков A-ленты. Эти участки назы- ваются областями и подобластями. При движении A-головки вперед выполняется чтение, а при движении назад выполняется только перемотка. A-головка может считывать записи с A-ленты и пере- давать в A-память или выбирать из A- памяти и записывать записи на A-ленту. После того как запись считана в A-память, становиться возможным доступ к Д- данным. Доступ к записям на A-ленте только последовательный. То есть, для то- го чтобы прочитать десятую запись, необ- ходимо перед этим прочитать девять запи- сей предшествующих десятой. С помощью A-ленты моделируется хранение Д-данных и иллюстрируется процесс генерации ал- горитмов. Типы записей, областей и подобла- стей на A-ленте должны быть различимы. Типы области и подобласти A-ленты име- нуются. Например, большие латинские буквы с нижними индексами (или без). Тот факт, что область или подоб- ласть некоторого типа содержит произ- вольное количество записей или подобла- стей будет отмечаться знаком μ на уровне верхнего индекса рядом с названием типа области. Или Rμ=<R1>, что означает “Об- ласть типа R (или область R) содержит произвольное количество подобластей типа R1”. Тот факт, что область или подоб- ласть содержит определенное количество записей или подобластей будет отмечаться знаком ν на уровне верхнего индекса ря- дом с названием области. Rν=<R2,R3,R4>, что означает “область R содержит три по- добласти R2, R3 и R4. Каждая из них встречается один раз”. Порядок перечис- ления подобластей в этом предложении соответствует порядку их размещения в области. Если это не так, то иной порядок оговаривается. Для описания того, как расположе- ны и вложены друг в друга области и по- добласти A-ленты используются предло- жения описанных двух типов. Все предло- жения вместе составляют кортеж RG, с помощью которого описывается структура областей и подобластей на A-ленте. Раз- мещение может быть представлено в виде дерева. Размещение Р-данных на A-ленте Существует несколько видов раз- мещения Р-данных в областях и подобла- стях. Простое А-данное. Наименьшая неделимая часть A-ленты – это запись. В записи размещается простое А-данное. То, что А-данное Q размещено в записи R, записывается следующим образом R[Q]. Записи и подобласти делят А-ленту на фрагменты. Далее эти фрагменты назы- ваются А-фрагментами. Расширенное C-данное. Расширен- ное С-данное занимает область или подоб- ласть, состоящую из записей. Одна запись содержит одно А-данное, являющееся компонентой С-данного. Область или по- добласть, занятая расширенным С-дан- ным, называется простой. Пример: Объект имеет совокупное свойство RA, которое состоит из Эл- свойства AD (рис. 1). Область D содержит RA AD D R R1[AD1] R2[AD2] Rn[ADn] О б л ас ть D C -д ан н о е R A Рис. 1. Размещение C-данного RA в области D на A-ленте Теоретичні та методологічні основи програмування 7 произвольное количество записей R. Эле- ментарное свойство AD размещено в запи- си R. Таким образом совокупное свойство RA размещается в области D. FS: RA = {AD}. RG: D [RA], R [AD], Dμ = <R>. Так как для Р-свойств RA и AD определено размещение, то они одновре- менно являются и Р-данными. Хотя после размещения Р-свойств их имена можно не присваивать соответствующим Р-данным, но присвоить другие имена. А-фрагменты должна быть разли- чимы на А-ленте. Для А-фрагментов должны быть определены признаки начала и конца. Признаком начала подобласти мо- жет быть:  служебная запись – маркер;  некое служебное Эл-данное (тип записи), содержащееся в каждой за- писи С-данного. Это Эл-данное имеет определенное значение. Если в записях хотя бы одного С-данного есть служебное Эл-данное, то оно должно быть во всех за- писях компонентах исходного расширен- ного А-данного;  изменение значения ключа. То есть, во всех записях, компонентах исход- ного А-данного есть Эл-данное с одним и тем же значением. Оно характерно тем, что для одного С-данного, это Эл-данное имеет одно и то же значение. Признаком конца подобласти может быть:  служебная запись – маркер;  изменение значения служебно- го Эл-данного (типа записи);  изменение значения ключа;  конец A-ленты. Способы размещения А-фрагментов Есть три способа размещения А- фрагментов внутри области A-ленты. Порядок относительно границ области размещения (ORb). Всем А- фрагментам содержащим компоненты расширенного A-данного установлен но- мер следования относительно начала или (и) конца области (рис. 2). Пример: FS: Z = {A,B,C,D,E}. A, B, D – про- стые А-данные. C и E – простые С-данные. RG: Rν=<R1[A],R2[B],R3[C],R4[D], R5[E]>, R3μ=< R31>, R5μ =<R51>. Здесь R1, R2, R4, R31, R51 – записи, R3, R5 – подобласти. R1 и R2 могут иметь или не иметь тип записи. Все остальные записи должны иметь тип записи обязательно. Если нет типа записи, то должно быть Эл-данное выполняющее функции ключа и для запи- сей R4, R31 и R51 должны быть определе- ны значения ключа. Для всех А-фрагментов установлен номера следования в зоне A-ленты: R1 – первый, R2 – второй, R3 – третий, R4 – четвертый, R5 – пятый. Начало подобласти R3 первая запись R31, конец подобласти R3 –запись R4. Начало подобласти R5 пер- вая запись R51, конец подобласти R5 – ко- нец A-ленты. Относительный порядок (ORn). Два или более А-фрагмента имеют поря- док следования относительно друг друга. Пример: FS: Z = {A,B,C,D,E}. A, B, D – про- стые А-данные. C и E – простые С-данные. RG: Rν=<R1[A],R2[B],R3[C],R4[D], R5[E]>, R3μ=< R31>, R5μ =<R51>. Здесь R1, R2, R4, R31, R51 – записи, R3, R5 – подобласти. Подобласть R3 следует непосред- ственно после записи R2. Записи R31 и R51 размещены компактно и должны иметь тип записи или ключ с определен- R1[A] R2[B] R3[C] R4[D] R5[E] R[Z] R31[C1] R51[E1] Рис. 2. Компоненты расширенного А-данного имеют номера следования относительно начала области Теоретичні та методологічні основи програмування 8 ным значением. Начало подобласти R5 первая запись R51, конец подобласти R5 – любая запись отличающаяся от R51. Если подобласть R5 в конце A-ленты, то при- знак конца подобласти будет конец A- ленты. Начало подобласти R3 – запись, ко- торая непосредственно следует после за- писи R2. Конец подобласти R3 – любая запись отличающаяся от R31. Если подоб- ласть R3 в конце A-ленты, то признак кон- ца подобласти будет конец A-ленты. Возможен способ размещения, ко- гда два А-фрагмента не следуют друг за другом непосредственно. Такая ситуация может возникнуть, когда А-фрагменты, не участвуют при обработке и их необхо- димо пропускать при чтении А-данных с А-ленты. Это так называемые непродук- тивные Д-данные. Порядок по значению ключа (ORs). Простая подобласть, содержащая А-фрагменты может иметь характеристи- ку – порядок своих компонент. Записи могут быть упорядочены по значениям одного или нескольких Эл-данных вхо- дящих в состав А-данного содержащегося в записи. Записи могут быть упорядоче- ны по возрастанию и по убыванию клю- ча. Могут быть и более сложные отно- шения между ключами записей. Порядок между записями – это характеристика подобласти. Размещение расширенных А-дан- ных может быть многообразным. Причи- ны этому следующие:  расширенное А-данное может состоять из простых А-данных. Последние размещаются в записях и вперемешку с расширенными С-данными. Так называе- мые промежуточные А-данные;  количество промежуточных А- данных может быть произвольное;  количество промежуточных С- данных может быть произвольное. Совмещение различных способов размещения А-фрагментов Компоненты расширенного А-дан- ного при размещении на А-ленте могут иметь различный порядок. Существует не- сколько способов совместного размещения компонент. Совместное размещение первого вида (mix1). Для А-фрагментов порядок размещения не установлен. FS: Z = {A,B,C,D,E}. A, B, D – про- стые А-данные. C и E – простые С- данные. RG: Rν = <R1[A], R2[B], R3[C], R4[D], R5[E]>, Rμ3=< R31>, Rμ5 = <R51>, R1, R2, R4, R31, R51 – записи; R3, R5 – подобласти. Ситуация показана на рис. 3. Все записи должны иметь тип записи. Каждая из подобластей R3 и R5 размещается ком- пактно. Начало и конец каждой из подоб- ластей должен быть определен. Начало области R одна из записей R1, R2, R4 – или начало подобластей R3 (запись R31), R5 (запись R51). Конец R это конец A-ленты или запись, отличающаяся от R1, R2, R4, R31, R51. Начало R3 – запись R31, конец R3 – запись, отличающаяся от R31. Начало R5 – запись R51, конец R5 – запись, отличаю- щаяся от R51. Записывается это так: RG: R=<R1[A]° R2[B]° R3[C]° R4[D]° R5[E]°>; R3μ =< R31>; R5μ = < < R51>. Здесь R1, R2, R4, R31, R51 – запи- си; R3, R5 – подобласти. Знак ° рядом с именами записей или подобластей показы- вает, что эти записи или подобласти пере- мешаны. Совместное размещение второго вида (mix2). Некоторые А-фрагменты мо- гут иметь относительный порядок следо- вания, а остальные имеют произвольный порядок. В этом случае выполняется раз- мещение в так называемых рабочих по- R1[A] R2[B] R3[C] R4[D] R5[E] R[Z] R31[C1] R51[E1] Рис.3. Компоненты расширенного А-данного имеют совместное размещение Теоретичні та методологічні основи програмування 9 добластях. Выполняется группировка ком- понент. Если какие-либо компоненты имеют порядок относительно друг друга и размещены рядом, то они объединяются в подобласть. В результате рабочие подоб- ласти и остальные компоненты имеют совместное размещение mix1. FS: Z = {A,B,C,D,E}. A, B, D – про- стые А-данные. C и E – простые С-данные. RG: Rν=<R1[A]° R6° R4[D]° R5[E]°>, R3μ = < R31>, R5μ = <R51>, здесь R1, R2, R4, R31, R51 – записи; R3, R5 – подобласти. R6 = <R2[B], R3[C]> – рабо- чая подобласть. Совместное размещение третьего вида (mix3). Одновременно некоторые А-фрагменты имеют определенное место относительно границ области размещения, а другие могут быть перемешаны. R1 – первый, R2 – последний, а запись R4 и по- добласти R3 и R5 перемешаны в одной области. Записи R31, R4 и R51 должны иметь тип. Признак начала подобласти, где они хранятся – первая встретившаяся сре- ди R31, R4 и R51. Признак конца подобла- сти – конец A-ленты или запись отличная от R31, R4 и R51. Если у некоторых по- добластей или записей есть порядок отно- сительно границ области, то они могут быть в начале или в конце содержащей их области. FS: Z = {A,B,C,D,E}. A, B, D – про- стые А-данные. C и E – простые С-данные. RG: Rν=<R1[A], R3[C]° R4[D]° R5[E]° R2[B] >, Rμ3=< R31>, Rμ5 =<R51>, здесь R1, R2, R4, R31, R51 – записи; R3, R5 – подобласти. Совместное размещение четвер- того вида (mix4). А-фрагменты могут иметь относительный порядок следования, порядок относительно границ области или (и) произвольный порядок. FS: Z = {A,B,C,D,E,F,G}. A, B, D, F,G – простые А-данные. C и E – простые С-данные. RG: Rν=<R1[A], R2[B], R3[C], R4[D], R5[E] , R6[F], R7[G] >, R3μ = < < R31>, R5μ = <R51>. R1, R2, R4, R31, R51, R6, R7 – записи; R3, R5 – подобласти. R1 – первая в области – R, R6 – предпоследняя и R7 – последняя. R4 и R5 – следуют непосредственно друг за другом. В этом случае выполняется разме- щение в рабочих подобластях. Выполняет- ся группировка А-фрагментов. Если какие- либо А-фрагменты имеют порядок относи- тельно друг друга и размещены рядом, то они объединяются в подобласть. В случае конкретного примера этот вид размещения записывается следующим образом: RG: Rν=<R1[A], R2[B]° R3[C]° R8°, R6[F], R7[G] >, R3μ = < R31>, R5μ = <R51>, здесь R1, R2, R4, R31, R51 , R6, R7 – запи- си; R3, R5 – подобласти. R8 = < R4[D], R5[E] > – рабочая подобласть. Входная и выходная A-ленты Существование А-зависимостей и КС предполагает, что есть Р-свойства (со- ответственно и Р-данные) исходные для расчетов и Р-свойства являющиеся ре- зультатом в расчетах. Если реализуется ААЗ, то и операнды, и результат размеще- ны в A-памяти, а затем выводятся в одной и той же записи. Но возможна ситуация, что перед расчетом Р-данные размещены на одной A-ленте, а результат расчета должен быть выведен на другую A-ленту. В DS-теории предусматривается возмож- ность работы с Р-данными размещенными во входных и выходных A-лентах. A-лента, используемая для хранения ис- ходных для расчета Р-данных, называется входной. A-лента, используемая для хра- нения Р-данных, являющихся результатом в расчетах, называется выходной. Представление ПСД средствами алгоритмического языка Из-за того, что размещение А-фрагменты, содержащие Р-данные, име- ет различные вариации, описанные выше, КА – более сложная конструкция по срав- нению с описанной в [1]. Далее КА будет описываться с помощью алгоритмического языка подобного ранним версиям языка КОБОЛ. Для описания алгоритмов исполь- зуется алгоритмический язык, синтаксиче- ские конструкции, которого вводятся по мере их необходимости. Язык не имеет строго формального определения, а осно- Теоретичні та методологічні основи програмування 10 ван на интуитивном понимании традици- онных строчных языков. По ходу изложе- ния определения могут быть уточнены на минимально необходимом уровне. Назна- чение языка временное. Реализация ААЗ. Наименьшая и основная частью КС – это действие, реали- зующее одну ААЗ. Оно описывается опе- ратором присваивания. Точнее, операто- ром присваивания, существующем в тра- диционных алгоритмических языках в их простейшей форме. Эл-свойства А и В связанные зна- ком равно A = α (B) реализуются в виде оператора присваивания A:=B, который обозначает: “На основании Эл-свойства B, в соответствии с существующей между A и B зависимостью α, формируется Эл- свойство A”. Зависимость α может содер- жать традиционно используемые знаки арифметических и алгебраических опера- ций, разделителей. Если по ходу изложе- ния будет необходимость использовать алгебраические функции, которые в тра- диционных алгоритмических языках реа- лизуются подпрограммами, то это будет оговариваться особо. Также будет особо оговариваться ситуация, когда ААЗ суще- ствует, но не может быть выражена компо- зицией арифметических или (и) алгебраи- ческих знаков. Частный случай оператора присваивания – это пересылка значения из B в A. Операторы, порождаемые ААЗ, то- же могут быть зависимыми или не зависи- мыми. Алгоритмические сочленения. Далее описываются способы объединения операторов алгоритмического языка в бо- лее сложные конструкции. Объединение выполняется с помощью, так называемых алгоритмических сочленений – последова- тельного, условного и альтернативного. Сочленения – это операции над алгорит- мическими объектами (и, соответственно, над операторами и предложениями алго- ритмического языка). Группа операторов называется предложением. Предложение завершается точкой или ограничивается операторными скобками, которые будут описаны далее. Предложение может быть разделено на части только с точки зрения удобства зри- тельно восприятия. Внутри предложения операторы разделяются запятой или про- белом (пробелами). Операторы в предложении объеди- нены последовательным сочленением. Предложение далее рассматривается как неделимая конструкция, и может быть использовано как компонента в дальней- ших сочленениях, в результате чего по- лучаются сложные предложения. Пред- ложение закрепляет порядок выполнения операторов и, соответственно, ААЗ, неза- висимо от того, какими они были перед компоновкой – зависимыми или незави- симыми. Условные ААЗ или ПРП представ- ляются условными операторами – (IF THEN). При описании условий использу- ются традиционные знаки сравнения (>, <, =, ≥, ≤, ⌐), логические операции (OR, AND, NOT) и разделительные знаки (про- бел, парные скобки). Как операнды в опе- рациях сравнения используются имена Р- данных. Пример: IF L=N THEN A := B ENDIF или IF L=N (A := B). Здесь операторные скобки “THEN” и “ENDIF” и круглые парные скобки вы- полняют одну и ту же функцию. Внутри скобок может быть более одного операто- ра. В случае предыдущего примера опера- тор называется условным. Если два или более ПРП выполня- ются при истинности одного и того же условия, то соответствующие операторы объединяются в предложение. Такое пред- ложение является условным, а сочленение операторов называется условным сочле- нением. Если условия двух или более условных предложений расположенных последовательно (не обязательно) взаим- но исключают друг друга, то они также сочленяются в одно предложение. Такое предложение называется альтернативным предложением, а сочленение называется альтернативным сочленением. Прототип альтернативного сочленения – оператор CASE в традиционных алгоритмических языках. Теоретичні та методологічні основи програмування 11 Пример: Три условных предложе- ния IF A=1 (B := C). IF А=2 (B := 2C). IF А=3 (B := 0). Сочленены в одно альтернативное CASE IF A=1 (B := C) IF А=2 (B := 2C) IF А=3 (B := 0) ENDCASE Здесь CASE и ENDCASE оператор- ные скобки, ограничивающие условное альтернативное предложение. Если в условных или в альтерна- тивных предложениях сочленяются только операторы, то эти предложения называют- ся простыми условными. Простые услов- ные предложения могут рассматриваться как неделимые целые и как компоненты (операторы) могут сочленяться в более сложные конструкции. Предложение, составленное из со- членений хотя бы из двух вышеупомяну- тых видов и имеющее в качестве компо- ненты предложение, а не только операто- ры, называется сложным. Сложное пред- ложение тоже можно рассматривать как неделимое целое и использовать его как компоненту. Таким образом, может по- рождаться сложная конструкция, состав- ленная из операторов, имеющая иерархи- ческую структуру. Условные, альтернативные и слож- ные предложения тоже могут быть зави- симыми или независимыми. Реализация DM. Для записи про- цедур DM применяется несколько видов алгоритмических конструкций, в кото- рых используются оператор чтения (READ) и оператор записи (WRITE). Прототип этих операторов – это операто- ры ввода-вывода в традиционных алго- ритмических языках. Оператор чтения – READ, исполь- зует указатель, сигнализирующий о том, закончилась или нет запись на A-ленте. Если при попытке чтения с A-ленты очередная запись прочитана и соответ- ствующее А-данное доступно в A-памя- ти, то значение указателя “Y”, иначе “N”. Оператор ввода работает следующим образом. Если при попытке чтения с A-ленты доступна очередная запись, то содержаще- еся там А-данное переносится в A-память. A-головка перемещается на одну запись вперед. Указатель устанавливается в со- стояние “Y”. Если на A-ленте очередная запись отсутствует, A-головка не смещает- ся, а указатель устанавливается в состоя- ние “N”. Имя указателя D_An, где n – идентификатор A-ленты. Повторяющееся выполнение опера- тора ввода реализуется с помощью кон- струкции, которая в традиционных алго- ритмических языках называется циклом. В большинстве строчных алгорит- мических языков заголовок и тело цикла текстуально неразрывны. Временный язык представляет оператор цикла двумя пред- ложениями, связь между которыми уста- навливается по идентификатору. Это сложное предложение. Это подобно тому как реализована связь между заголовком и телом цикла в ранних версиях КОБОЛа. PERFORM AA (условие) . . AA: BEGIN… END AA. Где PERFORM – имя оператора цикла. AA – имя тела цикла, по которому реализуется связь между заголовком и те- лом цикла. Условие в скобках – это усло- вие, при достижении которого прекраща- ется выполнение цикла. Здесь может быть указанно также количество повторений. BEGIN и END – операторные скобки, ограничивающие тело цикла. Далее пример размещения конкрет- ного С-данного в области (рис. 4). FS: Z = {B}, B – простое C-данное. B = { C}, C – простое Эл-данное. RG: Rν = < R2 [B]>,R2μ =< R21[C] >. A-лента имеет идентификатор A1. DM представляется операторами следую- щим образом. PERFORM AA ((D_AA1 = “N”)) . . AA: BEGIN READ A1 END AA. Теоретичні та методологічні основи програмування 12 При реализации процедур DM мо- жет иметь условие начала – Sbegin. В тексте алгоритма условие реализуется условным и представляется оператором или предло- жением. При реализации DM могут иметь место также процедуры инициализации и (или) завершения. После того, как простое Д-данное перемещено из записи в A-память, доступ к компонентам А-данного по именам. В операторе ввода указывается имя иденти- фикатора A-ленты. Реализация САЗ. САЗ1 реализуется с помощью цикла. Частью этого цикла, точнее, частью тела, есть действие, кото- рое сохраняет каждую реализацию Эл- данного C на A-ленте. Пример: B – простое С-данное; C – простое Эл-данное; B = { C }; E – Эл- данное размещенное в A-памяти; RG: R[B]; Rμ = < R1[C] >; R размещено на A-ленте, иденти- фикатор которой A1. Между E и B суще- ствует зависимость. Алгоритмическая кон- струкция состоит из двух частей. PERFORM BB (“завершение вы- числений”). BB: BEGIN; (“реализация C = E”); WRITE R1; END BB. Здесь “завершение вычислений” – это условие завершения вычислений. Условие должно быть задано при описа- нии DM. Здесь “реализация C = E” – это опе- ратор присваивания или предложение, ко- торое выполняет формирование каждой из компоненты C, используя E. Это может быть просто вычитание, сравнение и уста- новление некоего признака или любое вы- ражение, порождаемое прикладной обла- стью и реализуемое языком. При одном выполнении тела цикла вычисляется одна компонента C. САЗ2 реализуется с помощью цик- ла, его неотъемлемая часть – это действия, обеспечивающие доступ к каждому Эл- данному или А-данному, которое является компонентой С-данного. Конструкция цикла приводится в следующем примере: B – простое С-данное; C – простое Эл-данное; B = { C }; D – Эл-данное размещенное в A-памяти; RG: R[B]; Rμ = < R1[C] >; R размещено на A-ленте, иденти- фикатор которой A1. Между D и B суще- ствует некая зависимость, реализующаяся предложением “реализация D = C”. Алго- ритмическая конструкция состоит из двух частей. READ A1 PERFORM BB (D_AA1 = “N”). BB: BEGIN; (“реализация D = C”); READ A1; END BB. Здесь “реализация D = C” – это опе- ратор присваивания или предложение, вы- полняющее обработку или формирование D используя C. Предложение может со- держать любое арифметическое или алгеб- раическое выражение, содержащее C как операнд. Любое выражение в смысле тех возможностей, которыми можно распола- гать в практической реализации DS-теория как средство описания схем декомпозиции и связанных с ними расчетов. Если это оператор присваивания, то он имеет такое выражение в правой части, после выпол- нения в цикла должен быть обеспечено формирование Эл-данного D. Предварительное описание структуры программы Компоненты тела фрейма. С каж- дым узлом DPS может быть связано про- извольное количество А-зависимостей, которые могут быть реализованы и про- стыми предложениями, и сложными. Все А-зависимости, что соотносятся с одним Рис. 4. Размещение расширенного А-данного Z в области R: а – дерево типов свойств; б – структура подобластей R[Z] R2[B] R21[C] Z B C а б Теоретичні та методологічні основи програмування 13 узлом DPS, ранее получили название АКУ. Все предложения алгоритмическо- го языка, что представляют АКУ, назы- ваются параграфом. Совокупность всех параграфов – это программа. Она тоже может быть представлена деревом. С каждым узлом этого дерева связывается один параграф. Далее это дерево называ- ется деревом алгоритма (DA). Как АКУ, так и параграф соотносятся с главным А-данным. Как упоминалось раньше, с одним узлом DA может быть соотнесено DM и (или) более (не менее) одной САЗ1. Заго- ловки циклов, реализующих DM и САЗ1 заменяются одним заголовком, так как все они определяют одинаковый цикл. Все АК, что являются телом цикла для DM и каждой САЗ1, объединяются в одно тело. Связь между параграфом с этим заголов- ком и параграфом с соответствующим объединенным телом цикла – это един- ственная связь между данными парагра- фами. Эта связь называется иерархиче- ским сочленением. Оно используется для сочленения параграфов. Иерархическое сочленение между двумя смежными уз- лами может быть только одно. В изобра- жении DA ребро, соединяющее два узла – родителя и потомка указывает на то, что параграфы, соответствующие этим узлам, будут сочленены иерархическим сочлене- нием. Связь между всеми параграфами программы изображена DA. В этом дереве узлы соотносятся с параграфами про- граммы. Вся совокупность иерархически со- члененных параграфов называется про- граммой. Программа содержит параграфы, количество которых соответствует количе- ству узлов DA. Параграфы сочленены иерархическим сочленением в таком же порядке, как соединены соответствующие узлы DPS. То есть, деревья DPS и DA – изоморфны. Между синтаксическими средства- ми языка существует зависимость, пока- занная на рис. 5. Между параграфами программы есть различия в зависимости от того, где расположены соответствующие им узлы DA. Рис. 5. Структура синтаксических конструкций изобразительного языка DS-теории 1. Корневой узел. Здесь могут быть предложения, реализующие заголовки циклов, САЗ и DM. Здесь не может быть тел циклов. 2. Концевой узел. Предложения, ре- ализующие тела циклов САЗ и (или) DM узла-родителя. Здесь не может быть заго- ловков циклов. 3. Промежуточный узел. Здесь мо- гут быть предложения – заголовки циклов, реализующие собственные САЗ и (или) DM и предложения тела циклов, реализу- ющие САЗ и (или) DM узла-родителя. ААЗ может быть реализовано в параграфах, соответствующих любому уз- лу DA. Порядок выполнения операторов связанных с узлом DA зависит от несколь- ких факторов: 1) содержимое АКУ; 2) порядок размещения А-фраг- ментов на входной A-ленте; 3) порядок размещения А-фраг- ментов на выходной на A-ленте. Представление АКУ Далее перечислены ситуации раз- мещения компонент главного А-данного. Учитывая то, что внутри записи до- ступ к А-данным по именам, то порядок размещения Д-данных в записи не влияет на порядок размещения ПРП, обрабатыва- ющие эти Д-данные. Программа Параграф Сложное предложение Простое предложение Повелительный оператор Теоретичні та методологічні основи програмування 14 Все предложения параграфа можно разбить на группы. Каждая из групп соот- носится с одним А-фрагментом. Связь группы и А-фрагмента обусловлена тем, что в А-фрагменте размещены Д-данные, которые являются исходными для А- зависимостей реализованных предложе- ниями группы. Далее эта группа будет называться АТ-предложением. Порядок АТ-предложений в пара- графе должен быть такой же, как порядок А-фрагментов на А-ленте. А-фрагменты имеют порядок от- носительно границ области главного А-данного. Если все А-фрагменты глав- ного А-данного имеют на А-ленте опре- деленные места, то соответствующие им AT-предложения должны быть записаны в том же порядке. AT-предложения бу- дут сочленены последовательным сочле- нением. Но возможна ситуация, когда АТ-предложения два или более зависимы и порядок их сочленения не соответству- ет порядку А-фрагментов на А-ленте. В этом случае параграф не может быть скомпонован. В практике программиро- вания ищут возможность изменить поря- док размещения А-фрагментов и разме- стить А-фрагменты соответственно по- рядку АТ-предложений. Также могут быть выполнены повторные проходы вдоль А-ленты. А-фрагменты имеют относитель- ный порядок следования. Ситуация, ко- гда А-фрагменты имеют порядок следо- вания по отношению друг к другу по- добная размещению с порядком относи- тельно границ области. Порядок АТ-пред- ложений должен быть таким же, как и порядок соответствующих А-фрагментов. Сочленение AT-предложений будет по- следовательным. Если же A-фрагменты будут разделятся непродуктивными А- фрагментами, то каждое АТ-предложение должно быть условным, а сочленение их должно быть альтернативным. Суть усло- вий в том, чтобы распознать непродук- тивный А-фрагмент и пропустить его на А-ленте. Возможна ситуация, когда АТ- предложения два или более зависимы и порядок их сочленения не соответствует порядку А-фрагментов на А-ленте, раз- мещенных относительно друг друга. В этом случае параграф не может быть скомпонован. В практике программирова- ния ищут возможность изменить порядок размещения А-фрагментов и разместить А-фрагменты соответственно порядку АТ-предложений. Также могут быть вы- полнены повторные проходы вдоль А- ленты. Совместное размещение компо- нент первого вида (mix1). Все А- фрагменты, как компоненты главного А- данного, перемешаны по виду mix1. Соот- ветствующие им AT-предложения соеди- нены альтернативным сочленением. Усло- вия должны проверять (различать) встре- тившийся А-фрагмент и выполнять соот- ветствующее АТ-предложение. Весь такой параграф – это одно альтернативное со- членение. Совместное размещение компо- нент второго вида (mix2). При таком размещении вся область главного А-дан- ного рассматривается разделенной на зо- ны. В зонах объединяются А-фрагменты с относительным порядком размещения. Эти зоны и остальные А-фрагменты рас- сматриваются как совокупность компо- нент на А-ленте, которые перемешаны по виду mix1. Для компонент с размещением mix1 используется альтернативное сочле- нение соответствующих АТ-предло- жений. Внутри зон где компоненты раз- мещены относительно друг друга исполь- зуется последовательное сочленение с уточнениями описанными выше для тако- го случая. Совместное размещение компо- нент третьего вида (mix3). При таком размещении (рис. 6) А-фрагменты могут иметь определенные позиции в начале (а) или в конце (б) области занимаемой глав- ным A-данным. Компоненты главного A- данного, у которых определенные пози- ции, могут быть также и в начале и в конце области (в). При таком размещении область рас- сматривается разделенной на зоны. Зоны А-фрагментов с определенными местами и зоны, где А-фрагменты перемешаны по виду mix1. Теоретичні та методологічні основи програмування 15 AT-предложения, соответствую- щие А-фрагментам, размещенным в зоне с определенными позициями, соединяются последовательным сочленением. Полу- ченную АК временно (в условиях приме- ра) назовем A. AT-предложения, соответ- ствующие А-фрагментам, размещенным в зоне с совместным размещением, соеди- няются альтернативным сочленением. Полученную АК назовем B. Получившие- ся конструкции (A и B) соединяются по- следовательным сочленением в том по- рядке, который есть между соответству- ющими зонами. В условиях примеров на рис. 6. соединения будут следующими: а: AК A + АК B б: АК B + АК A в: АК A + АК B + АК A Любое из этих соединений – это па- раграф, соотносящийся с главным А-да- нным. Условные A-фрагменты. Некото- рые А-фрагменты к моменту расчета мо- гут отсутствовать. Такая ситуация может быть обусловлена природой и значениями Р-свойств и, соответственно, Р-данных. Информация об их наличии может быть известна к началу расчета или нет. То, что запись или подобласть отсутствует, может стать известным только после того, как обработаны все компоненты главного А-данного или достигнут конец содержа- щей их подобласти. Существование таких компонент следует учитывать при сочле- нении АК в параграфе. Условными могут быть А-фраг- менты с определенными местами. Соот- ветствующие АТ-предложения должны быть условными. В условии проверяется тип встретившийся записи или подобла- сти. Алгоритмическая конструкция будет выполнена, если встретится соответству- ющая компонента. В условии могут быть проверены Д-данные, к которым есть до- ступ и которые могут содержать признак наличия условного Д-данного. Возможна ситуация, когда при- знаком конца подобласти есть А-фрагмент с определенным местом. Если эта компо- нента условная, то в качестве признака за- вершения подобласти необходимо учиты- вать также следующую безусловную ком- поненту. Пример (рис. 7). Если условных А- фрагментов (записи A2, A3, … An) с опре- деленными местами, которые являются условием завершения подобласти, более одной, то они все должны быть учтены в условии, проверяющем признак заверше- ния подобласти. Условием завершения по- добласти A1, будет первая из встретив- шихся записей A2, A3, … An. Наличие условных компонент необходимо учитывать при сочленении АК порождаемых Р-данными, имеющими от- носительный порядок следования. Как и в случае Д-данных с определенными пози- циями, сочленяемые АК должны допол- няться условием проверки их наличия. Для проверки используется либо А-данное со служебным Эл-данным признаком, либо наличие следующей подобласти. Как и в случае условных А-фрагментов с опреде- ленной позицией, если условные компо- Рис. 7. Обусловленные А-фрагменты с определенными местами как при- знаки завершения подобласти Подобласть A1 A2 A3 An … Рис. 6. Размещение А-фрагментов в об- ласти главного А-данного. Чис- ло в прямоугольных скобках ря- дом с именем А-фрагмента ука- зывает на его позицию во вклю- чающей его подобласти. N-1 – предпоследняя позиция, N – последняя а R1°R2°R3° R4 – [N] б R2°R3° R1 – [1] R4 – [N-1] R5 – [N] в R3°R °4 R2 – [2] R3 – [1] Теоретичні та методологічні основи програмування 16 ненты с относительным порядком следо- вания используются при определении кон- ца подобласти, то условие завершения по- добласти должно учитывать условные компоненты. Обязательные A-фрагменты. При размещении компонент главного А-дан- ного возможна ситуация, когда некоторые компоненты должны присутствовать обя- зательно. При совместном размещении должно быть определено служебное Эл- данное, выполняющее функцию флажка. Флажок должен быть установлен в состоя- ние “компонента отсутствует” перед на- чалом работы с компонентами, имеющими совместное размещение, а затем в процес- се их обработки, когда обязательная ком- понента встретится, флажок переустанав- ливается в состояние “компонента присут- ствует”. Если компонента не встретилась, то это рассматривается как ошибка специ- фикации на основе, которой строилась DS. С каждой обязательной компонентой со- относится собственный флажок. Структура программы Все предложения программы мож- но разделить на две категории. К первой категории относятся предложения, кото- рые непосредственно реализуют обработку А-зависимостей. В этих предложениях ис- пользуются имена Эл-данных (и, соответ- ственно, Эл-свойств). Ко второй категории относятся предложения, реализующие САЗ обеих видов, DM, доступ к Д-данным на А-ленте, условные операто- ры, существование которых обусловлено размещением Д-данных в областях и запи- сях на А-ленте. Совокупность всех пред- ложений первой категории параграфа называется функциональным ядром (ФЯ) этого параграфа. Совокупность всех пред- ложений второй категории параграфа называется алгоритмическим фреймом (АФ) этого параграфа. Рассмотрим DS, DA имеющих два узла (рис. 8). В параграфе уровня K0 дол- жен быть заголовок цикла, реализующее собственную САЗ. В AT-предложении, со- ответствующее уровню K1, должен быть оператор, реализующий тело этой САЗ (уровня K0). На уровне K0 должен быть также заголовок цикла, обеспечивающий реализацию расчета ААЗ, соотносящиеся с уровнем K1. Также должен быть заголо- вок цикла, обеспечивающий доступ к за- писям на А-ленте. Все три вышеупомянутые циклы управляемы одним и тем же параметром цикла – количеством записей. Эти три цикла синтезируются в один. Заголовок общий для всех, а в теле цикла будут сле- дующие компоненты: AT-предложение уровня K1, вклю- чающее операторы, реализующие ААЗ уровня K1, и операторы, реализующие тело цикла САЗ уровня K0. Порядок и характер сочленений операторов, реализующих А-зависимостей уровнях K1 и K0 зависят от размещения данных в областях и будет реализован со- ответствующими сочленениями в соответ- ствующих AT-предложениях. Количество записей неизвестно. Идентификатор A- ленты A1. В параграфах уровня K0 в первом и втором случае операторы BEGIN, READ A1, PERFORM, END AA – это алгоритми- ческий фрейм, обеспечивающий реализа- цию САЗ уровня K0. Алгоритмический фрейм обеспечивает реализацию функцио- нальности уровня K0. В параграфах уровня K1 в обоих случаях операторы BEGIN, READ A1, END BB тоже алгоритмический фрейм, обеспечивающий реализацию функциональности уровня K1. Параграф, соответствующий уровню K0 AA: BEGIN READ A1 Оператор 1 PERFORM BB (D_AA1 = “N”). Оператор K K0 K1 Рис. 8. Двухуровневая DA Теоретичні та методологічні основи програмування 17 Совокупность алгоритмических фреймов всех параграфов программы с учетом их сочленений и взаимного разме- щения называется алгоритмической мат- рицей (АМ) программы. Совокупность всех функциональных ядер всех парагра- фов программы с учетом их сочленений и взаимного размещения называется функ- циональным содержанием (ФС) програм- мы. Графически алгоритм как сочетание алгоритмической матрицы и функцио- нального содержания показан на рис. 9. Две стрелки отражают передачу управле- ния от заголовка к телу цикла. Но дальше иерархическое сочленение между пара- графами будет изображаться одной линией (но не стрелками). Штриховка типа “кир- пичная кладка” изображает компоненты алгоритмических фреймов или алгоритми- ческой матрицы. Штриховка типа “волна” изображает компоненты функциональных ядер или функционального содержания алгоритма. Дополнительные замечания Исходными данными для генерации алгоритма выступает DS с кортежами опи- саний узлов. С точки зрения более доступ- ного изложения, DS можно рассматривать как схему алгоритма высокого уровня аб- стракции. Иными словами, традиционная блок-схема алгоритма или иное графиче- ское изображение движения управления или потока данных, строится на основании DS. Хотя с точки зрения реального прак- тического программирования в этом нет необходимости. Результат возможной ге- нерации на настоящем уровне развития DS-теории – это текст программы на алго- ритмическом языке. Этот текст не предна- значен для практической работы програм- миста с ним. Текст – это промежуточный результат и рассматривается как исходные данные для последующей компиляции, и создания работающей прикладной про- граммы, и нужен он только в период те- стирования возможного генератора алго- ритмов. Естественное желание исследова- телей в сфере программирования – это желание формализовать процесс про- граммирования. Программу можно рас- сматривать как результат некоторых опе- раций над операндами. Если продолжить поиск в этом направлении, то появится понятие неких примитивов, операций над ними и конструкций составленных из примитивов. Такой подход позволяет применить или разработать математиче- ский аппарат для анализа, верификации и исследования программ. На этом пути по- явились идеи структурного программиро- вания [4]. В рамках DS-теории идея “опе- рация-операнд” имеет место и в отноше- нии DS, и в отношении алгоритмов, запи- сываемых с помощью алгоритмического языка. В статье описаны операции и опе- ранды в отношении алгоритмов. Опера- ции – это последовательные, условные, альтернативные и иерархические сочле- нения. Операнды – это АК и ПРП, реали- зующие DM и А-зависимости. По мере того, как при реализации КА учитываются алгоритмически реле- вантные факторы другого типа, в DA по- являются дополнительные узлы-параграфы END AA Параграф, соответствующий уровню K1 BB: BEGIN Оператор 1 Оператор M READ A1; END BB Параграф K0. Параграф K1. – компоненты алгоритмических фреймов; – компоненты функциональных ядер. Рис. 9. Графическое представление программы Примечание: Теоретичні та методологічні основи програмування 18 и вследствие этого изоморфизм деревьев DPS и DA разрушается. Это явление будет описано в следующей статье. Выводы В данной работе описаны способы размещения Р-данных на А-ленте. Внесе- ние в КА изменений, обусловленных спо- собами размещения Р-данных, позволяет создать текст программы, что приближает DS, как теоретическую модель, к реальным прикладным алгоритмам. Анализ и исследование КА, пред- ставленного в виде текста на алгоритмиче- ском языке, позволяет определить ряд по- нятий: функциональное ядро, алгоритми- ческий фрейм, функциональное содержа- ние и алгоритмическая матрица. Данные понятия необходимы для дальнейшего ис- следования и синтеза алгоритмов. DS, как теоретическая модель ори- ентированная на разработку реальных прикладных программ, требует, исполь- зуя специфические понятия, описывать некоторые факторы задачи или приклад- ной области на ранних этапах, начиная с исследования. Данными факторами яв- ляются КС, С-свойства и некоторые дру- гие. Подобное описание задачи в рамках DS-теории создает предпосылки для по- степенного упразднения этапов алгорит- мизации и программирования, как наиболее насыщенных в интеллектуаль- ном плане. 1. Колесник В.Г. DS-теория как прототип теории прикладных алгоритмов // Пробле- ми програмування. – 2012. – № 1. – С. 17–33. 2. Robert Harper. Existential Type. What, If Anything, Is A Declarative Language? 18 July 2013. 3. Lloyd J.W. Practical Advantages of Declara- tive Programming. GULP-PRODE'94 1994 Joint Conference on Declarative Programming. Peniscola (Spain), September 19–22, 1994. 4. Дал У., Дейкстра Э., Хоор К. Структурное программирование (Математическое обес- печение ЭВМ). – М.: Мир, 1975. – 248 с. Получено 24.09.2014 Об авторе: Колесник Валерий Георгиевич, старший научный сотрудник кафедры АПП. Место работы автора: Донбасская государственная машиностроительная академия. г. Краматорск, ул. Шкадинова, 72, п/я 13.

DS-theory. Presentation of canonical algorithm by means of algorithmic language

Institution

Ähnliche Einträge