Применение алгоритма блочно-функционального распределения для вычисления значений алгебраических выражений | Статья в журнале «Молодой ученый»

Авторы: ,

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

Опубликовано в Молодой учёный №7 (111) апрель-1 2016 г.

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

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

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

Секачев В. А., Авдеюк О. А. Применение алгоритма блочно-функционального распределения для вычисления значений алгебраических выражений // Молодой ученый. — 2016. — №7. — С. 167-170. — URL https://moluch.ru/archive/111/27283/ (дата обращения: 14.12.2018).



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

Успех внедрения информационно-измерительных систем, информационно-вычислительных комплексов, автоматизированных систем управления технологическими процессами в различные сферы жизни зависит не только от требований заказчика, но и от того, насколько данные требования учтены и реализованы в необходимом объеме. Для того, чтобы учесть все требования заказчика, необходима детальная проработка этих сведений как для проектирования данного объекта с учетом реализованных функций, так и с учётом требований среды, в которой будет функционировать объект. Детальная проработка этих требований достигается только с позиций структурно-иерархического системного подхода. Этот подход представляет собой математический аппарат, на основании которого возможно, детализируя алгоритм БФР путём проработки под конкретные случаи, разработать многочисленные алгоритмы процедур и функций как основу для построения специализированных программных систем (ПС). Проектируемая структура отображается в виде направленного графа, где вершины — подсистемы, стойки, блоки, платы, дискретные элементы — это зависит от уровня детализации по структурно-иерархическому представлению, а рёбра — информационные связующие функциональных элементов. Согласно алгоритму блочно-функционального распределения (БФР) [1, 3], нулевой уровень детализации это граф — состоящий из одной единственной вершины с описанием свёртки входящих и выходящих информационных составляющих. Первый уровень детализации — это уровень подсистем (в случае, если при проектировании используется модель предметов). Вершины графа первого уровня детализации в этом случае — это подсистемы. Свертка входящих и выходящих информационных составляющих в этом случае распределяется на все подсистемы, представленные вершинами. Каждая вершина подсистемы может быть детализирована направленным графом стойки и т. д. Детализация ведётся до тех пор, пока обнаружится принципиальная схема, образующая тот или иной функциональный элемент.

