Реферат

Реферат Способы построения циклических вычислительных процессов

Работа добавлена на сайт bukvasha.net: 2015-10-28

Поможем написать учебную работу

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

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 8.11.2024





Содержание:
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.

1. Реферат на тему Образ медведя в фольклоре
2. Реферат на тему Crusades A Paper Essay
3. Реферат на тему Francisco Jos Goya Y Lucientes Essay Research
4. Реферат на тему Benefits Of Pet Ownership Essay Research Paper
5. Книга Образ головного персонажу роману Панаса Мирного Хіба ревуть воли, як ясла повні Чіпка
6. Реферат Сталинка
7. Реферат на тему Концепция истории отечественной словесности в Обзоре русской духовной литературы архиепископа Филарета
8. Реферат Экономическое развитие западноевропейских стран в эпоху феодализма V-XV вв.
9. Реферат на тему The Three Most Significant Events In US
10. Диплом на тему Підвищення ефективності режиму праці і відпочинку працівників торгової групи підприємств ресторанного