3. Способы представления (описания) алгоритмов

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

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

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

Далее более подробно рассматриваются различные формы представления алгоритмов. Однако сначала уточним понятие «исполнитель алгоритма».

3.1. Исполнитель алгоритма

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

Введем понятие формального исполнителя:

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

Исполнитель алгоритма считается заданным, если для него установлены:

• система команд (элементарных действий алгоритма, которые способен выполнить исполнитель);

• формы представления входной и выходной информации;

• система допустимых внутренних состояний;

• язык представления алгоритма.

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

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

• ошибки синтаксиса, т.е. нарушение формальных правил записи алгоритма;

• выход начальных данных за пределы допустимого множества;

• несоответствие алгоритма возможностям исполнителя.

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

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

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