Матричный способ представления алгоритма | Статья в журнале «Молодой ученый»

Автор:

Рубрика: Технические науки

Опубликовано в Молодой учёный №6 (110) март-2 2016 г.

Дата публикации: 16.03.2016

Статья просмотрена: 333 раза

Библиографическое описание:

Поляков В. С. Матричный способ представления алгоритма // Молодой ученый. — 2016. — №6. — С. 159-164. — URL https://moluch.ru/archive/110/26901/ (дата обращения: 24.09.2018).



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

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

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

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

В настоящее время алгоритмы рассматриваются как последовательностные структуры, то есть выполнение операций осуществляется последовательно.

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

Здесь:

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

– вершины, определяющие логику (порядок) выполнения алгоритма, будем называть предикативными или логическими блоками.

Рис. 1. Граф-схема алгоритма

Задание алгоритма в виде ГСА имеет ряд недостатков:

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

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

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

Второй из этих недостатков устраняется путём объединения нескольких логических функций одной известными приёмами алгебры логики.

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

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

Рис. 2. «Доопределённая» граф-схема алгоритма

Рис. 3. Изображение алгоритма в модульном исполнении

Алгоритм можно задать в виде графа (рис. 4), вершины которого делятся на два непересекающихся множества, то есть граф будет дуальным.

Рис. 4. Задание алгоритма в виде дуального графа

Использование матрично-предикатного способа представления графа [1–3] и представление алгоритма модулями (рис. 3), позволяет задать алгоритм в виде матрицы (рис. 5).

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

Такое представление алгоритма будем называть модульнымвматрично-предикатном виде.

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

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

Такое представление алгоритма будем называть в матрично-предикатной форме.

Задание алгоритмов в матрично-предикатном виде позволяет проводить практически любые операции над ними. Недостатком является то, что при большом количестве компонентов вывод результатов на экран или бумагу получается очень громоздким. Это происходит из-за большой разреженности исходных матриц. Например, квадратная матрица (рис. 5) содержит 324 элемента, а значащих (ненулевых) всего 47.

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

Такое соотношение значащих и нулевых элементов матрицы наводит на мысль использовать для представления алгоритма таблицу составляемую следующим образом.

Предположим, что рассматриваемый алгоритм (как оператор действия, так и оператор логики) представляют собой истинные значения двенадцатиместного предиката, описывающего рассматриваемый процесс.

Второе, третье и четвёртое места определяют процесс функционировния компонента. Места с 4-го по 12-е определяют свойства, положение, время функционировния и другие характеристики объекта в данной точке процесса.

Первая и последняя строки определяют связи истинных значений предиката между собой. Такую форму задания алгоритма будем называть таблично-предикатной.

Таблично-предикатная форма задания рассматриваемого алгоритма представлена ниже.

Рис. 7. Фрагмент задания алгоритма в таблично-предикатной форме

Рассмотрим матрично-предикатное представление алгоритма в модульном виде (рис. 5) и переход к таблично-предикатной форме. На рисунке (рис. 8) представлена таблично-предикатная форма задания рассмотренного алгоритма.

На рисунке (рис. 8) пунктиром выделены модули, 1–4 строчки — это первый модуль — I, 6–9 — это второй -II. После выполнения модуля I происходит выполнение перехода μ0μ01А1 (строка 5) и переход к выполнению модуля II.


Рис. 8. Таблично-предикатная форма алгоритма заданного в модульном виде

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

Литература:

  1. Построение формального описания технологического процесса в матрично-предикатной форме / В. С. Поляков, С. В. Поляков, П. В. Федченков // Известия ВолгГТУ. Серия «Прогрессивные технологии в машиностроении». Вып. 9: межвуз. сб. науч. ст. / ВолгГТУ. — Волгоград, 2013. — № 7 (110). — C. 105–108.
  2. Поляков В. С., Поляков С. В. Запись алгоритма матрицей инцидентора // Инновации на основе информационных и коммуникационных технологий. Инфо 2014: матер. XI междунар.научн.-практ. Конф. (г. Сочи, 1–10 окт. 2014) /Национальный исследовательский ун-т «Высшая школа экономики» [и др.]. — М., 2014. — с. 149–152.
  3. Использование нагруженных матриц инцидентора (операторов) для моделирования сложных систем / В. С. Поляков, С. В. Поляков // Контроль. Диагностика. — 2013. — № 3. — C. 57–62.
  4. Поляков С. В., Сластинин С. Б., Поляков В. С. Исключение изоморфизма при операциях над графами, описывающими технологический процесс. // Контроль. Диагностика — 2006.– № 1
