Представление алгоритма в матрично-предикатном виде

TECHNICAL SCIENCES

Presentation of the algorithm in the form of a matrix-predicate Poliakov V.1, Poliakov S.2

1 Поляков Владимир Сергеевич /Poliakov Vladimir - кандидат технических наук, доцент;

2Поляков Сергей Владимирович /Poliakov Sergei - кандидат технических наук, доцент, кафедра вычислительной техники,

Волгоградский государственный технический университет, г. Волгоград

Аннотация: в работе рассматривается представление алгоритмов в матричнопредикатном виде. Рассмотрены два варианта такого представления алгоритма: модульное и функционально-предикативное. Показана возможность разбиения последнего на четыре составляющие, что облегчает проведение операций над ними. Abstract: the paper considers the idea of algorithms in the form of a matrix-predicate. Two variants of the presentation of the algorithm: a modular and functional and predicative. The possibility of splitting the last four components that facilitates operations on them.

Ключевые слова: алгоритм, параллелизм, граф, предикат.

Keywords: algorithm, parallelism, graph, predicate.

Существует несколько способов представления алгоритмов [1-3]. Наибольшее распространение получили графические способы, как наиболее наглядные и компактные. На практике чаще всего встречаются граф-схемы алгоритма (ГСА), диаграммы Насси — Шнейдермана, ДРАКОН и др. [3-5].

Современные методики построения алгоритмов хороши и достаточны лишь в тех случаях, когда требуется описывать достаточно простые процессы. В противном случае существует возможность разделения основной ветви алгоритма на несколько. Среди них может быть как одна главная и несколько побочных, так и их равноценность с точки зрения важности. В данной статье рассматривается задание алгоритма в матрично-предикатном виде посредством использования в качестве базы двудольного графа.

Количество блочных символов при различных подходах к заданию алгоритма в графическом виде различно, зависит от поставленных задач и методов их решения. Например, в [6] показано, что любая блок-схема - это ориентированная сеть с вершинами трёх типов: функциональные, предикативные и объединяющие.

Рассмотрим произвольную ГСА (рис. 1).

Здесь:

А = { Ао, Ах, А2, А3, А4, А5, А6, А7, А8 } - вершины, определяющие

выполнение отдельных операций, будем называть функциональными блоками;

а = {а2, а3, а4, а5, а40}— вершины, определяющие логику (порядок) выполнения

алгоритма, будем называть функциональными или логическими блоками.

Работа с алгоритмами, заданными в таком виде (рис. 1), осложняется следующими недостатками:

- переход от выполнения одной операции к выполнению другой в некоторых случаях ничем не обозначен, например, вершины А0 - А1 - А2, здесь подразумевается, что после выполнения операции А1 следует переход к выполнению операции А2, хотя такой переход ничем не фиксируется;

- условия, определяющие порядок выполнения алгоритма, часто задаются несколькими логическими функциями, что усложняет рассмотрение алгоритма.

29

Возможны два варианта устранения первого из этих недостатков:

1. При наличии последовательно соединённых операторов действия их заменяют на один, например, в рассматриваемом примере операторы. А1 и А2 заменяют на оператор А12. В этом случае окончание выполнения объединенного оператора А12 будет фиксироваться оператором логики а2.

2. Необходимо определить окончание каждого из функциональных операторов и, тем самым, определить зоны их действия. В результате проведения такой операции приходим к получению модульных блоков алгоритма. Такую операцию будем называть в дальнейшем операций доопределения.

Рассмотрим связанную пару из функционального - Д (рис. 2) и предикативного -Л (рис. 3) блоков:

Д - блок имеет один выход и может иметь несколько входов;

Л - блок имеет один вход и может иметь несколько выходов.

Рис. 2. Функциональный блок

Связанную пару (рис. 4) будем называть функционально-предикатным модулем - М. Внутренняя связь Xq показывает, что работа функционального узла - Д проводится до момента исчезновения сигнала. В общем виде модуль - М будет выглядеть (рис. 5).

Рис. 3. Предикативный блок

30

Рис. 4. Функционально-предикатный

Рис. 5. Модульный блок

Для построения алгоритма в модульном виде проведём ряд предварительных операций. Зафиксируем окончание выполнения каждого функционального блока соответствующим предикативным блоком. Если переход от выполнения одной операции к выполнению другой ведётся напрямую, иначе говоря, если между функциональными блоками отсутствует предикативный, то, введя предикативную вершину аг0, получим модуль (рис 6).

Рис. 6. Введение предикативной вершины

Если после функционального блока существует один или несколько предикативных блока, но отсутствует фиксация окончания работы функционального блока, вводим дополнительно предикативную вершину аг0. Объединим все предикативные вершины в один многозначный предикативный блок и получим модуль (рис. 7).

Рис. 7. Переход к модульному блоку

31

Используя вышеприведённые принципы получения модулей «доопределим» функциональные блоки алгоритма (рис. 1) в итоге исходная ГСА примет вид (рис. 8).

