Подходы к алгоритмизации

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

Основными критериями эффективности программ являются:

1) объем памяти, необходимый для программы;

2) время выполнения программы;

3) ясность и простота структуры программы, определяющая степень ее сопровождаемости.

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

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

BS подход получил свое название как аббревиатура от "Bowl of Spaghetti" ("Блюдо макарон"). В этом подходе на структуру алгоритма не накладывается никаких ограничений. В результате полученная программа может быть очень эффективна по памяти и по времени. Поскольку в общем случае временные связи между отдельными программными модулями могут быть очень сложными, то получаемая при этом ГСА также будет очень сложной и запутанной (как блюдо макарон). Подобные структуры плохо сопровождаютсяих трудно понять, модифицировать, тестировать и отлаживать. В связи с этим программа может содержать множество ошибок, не выявленных в процессе ее создания. Однако, достоинства BSподхода дают основание применять его для алгоритмизации простых задач, в которых невозможно сильно напутать даже при большом желании.

Для повышения ясности и упрощения структуры алгоритма был разработан структурный подход к алгоритмизации. В этом подходе накладываются жесткие ограничения на структуру ГСА.

В соответствии со структурным подходом любой алгоритм может быть реализован с помощью трех базовых логических конструкций: СЛЕДОВАНИЕ,ВЕТВЛЕНИЕиЦИКЛ,ГСА которых приведены на рис. 6.32.

Рис. 6.32. Базовые логические конструкции:

а) СЛЕДОВАНИЕ; б)ВЕТВЛЕНИЕ;

в) ЦИКЛ С ПРЕДУСЛОВИЕМ; г)ЦИКЛ С ПОСТУСЛОВИЕМ

Конструкция СЛЕДОВАНИЕпредставляет собой некоторую последовательность операторов действия.

Конструкция ВЕТВЛЕНИЕобеспечивает возможность принятия двоичного решения. При этом в зависимости от значения проверяемого условия выполняется либо один, либо другой оператор действия. В частном случае одна из ветвей конструкцииВЕТВЛЕНИЕможет быть пустой.

Конструкция ЦИКЛобеспечивает многократное выполнение одних и тех же действий до тех пор, пока не будет выполнено условие выхода из цикла. При этом существуют две разновидности конструкцииЦИКЛ. В конструкцииЦИКЛСПРЕДУСЛОВИЕМвозможен случай, когда оператор действия не будет выполнен ни разу. В конструкцииЦИКЛСПОСТУСЛОВИЕМоператор действия выполняется минимум один раз.

Характерной особенностью всех базовых логических конструкций является наличие одного входа и одного выхода. Этому условию удовлетворяют также и более сложные логические конструкции: ВЫБОРиВЫБОРПОВТОРЕНИЕ,которые могут использоваться при разработке структурированных алгоритмов. ГСА этих расширенных конструкций приведены на рис. 6.33.

Рис. 6.33. Расширенные логические конструкции:

а) ВЫБОР; б) ВЫБОРПОВТОРЕНИЕ

В конструкции ВЫБОРпо значению параметра выбора I выбирается соответствующая ветвь и выполняется находящийся в ней оператор действия. После этого управление передается на выход из логической конструкции.

В конструкции ВЫБОРПОВТОРЕНИЕоператор действия выбирается и выполняется точно так же, как в конструкции ВЫБОР. Однако, после этого осуществляется модификация параметра выбора I и управление вновь передается на его анализ и т.д. Некоторое значение I соответствует выходу из этой логической конструкции. КонструкцияВЫБОРПОВТОРЕНИЕфактически объединяет все базовые логические конструкции и является универсальной, так как любой алгоритм может быть представлен с ее помощью.

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

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

Рассмотрим этот процесс в обобщенном виде, предполагая, что общая задача разбита на две подзадачи. Выполним взаимоувязку этих подзадач во времени с помощью двух противоположных логических конструкций: последовательной конструкции СЛЕДОВАНИЕи параллельной конструкцииВЫБОРПОВТОРЕНИЕ. Применение остальных логических конструкций для решения этой задачи рассматривать не будем, так как это даст лишь промежуточные варианты построения алгоритма.

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

Рис. 6.34. Представление алгоритма решения общей задачи:

а) логической конструкцией СЛЕДОВАНИЕ;

б) логической конструкцией ВЫБОРПОВТОРЕНИЕ

Действительно, любой алгоритм начинается с подзадачи "Подготовка", обеспечивающей исходное корректное состояние всех наборов данных программы. Далее в обоих алгоритмах выполняется подзадача 1, а затем подзадача 2. Особенностью этих алгоритмов является отсутствие оператора конца. В связи с этим общая задача решается в течение бесконечного времени, в ходе которого чередуется выполнение подзадач 1 и 2. Эта особенность очень характерна для МПС, чаще всего решающих вычислительные и управляющие задачи, не имеющие конца. Полученный вывод об эквивалентности ГСА справедлив и для алгоритмов, увязывающих подзадачи любого этапа декомпозиции.

Таким образом, алгоритмизация программы с помощью различных логических конструкций в однопроцессорных МПС дает эквивалентные результаты. Поскольку наиболее простой является конструкция СЛЕДОВАНИЕ, то ее и целесообразно использовать для этой цели.

Рис. 6.35. Условное выполнение

подзадачи

Условное выполнение некоторой подзадачи в конструкцииСЛЕДОВАНИЕобеспечивается путем анализа управляющих признаков (ключей) на ее входе (рис. 6.35). Если значение ключа соответствует выполнению подзадачи, то реализуются необходимые действия. В противном случае выполнение подзадачи сразу прекращается, и управление передается на ее конец.

Такая организация имеет некоторую избыточность, так как требует анализа всех управляющих ключей на входе подобных подзадач. Это является следствием применения структурного подхода к алгоритмизации программы. Однако, затраты на реализацию этой избыточности весьма невелики и, чаще всего, являются вполне приемлемой платой за упрощение алгоритма программы путем его представления в виде логической конструкции СЛЕДОВАНИЕ.