§ 6. ПРОГРАММА (машинный алгоритм)

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

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

указываются в командах номерами 1, 2, 3, 4 соответственно (см. § 5).

Пример 1. Запрограммируем решение системы уравнений

Примем для определенности, что коэффициенты помещены подряд в ячейки памяти, начиная с номера 51:

Далее, для промежуточных и окончательных результатов вычислений отведем ячейки 31—50.

Как видно из формул

для получения результата нужно совершить последовательно 6 умножений, три вычитания и два деления. В соответствии с этим предлагаемая нами программа состоит из 12 команд, записанных в ячейках 1—12:

Команды поступают в блок управления и выполняются в порядке возрастания их адресов. После выполнения последней команды в ячейки 31—41 приняты на хранение следующие числа:

представляющие собой промежуточные результаты вычислений и окончательный результат (помещенный в ячейках 40, 41).

Пример 2. Пусть требуется найти решения заданных систем уравнений:

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

После того, как первый цикл из 11 команд выработает решение первой системы, второй цикл из 11 команд выработает решение второй системы и так дальше раз, командой является команда остановки.

Однако такое значительное увеличение объема программы нецелесообразно и его можно избежать. Для этого заметим, что каждый последующий цикл из 11 команд может быть получен из предыдущего путем изменения адресов, участвующих в командах. Именно, если коэффициентов расположены по одному в ячейках, следующих подряд одна за другой, например, начиная с № 51, то в первых шести командах адреса множителей должны быть увеличены каждый на 6, для того чтобы получить соответствующие команды второго цикла.

Далее, для того чтобы решение очередной системы оказалось записанным в двух ячейках, следующих за ячейками, хранящими решение предыдущей системы, необходимо увеличить каждый из последних адресов в десятой и одиннадцатой командах на два. Такое изменение адресов может быть осуществлено посредством так называемых команд переадресации, которых в нашем случае будет 8. Для этого поместим в ячейки 25 и 26 параметры:

а в ячейки 12—18 восемь команд переадресации:

После выполнения команд из ячеек 1—19 в ячейках 40—41, как и прежде, будет принято на хранение решение первой системы уравнений, но вместе с тем в

ячейках 1—6 и 10—11 уже окажутся следующие переадресованные команды:

Поэтому, если теперь вторично принять к исполнению команды из ячеек 1 —19, то в результате такого второго цикла работы машины уже будет найдено решение второй системы уравнений, которое будет направлено на хранение в ячейки 42—43; кроме того, будет осуществлена очередная переадресация команд 1—6 и 10—11, создающая условия для аналогичного третьего цикла работы и т. д.

Как же обеспечить подобное циклическое выполнение 19 команд столько раз, сколько дано систем уравнений с тем, однако, чтобы после того, как будут найдены решения всех заданных систем, машина остановилась? Для этого поместим еще в ячейки 27 и 28 параметры равно числу всех заданных систем), а к рассмотренным ранее 19 командам присоединим следующие три:

Команда 20 уменьшает на единицу содержимое ячейки 28 после каждого выполнения цикла команд 1 —19. Команда 21 — это условная передача управления команде 1: она выполняется до тех пор, пока в ячейке 28 все еще хранится положительное число, и тем самым обеспечивает переход к следующему циклу команд 1 —19 для решения следующей системы уравнений. Если же в ячейке 28 хранится 0, а это случится в точности после циклов 1 —19, то передача управления не

осушествлястся, а выполняется следующая команда 22, которая останавливает машину.

Из всего сказанного ясно, что для поставленной задачи о решении систем уравнений пригодна программа из указанных выше команд 1—22, с учетом параметров, вводимых в ячейки 25—28. Структуру этой программы в целом удобно изобразить в виде следующей схемы:

(см. скан)

Пример 3. Рассмотрим теперь программу для нахождения общего наибольшего делителя двух чисел Условимся отвести ячейки 12 и 13 для исходных данных соответственно, а ячейки 14 и 15 для промежуточных вычислений с тем, чтобы окончательный результат после остановки машины оказался в ячейке 15. Предлагаемая ниже программа составлена в соответствии с приведенной в § 1 формулировкой алгоритма Евклида.

(см. скан)

После первых двух тактов в ячейках 12—15 возникают следующие числа:

Если (т. е. то команды об условной передаче управления пропускаются и выполняется команда которая останавливает машину. К этому моменту в ячейке 15, действительно, уже содержится нужный результат (сравнить с указанием 3 § 1).

Если (т. е. то команда передает управление команде которая вместе со следующей за ней командой осуществляет перестановку местами чисел в ячейках 12 и 13 (сравнить с указанием 4). Потом команда обеспечивает безусловный переход к и тем самым начинается второй цикл работы машины.

Если же то команда пропускается, а команда передает управление команде которая вместе со следующей за ней командой 10 пересылает в ячейки 12 и 13 прежнее вычитаемое и остаток, соответственно (сравни с указанием 4). Потом команда 11 обеспечивает безусловный переход к команде и тем самым начинается второй цикл работы машины.

Последовательность циклов работы машины будет порождать в ячейках 12 и 13 последовательность пар чисел:

а в ячейке 15 последовательность чисел

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

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

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

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

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

Эти же принципы характеризуют работу машины и при решении таких задач, которые не носят явного

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

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

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

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

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