Основные термины (генерируются автоматически): представление алгоритма, матрично-предикатный вид, таблично-предикатная форма, алгоритм, модульное исполнение, модульный вид, матрично-предикатная форма, выполнение модуля, выполнение операции, таблично-предикатная форма задания.


Похожие статьи

Представление формального описания функционирования...

В работе рассмотрено представление алгоритма в матрично-предикатном виде двумя способами: модульном и функционально-предикативном. Рассмотрено параллельное взаимодействие компонентов путём применения операции композиции.

Матричный способ представления алгоритма

Представление формального описания функционирования механизмов судоходного шлюза в матрично-предикатной форме.

Матричный способ представления алгоритма. №6 (110) март-2 2016 г.

Предложения с модальными лексемами со значением...

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

- глагольной лексемой (личный глагол, неличные формы глагола, отглагольные имена).

Особенности изучения способа тестирования базового пути...

Различают операторные и предикатные узлы. Из операторного узла выходит одна дуга, а из предикатного — две дуги.

Свойства базового множества: 1) тесты, обеспечивающие его проверку, гарантируют: а) однократное выполнение каждого оператора

Поляков Сергей Владимирович — Информация об авторе

Представление формального описания функционирования механизмов судоходного шлюза в матрично-предикатной форме. №17 (151) апрель 2017 г. Авторы: Поляков Сергей Владимирович, Поляков Владимир Сергеевич.

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

В результате выполнения такого алгоритма получится развернутая запись числа, которая громоздкая на вид, но дает колоссальный эффект при вычислении выражений типа an; Например, число a10 можно представить как ((a2)2*a)2...

Программирование разностного метода решения одной задачи для...

При записи в разностной форме начальное условие , , запишется в следующем виде

Данная схема условно устойчива (устойчива при выполнении условия ). Алгоритм вычислений по явной схеме.

Анализ уязвимости переполнения буфера | Статья в журнале...

Такие уязвимости могут принимать разнообразные формы: несовершенство протоколов, недостаточная обработка

Рис. 3. Состояние стека к моменту исполнения инструкции ret.

Видно, что по адресу 0040134d происходит выполнение команды lea, которая в данном случае...

Использование матричной схемы агрегирования в задаче оценки...

Отдельное независимое предприятие перестало быть доминирующей формой бизнеса, широкое распространение

… Рассмотрим алгоритм ранжирования объектов на основе матричной схемы агрегирования с помощью стандартного трехуровнего нечеткого 01-классификатора

Представление формального описания функционирования...

В работе рассмотрено представление алгоритма в матрично-предикатном виде двумя способами: модульном и функционально-предикативном. Рассмотрено параллельное взаимодействие компонентов путём применения операции композиции.

Матричный способ представления алгоритма

Представление формального описания функционирования механизмов судоходного шлюза в матрично-предикатной форме.

Матричный способ представления алгоритма. №6 (110) март-2 2016 г.

Предложения с модальными лексемами со значением...

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

- глагольной лексемой (личный глагол, неличные формы глагола, отглагольные имена).

Особенности изучения способа тестирования базового пути...

Различают операторные и предикатные узлы. Из операторного узла выходит одна дуга, а из предикатного — две дуги.

Свойства базового множества: 1) тесты, обеспечивающие его проверку, гарантируют: а) однократное выполнение каждого оператора

Поляков Сергей Владимирович — Информация об авторе

Представление формального описания функционирования механизмов судоходного шлюза в матрично-предикатной форме. №17 (151) апрель 2017 г. Авторы: Поляков Сергей Владимирович, Поляков Владимир Сергеевич.

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

В результате выполнения такого алгоритма получится развернутая запись числа, которая громоздкая на вид, но дает колоссальный эффект при вычислении выражений типа an; Например, число a10 можно представить как ((a2)2*a)2...

Программирование разностного метода решения одной задачи для...

При записи в разностной форме начальное условие , , запишется в следующем виде

Данная схема условно устойчива (устойчива при выполнении условия ). Алгоритм вычислений по явной схеме.

Анализ уязвимости переполнения буфера | Статья в журнале...

Такие уязвимости могут принимать разнообразные формы: несовершенство протоколов, недостаточная обработка

Рис. 3. Состояние стека к моменту исполнения инструкции ret.

Видно, что по адресу 0040134d происходит выполнение команды lea, которая в данном случае...

Использование матричной схемы агрегирования в задаче оценки...

Отдельное независимое предприятие перестало быть доминирующей формой бизнеса, широкое распространение

