DS-theory. Research of R-data division factors in order to generate applied algorithms. Part 1
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 va...
Збережено в:
| Дата: | 2017 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
PROBLEMS IN PROGRAMMING
2017
|
| Теми: | |
| Онлайн доступ: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/143 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Problems in programming |
| Завантажити файл: |  |
Репозитарії
Problems in programming| id |
pp_isofts_kiev_ua-article-143 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/7b/0a173175174cc563e978adadc9e85b7b.pdf |
| spelling |
pp_isofts_kiev_ua-article-1432018-07-16T12:04:37Z DS-theory. Research of R-data division factors in order to generate applied algorithms. Part 1 DS-теория. Исследование факторов деления Р-данных для генерации прикладных алгоритмов. Часть 1 DS-теорія. Дослідження факторів поділу Р-даних з метою генерації алгоритмів. Частина 1 Kolesnyk, V.G. UDC 004.424, 004.415 УДК 004.424, 004.415 УДК 004.424, 004.415 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. Описаны виды деления Р-данных и рассмотрены факторы размещения их фрагментов и компонент. Для всех вариантов деления Р-данных описаны изменения в канонический алгоритм необходимые для их объединения. Изменения в алгоритме в плане сложности – это и примитивы в несколько повелительных операторов, и алгоритмические конструкции с циклами и управлением. Для построения алгорит-мических конструкций предложен механизм синтеза – привязка по уровням дерева алгоритма. Для сравнительного анализа зависимости между схемой декомпозиции и прикладным алгоритмом предложено понятие АКУ-обусловленности как более подходящее, чем изоморфизм графов. Показано, что описание вариантов и факторов деления Р-данных имеет декларативный характер. Описано види поділу Р-даних і розглянуті фактори розміщення їх фрагментів та компонент. Для всіх варіантів поділу Р-даних описані зміни в канонічний алгоритм необхідні для їх об’єднання. Зміни в алгоритмі в плані складності є як примітиви в кілька наказових операторів, так і алгоритмічні конструкції з циклами та управлінням. Для побудови алгоритмічних конструкцій запропоновано механізм синтезу – прив’язка до рівнів дерева алгоритму. Для порівняльного аналізу залежності між схемою декомпозиції і прикладним алгоритмом запропоновано поняття АКУ-обумовленості як більш підходяще, ніж ізоморфізм графів. Показано, що опис варіантів і факторів поділу Р-даних має декларативний характер. PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2017-06-15 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/143 PROBLEMS IN PROGRAMMING; No 3 (2015) ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 3 (2015) ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 3 (2015) 1727-4907 ru https://pp.isofts.kiev.ua/index.php/ojs1/article/view/143/136 Copyright (c) 2017 ПРОБЛЕМИ ПРОГРАМУВАННЯ |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2018-07-16T12:04:37Z |
| collection |
OJS |
| language |
Russian |
| topic |
UDC 004.424 004.415 |
| spellingShingle |
UDC 004.424 004.415 Kolesnyk, V.G. DS-theory. Research of R-data division factors in order to generate applied algorithms. Part 1 |
| topic_facet |
UDC 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. Research of R-data division factors in order to generate applied algorithms. Part 1 |
| title_short |
DS-theory. Research of R-data division factors in order to generate applied algorithms. Part 1 |
| title_full |
DS-theory. Research of R-data division factors in order to generate applied algorithms. Part 1 |
| title_fullStr |
DS-theory. Research of R-data division factors in order to generate applied algorithms. Part 1 |
| title_full_unstemmed |
DS-theory. Research of R-data division factors in order to generate applied algorithms. Part 1 |
| title_sort |
ds-theory. research of r-data division factors in order to generate applied algorithms. part 1 |
| title_alt |
DS-теория. Исследование факторов деления Р-данных для генерации прикладных алгоритмов. Часть 1 DS-теорія. Дослідження факторів поділу Р-даних з метою генерації алгоритмів. Частина 1 |
| description |
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. |
| publisher |
PROBLEMS IN PROGRAMMING |
| publishDate |
2017 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/143 |
| work_keys_str_mv |
AT kolesnykvg dstheoryresearchofrdatadivisionfactorsinordertogenerateappliedalgorithmspart1 AT kolesnykvg dsteoriâissledovaniefaktorovdeleniârdannyhdlâgeneraciiprikladnyhalgoritmovčastʹ1 AT kolesnykvg dsteoríâdoslídžennâfaktorívpodílurdanihzmetoûgeneracííalgoritmívčastina1 |
| first_indexed |
2025-07-17T09:54:18Z |
| last_indexed |
2025-07-17T09:54:18Z |
| _version_ |
1850410956800131072 |
| fulltext |
Теоретичні та методологічні основи програмування
© В.Г. Колесник, 2015
ISSN 1727-4907. Проблеми програмування. 2015. № 3 3
УДК 004.424, 004.415
В.Г. Колесник
DS-ТЕОРИЯ. ИССЛЕДОВАНИЕ ФАКТОРОВ ДЕЛЕНИЯ
Р-ДАННЫХ ДЛЯ ГЕНЕРАЦИИ ПРИКЛАДНЫХ
АЛГОРИТМОВ. ЧАСТЬ 1
Описаны виды деления Р-данных и рассмотрены факторы размещения их фрагментов и компонент. Для
всех вариантов деления Р-данных описаны изменения в канонический алгоритм необходимые для их
объединения. Изменения в алгоритме в плане сложности – это и примитивы в несколько повелитель-
ных операторов, и алгоритмические конструкции с циклами и управлением. Для построения алгорит-
мических конструкций предложен механизм синтеза – привязка по уровням дерева алгоритма. Для
сравнительного анализа зависимости между схемой декомпозиции и прикладным алгоритмом предло-
жено понятие АКУ-обусловленности как более подходящее, чем изоморфизм графов. Показано, что
описание вариантов и факторов деления Р-данных имеет декларативный характер.
Введение
В работе [1] изложена идея, заклю-
чающаяся в том, что вместо попыток ис-
следования множества реальных приклад-
ных алгоритмов и программ следует ис-
следовать множество схем декомпозиции
(DS). Последнее множество значительно
меньше множества реальных алгоритмов и
программ. Также DS проще соответству-
ющего алгоритма записанного с помощью
алгоритмического языка. Соответственно,
вместо проектирования алгоритмов и
написания программ предпочтительнее
проектировать DS. Но для этого необхо-
димо иметь механизм преобразования DS в
реальную программу. В работе [2] проде-
монстрирована возможность подобного
преобразования. Канонический алгоритм,
построенный на основании дерева полной
схемы декомпозиции (DPS), задает струк-
туру программы в целом. DS имеет в каче-
стве компонент (строительных клеток) ал-
горитмические конструкции узла (АКУ).
АКУ преобразуется в текст программы.
Одна АКУ реализуется одним параграфом.
Вся DS превращается в логически завер-
шенную программу. В работе [2] показано,
как размещение Р-данных на А-ленте вли-
яет на содержимое параграфа.
В этой работе рассматривается еще
один аспект работы с Р-данными.
А-данные и С-данные, являющиеся аргу-
ментами при реализации А-зависимостей,
перед началом расчета программы ЭВМ
могут быть разделены и размещены в раз-
личных подобластях. В практике элек-
тронной обработки данных это значит, что
группы и совокупности данных, могут
быть размещены в различных файлах.
Файлы же могут быть расположены как на
одном носителе, так и на нескольких носи-
телях. Данные могут быть расположены в
различных базах данных. Кроме того, вме-
сто файлов могут быть потоки данных [3],
поступающих с различных источников –
от датчиков, с интернета и т. п. Соответ-
ственно, Р-данные, как абстракция реаль-
ных данных, тоже могут быть расположе-
ны на различных носителях. В DS-теории в
качестве носителей областей и А-фрагмен-
тов, содержащих фрагменты Р-данных,
рассматривается абстрактная А-лента.
Размещение Р-данных на А-ленте отлича-
ется от размещения реальных данных на
реальных носителях. По сравнению с алго-
ритмами доступа к Р-данным на А-ленте,
существуют различные факторы, которые
следует учитывать при проектировании
реальных алгоритмов для доступа к реаль-
ным данным. Факторы, которые учитыва-
ются при размещении разделенных Р-
данных в областях или (и) на различных
носителях, называются алгоритмически
релевантными факторами деления Р-
данных (АРФД).
Цель данной работы – показать
обобщенную картину деления Р-данных, а
также описать (очертить) группу алгорит-
мов объединения разделенных Р-данных –
Теоретичні та методологічні основи програмування
4
алгоритмы слияния Р-данных. Описать
группу АРФД и то, как эти факторы влия-
ют на канонический алгоритм1. Описать те
изменения, которые необходимо внести в
канонический алгоритм, чтобы собрать
Р-данные для реализации расчета А-зави-
симостей в виде одного непрерывного по-
тока, так как будто они поступают с одной
А-ленты.
Изменения, которые должны быть
внесены в канонический алгоритм, это
операторы или АК. Далее они будут либо
полностью приведены, либо бегло описа-
ны. Технически в условиях статьи невоз-
можно показать весь набор изменений
обусловленных группой АРФД. При ана-
лизе алгоритма объединения Р-данных,
когда есть два или более разделенных Р-
данных, будет обращаться внимание на то,
появляется или нет синергетический эф-
фект. То есть, не увеличивается ли непро-
порционально сложность из-за включения
двух или более АК для объединения раз-
деленных Р-данных. Синергетический эф-
фект – это дополнительное препятствие
для процедур синтеза.
1. Простейшие ситуации деления
Р-данных и алгоритмы их
объединения
Разделены могут быть А-данные и
С-данные всех видов – простые, расши-
ренные и сложные. Ситуации размещения
фрагментов А-данных в областях на А-
лентах возможны такие же, как и для А-
данных, которые не разделены. А именно:
все виды порядка размещения и все виды
совместного размещения [2]. Аналогично
ситуации размещения фрагментов С-
данных в областях на А-лентах возможны
такие же как и для неразделенных С-
данных. В областях размещения фрагмен-
тов А-данных и С-данных наряду с по-
1 В истории математики есть прецедент подобного
подхода в исследованиях. В какой-то момент стало
понятно, что непродуктивно искать универсальные
решения алгебраических уравнений пятой, шестой
и больших степеней. Вместо этого были предпри-
няты попытки исследовать свойства коэффициен-
тов, от которых зависят решения. Это дало воз-
можность ответить на вопрос о возможности
нахождения корней в радикалах в принципе.
следними могут быть Р-данные, которые
являются непродуктивными для исходной
DS. Фрагменты разделенных Р-данных в
областях размещения являются просто А-
фрагментами. А-фрагменты могут быть
как условными, так и обязательными.
Часть Р-данного может быть размещена не
одной А-ленте, а другая на другой А-
ленте. Первая А-лента называется основ-
ной, а вторая – смежной. Смежных А-лент
может быть более одной2.
Р-данные могут быть разделены пе-
ред их обработкой, но может быть необхо-
димость их разделить после обработки. В
работе рассматривает только один аспект –
объединение Р-данных перед обработкой.
1. Простое А-данное. Тот факт, что
простое А-данное разделено, обозначает
следующее. А-данное (A) исходного дере-
ва типов свойств (FS) состоит, по крайней
мере, из двух Эл-данных: A = {B,C}
(рис. 1, а). Одно из этих Эл-данных (B)
размещено в записи (R1) на одной из А-
лент, а другое из Эл-данных (C) размеще-
но в записи (R2) на другой А-ленте. Для
того, чтобы соединить их для обработки,
необходимо прочитать в А-память записи
с каждой из А-лент. Эта процедура реали-
зуется в процессе вычислений при усло-
вии, что вычислительное устройство, упо-
минаемое в [1] в состоянии читать инфор-
мацию с более чем одной А-ленты. Текст
соответствующего фрагмента программно-
го текста содержит два оператора READ3.
В пределах этой статьи факт деления А-
данного на чертеже изображается стрел-
кой, направленной снизу вверх, указыва-
ющей на границу разделения А-данного.
Если Эл-данное в записи на смеж-
ной А-ленте только одно из нескольких и
имя не совпадает с именем в исходном
А-данном, то необходимо уточнять, какое
именно Эл-данное является частью разде-
ленного исходного А-данного. В примере
(рис. 1, б) – Эл-данное M в записи (R1) на
первой А-ленте – это Эл-данное B исход-
ного А-данного A, а Эл-данное Z в записи
(R2) на второй А-ленте – это Эл-данное C
в составе А-данного A. Если на одной из
2 В большинстве случаев между основной и смеж-
ной А-лентам может отсутствовать различие.
3 Краткое описание алгоритмического языка в [2].
Теоретичні та методологічні основи програмування
5
А-лент записей более одной, то искомую
следует идентифицировать. Для этого надо
указать ее тип. Для того, чтобы найти не-
обходимую запись на смежной А-ленте
необходимо построить алгоритмическую
конструкцию (АК). Это цикл, в теле кото-
рого есть оператор чтения записи и услов-
ный оператор, который проверяет тип про-
читанной записи. Цикл завершит работу,
когда необходимая запись будет найдена.
Если необходимые записи с компонентами
исходного А-данного найдены на основ-
ной и смежных А-лентах, то дальше в тек-
сте это факт будет звучать как “записи
синхронизированы”.
Возможно, что А-данное содержит
произвольное количество Эл-данных и
разделено более одного раза. В результате
деления получено несколько фрагментов
А-данного и для размещения каждого
фрагмента использована отдельная А-
лента. То есть, для размещения фрагмен-
тов А-данного кроме основной использо-
вано более одной смежной А-ленты. В та-
ком случае синхронизация записей долж-
на быть выполнена на всех А-лентах.
2. Расширенное А-данное. Тот
факт, что расширенное А-данное разделе-
но, обозначает следующее. А-данное A
исходного дерева типов свойств состоит
из произвольного количества Эл-данных,
А-данных и простых или расширенных С-
данных (рис. 2, а). Часть А-данного раз-
мещена в А-фрагменте (запись R1, запись
R5 и подобласть R2) на основной А-ленте,
а другая часть размещена в А-фрагменте
(запись R3, R6 и подобласть R4) на смеж-
ной. АК в условиях примера на рис. 2 со-
держит оператор READ для чтения записи
R1, оператор READ для чтения первой за-
писи из подобласти R2, цикл для чтения
остальных записей из R2, оператор READ
для чтения записи R3 и оператор READ
для чтения первой записи из подобласти
R4 и цикл для чтения остальных записей
из R4. Операторы READ и циклы соеди-
нены последовательным сочленением.
Ниже приведен текст фрагмента на алго-
ритмическом языке (алг. 1.1).
Рис. 2. Деление расширенного А-данного
FS: A={O,P,Q,R}, P = {S},
R = {T},
RG1: R1 [O], R2 [P], R5 [S]
RG2: R3 [Q], R4 [R], R6 [T]
Имена Р-данных в записях на А-
лентах могут не совпадать с именами в FS.
В таком случае необходимо установить
соответствие между ними. В записях на А-
лентах могут быть непродуктивные Р-
данные. В этом случае никакие изменения
в алгоритм не требуются. В подобластях
на А-лентах могут быть непродуктивные
записи, которые размещены вперемежку с
искомыми. В таких случаях записи с иско-
мыми Р-данными должны быть снабжены
признаком, и при чтении записи без этого
признака необходимо пропускать.
A
P Q
а
S
T
Q R
б
R O
T
T
U
O P
S
в
Рис. 1. Деление простого А-данного
FS: A = {C,B}
U={M,N}, T={Z,S,O}
RG1: R1 [U]
RG2: R2 [T]
а
б
A
C B
U
M N
T
Z S Q
R1 R2
Теоретичні та методологічні основи програмування
6
AA: BEGIN
Чтение с первой А-ленты
READ A1
READ A1
PERFORM BB (Конец подобласти
R2).
Чтение с второй А-ленты
READ A2
READ A2
PERFORM CC (Конец подобласти
R4).
END AA
BB: BEGIN
READ A1;
END BB
CC: BEGIN
READ A2;
END CC
Алгоритм 1.1
Возможна ситуация, когда искомая
запись (R1) и все записи, содержащие ком-
поненты С-данного (например, P) разме-
щены в одном А-фрагменте, но на А-ленте
есть и другие – непродуктивные А-
фрагменты. В таком случае перед чтением
искомого фрагмента, должна быть выпол-
нена АК, которая обеспечит поиск этого
А-фрагмента на смежной А-ленте. Успеш-
ное завершение поиска обозначается как
“синхронизированы А-фрагменты”. При
этом возможна ситуация, что внутри необ-
ходимого А-фрагмента есть непродуктив-
ные записи. Существование таких записей
влечет включение в текст фрагмента про-
граммы АК, которая позволит пропускать
непродуктивные записи. Если искомые и
непродуктивные А-фрагменты размещены
в соответствии с некоторым порядком, то
этот порядок в алгоритме может быть
учтен, но его можно и не учитывать, но
допустить, что искомый и непродуктивные
А-фрагменты просто перемешаны.
Если расширенное А-данное разде-
лено более чем на две части и для разме-
щения разделенных частей используется
кроме основной А-ленты более одной
смежной А-ленты, то А-фрагменты долж-
ны быть синхронизированы на всех смеж-
ных А-лентах.
3. Простое и расширенное С-
данное. Часть компонент (Q) С-данного
(P) размещены в подобласти (U1) на ос-
новной А-ленте (A1) (рис. 3). Эл-данное
(Q) исходного С-данного размещено в за-
писи (V1). Другая часть компонент (Q) С-
данного (P) размещены в подобласти (U2)
на смежной А-ленте (A2). Эл-данное (Q)
исходного С-данного размещено в записи
(V2).
Рис. 3. Деление простого С-данного
FS: P = {Q}.
RG1: U1 [P], V1 [Q]
RG2: U2 [P], V2 [Q]
АК, которая обеспечит ввод иско-
мых записей непрерывным потоком, в
условиях примера на рис. 3 содержит опе-
ратор READ для чтения первой записи
(V1) с А-ленты (А1), цикл для чтения
остальных записей(V1) с той же подобла-
сти, оператор READ для чтения первой
записи (V2) с А-ленты (А2) и цикл для чте-
ния остальных записей (V2) с той же по-
добласти. Операторы READ и циклы со-
единены последовательным сочленением.
Компонентами С-данного могут
быть также простые А-свойства. Если А-
свойства в подобластях на А-лентах и в FS
совпадают по именам, то никакие измене-
ния в алгоритме не нужны. Иначе для всех
Эл-данных в FS и в записях, которые на
А-лентах необходимо установить соответ-
ствие в именах.
В подобласти, как на основной, так
и на смежной А-лентах могут быть записи,
которые содержат непродуктивные Р-да-
нные. А-фрагменты с продуктивными и
непродуктивными Р-данными должны
P
а
Q
P
б
Q
P
в
Q
U2
в
V2
Vв
V1
U1
Теоретичні та методологічні основи програмування
7
иметь признаки, по которым их можно
различать. Существование таких А-
фрагментов влечет включение в текст
фрагмента программы АК, которая позво-
лит различать А-фрагменты с искомыми Р-
данными. Если искомые и непродуктивные
А-фрагменты размещены в соответствии с
некоторым порядком, то этот порядок в
алгоритме может быть учтен, но его мож-
но и не учитывать, но допустить, что ис-
комые и непродуктивные А-фрагменты
просто перемешаны.
Возможна ситуация (рис. 4), когда
а) для размещения разделенного расши-
ренного С-данного использовано две А-
ленты; б) в FS в А-данном, которое являет-
ся компонентой расширенного С-данного,
есть Эл-данное (E), по возрастанию значе-
ния которого упорядочены записи; в) на
основной (E1) и смежной А-лентах (E2) за-
писи с искомым А-данным тоже упорядо-
чены по значению этого же Эл-данного.
Эл-данное, по значению которого упоря-
дочены записи, называется ключом. Далее
приведен алгоритм (алг. 1.2) для объеди-
нения упорядоченных по ключам записей с
основной и смежной А-лент с сохранением
порядка. Это так называемый алгоритм
балансировки [4]. В условиях примера рис.
4. Эл-данное E1 в записи V1 соответствует
Эл-данному E в А-данном T в FS, а в за-
писи V2 исходному Эл-данному E соответ-
ствует Эл-данное E2.
Параграф, соответствующий уровню
исходного С-данного
AA: BEGIN
READ A1
READ A2
PERFORM BB (У1+) AND (У2+).
END AA
Параграф, соответствующий уровню
исходного А-данного.
BB: BEGIN
CASE
IF (У2+) THEN
IF (У1-) THEN READ A1
IF (У2-) THEN
CASE
IF (У1+) THEN READ A2
IF (У1-) THEN
CASE
IF (E2 > E1) THEN READ A1
IF (E1 > E2) THEN READ A2
ENDCASE
ENDCASE
ENDCASE
END BB
Здесь:
У1+ – условие “достигнут конец подобла-
сти R1”;
У2+ – условие “достигнут конец подобла-
сти R2”;
У1- – условие “конец подобласти R1 не до-
стигнут”;
У2- – условие “конец подобласти R2 не до-
стигнут”;
Алгоритм 1.2
Рис. 4. Деление расширенного упорядо-
ченного С-данного
FS: P = {T}, T={E,Q}
RG1: R1 [P], V1 [T]
RG2: R2 [P], V2 [T]
Если смежных А-лент более одной,
то в параграф, который обеспечивает чте-
ние записей непрерывным потоком без
сохранения порядка, необходимо доба-
вить АК для чтения с каждой дополни-
тельной смежной А-ленты. Количество
циклов в этих АК равно количеству
смежных А-лент и одной основной. Если
же необходимо объединить компоненты
С-данного с сохранением порядка с не-
скольких А-лент, то в АЗП-параграфе по-
P
а
Q E
T
P
б
P
в
R2
в
V2
Vв
V1
R1
Q E1
T
Q E2
T
Теоретичні та методологічні основи програмування
8
требуется АК, реализующая алгоритм ба-
лансировки для всех обрабатываемых А-
лент. Размер и цели статьи не позволяют
привести алгоритм для объединения С-
данного разделенного и размещенного в
записях на А-лентах, количество которых
произвольно4.
4. Расширенное А-данное как
компонента С-данного. Расширенное А-
данное – это компонента С-данного. Каж-
дый экземпляр А-данного однообразно
разделен на две части (рис. 5). Как первая
часть А-данного, содержащая одни и те же
Эл-данные, размещена в записи одного и
того же типа (V1) в подобласти (R1) на ос-
новной А-ленте, так и вторая часть А-
данного, содержащая остальные Эл-
данные, размещена в записи одного и того
же типа (V2) в подобласти (R2) на смежной
А-ленте. Ниже приведен алгоритм
(алг. 1.3) для объединения исходного А-
данного (рис. 6, а).
Рис. 5. Деление расширенного А-данного
как компоненты С-данного
FS: P = {T}, T = {D,E,Q,F}
RG1: R1 [P1], V1 [T1]
RG2: R2 [P2], V2 [T2]
4 В 80-е годы при программировании обработки
линейных файлов или иерархических баз данных,
если записи были разделены и размещены в не-
скольких файлах (более двух), а каждый файл на
отдельной А-ленте, то написание алгоритма балан-
сировки составляло определенную трудность и да-
леко не каждый программист мог его написать.
Параграф, соответствующий уровню
исходного С-данного
AA: BEGIN
READ A1
READ A2
PERFORM BB (У1+).
END AA
Параграф, соответствующий уровню
исходного А-данного.
BB: BEGIN
READ A1
READ A2
END BB
Здесь:
У1+ – условие “достигнут конец подобла-
сти R1”.
Алгоритм 1.3
В этом алгоритме предполагается,
что записи в областях на основной и
смежной А-лентах одинаково упорядоче-
ны, и этот порядок будет сохранен при об-
работке. Между тем возможна ситуация,
когда записи с фрагментами исходного А-
данного на основной и исходной А-лентах
имеют различный порядок. Алгоритм в
этом случае будет построен исходя из то-
го, в каком порядке будет необходимость
их обрабатывать. Порядок может соответ-
ствовать порядку записей на основной или
на смежной А-ленте. В любом из этих слу-
чаев в алгоритме необходимо добавить
АК. Суть ее в следующем. Основной опре-
деляется А-лента, записи, на которой рас-
положены в необходимом для обработки
P
а
Q E
T
F D
P1
б
P2
в
R2
в
V2
Vв
V1
R1
E D1
T1
Q D2
T2
F
Рис. 6. Графы алгоритмов объединения
разделенных А-данных
AA
BB
AA
BB
CC
AA
BB
CC DD
а
б в
Теоретичні та методологічні основи програмування
9
порядке. В алгоритм добавляется цикл, ко-
торый для каждой записи на основной А-
ленте найдет соответствующую запись на
смежной А-ленте. При этом поиск на
смежной А-ленте каждый раз начинать с
начала подобласти (рис. 6, б). Также в
каждой из записей на основной и на смеж-
ной А-лентах должно Эл-данное (или А-
данное), которое является ключом для их
синхронизации.
Возможен вариант, когда порядок
обработки записей не совпадает с поряд-
ком их размещения ни на основной, ни на
смежной А-лентах. Для работы алгоритма
необходимо обеспечить способ, с помо-
щью которого будет указан порядок обра-
ботки записей. Возможно потребуется из-
менить исходную FS – добавить вспомога-
тельный набор записей, определяющий
порядок обработки. Алгоритм в таком слу-
чае будет следующим: после чтения запи-
си со вспомогательного набора записей
выполнить цикл для поиска необходимого
фрагмента исходного А-данного на основ-
ной А-ленте и цикл для поиска необходи-
мого второго фрагмента исходного А-
данного на смежной А-ленте5 (рис. 6, в).
Особые виды порядка размещения записей
с фрагментами А-данного в подобластях,
как на основной, так и на смежной А-
лентах, а именно, относительно начала или
конца подобласти или относительно друг
друга, не имеют значения, так как важно
соответствие порядка на А-лентах.
Как на основной, так и на смежной
А-лентах в подобластях, где расположены
записи с фрагментами исходного А-
данного, могут быть также и записи с не-
продуктивными Р-данными. В таком слу-
чае в алгоритм подобный алгоритму 1.3
необходимо внести изменения. Вместо
оператора READ, который читает записи с
А-ленты с непродуктивными Р-данными
необходимо вставить АК, которая будет
распознавать тип прочитанной записи и
поставлять в поток для обработки только
записи с фрагментом искомого А-данного.
Как на основной, так и на смежной
А-лентах могут отсутствовать некоторые
5 В практике электронной обработки данных по-
добные задачи решаются с помощью сортировки
или индексации данных.
записи с фрагментами искомого А-
данного. Такой вариант с фрагментами А-
данного должен быть описан в FS и в опи-
сании размещения Р-данных в подобла-
стях. Если в FS это не описано, то это зна-
чит, что FS – ошибочна. Если же описано,
то следующим образом.
Первый вариант. Некоторые за-
писи отсутствуют только на одной из А-
лент. Это значит, что исходное С-данное
содержит как компоненты два типа А-
данных – укомплектованное фрагментами
и неукомплектованное фрагментами пер-
вой частью А-данного.
Второй вариант. Исходное С-
данное содержит как компоненты два типа
А-данных – укомплектованное фрагмента-
ми и неукомплектованное фрагментами
другой частью А-данного.
Третий вариант. Исходное С-
данное содержит как компоненты четыре
типа исходного А-данного – укомплекто-
ванное фрагментами, неукомплектованное
фрагментами одной части, неукомплекто-
ванное фрагментами другой части А-
данного и неукомплектованное фрагмен-
тами обоих частей.
То, какой вариант предлагается для
последующей обработки в потоке экзем-
пляров исходного А-данного, определяется
только после того, когда найдены (или не
найдены) записи с фрагментами на обеих
А-лентах.
При объединении записей с фраг-
ментами исходного А-данного возможно
сочетание вариантов: упорядочены или нет
записи с фрагментами исходного А-
данного, наличие записей непродуктивны-
ми Р-данными и отсутствие записей с
фрагментами исходного А-данного. Это
должно быть описано в FS и в описании
размещения Р-данных в подобластях.
Исходное А-данное может быть
разделено на фрагменты, которых больше
чем два. В таком случае для размещения
записей может быть использовано количе-
ство А-лент равное количеству типов
фрагментов или меньшее этого количе-
ства. В последнем случае предполагается,
что на одной А-ленте размещено более од-
ного типа записи с фрагментами исходного
А-данного. Каждый тип фрагмента сохра-
Теоретичні та методологічні основи програмування
10
няется в уникальном типе записи. Для все-
го этого разнообразия разделенного А-
данного алгоритмы изменяются только
механически. А именно, в одном и том же
параграфе добавляются АК, которые опи-
саны выше, кроме той ситуации, когда
надо учитывать различающийся порядок
размещения записей в подобластях. В том
случае, когда надо учитывать различный
порядок записей в подобластях на основ-
ной и (или) смежной А-лентах, появляется
дополнительный цикл (циклы) и, соответ-
ственно, дополнительный параграф. В
условиях примера (рис. 5 и алгоритм 1.3) –
это параграф BB на рис. 6, б и в.
5. Алгоритмически-зависимый
параграф. Как было показано в [2] каж-
дая алгоритмическая конструкция узла
(АКУ) реализуется как один параграф.
Каждый параграф связан со “своей” АКУ
или, точнее, каждый параграф зависит от
“своей” АКУ. Также можно говорить, что
каждый узел дерева алгоритма (DA) зави-
сит от “своего” узла в DPS. Для того, что-
бы подчеркнуть связь между конкретным
АКУ (узлом DPS) и параграфом (узлом в
DA), используется понятие “алгоритмиче-
ски-зависимый” (АЗ). А именно, алгорит-
мически-зависимый параграф (АЗ-
параграф), алгоритмически-зависимый
узел (АЗ-узел), алгоритмически-
зависимый узел-параграф (АЗ-узел-
параграф). Это же понятие будет исполь-
зоваться для иллюстрации связи между
главным А-данным (узлом в FS) и пара-
графом (узлом в DA).
В следующей ситуации вводится
еще одно определение связи между FS и
алгоритмом. В главном А-данном есть не-
кое С-данное. Главное А-данное соотно-
сится с АЗ-параграфом. В С-данном есть
компоненты, для обработки которых в ал-
горитме порождается параграф. Последний
будет подчинен исходному АЗ-параграфу
(связан с ним иерархическим сочленени-
ем). Этот подчиненный параграф по отно-
шению к упомянутому С-данному будет
называться алгоритмически-зависимым
подчиненным (АЗП) параграфом, а имен-
но, АЗП-параграф (АЗП-узел, АЗП-узел-
параграф).
Если выполнение АЗ-параграфа
инициируется другим параграфом, то по-
следний называется алгоритмически зави-
симым управляющим параграфом (АЗУ-
параграф) для исходного АЗ-параграфа.
АЗУ-параграф и АЗ-параграф соединены
иерархическим сочленением. Соответ-
ственно, существуют АЗУ-узел, АЗУ-узел-
параграф. Для АЗ-узла (АЗ-параграфа)
АЗУ-узел (АЗУ-параграф) может отсут-
ствовать только в том случае, если АЗ-узел
размещен на нулевом уровне AD. С точки
зрения FS и DA как деревьев, АЗУ-узел
это узел-родитель для АЗ-узла, а АЗП-узел
– узел-потомок для того же АЗ-узла.
Если алгоритм, с помощью которо-
го реализована некая DPS, содержит толь-
ко АЗ-параграфы, количество которых
совпадает с количеством узлов в DPS, то
он называется АКУ обусловленной тексто-
вой реализацией канонического алгоритма.
Или в другой формулировке – алгоритм
имеет свойство АКУ-обусловленности.
Свойством АКУ-обусловленности облада-
ет не каждый реальный алгоритм. Как пра-
вило в реальных алгоритмах появляются
дополнительные вспомогательные пара-
графы.
2. Произвольное деление
С-данных
1. Деление С-данного в трехуров-
невом FS (первый вариант). С-данное
разделено и при этом оно является компо-
нентой трехуровневого FS. С-данное, бу-
дучи в узле на нулевом уровне FS, имеет
своими компонентами не простое А-
свойство, а расширенное6 (рис. 7, а). Это
означает, что объединять надо не записи,
размещенные в различных подобластях, а
подобласти7.
DA как и FS тоже имеет три уровня.
Подобласти на различных А-лентах
неупорядочены. В параграфе на нулевом
уровне, который является АЗ-параграфом
для узла, где разделено С-данное, органи-
6 На рис. 7 только в пункте “а” детально изобража-
ется примерный состав FS. В остальных пунктах FS
изображается сжато – только узлы, количество
уровней FS, количество и места деления С-данных.
7 Подобласти как и записи тоже могут быть упоря-
дочены.
Теоретичні та методологічні основи програмування
11
зованы циклы для объединения компонент
С-данного. В параграфе первого уровня
(рис. 7, в – параграфы BB и DD), вместо
оператора READ, который читал бы оче-
редную запись, организован цикл для чте-
ния подобластей – компонентой разделен-
ного С-данного. Содержимое параграфов
первого и второго уровня (рис. 7, в – пара-
графы CC и EE) такое, как если бы С-
данное на нулевом уровне FS не было бы
разделено. Объединение разделенного С-
данного для варианта неупорядоченных
компонент реализовано только в АЗ-
параграфе.
Рис. 7. Различные виды деления
С-данных
Объединение разделенного С-
данного для варианта упорядоченных ком-
понент реализуется в АЗ-параграфе и в
АЗП-параграфе. Деления С-данного не
влияет на узел-параграф второго уровня.
2. Деление С-данного в трехуров-
невом FS (второй вариант). С-данное
разделено и при этом оно является компо-
нентой трехуровневого FS. В этом вариан-
те разделенное С-данное размещено в узле
на первом уровне и является компонентой
С-данного (рис. 7, г). Компоненты С-
данного в подобластях размещения неупо-
рядочены и нет необходимости поставлять
их для обработки в каком-либо порядке. В
АЗ-параграфе организованы циклы для
объединения компонент С-данного. В па-
раграфе второго уровня, будут использо-
ваны операторы READ, для чтения оче-
редных записей, содержащих компоненты
С-данного. Содержимое параграфов нуле-
вого и второго уровня такое, как если бы
С-данное на первом уровне FS не разделе-
но. Объединение разделенного С-данного
для варианта неупорядоченных компонент
реализовано только в параграфе на первом
уровне алгоритма – в АЗ-параграфе для
разделенного С-данного.
Объединение разделенного С-
данного для варианта упорядоченных ком-
понент реализуется в АЗ- и АЗП-
параграфах. Факт деления С-данного для
параграфа нулевого уровня (не в АЗ- или
АЗП-параграфах) не влияет на алгоритм.
3. Деление С-данного в много-
уровневом FS. С-данное разделено и при
этом оно является компонентой много-
уровневого FS (рис. 7, г). Количество
уровней в FS произвольное (n уровней
n > 3). С-данное может быть размещено в
узлах начиная с нулевого уровня и закан-
чивая уровнем n - 2.
Если компоненты С-данного неупо-
рядочены и нет необходимости поставлять
их для обработки в определенном порядке,
то в АЗ-параграфе будут два цикла, кото-
рые читают компоненты на основной и
смежной А-лентах, а от АЗ-узла будут от-
ходить две ветви. Циклы будут соединены
последовательным сочленением. В DA от
АЗ-узла будут отходить вниз две ветви,
несмотря на то, что в FS от узла с разде-
ленным С-данным отходит одна ветвь. Из-
за этого DA не сохраняет АКУ-
обусловленность.
Если компоненты С-данного упоря-
дочены и их необходимо поставлять для
обработки в определенном порядке, а раз-
деленное С-данное размещено на уровне
n - 2, то в АЗ-параграфе будут два цикла,
которые читают компоненты на основной
а
A
B2
Q
B1
B
C2 C1
C
б в
FS:
A = {B},
B={B1,B2},
B2 = {C},
C={C1,C2}
г д
е ж з
AA
BB
CC
DD
EE
Теоретичні та методологічні основи програмування
12
и смежной А-лентах, а от АЗ-узла будет
отходить вниз одна ветвь. В АЗП-
параграфе АК, которые читают компонен-
ты в определенном порядке, будут соеди-
нены альтернативным сочленением.
Если компоненты С-данного упоря-
дочены и необходимо поставлять их для
обработки в определенном порядке, а раз-
деленное С-данное размещено на уровне
n - 3 или выше, то в АЗ-параграфе будут
два цикла, которые читают компоненты на
основной и на смежной А-лентах, а от АЗ-
узла будет отходить ветвь к АЗП-узлу. В
АЗП-параграфе АК, которые читают ком-
поненты в определенном порядке, будут
соединены альтернативным сочленением.
От АЗП-узла будут отходить вниз две вет-
ви. Из-за этих двух ветвей (их более од-
ной) и узлов на этих ветвях DA не сохра-
няет АКУ-обусловленность.
Независимо от того, на каком из
возможных уровней FS будет расположено
разделенное С-данное, и независимо от
того упорядочены или нет компоненты С-
данного на А-лентах (и надо ли их постав-
лять для обработки в определенном поряд-
ке), АК, что реализует объединение С-
данного, будет расположена в АЗ-
параграфе для узла FS на котором разде-
ленное С-данное. Все параграфы располо-
женные выше в DA, будут такими, как
будто разделения С-данного нет. Для упо-
рядоченных компонент изменения в алго-
ритме, связанные с объединением С-
данного, будут еще в АЗП-параграфе.
Если эти АЗП-узлы не конечные, то
они будут началами ветвей. Различие меж-
ду этими ветвями будет только в том, что в
соответствующих АК операторы READ
будут читать записи с различных А-лент.
4. Деление двух С-данных в трех-
уровневом FS. В трехуровневом FS одно
С-данное разделено в узле на нулевом
уровне, а другое в узле на первом уровне
(рис. 7, е). АЗ-параграф нулевого уровня
FS будет содержать АК, которая будет по-
ставлять для обработки компоненты раз-
деленного С-данного. Этими компонента-
ми есть подобласти. АК будут соответ-
ствовать тому, упорядочены или нет раз-
деленные компоненты на основной и
смежной А-лентах. В АЗП-параграфе
(АЗП-параграфах) используются АК для
объединения С-данного, разделенного на
первом уровне. Для АК нулевого уровня
не имеет значения, какая именно исполь-
зована АК в АЗП-параграфе – объединяет
ли она поставляемую подобласть или
только прочитывает ее с А-ленты. Обе АК,
предназначенные для объединения разде-
ленных С-данных, что размещены в АЗ-
параграфе и в АЗП-параграфе независимы
друг от друга. Их взаимное существование
в этих параграфах не добавляет каких-либо
дополнительных АК или операторов. То
есть, существование более чем одной АК,
предназначенных для объединения разде-
ленных С-данных не порождает синерге-
тического эффекта, – не добавляет слож-
ности в алгоритм. Сложность растет толь-
ко при описании RG. То есть, необходимо
описать то, как размещены Р-данные на А-
лентах, которых более двух.
Если С-данное разделено на нуле-
вом уровне, то оно будет размещаться на
двух А-лентах (Л1 и Л2). Далее, с точки
зрения количества А-лент, при делении С-
данного на первом уровне для окончатель-
ного размещения возможны два варианта.
Первый. Р-данные размещены на трех А-
лентах (Л1 и (Л2 и Л2а) или (Л1 и Л1а) и
Л2. Второй. Р-данные размещены на четы-
рех А-лентах ((Л1 и Л1а) и (Л2 и Л2а). Это
должны быть различные А-ленты. Если же
какие-то из А-лент будут совпадать
(например, Л1 и Л2а или Л1 и Л2 или Л1а
и Л2а), алгоритм будет многопроходным.
При любом размещении в DA отсутствует
АКУ-обусловленность.
5. Общий случай деления С-
данных в многоуровневом FS. В много-
уровневом FS (n уровней, n>3) два С-
данных разделены в узлах на смежных
уровнях (рис. 7, ж). Деление С-данного на
уровне с меньшим номером может быть,
начиная с нулевого и заканчивая уровнем,
номер которого (n-2) на два меньше номе-
ра самого нижнего уровня. Деление С-
данного на смежном с меньшим номером
может быть, соответственно, начиная с
первого и заканчивая уровнем, номер ко-
торого на один меньше номера самого
нижнего уровня (n-1). При этом уровни с
разделенными С-данными соединены вет-
Теоретичні та методологічні основи програмування
13
вью. Независимо от того, на каком уровне
разделено С-данное (от нулевого до n-2),
для объединения разделенных компонент
необходима одна из тех АК, что упомяну-
ты выше, – для упорядоченных или неупо-
рядоченных компонент. Никакие дополни-
тельные операторы или АК не нужны.
Также не нужны дополнительные АК или
операторы в АЗП-параграфе. Ситуация с
DA такая же как и в п. 4. АКУ-
обусловленность не сохраняется.
В многоуровневом FS (n уровней,
n>3) два С-данных разделены на уровнях с
произвольными номерами. Разделенные
С-данные могут быть на различных уров-
нях, которые не обязательно смежные
(рис. 7, з). Деление может быть на уров-
нях, начиная с нулевого и заканчивая
предпоследним (n-1). Как и в предыдущем
случае для объединения разделенных ком-
понент необходима одна из АК, – для упо-
рядоченных или неупорядоченных компо-
нент. Никакие дополнительные операторы
или АК не нужны в обоих АЗ-параграфах.
Ситуация с DA такая же как и в п. 4. АКУ-
обусловленность не сохраняется.
С одним узлом FS может соотно-
ситься более одного С-данного и некото-
рые из них разделены. Разделенных С-
данных в этом узле более одного. То, как
С-данные разделены, описано в RG. Для
объединения компонент каждого из разде-
ленных С-данных подбираются соответ-
ствующие АК. Содержимое каждой из
этих АК независимо друг от друга. Синер-
гетический эффект не порождается. АЗП-
параграфы для объединения каждой груп-
пы компонент независимы друг от друга.
АКУ-обусловленность не сохраняется.
FS содержит много ветвей. Каждая
из ветвей содержит произвольное количе-
ство уровней. В узлах на любом из уров-
ней, кроме узлов конечных по ветви, есть
С-данные. Разделенные С-данные разме-
щены в узлах, которые расположены по
различным ветвям. АК и соответствующие
АЗП-параграфы, необходимые для объ-
единения компонент разделенных С-
данных, независимы друг от друга и не по-
рождают синергетический эффект. АКУ-
обусловленность не сохраняется.
FS содержит произвольное количе-
ство узлов, на произвольном количестве
уровней. Одно С-данное может быть раз-
делено и размещено на более чем двух А-
лентах. Если компоненты необходимо
представить для обработки без сохранения
порядка, то включаются АК, что содержат
циклы для чтения компонент на соответ-
ствующих А-лентах. Количество АК равно
количеству А-лент. Происходит механиче-
ское увеличение количества АК, соеди-
ненных последовательным сочленением.
Если же компоненты необходимо предста-
вить для обработки в определенном поряд-
ке, то потребуется алгоритм балансировки.
Алгоритм формируется независимо от то-
го, есть какое-либо деление С-данных в
узлах на других уровнях. В каждом из этих
двух случаев не наблюдается синергетиче-
ский эффект. АКУ-обусловленность не со-
храняется.
1. Колесник В.Г. DS-теория как прототип
теории прикладных алгоритмов // Пробле-
ми програмування. – 2012. – № 1. – С. 17–
33.
2. Колесник В.Г. DS-теория. Представление
канонического алгоритма с помощью ал-
горитмического языка // Проблеми про-
грамування. – 2015. – № 1. – С. 3–18.
3. Jackson structured programming [Электрон-
ный ресурс] // http://en.wikipedia.org/wiki/
Jackson_structured_programming.
4. Сортировка слиянием [Электронный ре-
сурс] // https://ru.wikipedia.org/wiki/ Сорти-
ровка_слиянием.
Получено 20.04.2015
Об авторе:
Колесник Валерий Георгиевич,
старший научный сотрудник
кафедры АПП.
Место работы автора:
Донбасская государственная
машиностроительная академия.
г. Краматорск, ул. Шкадинова, 72, п/я 13.
|