Общие принципы разработки алгоритмов

 

Любые действия, процедуры, по обработке информации, в частности цифровой, выполняются по тому или иному алгоритму. Перед тем, как подробно рассматривать алгоритмы арифметических действий, выполняемых в цифровых автоматах, приведем определение самого понятия алгоритма и общие принципы составления любых алгоритмов.

Совокупность правил перехода цифрового автомата из одного состояния в другое в зависимости от входной информации и внутренних состояний автомата называется алгоритмом преобразования (переработки) информации.

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

Можно привести еще одно определение понятия алгоритма. Алгоритм - это строго формальное описание конечной последовательности некоторых "элементарных" действий или процедур, которые надо выполнить над исходными данными и над промежуточными результатами, возникшими в ходе выполнения этих операций, для того чтобы прийти к информации, являющейся результатом обработки исходных данных.

Последовательность операций, описываемых в алгоритме, может быть статической (в порядке описания) и динамической (в порядке выполнения). Соответствие между статической и динамической последовательностями нарушается в тех местах алгоритма, где происходит его ветвление по условию и в местах обращения к подпрограммам и функциям. Участок алгоритма, на котором эти последовательности совпадают называется линейным участком или цепочкой.

Цепочки и ветвления являются базовыми структурами алгоритов. К таким структурам относятся также подпрограммы, функции и циклы.

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

Участок алгоритма, который по условию решения задачи должен быть выполнен подряд несколько раз, называется циклом. Чтобы обеспечить многократное выполнение какой-либо группы команд (команды "тела цикла"), достаточно завершить эту группу командой перехода на первую ее команду. Такой переход должен быть условным, т.е. зависить от выполнения некоторого условия, определяющего необходимость повторения этой группы команд.

Циклы могут быть:

- итерационного типа, когда число повторений заранее не известно, а определяется по некоторому условию, которое может изменяться в процессе выполнения цикла;

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

Нужно учесть что совокупность команд или процедур, образующих тело цикла, может в свою очередь содержать другой цикл. Такую структуру называют вложенными циклами.

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

Следовательно, подпрограммы, функции и циклы позволяют мини-мизировать структуру разрабатываемого алгоритма. Использование готовых подпрограмм и функций к тому же минимизирует объем необходимых разработок и облегчает процедуру модернизации разработанного алгоритма, если возникает в этом необходимость. Но нужно учесть, что все перечисленные структуры не увеличивают скорость выполнения алгоритма.

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

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

Словесное описание алгоритма состоит из словесного перечня действий (шагов), составляющих алгоритм. Каждый шаг имеет порядковый номер. Алгоритм выполнятся последовательно шаг за шагом. Если последовательность выполнения действий должна быть нарушена, то в тексте алгоритма отмечается переход к пункту с необходимым номером. Словесное описание алгоритмов не отличается наглядностью, поэтому такое описание используется для несложных алгоритмов.

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

каждый операторный символ имеет один вход и один выход;

начальный символ- один выход, а конечный - один вход;

условный символ имеет один вход и два выхода, обозначаемых цифрами 1 и 0 или словами "да" и "нет";

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

каждый выход соединяется только с одним входом;

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

Рассмотрим назначение и конфигурацию некоторых основных символов граф-схем алгоритмов.

Начало и конец алгоритма представляются овалами:

 

 

Начало Конец

 

 

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

 

 

и т.д.

 

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

Условный символ, т.е участок ветвления алгоритма, изображается ромбом:

 

 

1 0

 

 

Этот символ означает выбор направления выполнения алгоритма в зависимости от того выполняется или нет некоторое логическое условие, обозначение которого вписывается в ромб. Если условие выполняется, то ветвление происодит по выходящей линии, обозначенной "1" или словом "да", в противном случае по выходящей линии, обозначенной "0" или словом "нет".

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

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

 

 

Приведем простой пример граф-схемы алгоритма:

 

 

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

 

 

или и т.д,

где Y - это YES, а N - это NO.

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

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

При помощи этих символов можно описать практически любой алгоритм обработки информации.

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

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

Содержательные термины можно обозначать по разному, но они должны быть максимально лаконичными и в тоже время четко обозначать выполняемую процедуру. Например, можно привести следующие общепринятые содержательные термины.

Pr1:= A - в регистр Pr1 загружается значение операнда А;

[PrА] - сдвиг содержимого регистра PrА вправо на один разряд;

[SC] - содержимое счетчика SC;

SC |= SC + 1 - прибавление 1 к содержимому счетчика SC;

Pr2:= [Hu2] - инвертирование содержимого регистра Pr2;

Pr1:= [Pr1]ДП- перевод содержимого регистра Pr1 в дополнительный код;