… Рассмотрим алгоритм ранжирования объектов на основе матричной схемы агрегирования с помощью стандартного трехуровнего нечеткого 01-классификатора

Обсуждение

Социальные комментарии Cackle

Похожие статьи

Представление формального описания функционирования...

В работе рассмотрено представление алгоритма в матрично-предикатном виде двумя способами: модульном и функционально-предикативном. Рассмотрено параллельное взаимодействие компонентов путём применения операции композиции.

Матричный способ представления алгоритма

Представление формального описания функционирования механизмов судоходного шлюза в матрично-предикатной форме.

Матричный способ представления алгоритма. №6 (110) март-2 2016 г.

Предложения с модальными лексемами со значением...

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

- глагольной лексемой (личный глагол, неличные формы глагола, отглагольные имена).

Особенности изучения способа тестирования базового пути...

Различают операторные и предикатные узлы. Из операторного узла выходит одна дуга, а из предикатного — две дуги.

Свойства базового множества: 1) тесты, обеспечивающие его проверку, гарантируют: а) однократное выполнение каждого оператора

Поляков Сергей Владимирович — Информация об авторе

Представление формального описания функционирования механизмов судоходного шлюза в матрично-предикатной форме. №17 (151) апрель 2017 г. Авторы: Поляков Сергей Владимирович, Поляков Владимир Сергеевич.

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

В результате выполнения такого алгоритма получится развернутая запись числа, которая громоздкая на вид, но дает колоссальный эффект при вычислении выражений типа an; Например, число a10 можно представить как ((a2)2*a)2...

Программирование разностного метода решения одной задачи для...

При записи в разностной форме начальное условие , , запишется в следующем виде

Данная схема условно устойчива (устойчива при выполнении условия ). Алгоритм вычислений по явной схеме.

Анализ уязвимости переполнения буфера | Статья в журнале...

Такие уязвимости могут принимать разнообразные формы: несовершенство протоколов, недостаточная обработка

Рис. 3. Состояние стека к моменту исполнения инструкции ret.

Видно, что по адресу 0040134d происходит выполнение команды lea, которая в данном случае...

Использование матричной схемы агрегирования в задаче оценки...

Отдельное независимое предприятие перестало быть доминирующей формой бизнеса, широкое распространение

… Рассмотрим алгоритм ранжирования объектов на основе матричной схемы агрегирования с помощью стандартного трехуровнего нечеткого 01-классификатора

Представление формального описания функционирования...

В работе рассмотрено представление алгоритма в матрично-предикатном виде двумя способами: модульном и функционально-предикативном. Рассмотрено параллельное взаимодействие компонентов путём применения операции композиции.

Матричный способ представления алгоритма

Представление формального описания функционирования механизмов судоходного шлюза в матрично-предикатной форме.

Матричный способ представления алгоритма. №6 (110) март-2 2016 г.

Предложения с модальными лексемами со значением...

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

- глагольной лексемой (личный глагол, неличные формы глагола, отглагольные имена).

Особенности изучения способа тестирования базового пути...

Различают операторные и предикатные узлы. Из операторного узла выходит одна дуга, а из предикатного — две дуги.

Свойства базового множества: 1) тесты, обеспечивающие его проверку, гарантируют: а) однократное выполнение каждого оператора

Поляков Сергей Владимирович — Информация об авторе

Представление формального описания функционирования механизмов судоходного шлюза в матрично-предикатной форме. №17 (151) апрель 2017 г. Авторы: Поляков Сергей Владимирович, Поляков Владимир Сергеевич.

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

В результате выполнения такого алгоритма получится развернутая запись числа, которая громоздкая на вид, но дает колоссальный эффект при вычислении выражений типа an; Например, число a10 можно представить как ((a2)2*a)2...

Программирование разностного метода решения одной задачи для...

При записи в разностной форме начальное условие , , запишется в следующем виде

Данная схема условно устойчива (устойчива при выполнении условия ). Алгоритм вычислений по явной схеме.

Анализ уязвимости переполнения буфера | Статья в журнале...

Такие уязвимости могут принимать разнообразные формы: несовершенство протоколов, недостаточная обработка

Рис. 3. Состояние стека к моменту исполнения инструкции ret.

Видно, что по адресу 0040134d происходит выполнение команды lea, которая в данном случае...

Использование матричной схемы агрегирования в задаче оценки...

Отдельное независимое предприятие перестало быть доминирующей формой бизнеса, широкое распространение

… Рассмотрим алгоритм ранжирования объектов на основе матричной схемы агрегирования с помощью стандартного трехуровнего нечеткого 01-классификатора

Задать вопрос