Загрузка...
Учебная работа. Реферат: Способы построения циклических вычислительных процессов
1. методы построения повторяющихся вычислительных действий в программках.
2. В комп вводится
N
вещественных чисел. Составить программку, выдающую на экран среднее арифметическое
Введение
Циклические программки употребляются фактически в любом программном обеспечении. При всем этом циклы могут быть очевидными и неявными. А именно неявный цикл находится в обработчиках прерываний, которые практически работают в нескончаемом цикле, чье тело инициируется прерыванием. Повторяющимися являются и подпрограммы — оконные функции приложений Windows. Дальше рассматриваются программки с циклом, тело которого содержит многофункциональные модули.
Повторяющийся процесс
— это вычислительный процесс, в каком неоднократно производятся вычисления по одним и этим же формулам при разных значениях аргумента.
Программки
, реализующие повторяющийся процесс именуются повторяющимися программками.
В организации цикла можно выделить последующие этапы:
подготовка (инициализация) цикла (И);
выполнение вычислений цикла (тело цикла) (Т);
модификация характеристик (М);
проверка условия окончания цикла (У).
порядок выполнения этих шагов, к примеру, Т и М, может изменяться. Зависимо от расположения проверки условия окончания цикла различают циклы с нижним и верхним окончаниями. Для цикла с нижним окончанием тело цикла производится как минимум один раз, потому что поначалу выполняются вычисления, а потом проверяется условие выхода из цикла.
В случае цикла с верхним окончанием тело цикла может не выполниться никогда в случае, если сходу соблюдается условие выхода.
Цикл именуется детерминированным, если число повторений тела цикла заблаговременно понятно либо определено. Цикл именуется итерационным, если число повторений тела цикла заблаговременно непонятно, а зависит от значений характеристик (неких переменных), участвующих в вычислениях.
тело цикла
— это неоднократно циклический участок программки.
Параметр цикла
— это переменная, которая воспринимает новейшие значения при любом повторении цикла (циклы бывают обыкновенные и сложные).
Вид цикла n раз
В общем виде цикл n раз записывается так:
нц число повторений раз
| тело цикла (последовательность установок)
кц
Служебное слово нц (начало цикла) и кц (конец цикла) пишутся строго одно под остальным и соединяются вертикальной чертой. Правее данной черты записывается повторяемая последовательность установок (тело цикла).
Число повторений – случайное целое число.
При выполнении метода последовательность установок в теле цикла повторяется обозначенное число раз. Правила алгоритмического языка допускают задание хоть какого целого числа повторений. Оно быть может нулевым и даже отрицательным. Эти случаи не числятся неверными, просто тело цикла не будет выполнено никогда, а комп сходу перейдет к выполнению установок, записанных опосля кц
Вид цикла пока
В общем виде цикл пока записывается так:
нц пока условие
| тело цикла (последовательность установок)
кц
При выполнении цикла комп повторяет последующие деяния:
а) инспектирует записанное опосля служебного слова пока условие;
б) если условие не соблюдается, то выполнение цикла заканчивается и комп начинает делать команды, записанные опосля кц. Если же условие соблюдается, то комп делает тело цикла, опять инспектирует условие и т.д.
Вид цикла для
нц для i от i1 до i2
| тело цикла (последовательность установок)
кц
Тут i – имя величины целого типа, i1, i2 – произвольные целые числа либо выражения с целыми значениями. тело цикла поочередно производится для i = i1, i = i1 + 1, i1 + 2, …i = i2.
Правила алгоритмического языка допускают задание всех целых i1, i2. а именно, i2 быть может меньше i1. этот вариант не считается неверным – просто тело цикла не будет выполнено никогда, а комп сходу перейдет к выполнению установок, записанных опосля кц.
Цикл n раз и цикл пока
Циклы n раз и пока оформляются в алгоритмическом языке практически идиентично. Это не умопомрачительно, ведь обе эти команды задают цикл – повторяющуюся последовательность установок. Служебные слова нц и кц указывают, что исполняется цикл, а заголовок цикла задает определенный механизм его выполнения.
Но у этих 2-ух циклов есть одно существенное отличие. Начиная делать цикл n раз, комп понимает, сколько раз придется повторить тело цикла. При выполнении цикла пока это не так: комп всякий раз инспектирует условие цикла и не может заблаговременно найти, когда выполнение завершится. Выяснить количество повторений цикла пока можно лишь опосля того, как цикл завершен.
Отсюда ясно, в которых вариантах какой цикл следует применять. Если к моменту начала цикла количество повторений понятно, комфортно пользоваться циклом n раз. Если же количество повторений заблаговременно найти недозволено, нужен цикл пока.
к примеру, программка автоматического управления имеет структуру, изображенную на рис. 1. Модули, входящие в цикл
(также модули обработки прерываний), с одним входом и одним выходом любой, как правило, имеют соответствующую изюминка: модули содержат статические переменные, которым присваивается состояние модуля на конец текущего либо начало последующего цикла программки. В предстоящем будем разглядывать лишь такие модули повторяющихся программ и обозначать их коротко МЦП.
Рис.1. Типовая структура управляющей программки с нескончаемым циклом.
МЦП имеют различную структуру, сложность которой нужно оценивать по особым аспектам. В.В.Липаевым предложен удачный и беспристрастный аспект трудности программных модулей, а конкретно: число и суммарная длина путей в управляющем графе модуля [1]. При всем этом учитываются лишь условные операторы и операторы выбора. Но этого аспекта очевидно недостаточно для МЦП со статической памятью, ибо при анализе МЦП нужно держать в голове значения всех статических переменных, установленные в предыдущем цикле. Кроме этого, никаких советов по стандартизации алгоритмов и программ, не считая издавна известного структурного программирования [2] на общеупотребительных языках программирования типа Си и Паскаль — нет. В данной статье предлагается восполнить эти пробелы применительно к МЦП.
2. Фрагменты модулей повторяющихся программ
Двухполюсным фрагментом, либо просто фрагментом, будем считать участок программки с одним входом и одним выходом (включая операторы циклов) в предположении, что рассматриваемые МЦП структурированы. Простой фрагмент включает единственный оператор. Последовательность фрагментов также является фрагментом. МЦП в свою очередь является фрагментом и состоит из последовательности фрагментов.
В [3] предложен способ независящих фрагментов для синтеза структуры модулей, реализующих таблицы решений. При всем этом независящим считается таковой фрагмент, который можно вставить в любом месте последовательности фрагментов модуля. Независимость местоположения такового фрагмента обоснована тем, что анализируемые в нем данные не формируются в обозначенной последовательности фрагментов, а создаваемые в независящем фрагменте данные не анализируются в данной последовательности фрагментов. Потому независящие фрагменты могут производиться параллельно (псевдопараллельно). На рис. 2 показаны вероятные варианты реализации модуля с 2-мя независящими фрагментами. В вариантах “а” и “б” фрагменты переставлены местами без преломления существа программки; в варианте “в” фрагменты реализуются параллельно.
Рис.2. Варианты реализации модуля с независящими фрагментами:
а) и б) — поочередная реализация,
в) — параллельная реализация: двойная горизонтальная линия обозначает распараллеливание программки, жирная горизонтальная черта обозначает окончание параллельных действий.
Зависимым фрагментом является таковой, положение которого зависит от местоположения другого (остальных) фрагмента в модуле. Будем различать сверху- и снизу зависимые фрагменты. Сверху-зависимый фрагмент должен быть размещен постоянно ниже некого фрагмента, в каком формируются переменные, применяемые в данном (зависимом) фрагменте. Снизу-зависимый фрагмент должен располагаться постоянно выше фрагмента, в каком употребляются переменные, создаваемые в данном фрагменте. Два зависимых фрагмента, один из которых является сверху зависимым от второго, а 2-ой снизу зависимым от первого, будем именовать взаимно зависимыми фрагментами. Их недозволено поменять местами и недозволено реализовывать параллельно. На рис. 3 приведен пример модуля с взаимно зависимыми фрагментами. Меж взаимно зависимыми фрагментами могут находиться остальные, зависимые либо не зависимые от их. Рис.3. Модуль с зависимыми фрагментами.
Фиксированным будем именовать зависимый фрагмент, положение которого в модуле строго определено. к примеру, в модуле определения знака, введенного с клавиатуры, первым должен быть снизу зависимый фрагмент конкретно ввода знака. Операторы “начало” и “конец” модуля есть фиксированные фрагменты.
Полностью независящих фрагментов не существует хотя бы поэтому, что в любом модуле есть упомянутые фиксированные фрагменты начала и конца. Потому независящий фрагмент, в общем случае, имеет ограниченную 2-мя взаимно зависимыми фрагментами область вероятного местоположения. Другими словами наиболее серьезное определение независящего фрагмента звучит последующим образом: независящим относительно 2-ух фиксированных фрагментов будем именовать таковой фрагмент, который быть может расположен в любом месте последовательности фрагментов, ограниченной сверху и снизу обозначенными фиксированными фрагментами.
Потому что модули программки являются ее фрагментами, то все перечисленные определения распространяются и на их; модули могут быть зависимыми, фиксированными и независящими.
Математических определений зависимости и независимости фрагментов тут не дается, потому что нас заинтересовывают не вопросцы размещения фрагментов, а воздействие их зависимости на аспекты трудности МЦП.
3. Число маршрутов в модулях повторяющихся программ
Разглядим воздействие зависимости фрагментов на аспект трудности модулей по Липаеву, другими словами на число маршрутов в модулях. В предстоящем под термином “маршрут” (“путь”) будем иметь в виду так именуемые условные (разъясняется ниже) маршруты (пути).
Обозначим S — общее число маршрутов (путей) в модуле, а Sn — число путей в n-ом фрагменте этого модуля.
Пусть модуль содержит лишь зависимые фрагменты (рис. 3). Управляющий граф [1] этого модуля изображен на рис. 4,а, из которого следует, что фрагмент 1 содержит 5 маршрутов, а фрагмент 2 — 3 маршрута. Потому что любой маршрут фрагмента 2 зависит от маршрутов фрагмента 1, то общее число маршрутов в данном модуле равно произведению чисел маршрутов всякого из фрагментов, другими словами S = S1 * S2.
Рис.4. Расчетные маршрутные схемы (РМС):
а) управляющий граф модуля по рис.3,
б) РМС этого модуля,
в) РМС модуля по рис. 2,в.
Управляющий граф не весьма комфортен для рисования и подсчета общего числа маршрутов модулей, фрагменты которых содержат сравнимо огромное число путей любой. Потому заместо управляющего графа предлагается наиболее обычная расчетная маршрутная схема (РМС) модуля (рис.4,б). В РМС прямоугольниками обозначены: оператор начала — “нач”, оператор конца — “кон”, фрагмент n — “fn”. В нижней части прямоугольника, обозначающего фрагмент, обозначено число путей в данном фрагменте; в нижней части прямоугольника,обозначающего начало модуля указана константа единица. с дугой, соединяющей два прямоугольника, указывается число маршрутов, образованных всеми фрагментами, размещенными поочередно от начала модуля до того фрагмента, в который заходит рассматриваемая дуга. В нижней части прямоугольника,обозначающего конец модуля, указывается общее число путей в модуле. Фрагменты, имеющие единственный путь в РМС не врубаются.
В общем случае, общее число S путей последовательности из N зависимых фрагментов определяется последующим образом:
S = S1 * S2 * … * SN, где символ “*” обозначает операцию произведения.
Разглядим сейчас независящие фрагменты. Как уже упоминалось, независящие фрагменты могут быть реализованы параллельно. Хоть какой маршрут независящего фрагмента не связан с иными фрагментами модуля, потому он анализируется автономно. На рис. 4,в показана РМС модуля с 2-мя независящими фрагментами. Для модуля с независящими фрагментами РМС производится в варианте параллельного соединения фрагментов даже, если модуль реализован с поочередным включением этих фрагментов. Числа, обозначенные в РМС на рис.4,в интерпретируются так же, как и на рис. 4,б. Добавочно поясним: дуги, исходящие из двойной черты (распараллеливание процесса) отмечены этим же числом, что и заходящая в двойную черту дуга; дуга, исходящая из жирной горизонтальной черты, обозначающей конец распараллеливания, отмечается числом, равным сумме чисел, помечающих заходящие в эту черту дуги. Тем устанавливается последующий факт.: общее число S анализируемых путей модуля, содержащего лишь независящие фрагменты, определяется суммой вида S = S1 + S2 + … + SN, где N — число независящих фрагментов. Но, настоящий путь в поочередной программке проходит через все фрагменты, несмотря на их независимость. Потому число R настоящих путей равно числу путей S, вычисленному из той посылки, что независящих фрагментов в модуле нет.
Отметим, что пути в РМС с параллельным включением независящих фрагментов будем именовать условными, а величину S — числом условных (по дефлоту) путей, в отличие от величины R — числа настоящих путей в МЦП. При всем этом S < R.
Фактически МЦП, включающие лишь независящие либо лишь зависимые фрагменты встречаются довольно изредка. Для расчета числа анализируемых путей в МЦП с фрагментами обоих типов поначалу устанавливается взаимозависимость фрагментов и групп фрагментов, что покажем на примере.
На рис. 5,а представлен модуль из 9 фрагментов, поочередно размещенных в согласовании с текстом поочередно реализуемой подпрограммы. Через дробь опосля обозначения фрагмента обозначено число путей в нем. Отметим, что случайная группа последующих попорядку фрагментов так же является фрагментом, который будем обозначать перечислением в скобках обозначений составляющих группу фрагментов. Пусть, к примеру, имеет пространство последующая зависимость фрагментов в модуле (рис. 5,а): фрагменты (f1,f2,f3) и (f4,f5,f6,f7,f8,f9) независимы относительно начала и конца, фрагмент f3 сверху зависим от f1 (f2), фрагменты f1 и f2 независимы относительно начала и фрагмента f3, фрагмент f5 сверху зависим от f4, фрагмент (f6,f7) сверху зависим от f5, фрагмент (f8,f9) сверху зависим от f6 (f7), фрагменты f6 и f7 независимы относительно f5 и (f8,f9), фрагменты f8 и f9 независимы относительно (f6,f7) и конца.
Рис.5. Модуль с зависимыми и относительно независящими фрагментами (а) и его РМС (б).
На основании изложенного получена РМС (рис. 5,б) и расчитано общее число условных путей в модуле (рис. 5,а) S = 1545, в то время как реальное число путей
R = 10 * 5 * 7 * 4 * 6 * 2 * 3 * 5 * 7 = 1764000
Данное число на три порядка (!) превосходит ранее приобретенное.
Таковым образом независимость фрагментов дозволяет существенно понизить число анализируемых (условных) маршрутов в МЦП, а РМС упрощает соответственный расчет.
Введем для МЦП коэффициент Kn независимости: Кn = S / R. Он имеет пределы: верхний, равный единице, (все фрагменты зависимые) и нижний, равный отношению суммы числа путей фрагментов к R (все фрагменты независимы).
4. Число маршрутов во фрагментах, содержащих булевы операции
Ранее рассмотренные в примерах фрагменты содержали конструкции логического либо множественного выбора, в условных верхушках которых содержались простые логические условия без символов булевых операций “И” и “ИЛИ”. Потому число путей фрагмента определялось зрительно без доп построений. Но наличие символов булевых операций в логических выражениях просит построения специальной схемы для расчета числа путей как для единичного значения выражения так и для нулевого. В качестве таковой схемы предлагается применять линейный бинарный граф [4] (ЛБГ). Построение ЛБГ и расчет числа путей, порождаемых логическим выражением с булевыми операциями, разглядим на последующем примере.
Пусть в условной верхушке некого фрагмента представлено сложное логическое выражение вида
( Sin(a) == Cos(b) && (! c % 5 || d > 3) && (e <= exp(f) || func(g)) ).
тут указаны: операции сопоставления (“==“, “>“, “<=“), деления по модулю (“%”), булевы операции (“!” — инверсия, “&&” — И, “||” — ИЛИ), функции синуса, косинуса, экспоненты и некой целочисленной функции (func). Введем понятие “атом” — это подформула, ограниченная слева и справа знаками булевых операций. В данном случае атомами являются последующие подформулы: Sin(a) == Cos(b), c % 5, d > 3, e <= exp(f), func(g).
Если в формуле содержится символ инверсии перед заключенной в скобки булевой операцией, то символ данной операции меняется (И на ИЛИ и напротив), а символ инверсии исключается перед данной подформулой и ставится перед каждым членом замененной операции. В данной формуле этого не требуется.
Для построения ЛБГ разместим атомы друг под другом в порядке обхода всей формулы слева вправо (рис. 6) и соединим их дугами, направленными вниз. Атомы образуют верхушки ЛБГ, а дуги — связь меж примыкающими верхушками. Вослед за крайним (нижним) атомом разместим две верхушки, надлежащие результатам вычисления формулы — единичному и нулевому; нижний атом соединим дугами с обозначенными новенькими верхушками. Все ранее построенные дуги именуются главными дугами ЛБГ. сейчас построим дуги, именуемые переходами.
Рис.6. ЛБГ и расчет числа его нулевых и единичных путей.
Переходы строятся по обе стороны от оси ЛБГ, образуемой главными дугами меж верхушками — атомами. Переходы строятся начиная с верхушки, предыдущей крайнему атому (в нашем случае с верхушки “e <= exp(f)”). Переход строится по ту сторону от оси, где размещена верхушка “итог 1”, если в формуле справа от соответственного атома стоит символ ИЛИ. В примере это переходы от атомов “e <= exp(f)” и “!c%5”.Переход строится на иной стороне от оси, если в формуле справа от атома стоит символ И. Это переходы от атомов “d > 3” и “Sin(a) == Cos(b)”. Переход направляется к расположенной на стороне его построения верхушке “итог 1(0)”, если упомянутый символ ИЛИ (И) принадлежит наружной операции формулы. Это переходы от атомов “Sin(a) == Cos(b)” и “d > 3”. В неприятном случае переход направляется к ниже расположенной верхушке, соответственной атому, размещенному справа от закрывающей скобки, ограничивающей операцию,которой принадлежит упомянутый символ ИЛИ (И), а если такового атома нет — к верхушке “итог”. Это переходы от атомов “! c % 5” и “e <= exp(f)”. символ булевой операции отрицания на расчет числа путей не влияет, потому в построенном, следуя вышесказанному, ЛБГ он игнорируется (см. рис. 6). Формальное описание синтеза ЛБГ представлено в [5]. сейчас разглядим процесс подсчета числа единичных и нулевых путей в построенном ЛБГ. Будем применять специальную метку, представляющую собой два числа, разбитую знаком дроби. При всем этом левое число будет обозначать число нулевых путей, а правое — единичных. к примеру, метка “3 / 5” указывает три нулевых и 5 единичных путей.
Разумно представить, что расчет числа путей нужно начинать от исходной верхушки. Но предлагается наиболее обычный метод подсчета, начиная с вершин “итог”. Под верхушкой “итог 0” поставим метку “1 / 0”, а под верхушкой “итог 1” — метку “0 / 1”. На каждой дуге, заходящей в верхушку “итог” поставим такую же подобающую метку. Дальше, для каждой верхушки ЛБГ, начиная с крайнего атома и следуя ввысь, выполнить последующее. Сложить метки “a0 / a1” и “b0 / b1”, обозначенные на исходящих из данной верхушки дугах, в итоге чего же получится метка “c0 / c1”, где c0 = a0 + b0, c1 = a1 + b1. Полученную метку поставить на каждой заходящей в данную верхушку дуге. В итоге над самой верхней верхушкой ЛБГ выходит метка “s0 / s1”, где s0 — число нулевых путей, другими словами число путей, определяющих итог 0, а s1 — число единичных путей, определяющих итог 1.
5. Число путей во фрагментах, содержащих циклические операторы
В структурированных программках циклические операторы могут быть сведены к двум типам фрагментов: с проверкой условия цикла до входа в тело цикла и — опосля тела цикла (рис. 7). Число S путей таковых фрагментов определяется 4-мя компонентами: числом Sp путей пролога цикла (где инсталлируются исходные значения переменных, применяемых в условии и в теле цикла), числом St тела цикла ( в каком включим счетчики и остальные операторы приращений) и числами S1 и S0 единичных и нулевых путей, соответственно, условия (“усл” на рис.7) выполнения цикла.
Рис.7. Два типа повторяющихся операторов.
В первом случае (рис. 7,а) тело цикла может не выполниться никогда, при всем этом анализируется S = Sp * S1 путей. Если условие выполнено хотя бы один раз, то анализируется S = Sp * S1 * St * S0 путей. По максимуму принимаем крайнее выражение для определения числа путей в повторяющихся операторах первого типа.
Во 2-м случае (рис. 7,б) тело цикла постоянно производится хотя бы один раз, даже, если условие не производится. При всем этом анализируется S = Sp * St * S0 путей. Если же условие цикла выполнится хотя бы один раз, то число путей S = Sp * St * S0 * St * S1. С учетом того, что пути тела цикла анализируются лишь один раз, получим S = Sp * St * S0 * S1.
Таковым образом, для хоть какого из 2-ух представленных типов фрагментов с повторяющимися операторами число анализируемых путей определяется выражением S = Sp * St * S1 * S0.
6. Условно-независимые фрагменты
Не считая повторяющихся операторов фрагменты могут быть образованы операторами ветвления. Таковыми операторами являются условные (двоичного выбора) и операторы множественного выбора. Пример фрагмента с оператором двоичного выбора показан на рис. 2 (“фрагмент 1”). а с множественным выбором — на рис.3 (“фрагмент 2”). Фрагменты операторов выбора включают верхушку, в общем случае, с целочисленной переменной (в том числе операция сопоставления есть булева переменная с 2-мя значениями), из данной верхушки исходит по последней мере две помеченые дуги, заходящие в верхушки, надлежащие операторам нижнего уровня и являющиеся вложенными фрагментами, которые и будем именовать условно-независимыми. Такое заглавие разъясняется тем, что с позиции расчета числа путей эти вложенные фрагменты не зависят друг от друга. Потому число путей во фрагменте с оператором двоичного выбора определяется так: рассчитываются числа единичных и нулевых путей логического условия (при наличии булевых операций в нем), считается число путей в любом из условно-независимых фрагменте, которое множится на соответственное число единичных (нулевых) путей, и приобретенные произведения складываются. Для операторов недвоичного выбора просто складываются числа путей условно-независимых фрагментов.
7. Структурный размер памяти модулей повторяющихся программ
МЦП с памятью будем именовать таковой модуль, который обрабатывает локальные статические переменные (ЛСП), область деяния которых не выходит за рамки данного модуля. При всем этом в МЦП формируется
ЛСП усложняют анализ структуры модуля, потому что при разборе еще одного цикла нужно держать в голове значения этих переменных, приобретенные в предшествовавшем цикле. Потому такового аспекта как число маршрутов уже недостаточно. Введем новейший аспект структурной трудности для МЦП с памятью, нареченный структурным объемом памяти (СОП) модуля. Введем обозначения: m — число ЛСП, применяемых в модуле, i — порядковый номер маршрута модуля, содержащего всего S маршрутов, ai — число операций присваивания (инициализации, модификации) ЛСП на i-ом маршруте.
где “max” — операция взятия максимума из 2-ух переменных.
тут предполагается, что S вычислено по РСМ. Нижняя оценка СОП рассчитывается в предположении, что каждой переменной (ЛСП) на одном маршруте присваивается не наиболее 1-го новейшего значения: Pmin = m * S.
Для уменьшения СОП следует так поменять МЦП, чтоб уменьшилось число ЛСП и число путей S. Этого можно достигнуть, создавая независящие либо условно-независимые фрагменты с подменой нескольких ЛСП, определяющих маршруты фрагмента, на одну ЛСП с образованием множественного оператора выбора. Решение данной задачки обеспечивается типовой реализацией МЦП, рассматриваемой ниже.
8. Реализация модулей повторяющихся программ С-автоматами
В качестве типовой реализации МЦП с ЛСП предлагается применять модель С-автомата [6], направленную на программную реализацию. Применение моделей конечных автоматов в программировании не ново (к примеру, [7]). А именно R-технология [8] употребляет модель автоматов Мили, а разработка программирования алгоритмов логического управления [9] употребляет модель автоматов Мура. Программки различного профиля, в том числе и логического управления, требуют, в общем случае, объединения обозначенных моделей в одну, другими словами применять С-автомат [10].
Выбор конечно-автоматной реализации МЦП обоснован, во-1-х, универсальностью (как правило, МЦП имеют не наименее 2-ух состояний), а, во-2-х, тем, что заместо почти всех ЛСП, управляющих маршрутами в МЦП, быть может применена единственная целочисленная ЛСП, каждое
метод МЦП задается графом переходов С-автомата , пример которого изображен на рис. 8. Граф содержит три верхушки, отмеченные снутри прямоугольников, им соответственных, дробными отметками. В числителе указан идентификатор состояния (знаки a,b,c), который быть может или целым произвольным числом или произвольным эмблемой. В знаменателе указан идентификатор оператора (Za,Zb,Zc), непременно выполняющегося в данном состоянии. У верхушки быть может петля, также отмеченная дробъю, в числителе которой обозначено условие, к примеру Xa, а в знаменателе — идентификатор оператора, соответственно Ya, выполняющегося, если условие Xa = 1 (без перехода в другое состояние). Верхушки соединены дугами, помеченные аналогично, к примеру, дуга из состояния “a” в состояние “b” отмечена дробью “Xab/Yab”, где Yab — оператор, выполняемый при наличии условия Xab, и опосля реализации Yab новеньким состоянием автомата становится “b”. Условия, помечающие дуги, исходящие из одной верхушки, включая петлю, должны быть попарно ортогональны.
Рис.8. Граф переходов С-автомата.
Практика программирования указывает, что, в общем случае, переход из 1-го состояния, к примеру из “а”, в другое состояние, к примеру в “с”, может осуществляться с реализацией не 1-го (Yac), а нескольких операторов, последующих в согласовании с выполнением ряда критерий. к примеру, по условию Xac1 реализуется оператор Yac1, и производится переход из “а” в “с”; по условию Xac2 реализуется оператор Yac2, и производится таковой же переход. Ортогональных критерий вида Xack схожего перехода из состояния “а” в состояние “с” с реализацией соответственных операторов вида Yack быть может несколько (k = 1,2,…,Lac). Таковым образом граф С-автомата, в общем случае, является мультиграфом.
9. Типовая структура модуля, реализующего С-автомат
Типовая структура МЦП, реализующего С-автомат (согласно рис.8) представлена на рис.9, где употребляется оператор множественного выбора [11] для определения состояния Т автомата. При всем этом образуются три схожих условно-независимых фрагмента, 1-ый из которых включает составляющие (Za, Xa, Ya, Xab, Yab, Xac, Yac). Этот фрагмент, в свою очередь, включает снизу-зависимый фрагмент Za. Из этого следует довольно обычный расчет числа условных путей в МЦП:
S = D(Za) * [E(Xa) * D(Ya) + F(Xa) * E(Xab) * D(Yab) +
+ F(Xa) * F(Xab) * E(Xac) * D(Yac) + F(Xa) * F(Xab) * F(Xac)] +
+ D(Zb) * [E(Xb) * D(Yb) + F(Xb) * E(Xba) * D(Yba) +
+ F(Xb) * F(Xba) * E(Xbc) * D(Ybc) + F(Xb) * F(Xba) * F(Xbc)] +
+ D(Zc) * [E(Xc) * D(Yc) + F(Xc) * E(Xca) * D(Yca) +
+ F(Xc) * F(Xca) * E(Xcb) * D(Ycb) + F(Xc) * F(Xca) * F(Xcb)].
тут обозначены: D(Za) — число путей во фрагменте Za, E(Xa) — число единичных путей в ЛБГ, реализующем логическое условие Xa, F(Xa) — число нулевых путей в этом ЛБГ.
Рис.9. структура МЦП, реализующего С-автомат
Если фрагменты Za,Ya, Yab, Yac и подобные им не содержат в себе независящих фрагментов, то число условных путей совпадает с числом настоящих путей.
Если ЛСП Т (номер либо знак состояния С-автомата) является единственной ЛСП в этом МЦП, то СОП рассчитывается элементарно: просто складываются число дуг и петель с числом вершин графа переходов.
В общем случае, операторы Z и Y могут быть составными и/либо включающими воззвания к подпрограммам, другими словами хоть какими допустимыми в языке программирования операторами.
10. оптимизация структуры модуля, реализующего С-автомат
Если логические условия X содержат как операции И так и операции ИЛИ, то они подлежат оптимизации по числу путей. При всем этом для всякого условия ищется таковая перестановка его членов, которая дает меньшее
иной оптимизацией является увеличение быстродействия МЦП. Самой обычный оптимизацией является переразмещение условно-независимых фрагментов, начинающихся с операторов Z. Для этого определяются вероятности p(Za) , p(Zb), p(Zc) пребывания МЦП в состояниях “a”, “b”, “c” соответственно. Потом условно-независимые фрагменты располагаются в операторе множественного выбора согласно убыванию соответственных им вероятностей p(Z).
Наиболее сложной является оптимизация по быстродействию методом перестановок критерий Xa, Xab, Xac с надлежащими фрагментами Ya, (Yab,”T=b”) и так дальше. Для выполнения таковой оптимизации полагаем, что задано начальное логическое выражение вида “Xa || Xab || Xac”. В данном выражении следует выполнить оптимизирующую перестановку членов согласно способу [13]. Опосля этого обозначенные условия с надлежащими фрагментами переставляются местами согласно хорошей перестановке выше приведенного логического выражения. Если аспект быстродействия является доминирующим для программки, то рациональные перестановки по [13] следует получить как для всякого из логических выражений Xa, Xab, Xac так и для логических выражений, входящих в операторы Z и Y.
11. Табличная реализация С-автомата
В случае, когда условия Xa, Xab, Xac представляют собой выражения вида “V == v1”, “V == v2”, “V == v3”, соответственно, где V — переменная, обозначающая, к примеру, знак с клавиатуры либо сообщение оконной функции приложения для операционной системы Windows [14], а v1, v2, v3 — значения переменной V, то состояние опосля перехода можно вычислить, используя табличный способ [2,11]. При табличной реализации значительно миниатюризируется число путей в МЦП.
Если, не считая того, операторы Z и Y представить в виде подпрограмм, то предлагаемая ниже табличная реализация является более действенной.
Пусть a = 0, b = 1, c = 2, Xa: “V == 0”, Xab: “V == 1”, Xac: “V == 2”, Xb: “V == 3” и так дальше. Составим по графу переходов (рис.8) таблицу переходов и сравним ей соответственный программный двухмерный массив МП (рис.10), строчки которого соответствуют переменной V, а столбцы — переменной состояния Т, элементами массива являются номера состояний опосля перехода. Составим также таблицу 2 выходов Мили и сравним ей двухмерный массив ММ (рис.10), строчки которого соответствуют переменной V, а столбцы — переменной Т. Если строчки МП (ММ) имеют однообразное (то есть внутренние войска) выходов Мура с элементами {Za, Zb, Zc}.
Рис.10. Массивы МП и ММ.
На основании изложенного структура МЦП (кроме инициализации Т = 0 и массивов ММ, МП, ВВ ) воспринимает вид:
Конвертировать входное сообщение при помощи оператора множественного выбора в
Выполнить подпрограмму ВВ [T];
Выполнить подпрограмму MM[V][T];
T = МП[V][T].
Конец.
Проще по структуре МЦП тяжело представить. При всем этом S = R = P = 9 (по первой операции).
Перечень литературы
1. Липаев В.В. Свойство программного обеспечения. — М.: деньги и статистика, 2003 – 200с.
2. Майерс Г. Надежность программного обеспечения. — М.: мир, 2000 – 130с.
3. Кузнецов Б.П. Структурирование бинарных программ — Сер. — 2003, № 29, с. 27 — 35.
4. Кузнецов Б.П., Шалыто А.А. Реализация булевых формул линейными бинарными графами. 1. синтез и анализ. — Техно продажная девка империализма — 2004, № 5, с.132 — 142.
5. Кузнецов Б.П., Шалыто А.А. Система преобразований неких форм представления булевых функций. — А и Т, 2005, № 11, с. 120 — 127.
6. Баранов С.И. синтез микропрограммных автоматов. — Л.: Энергия, 2009-220с
7. Байцер Б. Архитектура вычислительных комплексов. Том 1. — М.: мир, 2009-250с.
8. Вельбицкий И.В. и др. Технологический комплекс производства программ на машинках ЕС ЭВМ и БЭСМ-6. — М.: Статистика, 2000 – 200с.
9. Шалыто А.А. и др. Алгоритмизация и программирование задач логического управления техническими средствами. — С.-Пб.:Моринтех, 2006- 260с.
10. Кузнецов Б.П. Обычная реализация управляющих программ. — Судостроительная индустрия. Сер. системы автоматизации проектирования, производства и управления. 2006, вып. 1, с.51 — 55.
11. Джамп Д. AutoCAD. Программирование. — М.: Радио и связь, 2002.
12. Кузнецов Б.П., Шалыто А.А. Реализация булевых формул линейными бинарными графами. III. оптимизация числа и суммарной длины путей. — Теория и системы управления, 2005, № 5, с. 214 -223.
13. Кузнецов Б.П. Продолжительность вычислений на линейных бинарных графах. — А и Т, 2004, № 9, с. 166 — 172.
14. Петзолд Ч. Программирование для Windows 95. Том I. — СПб.: BHV — Санкт-Петербург, 2007.
]]>