Изначально алгоритм блочно-функционального распределения [1, 2] было принято использовать для оптимального размещения функций по элементам определённого уровня с целью сохранения функциональности всей проектируемой ИИС. Этот алгоритм может работать как и для синтеза (с использованием оптимизации структуры по критерию наименьшей/наибольшей внешней устойчивости), так и для анализа (например, построение синтаксического анализатора, позволяющего из функции, заданной алгебраически построить её структурное представление в виде направленного графа. Это производится путём выделения отдельных функциональных элементов, сопоставления выделенного функционального элемента с элементарным фрагментом, добавления фрагмента в массив данных получаемой структуры и вывод полученной структуры на контекст отображения. Таков алгоритм реализован [3].

Целесообразно вместо структурных фрагментов использовать фрагменты элементарных или составных математических выражений, представленные в виде строк. Затем вместо строковых аргументов поставить реальные числа и вычислить значение, результат преобразовать в строковое представление и подставить на место фрагмента выражения. В виде блок схемы это будет выглядеть как на рисунке 1.

Проиллюстрируем работу этого алгоритма на примере вычисления выражения

0,7*x^3+x^2–3*x-67 для значения x=0,349.

П.1;Ш.1 Подставляем вместо x числовое значение: '0,7*0,349^3+0,349^2–3*0,349–67'. (1)

П.1;Ш.2 Инициализируем строковый массив операторов ('+', '-', '*', '/', '+', '-', '*', '/', 'sin', 'cos', 'ctg', 'tg', 'cosec', 'sec', 'log', 'ln', 'lg', '^') и фрагментов выражений ('(?+?)', '(?-?)', '(?*?)', '(?/?)', '?+?', '?-?', '?*?', '?/?', 'sin(?)', 'cos(?)', 'ctg(?)', 'tg(?)', 'cosec(?)', 'sec(?)', 'log(?)(?)', 'ln(?)', 'lg(?)', '?^?'). (2)

П.1;Ш.3 Заменяем знак отрицательного числа на @1*: '0,7*x^3+x^2+@1*3*x+@1*67'. (3)

П.1;Ш.4 Выделяем из выражения числовые и буквенные составляющие с занесением в отдельный строковый массив ('0,7', 'x', '3', 'x', '2', '@1', '3', 'x', '@1', '67'). (4)

П.1;Ш.5 Формируем на основе исходной строки строку без числовых и буквенных составляющих, заменяя последние вопросительными знаками: '?*?^?+?^?+?*?*?+?*?'. (5)

П.1;Ш.6 Формируем массив порядковых номеров этих вопросительных знаков: (1, 3, 5, 7, 9, 11, 13, 15, 17, 19). (6)

Рис. 1. Блок-схема

П.1;Ш.7 Выделение первого фрагмента выражения и оператора:?^? и ^. (7)

П.1;Ш.8 Подстановка вместо? численных значений: '0,349^3'. (8)

П.1;Ш.9 Определение начала выражения (8) в выражении (3). (9)

П.1;Ш.10 Вычисление значения (8)вчисленном виде:0,042508549. (10)

П.1;Ш.11 Преобразование результата из (10)встроку и подстановка в (3)вместо '0,349^3': '0,7*0,042508549+0,349^2+@1*3*0,349+@1*67'. (11)

П.1;Ш.12 Проверка выражения из (11)на число. Оно числом не является.

Начинается второй проход с шагами 3–11.

П.2;Ш.3 Заменяем знак отрицательного числа на @1*: '0,7*0,042508549+0,349^2+@1*3*0,349+@1*67'. (3)

П.2;Ш.4 Выделяем из выражения числовые и буквенные составляющие с занесением в отдельный строковый массив ('0,7', '0,042508549', '0,349', '2', '@1', '3', '0,349', '@1', '67'). (4)

П.2;Ш.5 Формируем на основе исходной строки строку без числовых и буквенных составляющих, заменяя последние вопросительными знаками: '?*?+?^?+?*?*?+?*?'. (5)

П.2;Ш.6 Формируем массив порядковых номеров этих вопросительных знаков: (1, 3, 5, 7, 9, 11, 13, 15, 17). (6)

П.2;Ш.7 Выделение первого фрагмента выражения и оператора:?^? и ^. (7)

П.2;Ш.8 Подстановка вместо? численных значений: '0,349^2'. (8)

П.2;Ш.9 Определение начала выражения (8) в выражении (3). (9)

П.2;Ш.10 Вычисление значения (8)вчисленном виде:0,121801. (10)

П.2;Ш.11 Преобразование результата из (10)встроку и подстановка в (3)вместо '0,349^2': '0,7*0,042508549+0,121801+@1*3*0,349+@1*67' (11)

П.2;Ш.12 Проверка выражения из (11)на число. Оно числом не является.

Начинается третий проход с шагами 3–12.

Для того, чтобы получить результат вычисления — окончательное число, '@67,8954430157' для данного выражения потребовалось 9 проходов данного алгоритма. Нормальный результат — -67,8954430157.

Как показывает пример применения БФР к анализу и вычислению аналогового выражения, аналогичный подход можно использовать и для логических выражений, если заменить список элементарных компонент.

Литература:

  1. Муха, Ю.П., Алгебраическая теория синтеза сложных систем [Текст] / Ю. П. Муха, О. А. Авдеюк, И. Ю. Королёва. — Волгоград: Изд-во Политехник, 2003. — 320 с.
  2. Математические методы информатики в задачах и примерах: Опыт применения в проектировании сложных систем: учеб. пособие [Текст] / Авдеюк О. А., Горбачев С. В., Муха Ю. П., Секачев В. А., Сырямкин В. И.,Титов В. С., Ширабакина Т. А.; ФГБОУ ВПО «Национальный исследовательский Томский гос. ун-т».-Томск: Изд-во Томского ун-та, 2012. — 483 с.
  3. Синтезатор структур измерительных систем из функционального уравнения: свидетельство об официальной регистрации программы для ЭВМ. ВНТИЦ № 2007613258 Российская Федерация / Муха Ю. П., Секачёв В. А.; зарегистрировано в реестре программ для ЭВМ 03.08.2007.
  4. Рубичев, Н.А., Измерительные информационные системы [Текст] / Н. А. Рубичев. — М: Дрофа, 2010. — 334, [2] с.: ил.
  5. Новиков, Ф. А. Дискретная математика для программистов [Текст] / Ф. А. Новиков. — СПб.: Изд-во Питер, 2001. — 304 с.
Основные термины (генерируются автоматически): выражение, блочно-функциональное распределение, Вычисление значения, синтаксический анализатор, отрицательное число, отдельный строковый массив, исходная строка, детальная проработка, число, составляющая, знак, алгоритм, направленный граф, уровень детализации, требование заказчика, Проверка выражения, Преобразование результата, Выделение первого фрагмента выражения.


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

Статический анализатор кода на основе взаимодействия...

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

В случае, если переменная-указатель указывает на первый элемент массива, смещение равно нулю.

Использование алгоритмов нечеткого поиска при решении задачи...

Предложен алгоритм вычисления функции релевантности на основании метода N-gram.

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

Алгоритмы распознавания объектов | Статья в сборнике...

Используя эти выражения, получаем значения свойства, которые будут инвариантными к

Для вычисления значения признака подобного типа применяется формула(23).

Алгоритмы выделения параметрических кривых на основе преобразование Хафа [Электронный ресурс].

Разработка алгоритма нечеткого поиска на основе хэширования

Описание используемого алгоритма исравнение результатов.

словарь сортируется по возрастанию значений h(i) — значений хэшей. û(1): , где y — образ входного запроса.

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

Модальная сущность отрицания в форматах...

Отрицание в лингвистике — это “выражение при помощи лексических, фразеологических, синтаксических и других средств языка того, что связь

Субъективная оценка, или в целом модальность, является сущностью высказывания, а не отдельным его фрагментом.

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

Рис. 1. Граф-схема алгоритма. Задание алгоритма в виде ГСА имеет ряд недостатков

Это происходит из-за большой разреженности исходных матриц.

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

Анализ применения гомоморфных схем шифрования...

...обучения на основе алгоритмов криптографического преобразования ГОСТ РФ 28147–89 и алгоритмом

Исходные данные и результат работы могут быть доступны только клиенту

Ограничение на работу с целыми числами, количество возможных операций сложения и...

Алгоритм интервального оценивания параметров нелинейных...

. Выражение для масштабированного штрафа принимает вид: . III. Описание программы.

Ulog, Vlog, V — целые числа, определяющие поток алгоритма

Sub CT() — очистка таблиц от результатов предыдущих вычислений([1])

Анализ методов сегментации изображений | Статья в журнале...

В качестве примера комбинированного подхода можно привести алгоритм сегментации по цветовым характеристикам пикселей с выделением зон оценки признаков движения

А. Считаем значение первого пикселя P1 соответствующим некоторому классу S1.

Обсуждение

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

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

Статический анализатор кода на основе взаимодействия...

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

В случае, если переменная-указатель указывает на первый элемент массива, смещение равно нулю.

Использование алгоритмов нечеткого поиска при решении задачи...

Предложен алгоритм вычисления функции релевантности на основании метода N-gram.

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

Алгоритмы распознавания объектов | Статья в сборнике...

Используя эти выражения, получаем значения свойства, которые будут инвариантными к

Для вычисления значения признака подобного типа применяется формула(23).

Алгоритмы выделения параметрических кривых на основе преобразование Хафа [Электронный ресурс].

Разработка алгоритма нечеткого поиска на основе хэширования

Описание используемого алгоритма исравнение результатов.

словарь сортируется по возрастанию значений h(i) — значений хэшей. û(1): , где y — образ входного запроса.

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

Модальная сущность отрицания в форматах...

Отрицание в лингвистике — это “выражение при помощи лексических, фразеологических, синтаксических и других средств языка того, что связь

Субъективная оценка, или в целом модальность, является сущностью высказывания, а не отдельным его фрагментом.

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

Рис. 1. Граф-схема алгоритма. Задание алгоритма в виде ГСА имеет ряд недостатков

Это происходит из-за большой разреженности исходных матриц.

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

Анализ применения гомоморфных схем шифрования...

...обучения на основе алгоритмов криптографического преобразования ГОСТ РФ 28147–89 и алгоритмом

Исходные данные и результат работы могут быть доступны только клиенту

Ограничение на работу с целыми числами, количество возможных операций сложения и...

Алгоритм интервального оценивания параметров нелинейных...

. Выражение для масштабированного штрафа принимает вид: . III. Описание программы.

Ulog, Vlog, V — целые числа, определяющие поток алгоритма

Sub CT() — очистка таблиц от результатов предыдущих вычислений([1])

Анализ методов сегментации изображений | Статья в журнале...

В качестве примера комбинированного подхода можно привести алгоритм сегментации по цветовым характеристикам пикселей с выделением зон оценки признаков движения

А. Считаем значение первого пикселя P1 соответствующим некоторому классу S1.

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