Pr1[m] или Pr1(m)_ m -тый разряд регистра Pr1;

L(n, PrA) - сдвиг содержимого регистра PrA влево на n разрядов;

R(n,HuA) - сдвиг вправо;

PrC:= PrA PrB; PrC:= PrA PrB; и т.д.

Регистры можно обозначать только присвоенными им именами. Например, регистры А, С, СА, MQ, SR и т.д.

Процедура передачи некоторому регистру значения, полученного в результате определенных арифметических или логических действий, или же передача данных из другого регистра, а также из любых других источников, принято обозначать знаками действий:= или =. Например, АС:= 0,

0 AC, AC [SR], AC:= [SR] + [MQ] и т.д.

Знаки же =, <, > и т.д. обозначают соответствующие логические действия. Знаки + и - это двоичное сложение и вычитание, а символ add2 - означает двоичное алгебраическое сложение.

Как уже отмечалось, к названию регистра, при необходимости, в скобках приписывается название (или номер) разряда или группы разрядов этого регистра, с которыми выполняется та или иная процедура. Например: AC(S), MQ(M), SR(S, M) и т.д. Если содержимое всего регистра, или группы его разрядов, инвертируется, то это обозначается следующим образом: [MQ], [AC(M)] и т.д.

Рассмотренные варианты содержательных терминов используются также и при словесном описании алгоритмов.

Рассмотрим еще для примера граф-схему фрагмента алгоритма, в котором организуется цикл, обеспечивающий заданное число повторных выполнений некоторой группы процедур. Эта группа процедур будет составлять так называемое "тело цикла". Нужное количество повторных выполнений (n) записывается предварительно в некоторый счетчик SC. Тогда содержательная граф-схема такого цикл будет выглядеть следующим образом.

 

 

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

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

Очевидно, что для выполнения любой арифметической процедуры надо сперва загрузить операнды в соответствующие регистры арифметического устройства (АУ) и передать в АУ некоторый код, определяющий тип арифметического действия, которое надо выполнить над загруженными операндами. Результат арифметического действия в свою очередь считывается из определенного регистра АУ в форме, используемой в конкретном компьютере. АУ является важнейшей частью АЛУ процессора.

АЛУ процессора компьютера обычно состоит из нескольких регистров данных, в которых можно хранить информацию, и логических схем блока управления АЛУ, обеспечивающего выполнение определенных арифметических и логических операций с содержимым этих регистров.

В состав блока управления АЛУ, в частности, могут входить ряд двоичных счетчиков необходимой разрядности; группа триггеров и так называемый статусный регистр, при помощи которых фиксируются или устанвливаютя определенные логические условия; регистры "масок", в том числе сдвиговые, для выполнения различных логических операций с содержимым регистров данных.

Данные, хранящиеся в упомянутых регистрах данных могут обрабатыватся следующим образом.

1. Регистры могут быть сброшены.

2. Содержимое регистров может быть преобразовано в обратный или дополнительный код.

3. Содержимое регистров, или сразу двух регистров как одно целое, может быть сдвинуто вправо или влево.

4. Содержимое регистров может быть увеличино или уменьшено на единицу.

5. Передача содержимого одного регистра в другой.

6. Сложение или вычитание данных составляющих содержимое двух регистров, выполняемое при помощи соответствующего параллельного сумматора.

7. Дизъюнкция или конъюнкция данных составляющих содержимое двух регистров.

Каждая операция АЛУ выполняется по соответствующей микропрограмме, команды которой обеспечивают выполнение необходимых элементарных операций. Вся совокупность таких микропрограмм хранится в специальной памяти процессора. Каждая микропрограмма активизируетя под управлением соответствующей базовой команды (команды ассемблера) процессора.

Поскольку мы обсуждаем алгоритмы арифметических действий, то будем рассматривать только те узлы и функции АЛУ, которые обеспечивают выполнение именно этих действий, т.е. вкратце рассмотрим основное аппаратное обеспечение арифметического устройства.

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

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

Рассмотрим с этой точки зрения некоторые варианты алгоритмов арифметических действий при частном, но типичном, варианте соот-ветствующего аппаратного обеспечения. В начале вкратце опишем принятые варианты этого обеспечения арифметических устройств, предназначенных для реализации разрабатываемых алгоритмов. Это необходимо для того, чтобы при разработке алгоритмов использовать только те действия по обработке данных, которые может реализовать данное арифметическое устройство. Таким образом, перед рассмотрением алгоритмов арифметических действий нужно с необходимой детализацией привести описание соответствующих АУ, при помощи которых предполагается реализовать эти алгоритмы.