DS-theory. The research of P-data factors formating
This work continues the presentment of the theory of the decomposition schemes as the theory of applied algorithms. The mechanism of conversion of a decomposition scheme into a real applied algorithm conditioned by the variety of data storage forms on the data carriers has been considered. Data stor...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
PROBLEMS IN PROGRAMMING
2018
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/209 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозитарії
Problems in programming| _version_ | 1859475814947487744 |
|---|---|
| author | Kolesnyk, V.G. |
| author_facet | Kolesnyk, V.G. |
| author_sort | Kolesnyk, V.G. |
| baseUrl_str | https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| collection | OJS |
| datestamp_date | 2024-04-28T11:59:06Z |
| description | This work continues the presentment of the theory of the decomposition schemes as the theory of applied algorithms. The mechanism of conversion of a decomposition scheme into a real applied algorithm conditioned by the variety of data storage forms on the data carriers has been considered. Data storage portion as a phenomenon of electronic data processing has been described and there has also been suggested a general concept of a storage portion. The factors which generate the need for formatting and reformatting the data have been described. Generalized picture of data formatting has been given. The group of algorithmic constructions which realize the procedures of formatting and reformatting of the data for the general case has been suggested. The fact that within the theory of the decomposition schemes there exist considerably more circumstances of combining and cooperation of the storage portions than described in this work has been clarified. The mechanism of the canonic algorithm and synthesis of the algorithmic constructions which realize the procedures of data formatting has been suggested. The process of putting changes into the canonic algorithm is logical and methodic.Problems in programming 2016; 4: 14-26 |
| first_indexed | 2025-07-17T09:33:31Z |
| format | Article |
| fulltext |
Теоретичні та методологічні основи програмування
© В.Г. Колесник, 2016
14 ISSN 1727-4907. Проблеми програмування. 2016. № 4
УДК 004.424, 004.415
В.Г. Колесник
DS-ТЕОРИЯ.
ИССЛЕДОВАНИЕ ФАКТОРОВ ФОРМАТИРОВАНИЯ
Р-ДАННЫХ
В этой работе продолжается изложение теории схем декомпозиции как теории прикладных алгоритмов.
Рассматривается механизм преобразования схемы декомпозиции в реальный прикладной алгоритм,
обусловленный разнообразием способов хранения данных на носителях информации. Описана порция
хранения данных как явление электронной обработки данных и предложено обобщенное понятие пор-
ции хранения. Описаны факторы, которые порождают необходимость форматирования и реформатиро-
вания данных. Описана обобщенная картина форматирования данных. Предложена группа алгоритми-
ческих конструкций, которые реализуют процедуры форматирования и реформатирования данных для
общего случая. Уточняется тот факт, что в рамках теории схем декомпозиции существует значительно
больше обстоятельств сочетания и взаимодействия порций хранения, чем описано в работе. Предложен
механизм синтеза канонического алгоритма и алгоритмических конструкций, которые реализуют про-
цедуры форматирования данных. Процесс внесения изменений в канонический алгоритм последова-
тельный и методичный.
Ключевые слова: алгоритм, алгоритмическая конструкция, порция хранения, данное, узел, дерево,
форматирование.
Введение
В этой работе наряду с [1–4] про-
должается изложение теории схем деком-
позиции как теории прикладных алгорит-
мов. Рассматривается еще один аспект ме-
ханизма преобразования схемы декомпо-
зиции (DS) в реальный прикладной алго-
ритм. В работе [2] было продемонстриро-
вана возможность подобного преобразова-
ния. Канонический алгоритм (КА), постро-
енный на основании дерева полной схемы
декомпозиции (DPS), задает структуру
программы в целом. DS имеет в качестве
компонент (строительных клеток) алго-
ритмические конструкции узла (АКУ).
АКУ преобразуется в текст программы.
Одна АКУ реализуется одним параграфом.
Вся DS превращается в логически завер-
шенную программу. В работах [3, 4] рас-
смотрен аспект деления Р-данных (понятие
введено в [1]) при хранении их на реаль-
ных носителях.
Группа алгоритмов, рассматривае-
мых в статье, имеют отношение к проек-
тированию следующих алгоритмических
явлений:
отделение контента от формати-
рования [5];
упаковка-распаковка данных в
пакетах для передачи данных в сетях [6];
конвертация данных [7];
создание табличных выходных
форм [8];
стилевое форматирование веб-
страниц [9] и т. п.
В настоящее время ни в практиче-
ском плане, ни на теоретическом уровне не
существует обобщенной концептуальной
алгоритмической модели, которая могла
бы облегчить проектирование данной
группы алгоритмов. Далее предпринима-
ется попытка создать обобщенную картину
этой группы алгоритмов, с последующей
целью создать концептуальную алгорит-
мическую модель. Анализ проводится в
контексте развития DS-теории.
Описание порций хранения
Р-данных
Порция хранения. В DS-теории
внешним носителем есть А-лента. Порция
хранения Р-данных, которая записывается
и считывается с А-ленты – это запись.
Размер записи не оговаривается. Предпо-
лагается, что запись по размеру совпадает
с размером, сохраняемого в ней Эл-
данного или простого А-данного. Из запи-
сей на А-ленте составляются подобласти.
Теоретичні та методологічні основи програмування
15
Но “запись” и “подобласть” – это не тех-
нические, а концептуальные понятия DS-
теории. В практике электронной обработки
данных обмен информации между компь-
ютером и внешними устройствами выпол-
няется блоками или порциями. В рамках
статьи будет использоваться термин “пор-
ция хранения” (ПХ). Размеры ПХ, как пра-
вило, не совпадают ни с размерами запи-
сей (понятие DS-теории) и подобластей, ни
с размерами их содержимого – Эл-данных
или простых А-данных. Из-за этого необ-
ходимо включать в алгоритм конструкции
форматирования Р-данных. Факторы, ко-
торые учитываются при размещении фор-
матированных Р-данных в ПХ, называются
алгоритмически релевантными факторами
форматирования Р-данных (АРФФ).
При выводе Р-данных на реальные
носители информации записи абстрактной
длины и подобласти должны быть вложе-
ны в тот формат, в котором они будут хра-
ниться на этих носителях, – должны быть
форматированы1. Если размер ПХ больше
размера Р-данного, то форматирование за-
ключается в том, чтобы собрать несколько
Р-данных, чтобы укомплектовать ПХ и за-
тем его вывести. Если размер ПХ меньше
размера Р-данного, то форматирование за-
ключается в том, чтобы разделить
Р-данное на несколько ПХ, а потом их вы-
вести. При вводе информации с реальных
носителей должны быть восстановлены2
абстрактные записи с Р-данными предна-
1 Форматирование текста, выполняемое редакто-
рами текстов, – это частный случай форматирова-
ния Р-данных. Генерация кода этих программ,
выполняемая транслятором, содержит процедуры
форматирования. Вывод сообщения на экран мо-
нитора в процессе диалога в социальной сети тоже
включает процедуру форматирования в понима-
нии DS-теории.
2 Не существует термина общего плана для всех
алгоритмических явлений, связанных с разделени-
ем контента и форматирования, которым можно
было бы обозначить процесс восстановления Р-
данного – снятие или упразднение формы, в кото-
рой оно сохранялось. Наиболее близкое по смыслу
понятие – “деконструкция”, но это из другой сфе-
ры деятельности. Понятия “распаковка”, “разар-
хивирование”, “реформатирование” или “дефор-
матирования” (unformat) – ассоциируются с этим
процессом, но не совпадают с его сутью полно-
стью. В DS-теории с некоторой степенью услов-
ности используется понятие “реформатирование”.
значенными для обработки. Если размер
ПХ больше размера Р-данного, то рефор-
матирование заключается в том, чтобы
вычленить несколько Р-данных из уком-
плектованной ими ПХ для последующей
их обработки. Если размер ПХ меньше
размера Р-данного, то реформатирование
заключается в том, чтобы собрать ПХ ко-
торыми укомплектовано Р-данное для по-
следующей их обработки. Здесь очень ко-
ротко описаны процедуры форматирова-
ния-реформатирования (ФРФ) Р-данных.
Основной аспект процедур ФРФ – это со-
гласование размеров Р-данных и ПХ.
Цель работы. Показать обобщен-
ную картину форматирования Р-данных, а
также описать (очертить) группу алгорит-
мических конструкций, которые реализу-
ют процедуры ФРФ Р-данных. Описать
группу АРФФ и то, как эти факторы влия-
ют на канонический алгоритм. Описать те
изменения, которые необходимо внести в
канонический алгоритм, чтобы организо-
вать Р-данные для реализации расчета
А-зависимостей в виде одного непрерыв-
ного потока – так, как будто они в есте-
ственной для DS-теории форме.
Изменения, которые должны быть
внесены в канонический алгоритм, это
операторы или алгоритмические кон-
струкции (АК). Далее они будут либо пол-
ностью приведены, либо бегло описаны.
Технически в условиях статьи невозможно
показать весь набор изменений, обуслов-
ленных группой АРФФ. При анализе алго-
ритма объединения Р-данных будет обра-
щаться внимание на то, появляется ли си-
нергетический эффект [3].
Структура порции хранения. В
рамках DS-теории предполагается, что все
Р-данные состоят из знаков (цифры, бук-
вы, знаки препинания, специальные сим-
волы). Понятие “знак” есть прототип по-
нятия “байт”. С точки зрения внутреннего
закодированного представления, инфор-
мацию аудио-, видео- и любого другого
вида файлов можно рассматривать как со-
стоящую из знаков. Все Р-данные могут
быть измерены количеством представляе-
мых ими знаков. Аналогично могут быть
измерены и ПХ количеством знаков, кото-
Теоретичні та методологічні основи програмування
16
рые они содержат на носителе. ПХ – это
обобщения таких понятий как:
магнитная лента – бобина, файл, блок;
магнитный диск (физическая структу-
ра) – диск, дорожка, сектор;
магнитный диск (логическая структу-
ра) – диск, логический диск, сектор;
электронный документ – страница,
строка, знак;
бумажный документ – [книга], [раз-
дел], страница, строка, знак и т. п.
Многообразие порций хранения по-
рождается многообразием видов носителей
(рис. 1). Различной может быть также
вложенность ПХ. Так, например, страницу
текста можно рассматривать состоящей из
строк, но также состоящей из абзацев и
наоборот. Компоненты, из которых состо-
ят более сложные ПХ, могут быть различ-
ных видов и, возможно, различной длины.
В файлах – это записи разных типов, а в
документе строки различной длины. Наря-
ду с вложенностью Р-данных существует
вложенность реальных ПХ и вложенность
абстрактных ПХ. Вложенность ПХ (струк-
тура ПХ) на А-ленте изображается дере-
вом3. В практике обработки данных могут
использоваться ПХ, для измерения кото-
рых могут потребоваться и более двух ко-
ординат. Если для определения размера
реального носителя используются две ко-
ординаты, то сложность структуры ПХ
возрастает4.
С точки зрения длины простейшими
Р-данными (ПРД) – Эл-данные и простые
А-данные. Внутреннее представление чис-
ловой, текстовой информации или инфор-
мации иных видов в DS-теории не рас-
сматривается. Р-данные – это только це-
почки знаков или символов. Длина их из-
вестна перед началом обработки.
Простейшие Р-данные в практике
электронной обработки могут быть также
3 На рисунке 1, а показана структура ПХ в формате
FS [1]. На рис. 1, б и 1, в показаны структуры ПХ в
упрощенном виде. На рис. 1, г показана структура
ПХ в общем виде для случая, когда в каждой ПХ
содержится компонента только одного вида – в
дереве только одна ветвь.
4 В работе не рассматриваются ПХ, размеры кото-
рых определяются двумя координатами.
переменной и неопределенной длины.
Размеры их должны быть известны перед
началом работы с ними. В данной работе
предполагается, что перед началом работы
по ФРФ, длина Р-данного известна. Ситу-
ация, в которой для определения Р-данных
переменной или неопределенной длины,
необходимо выполнять предварительный
проход вдоль цепочки Р-данных на
А-ленте или в А-памяти в работе не рас-
сматривается.
Рис. 1. Виды порций
хранения (ПХ)
а
Электронный
документ
Строки
Q
Окно
Знаки
Строка
Окна
Знак
г
б
Знак
Электронный
документ
Окно
Строка
в
Книга
Раздел
Страница
Строка
Знак
ПХ0
ПХi
ПХn
Теоретичні та методологічні основи програмування
17
Форматирование Р-данных
Отношения между структурами
ПХ и Р-данными. Процедурам ФРФ
могут подвергаться Р-данные всех видов,
это: простые А-данные (рис. 2, а), расши-
ренные А-данные (рис. 2, б), сложные
А-данные (рис. 2, в), простые С-свойства,
расширенные С-свойства (рис. 2, г), слож-
ные С-свойства. ПХ, для которых приме-
няются процедуры ФРФ, могут быть про-
стыми (рис. 2, д), составными (рис. 2, е) а
также могут быть компонентами более
сложных ПХ (рис. 2, ж). Таким образом,
общий вид взаимодействия Р-данных и ПХ
посредством процедур ФРФ показан на
рис. 2, з. Двунаправленная двойная стрел-
ка на этом рисунке и в дальнейшем
будет указывать на то, какое именно
Р-данное взаимодействует с конкретной
ПХ. Это значит, что это Р-данное будет
при вводе изменено в соответствии с
форматом указанной ПХ. При выводе
это Р-данное будет реформатировано (из-
влечено или освобождено от формата
ПХ для последующей обработки). ПХ,
на которое указывает стрелка, называется
взаимодействующей порцией хранения
(ПХВ). Простейшие, несоставные ПХ обо-
значаются аббревиатурой ПХП, – это ли-
стья в дереве, которое изображает струк-
туру ПХ.
Все ПХ имеют свои атрибуты. Су-
ществование их связано со способом хра-
нения информации на носителях. Иногда
объем ПХ задается Р-данным и учитывая
это соответствующий атрибут ПХ форми-
руется перед началом и после форматиро-
вания Р-данного. Связь Р-данного и соот-
ветствующего ПХ обозначается аббревиа-
турой ПХК (порция хранения, коррели-
рующая с Р-данным). На чертеже такая
связь обозначается двунаправленной оди-
нарной стрелкой. ПХК всегда больше
ПХВ. В терминах деревьев это значит, что
Рис. 2. Варианты взаимодействия
Р-данных и ПХ
а
ПХ
б
ПХ
в
ПХ
г
ПХ
д
ПХ
е
ПХ0
ПХn
ж
ПХ1
ПХ0
з
ПХJ
ПХm
ПХ0
Р-данное
и
ПХВ
ПХm
ПХ0
Р-данное
ПХК
Теоретичні та методологічні основи програмування
18
узел ПХК всегда расположен в дереве
выше, чем узел ПХВ (рис. 2, и). ПХК мо-
жет быть более одной.
Операторы форматирования. В
работе [2] используются операторы READ
и WRITE, которые являются компонента-
ми гипотетического языка, используемого
только для иллюстрации алгоритмиче-
ских конструкций в рамках изложения
DS-теории. Эти операторы обеспечивают
ввод и вывод записей с А-ленты [2]. Но с
точки зрения АРФФ, операторы READ
используются для ввода ПХ (WRITE – для
вывода ПХ), а для АК, которые реали-
зуют процедуры ФРФ, вводятся операто-
ры UNPACK – для реформатирования
Р-данных и PACK – для форматирования5
Р-данных.
ПХ вводится оператором READ в
поименованный участок А-памяти [2]. С
этим участком соотносятся три служебных
Эл-данных: длина участка (префикс имени
– LNC_), адрес внутри участка (префикс
имени – APH_) и количество переносимых
символов (префикс имени LFR_). После
ввода выполняется реформатирование ин-
формации в Р-данное. Перед выводом в
участок ПХ вводится форматированная
информация и затем оператором WRITE
выводится на А-ленту. С учетом обработ-
ки ПХ операторы READ и WRITE допол-
няются атрибутами INTO и FROM соот-
ветственно.
READ имя_ленты INTO
имя_участка_ПХ – ввод ПХ с А-ленты
имя_ленты в участок ПХ
имя_участка_ПХ;
WRITE имя_ленты FROM
имя_участка_ПХ – вывод ПХ на А-ленту
имя_ленты с участка ПХ
имя_участка_ПХ.
Р-данное, подвергающееся проце-
дуре ФРФ, рассматривается как строка
символов. С ним соотносится два служеб-
ных Эл-данных: длина Р-данного (префикс
5 Операторы PACK и UNPACK гипотетические и
могут иметь большее или меньшее функциональ-
ное наполнение, но вложено именно такое, что поз-
волит лучше иллюстрировать АК реализующие
процедуры ФРФ.
имени – LNR_) и адрес внутри участка за-
нимаемого Р-данным (префикс имени –
ARD_). Формат оператора PACK следую-
щий: PACK имя_Р-данного INTO
имя_участка_ПХ (количество_пере-
носимых_символов) – перенос Р-данного
имя_Р-данного или его фрагмента в уча-
сток ПХ имя_участка_ПХ.
Перед выполнением оператора
PACK должны быть определены: адрес в
участке Р-данного, количество переноси-
мых символов и адрес в участке ПХ.
Формат оператора UNPACK следу-
ющий: UNPACK имя_Р-данного FROM
имя_участка_ПХ (количество_пере-
носимых_символов) – перенос содержимо-
го участка ПХ имя_участка_ПХ или его
части в Р-данное имя_Р-данного. Перед
выполнением оператора UNPACK должны
быть определены: адрес в ПХ, количество
переносимых символов и адрес в участке
Р-данного.
Принцип работы операторов PACK
и UNPACK рассматривается далее.
Описание алгоритмов
форматирования Р-данных
Отношения между ПРД и ПХ.
Есть три варианта реформатирования
Р-данных при вводе. Во всех случаях опе-
ратор UNPACK переносит информацию из
ПХВ в Р-данное. Во всех вариантах А1 –
имя А-ленты, NP – имя участка ПХВ, NRD
– имя ПРД.
1. Длина ПРД равна длине ПХВ. АК
имеет вид:
LFR_NP = LNC_NP
READ A1 INTO NP
UNPACK NRD FROM NP (LFR_NP)
Алгоритм 1
2. Длина ПРД больше длины ПХВ.
АК имеет вид:
LFR_NP = LNC_NP
READ A1 INTO NP
ARD_ NRD = 1
PERFORM AA UNTIL (ARD_NRD ≥
LNR_NRD)
{Адрес очередной части Р-данного
больше размера Р-данного}
Теоретичні та методологічні основи програмування
19
…
AA: BEGIN
UNPACK NRD FROM NP (LFR_NP)
ARD_ NRD = ARD_ NRD + LNC_NP
END AA
Алгоритм 2
После выполнения оператора
UNPACK увеличен адрес для загрузки
очередной порции информации в Р-данном
на размер ПХВ.
3. Длина ПРД меньше длины ПХВ.
АК имеет вид:
{Перед первым выполнением UNPACK}
LFR_NP = LNC_NRD
READ A1 INTO NP
APH_NP = 1
…
UNPACK NRD FROM NP (LFR_NP)
APH_NP = APH_NP + LNC_NRD
IF (APH_NP ≥ LNC_NP)
{Адрес очередной части ПХВ больше раз-
мера ПХВ}
READ A1 INTO NP
APH_NP = 1
ENDIF
Алгоритм 3
После выполнения оператора
UNPACK увеличен адрес для чтения оче-
редной порции информации в ПХВ на
размер Р-данного.
Есть три варианта форматирования
Р-данных при выводе. Во всех случаях
оператор PACK переносит информацию из
Р-данного в ПХВ. Во всех вариантах А1 –
имя А-ленты, NP – имя участка ПХВ, NRD
– имя ПРД.
1. Длина ПРД равна длине ПХВ. АК
имеет вид:
LFR_NP = LNC_NRD
PACK NRD INTO NP (LFR_NP)
WRITE A1 FROM NP
Алгоритм 4
2. Длина ПРД больше длины ПХВ.
АК имеет вид:
LFR_NP = LNC_NP
ARD_NRD = 1
PERFORM AA (ARD_NRD ≥ LNR_NRD)
{Адрес очередной части Р-данного
больше размера Р-данного}
…
AA: BEGIN
PACK NRD INTO NP (LFR_NP)
WRITE A1 FROM NP
ARD_NRD = ARD_NRD + LNC_NP
END AA
Алгоритм 5
После выполнения оператора PACK
увеличен адрес в Р-данном на размер ПХВ
для чтения очередной порции информа-
ции.
3. Длина ПРД меньше длины ПХВ.
АК имеет вид:
{Перед первым выполнением PACK}
LFR_NP = LNC_NRD
APH_NP = 1
…
PACK NRD INTO NP (LFR_NP)
APH_NP = APH_NP + LNR_ARD
IF (APH_NP ≥ LNC_NP) THEN
{Адрес очередной части ПХВ больше раз-
мера ПХВ – ПХВ заполнена}
WRITE A1 FROM NP
APH_NP = 1
ENDIF
Алгоритм 6
После выполнения оператора PACK
увеличен адрес на размер ПРД в участке
ПХВ для загрузки очередной порции ин-
формации.
Форматирование С-данного при
выводе6. При форматировании с последу-
ющим выводом простого или расширенно-
го С-данного нет смысла сопоставлять его
размер с размером ПХВ, так как размер
С-данного не постоянный. Кроме того, об-
работка С-данного происходит последова-
тельным перебором его компонент – про-
стейших Р-данных (Эл-данных и простых
А-данных) и, соответственно, последова-
тельно форматируются его компоненты.
Именно их размеры и следует сопостав-
6 Далее в работе рассматриваются только процеду-
ры форматирования при выводе.
Теоретичні та методологічні основи програмування
20
лять с размерами ПХВ. Далее рассматри-
ваются пять вариантов (алгоритмов) фор-
матирования. Во всех вариантах А1 – имя
А-ленты, NP – имя участка ПХВ, NRD –
имя ПРД – компоненты С-данного, NRC –
имя С-данного.
1. Длина ПРД (компоненты С-
данного) равна длине ПХВ. АК имеет вид:
AA: BEGIN
LFR_NP = LNC_NRD
PERFORM BB ({до конца С-данного})
…
END AA
BB: BEGIN
PACK NRD INTO NP (LFR_NP)
WRITE A1 FROM NP
END BB
Алгоритм 7
2. Длина ПРД больше длины ПХВ.
АК имеет вид:
AA: BEGIN
LFR_NP = LNC_NP
PERFORM BB ({до конца С-данного})
…
END AA
BB: BEGIN
ARD_NRD = 1
PERFORM CC (ARD_NRD ≥ LNR_NRD)
{до конца Р-данного адрес очередной ча-
сти Р-данного больше размера Р-данного}
WRITE A1 FROM NP
END BB
CC: BEGIN
PACK NRD INTO NP (LFR_NP)
ARD_NRD = ARD_NRD + LFR_NP
END CC
Алгоритм 8
3. Длина ПРД меньше длины ПХВ.
АК имеет вид:
AA: BEGIN
{Перед первым выполнением PACK}
LFR_NP = LNC_NRD
APH_NP = 1
PERFORM BB ({до конца С-данного})
…
END AA
BB: BEGIN
PACK NRD INTO NP (LFR_NP)
APH_NP = APH_NP + LNR_ARD
IF (APH_NP ≥ LNC_NP) THEN
{Адрес очередной части ПХВ больше
размера ПХВ – ПХВ заполнена}
WRITE A1 FROM NP
APH_NP = 1
ENDIF
END BB
Алгоритм 9
В следующем варианте учитывается
то, что размер ПРД может быть не крат-
ный размеру ПХВ, но последний фрагмент
ПРД заполнит ПХВ частично.
4. Длина ПРД больше длины ПХВ.
PRIZN – рабочее Р-данное. АК имеет вид:
AA: BEGIN
APH_NP = 1
ARD_NRD = 1
PERFORM BB ({до конца С-данного})
WRITE A1 FROM NP
…
END AA
BB: BEGIN
PRIZN = 0
{Р-данное не упаковано}
PERFORM CC ({до конца С-данного})
OR (PRIZN = 1)
{Р-данное упаковано}
END BB
CC: BEGIN
IF (LNR_NRD - ARD_NRD + 1 > LNC_NP
– APH_NP + 1) THEN
{Остающееся количество символов Р-
данного больше свободного участка ПХВ}
LFR_NP = LNC_NP - APH_NP + 1
ELSE
{Остающееся количество символов Р-
данного меньше или равно свободному
участку ПХВ}
LFR_NP = LNR_NRD - ARD_NRD + 1
ENDIF
PACK NRD INTO NP (LFR_NP)
APH_NP = APH_NP + LFR_NP
IF (APH_NP ≥ LNC_NP) THEN
Теоретичні та методологічні основи програмування
21
{ПХВ заполнена}
WRITE A1 FROM NP
APH_NP = 1
ENDIF
ARD_NRD = ARD_NRD + LFR_NP
IF (ARD_NRD > LNR_NRD) THEN
PRIZN = 1
ARD_NRD = 1
ENDIF
END CC
Алгоритм 10
Если форматируется С-данное
(NRC), но с ПХ взаимодействует компо-
нента С-данного – Р-данное (NRD), то в
параграфе AA нужно убрать операторы:
APH_NP = 1
ARD_NRD = 1
…
WRITE A1 FROM NP
А параграф BB будет иметь вид:
BB: BEGIN
APH_NP = 1
ARD_NRD = 1
PERFORM CC (ARD_NRD ≥ LNR_NRD)
{Адрес очередной части Р-данного боль-
ше размера Р-данного – Р-данное упакова-
но}
WRITE A1 FROM NP
END BB
Алгоритм 11
Длина Р-данного меньше длины
ПХВ и, что размер Р-данного может быть
не кратный размеру ПХВ. Данный случай
– это частный случай ситуации в п. 4.
С-данное в последних пяти ситуа-
циях – это FS двух уровней. АКУ-
обусловленность для этих алгоритмов со-
хранялась бы в том случае, если бы DA
тоже была бы двух уровней. Но в п. 4 по-
является параграф CC – это вследствие то-
го, что размер Р-данного превосходит раз-
мер ПХВ. АЗ-параграфом здесь есть пара-
граф BB.
Алгоритм форматирования будет
сохраняться и в том случае, если в ПХВ
будут форматироваться и перемещаться
более одного ПРД и хотя бы одно из них
будет отличаться размером от остальных.
При этом хотя бы одно из ПРД имеет раз-
мер не кратный размеру ПХВ.
Форматирование FS в простых
ПХ. Если форматированию подлежит
сложное С-свойство (FS трех уровней –
рис. 3, а), то на каком бы уровне не нахо-
дились ПРД, в АЗ-параграфах будут АК
реализующие процедуры ФРФ. При этом
не имеет значения соотношения размеров
между ПРД и ПХ, так как применяется
одна и та же АК – параграф CC алгоритма
10. Так как каждый из таких параграфов
сочленяется с DA иерархическим сочле-
нением, то АКУ-обусловленность про-
граммы отсутствует. Соответствующий
DA показан на рис. 3, б.
Произвольная FS может содержать
в каждом узле на каждом уровне произ-
вольное количество ПРД. Кроме того, во
всех узлах кроме листьев могут отсут-
ствовать ПРД. Лист должен содержать
хотя бы одно ПРД. Пример, на рис. 3, в
Рис. 3. Форматирование FS
AA
BB
CC
DD
в
а
EE
Q
S
б
R
P
An-2
An-1
H1
An
г
H3
A0
H2
Теоретичні та методологічні основи програмування
22
узел уровня n-1 содержит два ПРД – Q и
R; узлы нулевого и n-2 уровней не содер-
жат ПРД; узел уровня n содержит одно
ПРД – S. DA программы реализующей
процедуры ФРФ при выводе для соответ-
ствующей FS будет содержать в каждом
АЗ-параграфе цикл для форматирования
ПРД. Тело цикла – это вышеупомянутый
параграф CC алгоритма 10. DA для фор-
матирования FS на рис. 3, в показана на
рис. 3, г.
ПХВ может соотносится с
С-данными не только предпоследних, но
любых уровней FS. Узел, который соот-
носится с ПХВ, где бы он не находился в
FS, повлечет в DA изменения только в
АЗ-параграфе. Это начало и завершение
работы с ПХВ – те действия, что выпол-
няют операторы APH_NP = 1, ARD_NRD
= 1 и WRITE A1 FROM NP в параграфе
AA алгоритма 10.
Описание алгоритмов
взаимодействия с составными ПХ
Форматирование Р-данных с со-
ставными ПХ. Как упоминалось выше,
ПХ могут быть составными. Этот фактор
тоже рассматривается при построении
АК, реализующих процедуры ФРФ. Ана-
лиз АК проводится в следующих ситуа-
циях.
ПРД переносится в ПХВ. Размеры
Р-данного и ПХВ совпадают. ПХВ состо-
ит из кратного количества ПХП меньших
размеров (рис. 4, а). Во всех вариантах А1
– имя А-ленты, NP – имя участка ПХВ,
NPP – имя участка ПХП, NRD – имя ПРД.
ПХВ содержит кратное количество ПХП.
АК имеет вид:
AA: BEGIN
LFR_NPP = LNC_NPP
ARD_NRD = 1
APH_NP = 1
PERFORM BB (ARD_NRD ≥ LNR_NRD)
{До конца Р-данного}
WRITE A1 FROM NP
…
END AA
BB: BEGIN
PACK NRD INTO NP (LFR_NPP)
ARD_NRD = ARD_NRD + LNC_NPP
ARD_NP = ARD_NP + LNC_NPP
END BB
Алгоритм 12
Параграф BB необходим для того,
чтобы заполнять ПХВ фрагментами ПРД
равными по длине размерам ПХП. Эта си-
туация отличается параграфом алгоритма
12 от ситуации реализуемой алгоритмом 4.
Соответственно, в алгоритмах 5 и 6 тоже
появится параграф, который выполняет ту
же функцию форматирование ПХП. То
есть, то обстоятельство, что ПХВ состав-
ная, влечет в DA дополнительный пара-
граф. Этот дополнительный параграф
наряду с фактором несовпадения размеров
ПРД и ПХ тоже влечет нарушение АКУ-
обусловленности.
Анализ АК для форматирования
С-данного показывает, что необходимо
учитывать размеры компонент Р-данного и
размеры ПХП. Прежде всего эти размеры
определяют содержимое АК. Далее рас-
сматриваются три ситуации форматирова-
ния С-данных в сложных ПХ.
1. С-данное форматируется и пере-
носится в составную ПХВ (рис. 4, б). Ком-
понента С-данного – ПРД имеет длину
больше длины ПХП. Прототипом алго-
ритма необходимого для этой ситуации
есть алгоритм 8. После внесения соответ-
ствующих изменений АК имеет вид:
AA
BB
CC
в
а
б
Рис. 4. Форматирование составных ПХ
Р-данное: NRD ПХВ: NP
ПХП: NPP
С-данное: NRC
Р-данное: NRD
ПХВ: NP
ПХП: NPP
Теоретичні та методологічні основи програмування
23
AA: BEGIN
LFR_NP = LNC_NP
PERFORM BB ({до конца С-данного –
NRC})
…
END AA
BB: BEGIN
ARD_NRD = 1
PERFORM CC ({до конца C-данного –
NRC})
OR (ARD_NRD ≥ LNR_NRD)
{до конца Р-данного – NRD}
WRITE A1 FROM NP
END BB
CC: BEGIN
PACK NRD INTO NP (LFR_NP)
ARD_NRD = ARD_NRD + LFR_NP
END CC
Алгоритм 13
Параграф BB здесь появляется для
того, чтобы разделить на части и формати-
ровать ПРД (NRD). Этот параграф нару-
шает АКУ-обусловленность алгоритма.
Дерево алгоритма не совпадает с деревом
FS.
2. С-данное форматируется и пере-
носится в составную ПХВ (рис. 4, б). Ком-
понента С-данного – ПРД имеет длину
меньше длины ПХП. АК имеет вид:
AA: BEGIN
LFR_NP = LNC_NRD
PERFORM BB
({до конца С-данного – NRC})
…
END AA
BB: BEGIN
ARD_NRD = 1
PERFORM CC
({до конца C-данного – NRC})
OR (APH_NPP ≥ LNC_NPP)
{до конца ПХП – NPP}
WRITE A1 FROM NP
END BB
CC: BEGIN
PACK NRD INTO NP (LFR_NP)
APH_NPP = APH_NPP + LFR_NP
END CC
Алгоритм 14
Параграф BB здесь появляется для
того, чтобы форматировать и объединить
ПРД (NRD). Этот параграф нарушает
АКУ-обусловленность алгоритма.
3. В этом варианте учитывается то,
что размер ПРД может быть не кратный
размеру ПХП, но последний фрагмент
ПРД заполнит ПХВ частично. АК имеет
вид:
AA: BEGIN
APH_NP = 1
ARD_NRD = 1
PERFORM BB ({до конца С-данного})
WRITE A1 FROM NP
…
END AA
BB: BEGIN
PRIZN = 0
{ПРД не отформатировано}
PERFORM CC ({до конца С-данного})
OR (PRIZN = 1)
{ПРД отформатировано}
END BB
CC: BEGIN
IF (LNR_NRD - ARD_NRD + 1 > LNC_NP
- APH_NP + 1) THEN
{Остающееся количество символов Р-
данного больше свободного участка ПХВ}
LFR_NP = LNC_NP - APH_NP + 1
ELSE
LFR_NP = LNR_NRD - ARD_NRD + 1
ENDIF
PACK NRD INTO NP (LFR_NP)
APH_NP = APH_NP + LFR_NP
IF (APH_NP > LNC_NP) THEN
{Адрес очередной части ПХВ больше
размера ПХВ – ПХВ заполнена}
WRITE A1 FROM NP
APH_NP = 1
ENDIF
ARD_NRD = ARD_NRD + LFR_NP
IF (ARD_NRD > LNR_NRD) THEN
PRIZN = 1
ARD_NRD = 1
ENDIF
END CC
Алгоритм 15
Теоретичні та методологічні основи програмування
24
В процессе построения алгоритмов
13 и 14 сопоставлялись размеры двух со-
вокупностей: размер ПРД и размер ПХП.
Большая из них порождала параграф (и,
соответственно, дополнительный цикл).
Этот цикл должен был заполнить боль-
шую из совокупностей компонентами
меньшей совокупности. В алгоритме 15
дополнительный параграф (и цикл) по-
рожден тем, что в процессе форматирова-
ния компонентами, заполняющими ПХП,
становятся фрагменты ПРД независимо от
размеров ПРД и ПХП. 2, з и 2, и).
Форматирование FS в сложных
ПХ. Как упоминалось выше как FS, так
и структуры ПХ, в которые форматируют-
ся Р-данные, могут иметь произвольное
количество уровней. При этом необходи-
мо учитывать размеры между узлами дере-
ва последовательно всех уровней (рис. 2, з
и 2, и).
Общий подход рассматривается на
примере (рис. 5). FS имеет три уровня и
структура порций хранения имеет три
уровня. С-данные A и B имеют состоят из
произвольного количества компонент. ПХ
M состоит из 30 компонент. Длина ПРД C
– 200 знаков, а ПХП N может содержать
400 знаков. Параграф нулевого уровня со-
держит цикл который будет работать до
завершения обработки С-данного нулево-
го уровня FS – A. Вместе с завершением
этого цикла будет завершено форматиро-
вание исходной FS. Параграф первого
уровня тоже содержит цикл. Управлять
этим циклом будет большая из совокуп-
ностей – С-данное B (на первом уровне
FS) или ПХ M на первом уровне структу-
ры хранения ПХ. Здесь возможны следу-
ющие варианты:
1. B > M;
2. B < M;
3. B = M.
В первом случае цикл будет вы-
полняться до завершения обработки
С-данного B. В примере имеет место
именно эта ситуация. Построение DA
продолжается построением очередного
параграфа на уровне 2. Для этого сопо-
ставляются очередные совокупности или
ПРД. В данном случае сопоставляются
ПРД C и ПХ M.
Во втором случае цикл будет вы-
полняться до завершения обработки ПХ
M. Построение DA продолжается построе-
нием очередного параграфа на уровне 2.
Для этого сопоставляются очередные со-
вокупности или ПРД. В данном случае со-
поставляются С-данное B и ПХ N.
В третьем случае (Р-данное полно-
стью форматируется в ПХ) цикл будет вы-
полняться до завершения обработки С-
данного B. Для построения очередного па-
раграфа сопоставляются очередные сово-
купности или ПРД, которые до этого шага
не сравнивались. В данном случае сопо-
ставляются ПРД C и ПХП N.
При сравнении ПРД и ПХ (не
ПХП), учитывается, что ПРД представля-
ется как одна компонента. Соответственно,
при сравнении С-данного и ПХП, учиты-
вается, что ПХП представляется как одна
компонента. Третий случай предполагает,
что количество компонент в С-данном
равно количеству компонент в ПХ или ПХ
определяется количеством компонент С-
данного.
На рис. 5 показано как построена
DA для конкретного примера. Стрелки
указывают на то, какой объект порождает
соответствующий параграф.
AA
BB
CC
С-данное:
A
С-данное: B
ПХ: L
ПХП: N
ПРД: C
ПХ: M
DD
EE
Рис. 5. Форматирование FS в многоуров-
невых структурах ПХ
Теоретичні та методологічні основи програмування
25
Более сложная ситуация – это когда
количество уровней как в дереве FS, так и
в дереве структуры ПХ – произвольное. В
этом случае DA формируется в результате
последовательного перебора и сравнения
объектов соотносящимися с узлами дерева
FS с одной стороны и объектов соотнося-
щимися с узлами дерева структуры ПХ, с
другой стороны. Завершается перебор и
сравнение в тот момент, когда сопостав-
ляются ПРД с одной стороны и ПХП, с
другой стороны. В результате сравнения
порождается один или два параграфа в за-
висимости от соотношения значений ПРД
и ПХП. Алгоритмы для возможных вари-
антов описаны выше.
Общий случай предполагает следу-
ющее. Количество уровней в деревьях FS и
структуры ПХ может не совпадать. ПХ
могут быть различных типов и размеров.
Как дерево FS, так и дерево структуры ПХ
могут иметь произвольное количество вет-
вей. ПХ могут быть сгруппированы на
А-ленте в подобласти.
Может быть более одной структуры
ПХ в которые форматируются FS.
Совмещение дерева FS и дерева
структуры ПХ, порождает DA. Другими
словами производится синтез дерева FS и
дерева структуры ПХ или просто – произ-
водится синтез деревьев.
Выводы
Описаны порции хранения Р-дан-
ных как явление электронной обработки
данных и предложено обобщенное понятие
порции хранения. Описаны факторы, кото-
рые порождают необходимость формати-
рования и реформатирования Р-данных.
Описана обобщенная картина форматиро-
вания Р-данных. Предложена группа алго-
ритмических конструкций, которые реали-
зуют процедуры ФРФ Р-данных для неко-
торого уровня обобщения. Несоответствие
размеров Р-данных и ПХ порождает допол-
нительные параграфы в программе (узлы
в DA), что нарушает АКУ-обусловленность
канонического алгоритма. Процесс внесе-
ния изменений в канонический алгоритм
обусловленный результатами целенаправ-
ленных исследований.
1. Колесник В.Г. DS-теория как прототип
теории прикладных алгоритмов // Про-
блеми програмування. – 2012. – № 1. –
С. 17–33.
2. Колесник В.Г. DS-теория. Представле-
ние канонического алгоритма с помо-
щью алгоритмического языка // Про-
блеми програмування. – 2015. – № 1. –
С. 3–18.
3. Колесник В.Г. DS-теория. Исследова-
ние факторов деления Р-данных с це-
лью генерации прикладных алгорит-
мов. Первая часть // Проблеми програ-
мування. – 2015. – № 3. – С. 3–12 .
4. Колесник В.Г. DS-теория. Исследова-
ние факторов деления Р-данных с це-
лью генерации прикладных алгорит-
мов. Вторая часть // Проблеми програ-
мування. – 2015. – № 4. – С. 3–13.
5. Mark Baker. Algorithms in Structured
Writing: Processing Structured Text
[Electronic resource] — Mode access:
http://techwhirl.com/16098-2/
6. Основы локальных сетей: Пакеты, про-
токолы и методы управления обменом.
[Электронный ресурс] // Режим доступа:
http://www.intuit.ru/studies/courses/57/57/l
ecture/1678?page=2
7. Data Translation. 1 EDI Source. [Элек-
тронный ресурс] // – Режим доступа:
http://www.1edisource.com/what-is-edi-
translation
8. System Analysis and Design. Input/Output
and Form Design [Электронный ресурс]
// Режим доступа:
http://www.systemanalysisanddesigns.com/i
nputoutput-and-form-design/
9. Справочник CSS. WebReference.ru.
[Электронный ресурс] // URL:
https://webref.ru/css
References
1. Kolesnyk V.G. DS-theory as a prototype
of the theory of applied algorithms //
Problems in programming. – 2012. – № 1.
– P. 17–33. (In Russian).
2. Kolesnyk V.G. DS-theory. Presentation of
canonical algorithm by means of algo-
rithmic language // Problems in program-
ming. – 2015. – № 1. – P. 3–18. (In Rus-
sian).
Теоретичні та методологічні основи програмування
26
3. Kolesnyk V.G. DS-theory. Research of r-
data division factors in order to generate
applied algorithms. Part 1 // Problems in
programming. – 2015. – № 3. – P. 3–12.
(In Russian).
4. Kolesnyk V.G. DS-theory. Research of r-
data division factors in order to generate
applied algorithms. Part 2 // Problems in
programming. – 2015. – № 4. – P. 3–13.
(In Russian).
5. Mark Baker. Algorithms in Structured
Writing: Processing Structured Text
[Electronic resource] — Mode access:
http://techwhirl.com/16098-2/
6. Fundamentals of LANs: Packages, proto-
cols and exchange management. [Elec-
tronic resource] — Mode access:
http://www.intuit.ru/studies/courses/57/57/l
ecture/1678?page=2 (In Russian).
7. Data Translation. 1 EDI Source. [Elec-
tronic resource] // – Mode access:
http://www.1edisource.com/what-is-edi-
translation
8. System Analysis and Design. In-
put/Output and Form Design [Electronic
resource] // Mode access:
http://www.systemanalysisanddesigns.com/i
nputoutput-and-form-design/
9. CSS Reference. WebReference.ru. [Elec-
tronic resource] // URL:
https://webref.ru/css (In Russian).
Получено 29.12.2015
Об авторе:
Колесник Валерий Георгиевич,
старший научный сотрудник
кафедры АПП.
Количество научных публикаций в
украинских изданиях – 24.
http://orcid.org/0000-0002-2313-9852.
Место работы автора:
Донбасская государственная
машиностроительная академия.
г. Краматорск, ул. Академическая, 72,
п/я 13.
|
| id | pp_isofts_kiev_ua-article-209 |
| institution | Problems in programming |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T09:33:31Z |
| publishDate | 2018 |
| publisher | PROBLEMS IN PROGRAMMING |
| record_format | ojs |
| resource_txt_mv | ppisoftskievua/9c/b5d2e043ecccf366eb7671cb2684e89c.pdf |
| spelling | pp_isofts_kiev_ua-article-2092024-04-28T11:59:06Z DS-theory. The research of P-data factors formating DS-теория. Исследование факторов форматирования Р-данных DS-теорія. Дослідження факторів форматування Р-даних Kolesnyk, V.G. algorithm; algorithmic construction; storage portion; data; node; tree; formatting UDC 004.424, 004.415 алгоритм; алгоритмическая конструкция; порция хранения; данное; узел; дерево; форматирование УДК 004.424, 004.415 алгоритм; алгоритмічна конструкція; порція зберігання; дане; вузол; дерево; форматування УДК 004.424, 004.415 This work continues the presentment of the theory of the decomposition schemes as the theory of applied algorithms. The mechanism of conversion of a decomposition scheme into a real applied algorithm conditioned by the variety of data storage forms on the data carriers has been considered. Data storage portion as a phenomenon of electronic data processing has been described and there has also been suggested a general concept of a storage portion. The factors which generate the need for formatting and reformatting the data have been described. Generalized picture of data formatting has been given. The group of algorithmic constructions which realize the procedures of formatting and reformatting of the data for the general case has been suggested. The fact that within the theory of the decomposition schemes there exist considerably more circumstances of combining and cooperation of the storage portions than described in this work has been clarified. The mechanism of the canonic algorithm and synthesis of the algorithmic constructions which realize the procedures of data formatting has been suggested. The process of putting changes into the canonic algorithm is logical and methodic.Problems in programming 2016; 4: 14-26 В этой работе продолжается изложение теории схем декомпозиции как теории прикладных алгоритмов. Рассматривается механизм преобразования схемы декомпозиции в реальный прикладной алгоритм, обусловленный разнообразием способов хранения данных на носителях информации. Описана порция хранения данных как явление электронной обработки данных и предложено обобщенное понятие порции хранения. Описаны факторы, которые порождают необходимость форматирования и реформатирования данных. Описана обобщенная картина форматирования данных. Предложена группа алгоритмических конструкций, которые реализуют процедуры форматирования и реформатирования данных для общего случая. Уточняется тот факт, что в рамках теории схем декомпозиции существует значительно больше обстоятельств сочетания и взаимодействия порций хранения, чем описано в работе. Предложен механизм синтеза канонического алгоритма и алгоритмических конструкций, которые реализуют процедуры форматирования данных. Процесс внесения изменений в канонический алгоритм последовательный и методичный.Problems in programming 2016; 4: 14-26 Уцій роботі триває виклад теорії схем декомпозиції як теорії прикладних алгоритмів. Розглядається механізм перетворення схеми декомпозиції в реальний прикладний алгоритм, обумовлений різноманітністю способів зберігання даних на носіях інформації. Описана порція зберігання даних як явище електронної обробки даних і запропоновано узагальнене поняття порції зберігання. Описано чинники, які породжують необхідність форматування і реформатування даних. Описана узагальнена картина форматування даних. Запропоновано групу алгоритмічних конструкцій, які реалізують процедури форматування і реформатування даних для загального випадку. Уточнюється той факт, що в рамках теорії схем декомпозиції існує значно більше обставин поєднання і взаємодії порцій зберігання, ніж описано в роботі. Запропоновано механізм синтезу канонічного алгоритму і алгоритмічних конструкцій, які реалізують процедури форматування даних. Процес внесення змін до канонічного алгоритму послідовний і методичний.Problems in programming 2016; 4: 14-26 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2018-07-03 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/209 10.15407/pp2016.04.014 PROBLEMS IN PROGRAMMING; No 4 (2016); 14-26 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 4 (2016); 14-26 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 4 (2016); 14-26 1727-4907 10.15407/pp2016.04 ru https://pp.isofts.kiev.ua/index.php/ojs1/article/view/209/201 Copyright (c) 2017 ПРОБЛЕМИ ПРОГРАМУВАННЯ |
| spellingShingle | algorithm algorithmic construction storage portion data node tree formatting UDC 004.424 004.415 Kolesnyk, V.G. DS-theory. The research of P-data factors formating |
| title | DS-theory. The research of P-data factors formating |
| title_alt | DS-теория. Исследование факторов форматирования Р-данных DS-теорія. Дослідження факторів форматування Р-даних |
| title_full | DS-theory. The research of P-data factors formating |
| title_fullStr | DS-theory. The research of P-data factors formating |
| title_full_unstemmed | DS-theory. The research of P-data factors formating |
| title_short | DS-theory. The research of P-data factors formating |
| title_sort | ds-theory. the research of p-data factors formating |
| topic | algorithm algorithmic construction storage portion data node tree formatting UDC 004.424 004.415 |
| topic_facet | algorithm algorithmic construction storage portion data node tree formatting UDC 004.424 004.415 алгоритм алгоритмическая конструкция порция хранения данное узел дерево форматирование УДК 004.424 004.415 алгоритм алгоритмічна конструкція порція зберігання дане вузол дерево форматування УДК 004.424 004.415 |
| url | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/209 |
| work_keys_str_mv | AT kolesnykvg dstheorytheresearchofpdatafactorsformating AT kolesnykvg dsteoriâissledovaniefaktorovformatirovaniârdannyh AT kolesnykvg dsteoríâdoslídžennâfaktorívformatuvannârdanih |