Содержание:
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 раз и пока оформляются в алгоритмическом языке почти одинаково. Это не удивительно, ведь обе эти команды задают цикл – повторяющуюся последовательность команд. Служебные слова нц и кц указывают, что исполняется цикл, а заголовок цикла задает конкретный механизм его выполнения.
Однако у этих двух циклов есть одно существенное отличие. Начиная выполнять цикл n раз, компьютер знает, сколько раз придется повторить тело цикла. При исполнении цикла пока это не так: компьютер каждый раз проверяет условие цикла и не может заранее определить, когда выполнение закончится. Узнать количество повторений цикла пока можно только после того, как цикл завершен.
Отсюда ясно, в каких случаях какой цикл следует использовать. Если к моменту начала цикла количество повторений известно, удобно воспользоваться циклом n раз. Если же количество повторений заранее определить нельзя, необходим цикл пока.
Например, программа автоматического управления имеет структуру, изображенную на рис. 1. Модули, входящие в цикл
(а также модули обработки прерываний), с одним входом и одним выходом каждый, как правило, имеют характерную особенность: модули содержат статические переменные, которым присваивается значение в текущем цикле, а анализ этих переменных выполняется в следующем цикле. Таким образом, упомянутые переменные характеризуют состояние модуля на конец текущего или начало следующего цикла программы. В дальнейшем будем рассматривать только такие модули циклических программ и обозначать их кратко МЦП.
Рис.1. Типовая структура управляющей программы с бесконечным циклом.
МЦП имеют разнообразную структуру, сложность которой необходимо оценивать по специальным критериям. В.В.Липаевым предложен удобный и объективный критерий сложности программных модулей, а именно: число и суммарная длина путей в управляющем графе модуля [1]. При этом учитываются только условные операторы и операторы выбора. Однако этого критерия явно недостаточно для МЦП со статической памятью, ибо при анализе МЦП необходимо помнить значения всех статических переменных, установленные в предшествующем цикле. Помимо этого, никаких рекомендаций по стандартизации алгоритмов и программ, кроме давно известного структурного программирования [2] на общеупотребительных языках программирования типа Си и Паскаль - нет. В данной статье предлагается восполнить эти пробелы применительно к МЦП.
2. Фрагменты модулей циклических программ
Двухполюсным фрагментом, или просто фрагментом, будем считать участок программы с одним входом и одним выходом (включая операторы циклов) в предположении, что рассматриваемые МЦП структурированы. Простейший фрагмент включает единственный оператор. Последовательность фрагментов также является фрагментом. МЦП в свою очередь является фрагментом и состоит из последовательности фрагментов.
В [3] предложен метод независимых фрагментов для синтеза структуры модулей, реализующих таблицы решений. При этом независимым считается такой фрагмент, который можно вставить в любом месте последовательности фрагментов модуля. Независимость местоположения такого фрагмента обусловлена тем, что анализируемые в нем данные не формируются в указанной последовательности фрагментов, а формируемые в независимом фрагменте данные не анализируются в данной последовательности фрагментов. Поэтому независимые фрагменты могут выполняться параллельно (псевдопараллельно). На рис. 2 показаны возможные варианты реализации модуля с двумя независимыми фрагментами. В вариантах “а” и “б” фрагменты переставлены местами без искажения существа программы; в варианте “в” фрагменты реализуются параллельно.
Рис.2. Варианты реализации модуля с независимыми фрагментами:
а) и б) - последовательная реализация,
в) - параллельная реализация: двойная горизонтальная линия обозначает распараллеливание программы, жирная горизонтальная черта обозначает завершение параллельных процессов.
Зависимым фрагментом является такой, местоположение которого зависит от местоположения другого (других) фрагмента в модуле. Будем различать сверху- и снизу зависимые фрагменты. Сверху-зависимый фрагмент должен быть расположен всегда ниже некоторого фрагмента, в котором формируются переменные, используемые в данном (зависимом) фрагменте. Снизу-зависимый фрагмент должен размещаться всегда выше фрагмента, в котором используются переменные, формируемые в данном фрагменте. Два зависимых фрагмента, один из которых является сверху зависимым от второго, а второй снизу зависимым от первого, будем называть взаимно зависимыми фрагментами. Их нельзя менять местами и нельзя реализовывать параллельно. На рис. 3 приведен пример модуля с взаимно зависимыми фрагментами. Между взаимно зависимыми фрагментами могут находиться другие, зависимые или не зависимые от них. Рис.3. Модуль с зависимыми фрагментами.
Фиксированным будем называть зависимый фрагмент, местоположение которого в модуле строго определено. Например, в модуле распознавания символа, введенного с клавиатуры, первым должен быть снизу зависимый фрагмент непосредственно ввода символа. Операторы “начало” и “конец” модуля есть фиксированные фрагменты.
Абсолютно независимых фрагментов не существует хотя бы потому, что в любом модуле есть упомянутые фиксированные фрагменты начала и конца. Поэтому независимый фрагмент, в общем случае, имеет ограниченную двумя взаимно зависимыми фрагментами область возможного местоположения. То есть более строгое определение независимого фрагмента звучит следующим образом: независимым относительно двух фиксированных фрагментов будем называть такой фрагмент, который может быть размещен в любом месте последовательности фрагментов, ограниченной сверху и снизу указанными фиксированными фрагментами.
Так как модули программы являются ее фрагментами, то все перечисленные определения распространяются и на них; модули могут быть зависимыми, фиксированными и независимыми.
Математических определений зависимости и независимости фрагментов здесь не дается, так как нас интересуют не вопросы размещения фрагментов, а влияние их зависимости на критерии сложности МЦП.
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,в показана РМС модуля с двумя независимыми фрагментами. Для модуля с независимыми фрагментами РМС выполняется в варианте параллельного соединения фрагментов даже, если модуль реализован с последовательным включением этих фрагментов. Числа, указанные в РМС на рис.4,в интерпретируются так же, как и на рис. 4,б. Дополнительно поясним: дуги, исходящие из двойной черты (распараллеливание процесса) отмечены тем же числом, что и заходящая в двойную черту дуга; дуга, исходящая из жирной горизонтальной черты, обозначающей конец распараллеливания, отмечается числом, равным сумме чисел, помечающих заходящие в эту черту дуги. Тем самым устанавливается следующий факт.: общее число S анализируемых путей модуля, содержащего только независимые фрагменты, определяется суммой вида S = S1 + S2 + ... + SN, где N - число независимых фрагментов. Однако, реальный путь в последовательной программе проходит через все фрагменты, невзирая на их независимость. Поэтому число R реальных путей равно числу путей S, вычисленному из той посылки, что независимых фрагментов в модуле нет.
Отметим, что пути в РМС с параллельным включением независимых фрагментов будем называть условными, а величину S - числом условных (по умолчанию) путей, в отличие от величины R - числа реальных путей в МЦП. При этом S < R.
Практически МЦП, включающие только независимые или только зависимые фрагменты встречаются достаточно редко. Для расчета числа анализируемых путей в МЦП с фрагментами обоих типов сначала устанавливается взаимозависимость фрагментов и групп фрагментов, что покажем на примере.
На рис. 5,а представлен модуль из девяти фрагментов, последовательно размещенных в соответствии с текстом последовательно реализуемой подпрограммы. Через дробь после обозначения фрагмента указано число путей в нем. Отметим, что произвольная группа следующих подряд фрагментов так же является фрагментом, который будем обозначать перечислением в скобках обозначений составляющих группу фрагментов. Пусть, например, имеет место следующая зависимость фрагментов в модуле (рис. 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” показывает три нулевых и пять единичных путей.
Логично предположить, что расчет числа путей надо начинать от начальной вершины. Но предлагается более простой алгоритм подсчета, начиная с вершин “результат”. Под вершиной “результат 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 путей таких фрагментов определяется четырьмя компонентами: числом Sp путей пролога цикла (где устанавливаются начальные значения переменных, используемых в условии и в теле цикла), числом St тела цикла ( в котором включим счетчики и другие операторы приращений) и числами S1 и S0 единичных и нулевых путей, соответственно, условия (“усл” на рис.7) выполнения цикла.
Рис.7. Два типа циклических операторов.
В первом случае (рис. 7,а) тело цикла может не выполниться ни разу, при этом анализируется S = Sp * S1 путей. Если условие выполнено хотя бы один раз, то анализируется S = Sp * S1 * St * S0 путей. По максимуму принимаем последнее выражение для определения числа путей в циклических операторах первого типа.
Во втором случае (рис. 7,б) тело цикла всегда выполняется хотя бы один раз, даже, если условие не выполняется. При этом анализируется S = Sp * St * S0 путей. Если же условие цикла выполнится хотя бы один раз, то число путей S = Sp * St * S0 * St * S1. С учетом того, что пути тела цикла анализируются только один раз, получим S = Sp * St * S0 * S1.
Таким образом, для любого из двух представленных типов фрагментов с циклическими операторами число анализируемых путей определяется выражением S = Sp * St * S1 * S0.
6. Условно-независимые фрагменты
Кроме циклических операторов фрагменты могут быть образованы операторами ветвления. Такими операторами являются условные (двоичного выбора) и операторы множественного выбора. Пример фрагмента с оператором двоичного выбора показан на рис. 2 (“фрагмент 1”). а с множественным выбором - на рис.3 (“фрагмент 2”). Фрагменты операторов выбора включают вершину, в общем случае, с целочисленной переменной (в том числе операция сравнения есть булева переменная с двумя значениями), из этой вершины исходит по крайней мере две помеченые дуги, заходящие в вершины, соответствующие операторам нижнего уровня и являющиеся вложенными фрагментами, которые и будем называть условно-независимыми. Такое название объясняется тем, что с позиции расчета числа путей эти вложенные фрагменты не зависят друг от друга. Поэтому число путей во фрагменте с оператором двоичного выбора определяется так: вычисляются числа единичных и нулевых путей логического условия (при наличии булевых операций в нем), считается число путей в каждом из условно-независимых фрагменте, которое умножается на соответствующее число единичных (нулевых) путей, и полученные произведения складываются. Для операторов недвоичного выбора просто складываются числа путей условно-независимых фрагментов.
7. Структурный объем памяти модулей циклических программ
МЦП с памятью будем называть такой модуль, который обрабатывает локальные статические переменные (ЛСП), область действия которых не выходит за рамки данного модуля. При этом в МЦП формируется значение ЛСП в текущем глобальном цикле, а анализируется это значение уже в следующем цикле. Пример такого модуля представлен на рис.3, где переменная А есть ЛСП.
ЛСП усложняют анализ структуры модуля, так как при разборе очередного цикла необходимо помнить значения этих переменных, полученные в предшествовавшем цикле. Поэтому такого критерия как число маршрутов уже недостаточно. Введем новый критерий структурной сложности для МЦП с памятью, названный структурным объемом памяти (СОП) модуля. Введем обозначения: m - число ЛСП, используемых в модуле, i - порядковый номер маршрута модуля, содержащего всего S маршрутов, ai - число операций присваивания (инициализации, модификации) ЛСП на i-ом маршруте. Значение СОП определяется выражением
где “max” - операция взятия максимума из двух переменных.
Здесь предполагается, что S вычислено по РСМ. Нижняя оценка СОП вычисляется в предположении, что каждой переменной (ЛСП) на одном маршруте присваивается не более одного нового значения: Pmin = m * S.
Для уменьшения СОП следует так изменить МЦП, чтобы уменьшилось число ЛСП и число путей S. Этого можно добиться, создавая независимые или условно-независимые фрагменты с заменой нескольких ЛСП, определяющих маршруты фрагмента, на одну ЛСП с образованием множественного оператора выбора. Решение данной задачи обеспечивается типовой реализацией МЦП, рассматриваемой ниже.
8. Реализация модулей циклических программ С-автоматами
В качестве типовой реализации МЦП с ЛСП предлагается использовать модель С-автомата [6], ориентированную на программную реализацию. Применение моделей конечных автоматов в программировании не ново (например, [7]). В частности R-технология [8] использует модель автоматов Мили, а технология программирования алгоритмов логического управления [9] использует модель автоматов Мура. Программы различного профиля, в том числе и логического управления, требуют, в общем случае, объединения указанных моделей в одну, то есть использовать С-автомат [10].
Выбор конечно-автоматной реализации МЦП обусловлен, во-первых, универсальностью (как правило, МЦП имеют не менее двух состояний), а, во-вторых, тем, что вместо многих ЛСП, управляющих маршрутами в МЦП, может быть использована единственная целочисленная ЛСП, каждое значение которой соответствует определенному состоянию автомата. Это может существенно снизить значение СОП, например, до величины S. В случае предлагаемой ниже типовой реализации число маршрутов легко вычисляется по схеме алгоритма и поддается сравнительно легкой верхней оценке.
Алгоритм МЦП задается графом переходов С-автомата , пример которого изображен на рис. 8. Граф содержит три вершины, отмеченные внутри прямоугольников, им соответствующих, дробными отметками. В числителе указан идентификатор состояния (символы a,b,c), который может быть либо целым произвольным числом либо произвольным символом. В знаменателе указан идентификатор оператора (Za,Zb,Zc), обязательно выполняющегося в данном состоянии. У вершины может быть петля, также отмеченная дробъю, в числителе которой указано условие, например Xa, а в знаменателе - идентификатор оператора, соответственно Ya, выполняющегося, если условие Xa = 1 (без перехода в другое состояние). Вершины связаны дугами, помеченные аналогично, например, дуга из состояния “a” в состояние “b” отмечена дробью “Xab/Yab”, где Yab - оператор, выполняемый при наличии условия Xab, и после реализации Yab новым состоянием автомата становится “b”. Условия, помечающие дуги, исходящие из одной вершины, включая петлю, должны быть попарно ортогональны.
Рис.8. Граф переходов С-автомата.
Практика программирования показывает, что, в общем случае, переход из одного состояния, например из “а”, в другое состояние, например в “с”, может осуществляться с реализацией не одного (Yac), а нескольких операторов, следующих в соответствии с выполнением ряда условий. Например, по условию Xac1 реализуется оператор Yac1, и выполняется переход из “а” в “с”; по условию Xac2 реализуется оператор Yac2, и выполняется такой же переход. Ортогональных условий вида Xack одинакового перехода из состояния “а” в состояние “с” с реализацией соответствующих операторов вида Yack может быть несколько (k = 1,2,...,Lac). Таким образом граф С-автомата, в общем случае, является мультиграфом.
9. Типовая структура модуля, реализующего С-автомат
Типовая структура МЦП, реализующего С-автомат (согласно рис.8) представлена на рис.9, где используется оператор множественного выбора [11] для определения состояния Т автомата. При этом образуются три похожих условно-независимых фрагмента, первый из которых включает компоненты (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 содержат как операции И так и операции ИЛИ, то они подлежат оптимизации по числу путей. При этом для каждого условия ищется такая перестановка его членов, которая дает наименьшее значение числа путей, согласно методу [12]. В результате оптимизации уменьшается число как единичных так и нулевых путей в ЛБГ, реализующем условие X. Аналогично оптимизируются логические условия, содержащиеся в операторах Z, Y. После оптимизации общее число путей в МЦП должно уменьшиться.
Другой оптимизацией является повышение быстродействия МЦП. Самой простой оптимизацией является переразмещение условно-независимых фрагментов, начинающихся с операторов 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, а столбцы - переменной Т. Если строки МП (ММ) имеют одинаковое значение V, то они склеиваются. Составим вектор ВВ выходов Мура с элементами {Za, Zb, Zc}.
Рис.10. Массивы МП и ММ.
На основании изложенного структура МЦП (за исключением инициализации Т = 0 и массивов ММ, МП, ВВ) принимает вид:
Преобразовать входное сообщение с помощью оператора множественного выбора в значение переменной V;
Выполнить подпрограмму ВВ[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.