АЛГОРИТМ И ЕГО СВОЙСТВА. Определение алгоритма

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

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

Таким образом, задача обработки информации будет рассматриваться как задача получения выходных данных путем обработки входных данных. Решение этой задачи в самом общем виде приведено на Рис.1. Для решения задачи необходимо иметь:

1. Точное описание действий (операций), выполняемы над данными, и последовательность выполнения этих действий.

2. Исполнителя, способного выполнить требуемые действия.

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

Пример. Входные данные представляет собой коэффициенты квадратного уравнения AX² + BX + C =0. Вычислить корни уравнения X₁, X₂. Вычисления повторять до ввода нулевого значения коэффициента A.Решение задачи возлагается на исполнителя, который умеет выполнять операции с вещественными числами и вычислять типовые математические функции.

Алгоритм решения задачи представим в виде перечня действий. Каждый пункт этого перечня будем называть шагом:

1. Ввести значения коэффициентов A,B,C

2. Если А равно 0, то перейти к шагу 9

3. Вычислить D = B² – 4AC.

4. Вычислить

5. Вычислить

6. Вывести значение X₁ и значение X₂

7. Ввести значения коэффициентов A,B,C

8. Перейти к шагу 2.

9. СТОП – прекратить выполнения алгоритма.

Действия выполняются последовательно в порядке перечисления шагов. Такой порядок выполнения шагов называется естественным порядком. Для изменения естественного порядка в алгоритм включены специальные действия, выполняемые на шаге 2 и шаге 8.

2. Свойства алгоритма

Схематично основные свойства алгоритма приведены на Рис.2. Рассмотрим эти свойства подробнее.

Рис. 2

Дискретность - алгоритм должен быть записан в виде конечного числа шагов. Выполнение каждого шага начинается после завершения выполнения предыдущего.

Конечность- выполнение алгоритма завершается после выполнения конечного числа шагов. При выполнении алгоритма некоторые шаги могут выполняться многократно. В рассмотренном примере шаги с 2-го по 8-ой выполняются до ввода нулевого значения коэффициента A.

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

Определенность– алгоритм не должен допускать произвольной трактовки шагов со стороны исполнителя. Исполнитель должен действовать в строгом соответствии с командами, которые указаны в каждом шаге. У исполнителя не должно возникать необходимости предпринимать действия, не предусмотренные алгоритмом. Другими словами, алгоритм рассчитан на механическое выполнение устройством, не обладающим "здравым" смыслом.

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

Массовость означает, что один и тот же алгоритм можно использовать для решения многих однотипных задач, отличающихся количеством и/или значениями входных данных.

3. Способы записи алгоритма

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

Пример записи алгоритма на естественном языке был рассмотрен выше.

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

1. Схема алгоритма. Правила выполнения схемы алгоритма регламентируются стандартом ГОСТ 19.002-80 и ГОСТ 19.003-80 ( в измененной редакции объединены в ГОСТ 19.701-90).

2. Структурограмма.

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

Для составления алгоритма необходимо знать систему команд исполнителя. Это создает большие проблемы при замене исполнителя. Для решения проблемы используется запись алгоритма на языке, не зависящем от особенностей исполнителя. Такой язык не воспринимается техническим устройством и требует предварительного перевода на язык команд исполнителя. Запись обрабатываемых данных и алгоритма на языке, доступном для восприятия исполнителем непосредственно или через систему перевода, называется программой.