Пунктиром выделены модули алгоритма, а на рисунке (рис. 9) приведено изображение алгоритма в модульном исполнении, которое представляет собой граф Бержа.

Рис. 9. Модульное представление ГСА

Алгоритм можно задать в виде графа (рис. 10), вершины которого делятся на два непересекающихся множества, то есть граф будет дуальным. Использование матрично-предикатного способа [7 - 9] представления модулей алгоритма позволяет задать алгоритм в виде матрицы (рис. 11). Такое представление алгоритма будем называть модульным в матрично-предикатном виде.

32

Квадратная матрица алгоритм МА, заданная в матрично-предикатном виде, обладает свойством неизменности свойств описываемого объекта при одновременной замене строки и столбца с одинаковыми номерами на соответствующую пару с другим номером.

Проведём такую операцию с матрицей МА, разнеся функциональные и предикативные вершины алгоритма в противоположные стороны. В итоге получим описание того же алгоритма в виде в МА в несколько иной форме (рис. 12). Такое представление алгоритма будем называть функционально-предикативным в матрично-предикатной форме.

Матрицу, заданную таким способом, легко представить в виде четырех частей.

М

А*.

ОРАД ОРАд-Л Матрица операторов действия Матрица переходов операторы действия-операторы логики

ОРАдл ОРАЛ Матрица переходов операторы логики-операторы действия Матрица операторов логики

МА

^оИ°о А0 ^4оЦ°о и° 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

ц"м°0 Aq nVo и0 mVi U 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 А^о Ai Aii^o и1 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 Ai И1 ц’ц1! а2 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 А2ц2о а2 А2ц2о и2 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 М'Мо а2 М'Мо _л2__ ММ~2 А$ 0 0 0 0 0 0 0 1 А7 0 0 0

0 0 0 0 Ц2Ц2о а2 0 А$ц3о As ^4зЦ3о и3 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 мУ'л As Ц3Ц3о и3 mV'i А4 0 0 0 Ц3Ц32 А6 0 0 0 0 0

0 0 0 0 0 0 0 0 LT___ Л.4Ц4о и4 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 Ц Ц 0 L м4м4л _ м4 _ nVi 0 0 0 и4и42 А7 0 0 0

0 0 0 0 0 0 0 0 0 0 ^5Ц50 As ^5Ц50 и5 0 0 0 0 0 0

0 0 0 0 0 0 0 0 А4 0 As ЦэЦэо М5 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 Аб№6о А6 Аб.р6о и6 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 bV. А6 ЦбЙ60 М* 0 0 иУЗ Ак 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 A-j)^ о А6 А-}]^ 0 и7 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 nV'i A~j ЦЦо _а__, Ц Ц о Ак. 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 ЛкЛко Ак ЛкИко ик

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Цк hVk икик0 ик

Рис. 11. Модульное представление алгоритма в матрично-предикатном виде

33

А0Ц° о А0 0 0 0 0 0 0 0 0 АоЦ°о и0 0 0 0 0 0 0 0 0

0 А1ц1 0 А1 0 0 0 0 0 0 0 0 А1ц1 0 ц1 0 0 0 0 0 0 0

0 0 А2ц20 А2 0 0 0 0 0 0 0 0 А2Ц20 Ц2 0 0 0 0 0 0

0 0 0 А3ц30 А3 0 0 0 0 0 0 0 0 А3Ц30 Ц3 0 0 0 0 0

0 0 0 0 А4ц40 А4 0 0 0 0 0 0 0 0 А4Ц40 Ц4 0 0 0 0

0 0 0 0 0 А5ц50 А5 0 0 0 0 0 0 0 0 А5ц50 Ц5 0 0 0

0 0 0 0 0 0 А6ц60 А6 0 0 0 0 0 0 0 0 А6.ц60 Ц6 0 0

0 0 0 0 0 0 0 А7ц70 А6 0 0 0 0 0 0 0 0 А7.Ц70 Ц7 0

0 0 0 0 0 0 0 0 Ак.И 0 Ак 0 0 0 0 0 0 0 0 Ак.Ц 0

0 0 Ц Ц 0 А0 0 0 Ц Ц 1 А1 0 0 0 0 0 0 0 иУо и0 0 0 0 0 0 0 0 0

0 ЦЦ0 А1 ц1ц11 А2 0 0 0 0 0 0 0 ЦЦ0 ц1 0 0 0 0 0 0 0

0 0 ЦЦ0 А2 ЦЦ2 А3 0 0 0 ц2ц2 1 А7 0 0 0 ЦЦ0 Ц2 0 0 0 0 0 0

0 0 0 Ц3Ц30 А3 ц3ц31 А4 Ц3Ц32 А6 0 0 0 0 0 Ц3Ц30 Ц3 0 0 0 0 0

0 0 0 0 Ц4Ц40 А4 Ц4Ц41 А5 0 Ц4Ц42 А7 0 0 0 0 0 44 Ц4Ц40 Ц4 0 0 0 0

