Конспект главы 2

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

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

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

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

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

Для решения одних и тех же задач исполнители с более "бедным" набором допустимых действий требуют более сложных и подробных алгоритмов.

Итак, алгоритм - это организованная последовательность действий, допустимых для некоторого исполнителя. Это - не строгое определение алгоритма. Строгого определения алгоритма нет: в информатике это понятие фундаментальное.

Разные классы задач требуют разных наборов допустимых действий - разных исполнителей. Обычно набор допустимых действий явно или неявно указывается в формулировке задачи.

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

Задачи на вычисления - один из наиболее широких классов задач, решаемых на ЭВМ. Исполнитель вычислительных алгоритмов называется ВЫЧИСЛИТЕЛЕМ. Он имеет дело с числами и переменными. Вот некоторые из его допустимых действий:

1. Запросить исходные данные и обозначить их латинскими буквами. Это можно записывать так: "Запросить...", указывая вместо многоточия соответствующие буквы. Например,

 Запросить А, В, С.

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

 Сообщить X, Y. 
 Сообщить "Я работаю ВЫЧИСЛИТЕЛЕМ!".

3. Обозначить какой-либо буквой значение алгебраического выражения:

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

 Присвоить С значение А + 2В.

Остальные действия будут перечислены в следующих главах.

Записывая алгоритмы в тетради, можно использовать сокращения или, скажем, добавлять пояснения. Например: "Запр. v" или "Запросить значение скорости v". Важно лишь, чтобы каждая команда в точности соответствовала допустимому действию исполнителя. Нельзя, например, записывать для ВЫЧИСЛИТЕЛЯ команду "Сообщить X или Y", поскольку он не может сам выбрать, какое из чисел сообщать (у него нет соответствующего допустимого действия).

При записи программ для ВЫЧИСЛИТЕЛЯ, имитируемого на ЭВМ, запись команд жестко фиксируется и все команды нумеруются (не обязательно подряд). Например, в команде присваивания сначала пишется имя переменной, которой присваивается значение выражения, затем знак равенства и само выражение.

Вот пример записи алгоритма для ВЫЧИСЛИТЕЛЯ.

 Запр. знач. переменных А, В. 
 Присвоить С знач. (А + В)/2. 
 Сообщить полученное значение С.

Для ЭВМ соответствующая программа выглядит так:

 1 ЗАПРОСИТЬ А, В 
 4 С=(А + В)/2 
 10 СООБЩИТЬ С

Этот алгоритм исполняется следующим образом. Сначала ВЫЧИСЛИТЕЛЬ запросит у нас два числа. Когда мы сообщим их ему, он обозначит первое число буквой А, второе число - буквой В. Затем ВЫЧИСЛИТЕЛЬ найдет полусумму чисел А и В, а результат обозначит через С. После этого он сообщит значение С.

Каждую переменную, с которой работает ВЫЧИСЛИТЕЛЬ, удобно представлять себе как ящик, в котором можно хранить любое число. Когда в такой "ящик" кладут новое число, старое бесследно исчезает. Допустимые действия ВЫЧИСЛИТЕЛЯ не позволяют никакой переменной присваивать два значения одновременно. Букву, обозначающую переменную, называют именем этой переменной. Имена переменных можно использовать в записи различных алгебраических выражений. При вычислении значений этих выражений имена заменяются числами из соответствующих "ящиков". Запросив число, ВЫЧИСЛИТЕЛЬ кладет его в "ящик", предварительно обозначив этот "ящик" соответствующей буквой.

Поясним сказанное на примере команды Присвоить А значение А + 3.

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

1) пройти 1 см в направлении стрелки, рисуя линию;

2) повернуться на 90° влево вокруг начала стрелки;

3) прыгнуть на 1 см в направлении стрелки, не рисуя линии.

При имитации на ЭВМ ЧЕРТЕЖНИК выполняет первое действие по команде "СДЕЛАТЬ ШАГ", второе действие - по команде "ПОВЕРНУТЬ НАЛЕВО", а третье - по команде "ПРЫГНУТЬ".

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

Для расширения класса достижимых целей исполнителя надо расширить набор его допустимых действий.