DS-theory. Research of R-data division factors in order to generate applied algorithms. Part 2
This is the next essay from the cycle describing the theory of decomposition schemes as the theory of applied algorithms. A decomposition scheme is being considered as a prototype of an applied algorithm. The aim of the essay is to consider the turning of a decomposition scheme into an algorithm in...
Gespeichert in:
| Datum: | 2017 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Russisch |
| Veröffentlicht: |
PROBLEMS IN PROGRAMMING
2017
|
| Schlagworte: | |
| Online Zugang: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/155 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Institution
Problems in programming| _version_ | 1859475708366028800 |
|---|---|
| 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 | 2018-07-12T14:26:34Z |
| description | This is the next essay from the cycle describing the theory of decomposition schemes as the theory of applied algorithms. A decomposition scheme is being considered as a prototype of an applied algorithm. The aim of the essay is to consider the turning of a decomposition scheme into an algorithm in the case when the processed input P-data are placed in various media. R-data kinds of division are described and factors of their fragments and components placing are considered. For all the variants of R-data division the changes into the canonic algorithm which are necessary for their union are described. From the standpoint of the complexity changes in algorithm vary from primitives in several imperative operators to algorithmic constructions with loops and control constructs. For making the algorithmic constructions there is the mechanism of synthesis offered – bound to the levels of algorithm tree. For purposes of the comparative analysis the schemes of decomposition and applied algorithm there was offered the notion of NAC-conditionality as more fitting that the graph isomorphism. It is shown that description of the variants and factors of R-data division is declarative. This work endorses the idea that the theory of decomposition schemes allows to research the algorithms systematically. The aim of the research is to develop the mechanism of synthesis of the applied algorithms. The descriptions of the decomposition schemes are used as raw data for generating. |
| first_indexed | 2025-07-17T09:33:07Z |
| format | Article |
| fulltext |
Теоретичні та методологічні основи програмування
© В.Г. Колесник, 2015
ISSN 1727-4907. Проблеми програмування. 2015. № 4 3
УДК 004.424, 004.415
В.Г. Колесник
DS-ТЕОРИЯ. ИССЛЕДОВАНИЕ ФАКТОРОВ ДЕЛЕНИЯ
Р-ДАННЫХ ДЛЯ ГЕНЕРАЦИИ ПРИКЛАДНЫХ
АЛГОРИТМОВ. ЧАСТЬ 2
Статья – очередная из цикла работ описывающих теорию схем декомпозиции как теорию прикладных
алгоритмов. Схема декомпозиции рассматривается как прототип прикладного алгоритма. Цель статьи –
рассмотреть преобразование схемы декомпозиции в алгоритм для того случая, когда обрабатываемые
входные Р-данные размещены на различных носителях. Описаны виды деления Р-данных и рассмотре-
ны факторы размещения их фрагментов и компонент. Для всех вариантов деления Р-данных описаны
изменения в канонический алгоритм необходимые для их объединения. Изменения в алгоритме в плане
сложности – это и примитивы в несколько повелительных операторов, и алгоритмические конструк-
ции с циклами и управлением. Для построения алгоритмических конструкций предложен механизм
синтеза – привязка по уровням дерева алгоритма. Для сравнительного анализа зависимости между схе-
мой декомпозиции и прикладным алгоритмом предложено понятие АКУ-обусловленности как более
подходящее, чем изоморфизм графов. Показано, что описание вариантов и факторов деления Р-данных
имеет декларативный характер. Работа подтверждает идею о том, что теория схем декомпозиции поз-
воляет планомерно исследовать алгоритмы. Цель этих исследований в том, чтобы разработать меха-
низм синтеза прикладных алгоритмов. Как исходные данные для генерации используются описания
схемы декомпозиции.
Ключевые слова: алгоритм, конструкция, данные, фрагмент, структура, узел, уровень, область, пара-
граф, объединение, синтез.
3. Произвольное деление
А-данных
1. Расширенное А-данное как
компонента С-данного в трехуровневом
FS (первый вариант). Расширенное А-
данное – это компонента С-данного
(рис. 1). Первая часть А-данного, содер-
жащая одни и те же Эл-данные, размеще-
на в записях в подобласти на основной
А-ленте, а вторая часть А-данного, со-
держащая остальные Эл-данные, разме-
щена в записях в подобласти на смежной
А-ленте. С-данное, которое содержит как
компоненту разделенное А-данное, раз-
мещено в узле на первом уровне, а разде-
ленное А-данное в узле на втором уровне.
Алгоритм, который реализует объедине-
ния исходного А-данного, приведен далее
(алг. 1.4). На рис. 1, г показана DA этого
алгоритма.
Параграф, соответствующий узлу нулевого
уровня
AA: BEGIN
READ A1
READ A2
PERFORM BB (У1+).
END AA
Рис. 1. Деление А-данного
в трехуровневой FS
FS: A = {B}, B={B1,B2},
B2 = {C}, C={C1,C2}
RG1: R1 [P1], V1 [T1]
RG2: R2 [P2], V2 [T2]
а
A
B2
Q
B1
B
C2 C1
C
г
BB
CC
AA
P1
б
V1
R1
C1 D
1
T1
P2
в
R2
в
V2
V
в
Q D
2
T2
C2
д
AA
BB
DD
CC
EE
Теоретичні та методологічні основи програмування
4
Параграф, соответствующий узлу первого
уровня
BB: BEGIN
PERFORM CC (У2+).
END BB
Параграф, соответствующий узлу второго
уровня
CC: BEGIN
READ A1
READ A2
END CC
Здесь:
У1+ – условие “достигнут конец подобла-
сти, содержащей компоненты B”.
У2+ – условие “достигнут конец подобла-
сти R1”.
Алгоритм 1.4
Цикл в параграфе AA будет опре-
делен более точно в зависимости от того,
какого рода подобласть будет содержать
компоненты B С-данного A. Расположе-
ние двух операторов READ в параграфе
AA или в параграфе BB тоже зависит от
того, какого рода подобласти (R1,V1)
содержат Р-данные (P1,T1) на основной
А-ленте. Здесь CC – это АЗ-параграф, а
BB – это АЗУ-параграф. Параграф AA,
независимо от того, какая ситуация с раз-
мещением разделенного А-данного, не
меняется. Содержимое его такое, как буд-
то А-данное в узле на втором уровне не
разделено.
Подобная ситуация описанная выше
для двухуровневой FS (раздел 1 пункт 4).
Здесь, как и для упомянутой ситуации,
могут иметь место все обстоятельства раз-
мещения – порядок записей в подобластях,
наличие непродуктивных Р-данных, уком-
плектованы или нет фрагменты разделен-
ного А-данного в подобластях, где они
размещены. Для ситуации, когда записи в
подобластях и для обработки неупорядо-
чены, нет непродуктивных Р-данных и
фрагменты разделенного А-данного уком-
плектованы, приведена DA (рис. 1, д). Па-
раграфы DD и EE не АЗП-параграфы, а
дополнительные параграфы, необходимые
для реализации алгоритма. Из-за дополни-
тельных параграфов нарушается АКУ-
обусловленность алгоритма для этого
случая. Все остальные обстоятельства раз-
мещения фрагментов разделенного А-
данного тоже не меняют содержимого па-
раграфа на нулевом уровне.
2. Расширенное А-данное как
компонента С-данного в трехуровневом
FS (второй вариант). Расширенное А-
данное является компонентой С-данного
(рис. 2, а). С-данное, которое содержит
как компоненту разделенное А-данное,
размещено в узле на нулевом уровне, а
разделенное А-данное в узле на первом
уровне. Первая часть А-данного, содер-
жащая одни и те же Эл-данные, размеще-
на в записях в подобласти на основной
А-ленте, а вторая часть А-данного, со-
держащая С-данное (и, возможно Эл-
данные), размещена в подобласти на
смежной А-ленте. Соответствующий ал-
горитм как и алгоритм 1.4 имеет три
уровня. АК, содержащее цикл для объ-
единения А-данного будет в АЗУ-
параграфе на нулевом уровне. АК, обес-
печивающее чтение записей с фрагмента-
ми А-данного (первой части), будет в АЗ-
параграфе на первом уровне. Здесь же бу-
дет АК, которая обеспечит чтение второй
части разделенного А-данного со смеж-
ной А-ленты. Последняя АК будет содер-
жать цикл, который обеспечит чтение за-
писей – компонент С-данного первого
уровня. В АЗП-параграфе будет происхо-
дить чтение очередной записи в подобла-
сти на смежной А-ленте. В АЗП-
параграфе будет ссылка на смежную А-
ленту или ее имя. В остальном содержи-
мое этого параграфа такое, как будто А-
данное не разделено. То есть, с точки зре-
ния алгоритма, разделение А-данного
влечет изменения только в АЗ- и АЗУ-
параграфах.
Для ситуации, когда записи на ос-
новной А-ленте и подобласти на смежной
неупорядочены, нет непродуктивных Р-
данных и фрагменты разделенного А-
данного укомплектованы, требуют вклю-
чения дополнительных параграфов, необ-
ходимых для реализации алгоритма.
АЗП-параграф смещается на более глубо-
кий уровень. Из-за дополнительных пара-
графов нарушается АКУ-обусловленность
алгоритма.
Теоретичні та методологічні основи програмування
5
3. Расширенное А-данное как
компонента С-данного в FS с произ-
вольным количеством уровней (первый
вариант). Два предшествующих случая
когда разделенное А-данное как компо-
нента С-данного позволяют сделать вывод
об алгоритме для общего случая. Общий
случай в том, что FS имеет произвольное
количество уровней (рис. 2, б). С-данное
может быть в узле на любом из уровней,
кроме уровня с самым большим номером.
АК, необходимые для объединения А-
данного будут расположены только в АЗ-
и АЗУ-параграфах. В случае, когда компо-
ненты разделенного А-данного упорядоче-
ны, в AD АКУ-обусловленность будет со-
храняться. Если компоненты разделенного
А-данного не упорядочены, то будет необ-
ходимость включать дополнительный (до-
полнительные) параграфы. АКУ-обуслов-
ленность при этом не сохраняется.
4. Расширенное А-данное как
компонента С-данного в трехуровневом
FS (третий вариант). Два расширенных
А-данных являются компонентами С-
данных (рис. 2, в). Одно С-данное, кото-
рое содержит как компоненту разделен-
ное А-данное, размещено в узле на нуле-
вом уровне, а второе С-данное в узле на
первом уровне. Компоненты первого раз-
деленного А-данного (первая их часть) –
Эл-данные и (или) простые А-данные –
размещены в подобласти на основной А-
ленте. Остальные компоненты разделенно-
го А-данного (вторая их часть) – С-данное
(и, возможно, Эл-данные и (или) простые
А-данные) размещены на первой смежной
А-ленте. Компоненты второго разделенно-
го А-данного (первая их часть) – Эл-
данные и (или) простые А-данные – раз-
мещены в подобласти на первой смежной
А-ленте. Остальные компоненты второго
разделенного А-данного (вторая их часть)
– Эл-данные и (или) простые А-данные)
размещены на второй смежной А-ленте.
DA имеет три уровня. АК, содержащее
цикл для объединения первого А-данного,
будет в АЗУ-параграфе на нулевом уровне.
АК, обеспечивающие чтение записей с
фрагментами А-данного (первой части),
будет в АЗ-параграфе на первом уровне.
Здесь же будет АК, которая обеспечит
чтение второй части разделенного А-
данного с первой смежной А-ленты. По-
следняя АК содержит цикл для чтения
компонент С-данного первого уровня с
первой и второй смежных А-лент. В АЗП-
параграфе будет происходить чтение оче-
редных записей на первой и второй смеж-
ных А-лентах. В алгоритме для случая, ко-
гда компоненты на основной и на смеж-
ных А-лентах одинаково упорядочены и
их порядок совпадает с порядком их обра-
ботки, сохраняется АКУ-обусловленность.
Синергетический эффект не наблюдается.
Если компоненты какого-либо из разде-
ленных А-данных не упорядочены на А-
лентах, то в алгоритм необходимо вклю-
чить дополнительные параграфы как было
описано выше. АКУ-обусловленность от-
сутствует в любом из случаев отсутствия
порядка на А-лентах – на основной и (или)
на первой смежной и (или) на второй
смежной.
5. Расширенное А-данное как
компонента С-данного в FS с произ-
вольным количеством уровней (второй
вариант). Общий случай в том, что FS
(рис. 2, г) имеет произвольное количество
уровней (n). Два С-данных имеют в своем
составе разделенные А-данные. Оба С-
данных могут быть в узлах на любом из
уровней (i и i+1), кроме уровня с самым
Рис. 2. Различные виды
деления А-данных
а б
в г д
Теоретичні та методологічні основи програмування
6
большим номером (i+1 < n), но уровни
смежные. АК, необходимые для объедине-
ния А-данных будут расположены только
в АЗ- и АЗУ-параграфах. Если АЗ-
параграф соотносится с узлом уровня i, то
АЗУ-параграф будет соотноситься с узлом
уровня i-1. В параграфах, соотносящихся с
узлами уровней, номера которых меньше i-
1, нет никаких изменений или добавлений
из-за того, что в узле FS уровня i разделе-
но А-данное. Естественно, что речь идет
об узлах (и, соответственно, о параграфах)
расположенных на одной ветви. Не повле-
чет изменений в указанных параграфах и
объединение А-данного, разделенного в
узле уровня i+1.
Если АЗ-параграф соотносится с
узлом уровня i+1, то АЗУ-параграф будет
соотноситься с узлом уровня i. В парагра-
фах, соотносящихся с узлами уровней, но-
мера которых больше i+1, нет никаких из-
менений или добавлений из-за того, что в
узле FS уровня i+1 разделено А-данное. Не
повлечет изменений в указанных парагра-
фах и объединение А-данного, разделен-
ного в узле уровня i.
В случае, когда в фрагменты разде-
ленных А-данных в подобластях неупоря-
дочены, в алгоритме потребуются допол-
нительные параграфы. Но и для этого слу-
чая не потребуется вносить изменения в
параграфы соответствующие узлам на
уровнях больших i+1 и меньших i-1.
Фрагменты разделенных А-данных долж-
ны быть размещены в подобластях на раз-
личных А-лентах иначе будет другим опи-
сание RG и, соответственно, алгоритм.
АКУ-обусловленность в подобных алго-
ритмах не сохраняется. Синергетический
эффект отсутствует.
6. Общий случай деления А-
данного как компоненты С-данного в
многоуровневом FS. Более сложные си-
туации, которые могут быть в связи с де-
лением А-данных могут быть по разным
причинам. А именно.
А. Два или более А-данных разде-
лены. Разделенные А-данные размещены
в узлах на уровнях являющихся смеж-
ными. Выше была рассмотрена ситуация
когда в двух узлах на смежных уровнях
были разделенные А-данные. Количество
узлов с разделенными А-данными сверх
двух не меняет описанные выше алго-
ритмы и не порождает синергетической
эффект.
Б. Два или более А-данных разде-
лены. Разделенные А-данные размещены в
узлах на уровнях, которые могут быть и
смежными и не смежными. В таких ситуа-
циях, как и в предыдущем случае, количе-
ство узлов с разделенными А-данными
сверх двух не меняет описанные выше ал-
горитмы и не порождает синергетической
эффект.
Возможны еще два направления
усложнения ситуации деления А-данного.
В главном А-данном в любом из узлов FS
произвольной структуры более одного
разделенного А-данного. Более одного
деления А-данного в различных узлах. А-
данные могут быть размещены в узлах
как по одной ветви, так и на различных
ветвях. В каждом из этих двух случаев
алгоритмы объединения А-данных оста-
ются такими же как описаны выше. Ни
из-за того, что появляется более двух раз-
деленных А-данных, ни из-за того, где
они размещены в дереве FS, структура
алгоритмов не меняется и синергетиче-
ский эффект не появляется.
4. Совмещение деления С-данных
и А-данных
Эта группа ситуаций объединения
разделенных Р-данных условно разделена
три подгруппы:
Разделенные А-данное и С-данное раз-
мещены в узлах FS на различных уров-
нях. Номер уровня узла, где разделено
С-данное меньше номера уровня узла,
где разделено А-данное.
Разделенные А-данное и С-данное раз-
мещены в одном и том же узле FS (на
одном и том же уровне).
Разделенные А-данное и С-данное раз-
мещены в узлах FS на различных уров-
нях. Номер уровня узла, где разделено
С-данное больше номера уровня узла,
где разделено А-данное.
Общие случаи деления рассматри-
ваются в пределах каждой из подгрупп.
Теоретичні та методологічні основи програмування
7
1. В двухуровневом FS разделено
С-данное и разделенное А-данное его
компонента. Разделено С-данное и разде-
лено А-данное (рис. 3). Номер уровня узла,
где разделено С-данное на единицу мень-
ше номера уровня узла, где разделено А-
данное.
А-лента А1 содержит область R1.
Здесь записи (V1) с первым набором ком-
понент разделенного С-данного (P).
А-лента А2 содержит область R2.
Здесь записи (V2) со вторым набором ком-
понент разделенного С-данного (P).
А-лента А3 содержит область R3.
Здесь записи (V3) с фрагментами (S,U)
разделенного А-данного (T) для первого
набора компонент разделенного С-
данного (P).
А-лента А4 содержит область R4.
Здесь записи (V4) с фрагментами (S,U)
разделенного А-данного (T) для второго
набора компонент разделенного С-
данного (P).
Разделенное С-данное (P) в обла-
стях размещения упорядочено и при чте-
нии записей с его компонентами этот по-
рядок должен быть сохранен. Фрагменты
разделенного А-данного в подобластях на
А-лентах упорядочены одинаково.
Эл-данное E
1
в записи V1 соответ-
ствует Эл-данному E в А-данном T в FS,
а в записи V2 исходному Эл-данному E
соответствует Эл-данное E
2
. Далее приве-
ден алгоритм (алг. 1.5) для объединения
упорядоченных по ключам записей с со-
хранением порядка. Так как записи с
дополняемыми фрагментами разделенно-
го А-данного (T) упорядочены одинаково
с записями, содержащими начальные
фрагменты, то операторы чтения этих
фрагментов с соответствующих А-лент
выполняются одновременно – READ A1
вместе с READ A3, READ A2 вместе с
READ A4.
Параграф, соответствующий узлу
с исходным С-данным
AA: BEGIN
READ A1 READ A3
READ A2 READ A4
PERFORM BB (У1+) AND (У2+).
END AA
Параграф, соответствующий узлу
с исходным А-данным
BB: BEGIN
CASE
IF (У2+) THEN
IF (У1-) THEN READ A1
READ A3
IF (У2-) THEN
CASE
IF (У1+) THEN READ A2
READ A4
IF (У1-) THEN
CASE
IF (E
2
> E
1
) THEN
READ A1
READ A3
IF (E
1
> E
2
) THEN
READ A2
READ A4
ENDCASE
ENDCASE
ENDCASE
END BB
Рис. 3. Деление расширенного
упорядоченного С-данного
и А-данного
FS: P = {T}, T={E,Q,S,U}
RG1: R1 [P], V1 [T]
RG2: R2 [P], V2 [T]
RG3: R3 [P], V3 [T]
RG4: R4 [P], V4 [T]
P
а
Q E
T
S U
P
в
P
д
R2
в
V2
V
в
V1
R1
Q E
1
T
Q E
2
T
P
г
V3
R3
U S
T
P
е
R4
в
V4
V
в
U S
T
AA
BB
б
Теоретичні та методологічні основи програмування
8
Здесь:
У1+ – условие “достигнут конец подобла-
сти R1”;
У2+ – условие “достигнут конец подобла-
сти R2”;
У1- – условие “конец подобласти R1 не до-
стигнут ”;
У2- – условие “конец подобласти R2 не до-
стигнут ”.
Алгоритм 1.5
Синергетический эффект из-за то-
го, что алгоритм реализует объединение
двух видов разделенных Р-данных, не по-
является.
Алгоритм учитывает только одну
ситуацию деления Р-данных. Записи с
компонентами С-данного и фрагментами
А-данного могут быть неупорядоченными.
В подобластях на А-лентах могут быть за-
писи с непродуктивными или условными
Р-данными. Необходимые, для этих случа-
ев изменения в алгоритме для каждого ви-
да разделенных Р-данных, рассматрива-
лись выше. Изменения в алгоритмах, кото-
рые учитывают все эти аспекты, представ-
ляют собой вставки из дополнительных
операторов или фрагментов программного
текста. Содержимое этих фрагментов
обосновано и объяснимо. Процедура ком-
поновки текста, как правило, чисто меха-
ническая и рутинная.
2. Разделенное С-данное и разде-
ленное А-данное как его компонента в
многоуровневом FS. Следующих ситуа-
ций более сложны по сравнению с преды-
дущей в том, что FS, который содержит
два разделенных Р-данных, имеет узлы на
более чем двух уровнях. Ближайшие
усложнения приведены отталкиваясь от
предыдущей ситуации (рис. 3, а).
А. Разделенное С-данное есть ком-
понентой С-данного узла на нулевом
уровне (рис. 4, а).
Б. Разделенное А-данное – расши-
ренное и имеет в своем составе С-данное.
В. Разделенное С-данное есть ком-
понентой С-данного узла на нулевом
уровне и разделенное А-данное – расши-
ренное и имеет в своем составе С-данное
(рис. 4, б).
Если условия деления Р-данных, те
же что учитываются в алгоритме 1.5, то
алгоритм для реализации ситуации А бу-
дет иметь трехуровневую DA. Объедине-
ние разделенных Р-данных будет реализо-
вано в узлах на первом и втором уровнях.
Параграф в узле на нулевом уровне будет
обеспечивать только чтение компонент С-
данного в узле на нулевом уровне FS. Не-
смотря на то, что эти компоненты разделе-
ны, в цикле, который обеспечивает чтение
компонент, нет различения того, что ком-
поненты разделены. Узел-параграф на ну-
левом уровне такой, как будто Р-данные не
разделены.
Рис. 4. Различные ситуации
деления С-данных и А-данных
а б в
г д
и з ж
е
AA
BB
DD
CC
EE
Теоретичні та методологічні основи програмування
9
Если условия деления Р-данных, те
же что учитываются в алгоритме 1.5, то
алгоритм для реализации ситуации в под-
пункте Б будет иметь трехуровневую DA.
Объединение разделенных Р-данных бу-
дет реализовано в узлах на нулевом и
первом уровнях. В узле-параграфе на вто-
ром уровне будет реализовано чтение
компонент С-данного, из состава разде-
ленного расширенного А-данного. Цикл,
который обеспечит чтение этих компо-
нент, будет в узле-параграфе на первом
уровне. Он будет вместо оператора
READ, который добавляет фрагменты
разделенного А-данного или в дополне-
ние к этому параграфу. Это зависит от со-
става фрагмента, добавляемого со смеж-
ной А-ленты – есть ли там только С-
данное или С-данное с Эл-данными (и
простыми А-данными). Узел-параграф на
втором уровне такой, как будто Р-данные
не разделены.
Как видно из описания алгоритмов
подпунктов А и Б, объединение Р-данных
реализуется в АЗ-параграфах (и АЗП-
параграфах) и не влияет на АЗ-параграфы
тех узлов FS, где нет разделенных Р-
данных. Это утверждение справедливо не
только для алгоритма объединения (под-
пункт В) Р-данных в четырехуровневом
FS (рис. 4, б), но и для FS (и алгоритма), в
котором произвольное количество уров-
ней (рис. 4, в). При этом пара смежных
узлов с разделенными Р-данными может
быть на любом уровне.
Разделенные С-данное и А-данное
в узлах FS могут быть не только на смеж-
ных узлах. При этом узел с разделенным
А-данным с номером уровня большим, чем
номер уровня узла с разделенным С-
данным. Алгоритмы для объединения для
таких ситуаций будут теми же, что описа-
ны выше отдельно для объединения разде-
ленного С-данного и объединения разде-
ленного А-данного.
Синергетический эффект в алго-
ритмах для ситуаций описанных в пункте
2 не наблюдается.
3. Разделенное С-данное и разде-
ленное А-данное в одном и том же узле в
многоуровневом FS. Ситуации, в которых
на одном узле есть разделенные А-данные
и С-данные, рассматриваются в порядке их
усложнения.
А. FS имеет узлы на двух уровнях.
В узле на нулевом уровне разделены С-
данное и А-данное. Алгоритм для объ-
единения этого А-данного должен содер-
жать оператор для чтения первого фраг-
мента. Это либо оператор READ, если
фрагмент простое А-данное и содержится
в записи, либо цикл (циклы) для чтения
записей из подобласти, если фрагмент со-
держит С-данное (С-данные), которое со-
держится в подобластях. Для чтения дру-
гого фрагмента необходима АК, которая
обеспечит объединения разделенного С-
данного. Подобная АК обсуждалась ранее
– АК для объединения разделенных С-
данных. Синергетический эффект эти две
алгоритмические реализации для объеди-
нения разделенных А-данного и С-данного
не порождают.
Б. FS имеет узлы на трех уровнях
(рис. 4, г). Разделенные С-данное и А-
данное в одном и том же узле на первом
уровне. Если фрагменты разделенного А-
данного и компоненты разделенного С-
данного упорядочены в подобластях на А-
лентах, то DA будет иметь по одному уз-
лу на трех уровнях. Объединение фраг-
ментов разделенного А-данного будет в
АЗ-узле-параграфе на первом уровне, а
цикл, необходимый для объединения, бу-
дет в АЗУ-узле на нулевом уровне. Со-
держание изменений, необходимых для
объединения А-данного и С-данного,
описаны в предыдущей ситуации. В узле-
параграфе на втором уровне будет обес-
печено чтение записей с компонентами С-
данного с различных А-лент.
В. FS имеет узлы на четырех уров-
нях (рис. 4, д). Эта ситуация отличается
от предыдущей тем, что компонентами
разделенного С-данного могут быть С-
данные или расширенные А-данные. В
алгоритмическом плане отличие этой
ситуации от предыдущей в том, что в
узле-параграфе на втором уровне будут
не операторы READ, которые обеспечи-
вают чтение записей, а циклы, которые
обеспечат чтение подобластей содержа-
щих компоненты разделенного С-данного.
Теоретичні та методологічні основи програмування
10
Каждый цикл будет управлять своим уз-
лом-параграфом, которые будут обеспе-
чивать чтение записей с соответствующей
А-ленты. DA представлен на рис. 4, е.
Если компоненты разделенного С-данно-
го в подобластях на А-лентах неупорядо-
чены, то в алгоритме будут появляться
вспомогательные узлы-параграфы, как это
рассматривалось выше.
Г. FS имеет произвольное количе-
ство уровней (рис. 4, ж). Выводы об этой
обобщенной ситуации основаны на преды-
дущей (FS с четырьмя уровнями). Первое.
Несмотря на то, на каком уровне распо-
ложен узел (i) с разделенными Р-данными
(i>1), необходимости в изменениях в узлах
на более высоких уровнях (< i-1) нет. Вто-
рое. Изменения, обусловленные объедине-
нием Р-данных, на более низких уровнях
(> i+1) нет необходимости вносить. В
зависимости от порядка размещения ком-
понент разделенного С-данного в подоб-
ластях, могут появляться вспомогатель-
ные узлы-параграфы. Если в FS есть
узлы на уровнях ниже узла с разделен-
ным С-данным и номера различаются на
два и более, а компоненты в подобластях
упорядочены, и их чтение должно сохра-
нить порядок, то в DA после уровня i+1
будет умножаться количество узлов-
параграфов. Их количество будет равно
количеству А-лент.
4. Разделенное А-данное и разде-
ленное С-данное как его компонента в
многоуровневом FS. На рис. 4, з пред-
ставлена ситуация одна из этой группы.
FS имеет четыре уровня. В узле на одном
из уровней (1) разделено А-данное. В уз-
ле, уровень которого ниже (2), разделено
С-данное. Для объединения фрагментов
разделенного С-данного вносятся измене-
ния, которые описаны выше для таких си-
туаций. Аналогично, выше описаны изме-
нения в алгоритмы необходимые для объ-
единения компонент разделенного С-
данного. При этом изменения не имеют
взаимного влияния. Объединение фраг-
ментов разделенного А-данного реализу-
ется так, как будто С-данное на более
низком уровне не разделено и наоборот.
Более общий случай (рис. 4, и.)
есть усложнение предыдущего и выводы
для предыдущего остаются в силе. Изме-
нения, необходимые для объединения
разделенных Р-данных, не имеют взаим-
ного влияния.
5. Обобщение для ситуаций сов-
местного деления А-данных и С-данных.
Ситуации совместного деления Р-данных
могут быть обусловлены многими причи-
нами, а именно:
А. А-данное разделено на два фраг-
мента. В одном или обоих фрагментах есть
более одного С-данного. Одно из С-
данных разделено. АК для объединения Р-
данных не будет усложняться и останется
такой же как для одного разделенного С-
данного.
Б. А-данное разделено на два фраг-
мента. В одном или в обоих фрагментах
есть более одного С-данного. Более одного
С-данного разделено. АК для объединения
Р-данных увеличится по размеру, но не
будет усложняться. Механически увели-
чится количество АК для объединения
разделенных С-данных и будет равно их
количеству.
В. А-данное разделено на два фраг-
мента. В одном или обоих фрагментах есть
более одного С-данного. Более одного С-
данного разделено. Для хранения разде-
ленных С-данных – одного или всех их –
используется более одной А-ленты. Меха-
нически увеличится количество АК для
объединения разделенных С-данных и бу-
дет равно их количеству. Но сами АК
будут более сложными. Сложность обу-
словлена работой с А-лентами, которых
более двух.
Г. А-данное разделено на фрагмен-
ты, количество которых более двух. Для
этой ситуации надо последовательно
учесть обстоятельства пунктов А, Б и В.
Выводы для этих ситуаций остаются в си-
ле и в случае если А-данное разделено на
более чем два фрагмента.
Д. FS содержит по одной ветви уз-
лы более чем на двух уровнях. Разделен-
ные Р-данные (А-данные и С-данные)
Теоретичні та методологічні основи програмування
11
есть в узлах на более чем двух смежных
уровнях. Рассматривая деление Р-данных
последовательно сверху вниз (или снизу
вверх) для каждой пары узлов, можно по-
лучить те выводы, которые получены ра-
нее для деления на двух смежных узлах.
АК для объединения разделенных Р-
данных на двух смежных узлах определе-
ны и описаны выше и эти же АК исполь-
зуются для объединения Р-данных на бо-
лее чем двух смежных узлах. Синергети-
ческий эффект не наблюдается и в подоб-
ных ситуациях.
Е. FS содержит по одной ветви
узлы более чем на двух уровнях. Разде-
ленные Р-данные (А-данные и С-дан-
ные) есть в узлах на более чем двух
уровнях. Узлы могут быть как на смеж-
ных так и не смежных уровнях. Анализ и
выбор АК для объединения будет прово-
дится для разделенных Р-данных как в
отдельных узлах, так и для пар узлов. В
силе остаются выводы с предыдущего
пункта (Д).
Ж. FS содержит узлы более чем
на двух уровнях. Разделенные Р-данные
(А-данные и С-данные) есть в узлах на бо-
лее чем двух уровнях, но также и по раз-
ным ветвям. В этом случае АК для
объединения Р-данных в узлах на различ-
ных ветвях не связаны и не соотносятся
никаким образом.
Заключение
Как было сказано выше, разделе-
ны могут быть А-данные и С-данные
всех видов – простые, расширенные и
сложные. Это всего шесть вариантов.
Факторы, которые могут усложнить вари-
анты деления Р-данных – количество по-
добластей (и количество А-лент), в кото-
рых размещены компоненты и фрагменты
разделенных Р-данных. Также имеет зна-
чение есть ли в подобластях непродук-
тивные Р-данные, смешаны ли компонен-
ты и фрагменты разделенных Р-данных и
то, каким образом они смешаны, учиты-
вается характер Р-данных – обязательные,
условные. Учитывая разнообразие DS, FS,
RG, справедливо утверждение – количе-
ство ситуаций деления большое, но огра-
ниченное. Соответственно, большое, но
ограниченное количество АК для объеди-
нения разделенных Р-данных.
В процессе исследований выясни-
лось, что деление Р-данных в узле FS по-
рождает изменения в АЗ или в АЗ и
смежном узле-параграфе (АЗУ или АЗП).
То есть, для исследования АК, необходи-
мых для объединения Р-данных, доста-
точно ограничиться исследованием того,
как разделены Р-данные в главном А-
данном и нет необходимости одновре-
менно исследовать деление Р-данных в
узлах на всех уровнях FS и во всем мно-
гообразии FS. На даже в главном А-
данном, несмотря на то, что может быть
много разделенных Р-данных, следует
анализировать только виды их деления и
сочетания этих видов. Большое количе-
ство разделенных Р-данных может по-
рождать только увеличение количества
АК для их объединения, не порождая при
этом дополнительной сложности.
Алгоритмические конструкции,
обеспечивающие объединение Р-данных,
– простейшие. В большинстве случаев не
больше 4-6 операторов. Есть также не-
сколько видов сочленений этих конструк-
ций. Способы сочленения вытекают из
топологии DS, FS, RG и из того как Р-
данные разделены между А-лентами. Ко-
личество необходимых АК ограниченное,
но если учесть способы их сочленения, то
увеличится количество видов сгенериро-
ванных АК, оставаясь ограниченным. Все
приведенные выше утверждения позво-
ляют заключить, что генерация АК для
группы АРФД возможна.
Следует заметить, что описания
способов деления Р-данных и описания
факторов размещения Р-данных – это де-
кларативные утверждения. Императивные
утверждения – АК и операторы, которые
могут генерироваться, скрыты в процессе
генерации. Декларативность – это суще-
ственный положительный эффект DS-
теории.
Исследование алгоритмов и групп
алгоритмов в DS-теории проводится по-
добно тому, как проводится исследование
алгоритмов в классической теории алго-
Теоретичні та методологічні основи програмування
12
ритмов*. Но если в классической теории
алгоритмов исследуются вычислимость,
эффективность алгоритмов, то цель ис-
следований в DS-теории другая – очер-
тить и описать класс алгоритмов для раз-
личных групп факторов (в этой статье ча-
стично исследована группа АРФД) и
предложить возможность формального
вывода алгоритмов (и программ) на осно-
вании этих факторов.
___________________
* Алферова З.А. Теория алгоритмов. – М.:
Статистика, 1973. – 164 с.
* Alferova Z.A. The theory of algorithms. Mos-
cow: Statistics, 1973. – 164 p.
Получено 20.04.2015
Об авторе:
Колесник Валерий Георгиевич,
старший научный сотрудник
кафедры АПП.
Количество научных публикаций в
украинских изданиях – 22.
ORCID: orcid.org/ 0000-0002-2313-9852.
Место работы автора:
Донбасская государственная
машиностроительная академия.
г. Краматорск,
ул. Шкадинова, 72, п/я 13.
|
| id | pp_isofts_kiev_ua-article-155 |
| institution | Problems in programming |
| keywords_txt_mv | keywords |
| language | Russian |
| last_indexed | 2025-07-17T09:33:07Z |
| publishDate | 2017 |
| publisher | PROBLEMS IN PROGRAMMING |
| record_format | ojs |
| resource_txt_mv | ppisoftskievua/69/47aa958b602eaf26271fe4bf1cb18369.pdf |
| spelling | pp_isofts_kiev_ua-article-1552018-07-12T14:26:34Z DS-theory. Research of R-data division factors in order to generate applied algorithms. Part 2 . DS-теория. Исследование факторов деления Р-данных для генерации прикладных алгоритмов. Часть 2 DS-теорія. Дослідження факторів поділу Р-даних з метою генерації алгоритмів. Частина 2 Kolesnyk, V.G. algorithm; design; data; fragment; structure; node; level; area; section; merger; synthesis UDC 004.424, 004.415 алгоритм; конструкция; данные; фрагмент; структура; узел; уровень; область; параграф; объединение; синтез УДК 004.424, 004.415 алгоритм; конструкція; дані; фрагмент; структура; вузол; рівень; область; параграф; об’єднання; синтез УДК 004.424, 004.415 This is the next essay from the cycle describing the theory of decomposition schemes as the theory of applied algorithms. A decomposition scheme is being considered as a prototype of an applied algorithm. The aim of the essay is to consider the turning of a decomposition scheme into an algorithm in the case when the processed input P-data are placed in various media. R-data kinds of division are described and factors of their fragments and components placing are considered. For all the variants of R-data division the changes into the canonic algorithm which are necessary for their union are described. From the standpoint of the complexity changes in algorithm vary from primitives in several imperative operators to algorithmic constructions with loops and control constructs. For making the algorithmic constructions there is the mechanism of synthesis offered – bound to the levels of algorithm tree. For purposes of the comparative analysis the schemes of decomposition and applied algorithm there was offered the notion of NAC-conditionality as more fitting that the graph isomorphism. It is shown that description of the variants and factors of R-data division is declarative. This work endorses the idea that the theory of decomposition schemes allows to research the algorithms systematically. The aim of the research is to develop the mechanism of synthesis of the applied algorithms. The descriptions of the decomposition schemes are used as raw data for generating. Статья – очередная из цикла работ описывающих теорию схем декомпозиции как теорию прикладных алгоритмов. Схема декомпозиции рассматривается как прототип прикладного алгоритма. Цель статьи – рассмотреть преобразование схемы декомпозиции в алгоритм для того случая, когда обрабатываемые входные Р-данные размещены на различных носителях. Описаны виды деления Р-данных и рассмотре-ны факторы размещения их фрагментов и компонент. Для всех вариантов деления Р-данных описаны изменения в канонический алгоритм необходимые для их объединения. Изменения в алгоритме в плане сложности – это и примитивы в несколько повелительных операторов, и алгоритмические конструкции с циклами и управлением. Для построения алгоритмических конструкций предложен механизм синтеза – привязка по уровням дерева алгоритма. Для сравнительного анализа зависимости между схемой декомпозиции и прикладным алгоритмом предложено понятие АКУ-обусловленности как более подходящее, чем изоморфизм графов. Показано, что описание вариантов и факторов деления Р-данных имеет декларативный характер. Работа подтверждает идею о том, что теория схем декомпозиции позволяет планомерно исследовать алгоритмы. Цель этих исследований в том, чтобы разработать механизм синтеза прикладных алгоритмов. Как исходные данные для генерации используются описания схемы декомпозиции. Стаття – чергова з циклу робіт, що описують теорію схем декомпозиції як теорію прикладних алгоритмів. Схема декомпозиції розглядається як прототип прикладного алгоритму. Мета статті – розглянути перетворен-ня схеми декомпозиції в алгоритм для того випадку, коли оброблювані вхідні Р-дані розміщені на різних носіях. Описано види поділу Р-даних і розглянуті фактори розміщення їх фрагментів та компонент. Для всіх варіантів поділу Р-даних описані зміни в канонічний алгоритм необхідні для їх об’єднання. Зміни в алгоритмі в плані складності є як примітиви в кілька наказових операторів, так і алгоритмічні конструкції з циклами та управлінням. Для побудови алгоритмічних конструкцій запропоновано механізм синтезу – прив’язка до рівнів дерева алгоритму. Для порівняльного аналізу залежності між схемою декомпозиції і прикладним алгоритмом запропоновано поняття АКУ-обумовленості як більш підходяще, ніж ізоморфізм графів. Показано, що опис варіантів і факторів поділу Р-даних має декларативний характер. Робота підтверджує ідею про те, що теорія схем декомпозиції дозволяє планомірно досліджувати алгоритми. Мета цих досліджень у тому, щоб розробити механізм синтезу прикладних алгоритмів. Як вихі-дні дані для генерації використовуються описи схем декомпозиції. PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2017-06-16 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/155 PROBLEMS IN PROGRAMMING; No 4 (2015) ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 4 (2015) ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 4 (2015) 1727-4907 ru https://pp.isofts.kiev.ua/index.php/ojs1/article/view/155/149 Copyright (c) 2017 ПРОБЛЕМИ ПРОГРАМУВАННЯ |
| spellingShingle | algorithm design data fragment structure node level area section merger synthesis UDC 004.424 004.415 Kolesnyk, V.G. DS-theory. Research of R-data division factors in order to generate applied algorithms. Part 2 |
| title | DS-theory. Research of R-data division factors in order to generate applied algorithms. Part 2 |
| title_alt | . DS-теория. Исследование факторов деления Р-данных для генерации прикладных алгоритмов. Часть 2 DS-теорія. Дослідження факторів поділу Р-даних з метою генерації алгоритмів. Частина 2 |
| title_full | DS-theory. Research of R-data division factors in order to generate applied algorithms. Part 2 |
| title_fullStr | DS-theory. Research of R-data division factors in order to generate applied algorithms. Part 2 |
| title_full_unstemmed | DS-theory. Research of R-data division factors in order to generate applied algorithms. Part 2 |
| title_short | DS-theory. Research of R-data division factors in order to generate applied algorithms. Part 2 |
| title_sort | ds-theory. research of r-data division factors in order to generate applied algorithms. part 2 |
| topic | algorithm design data fragment structure node level area section merger synthesis UDC 004.424 004.415 |
| topic_facet | algorithm design data fragment structure node level area section merger synthesis UDC 004.424 004.415 алгоритм конструкция данные фрагмент структура узел уровень область параграф объединение синтез УДК 004.424 004.415 алгоритм конструкція дані фрагмент структура вузол рівень область параграф об’єднання синтез УДК 004.424 004.415 |
| url | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/155 |
| work_keys_str_mv | AT kolesnykvg dstheoryresearchofrdatadivisionfactorsinordertogenerateappliedalgorithmspart2 AT kolesnykvg dsteoriâissledovaniefaktorovdeleniârdannyhdlâgeneraciiprikladnyhalgoritmovčastʹ2 AT kolesnykvg dsteoríâdoslídžennâfaktorívpodílurdanihzmetoûgeneracííalgoritmívčastina2 |