0 0 0 0 Ц5Ц50 А4 Ц5Ц50 А5 0 0 0 0 0 0 0 0 Ц5Ц50 Ц5 0 0 0

0 0 0 0 0 0 Ц6Ц60 А6 0 nVi Ак 0 0 0 0 0 0 Ц6Ц60 Ц6 0 0

0 0 0 0 0 0 0 Ц7Ц70 А7 и7 Ц7(к4к 0 0 0 0 0 0 0 Ц7Ц70 Ц7 0

0 0 0 0 0 0 0 0 мк 0 0 0 0 0 0 0 0 Цкцк0

Рис. 12. Функционально-предикативное представление алгоритма в матрично-предикатном виде

A*

М

Показанные в данной работе два вида представления алгоритма, а именно модульный и функционально-предикативный, имеют одинаково важное значение. Использовать для серьезной многокомпонентной задачи или же для работы со сложными системами один из них, исключая другой, было бы нерационально. Лучшим вариантом является сочетание обоих методов по ходу работы, используя на каждом этапе преимущества того или иного метода.

Работать с алгоритмами, представленными в таком виде, значительно легче, так как появляется возможность частично автоматизировать эвристические методы их построения.

Литература

1. Колмогоров. А.Н. Теория ииформации и теория алгоритмов.— М.: Наука, 1987.304 с.

2. Альфред В. Ахо, Джон Е. Хопкрофт, Джеффри Д. Ульман, Структуры данных и алгоритмы: М.: Издательский дом «Вильяме», 2000. — 384 с.

3. ЯновЮ.И. О логических схемах алгоритмов.// Проблемы кибернетики. М.: 1958

4. Паронджанов В. Д. Учись писать, читать и понимать алгоритмы. Алгоритмы для правильного мышления. Основы алгоритмизации. — М.: ДМК Пресс, 2012. — 520 с.

5. Дж. Макконелл, Основы современных алгоритмов, М.: «Техносфера», 2004, С. 10-11.

6. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. - М.: Мир, 1981. 368 с.

7. Поляков В.С., Поляков С.В., Федченков П.В. Построение формального описания технологического процесса в матрично-предикатной форме // Известия ВолгГТУ.

34

Серия «Прогрессивные технологии в машиностроении». Вып. 9: межвуз. сб. науч. ст. / ВолгГТУ. - Волгоград, 2013. - № 7 (110). - C. 105-108.

8. Поляков В.С., Поляков С. В. Запись алгоритма матрицей инцидентора // Инновации на основе информационных и коммуникационных технологий. Инфо 2014: матер. XI междунар.научн.-практ. Конф. (г. Сочи, 1-10 окт. 2014) /Национальный исследовательский ун-т «Высшая школа экономики» [и др.]. - М., 2014. - с. 149-152.

9. Поляков В.С., Поляков С.В. Использование нагруженных матриц инцидентора (операторов) для моделирования сложных систем / // Контроль. Диагностика. -2013. - № 3. - C. 57-62.

Application of vegetable oils as diluents for the extragents applied at extraction processes of rare-earth elements from the water-salt systems Luckii D. , Shtirc G.

Применение растительных масел в качестве растворителей для экстрагентов, применяемых при извлечении редкоземельных

элементов из водно-солевых систем

12

Луцкий Д. С. , Штырц Г. А.

2Луцкий Денис Сергеевич /Luckii Denis - кандидат технических наук, доцент, кафедра общей и физической химии, факультет переработки минерального сырья;

2Штырц Герман Александрович / Shtirc German - студент, факультет переработки минерального сырья,

Национальный минерально-сырьевой университет «Горный», г. Санкт-Петербург

Аннотация: в статье изучена потенциальная возможность применения различных органических растворов на основе растительных масел (подсолнечное, оливковое) с добавлением чистой олеиновой кислоты в качестве экологически чистых экстрагентов для извлечения редкоземельных элементов из водно-солевых систем. Получены зависимости степени извлечения ионов Ce (III) от кислотности водной фазы и типа органического растворителя. Показана потенциальная возможность применения растительных масел в качестве эффективных, экологически безопасных растворителей для различных экстрагентов.

Abstract: article explore the potential application of different organic solutions based on vegetable oils (sunflower, olive) with the addition of pure oleic acid as an environmentally friendly extractants for the extraction of rare earths from water-salt systems. The dependences ion extraction extent Ce (III) on the acidity of the aqueous phase and the type of organic solvent. The potential application of vegetable oils as effective, environmentally safe solvents for various extractants was showed.

Ключевые слова: экстракция, растительные масла, редкоземельные элементы. Keywords: extraction, vegetable oils, rare-earth elements.

Введение

Редкоземельные элементы (РЗЭ) применяют в самых разнообразных технологических процессах металлургической, нефтяной, стекольной, керамической, атомной промышленности и предприятий оборонного комплекса [1].

Жидкостная экстракция - один из наиболее эффективных способов извлечения РЗЭ из водно-солевых систем [2-4].

35