книги из ГПНТБ / Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы

трическне сигналы, изображающие выходные данные. Вход­ ные сигналы поступают в арифметический блок из ячеек па­ мяти, где они хранились, а выходной сигнал отправляется из него в ту ячейку, в которой он будет храниться. Схема­ тически это изображено на рис. 10, б, где числа из ячеек 11 и 12 складываются, а результат отправляется в ячейку 15. Для того чтобы такая операция была осуществлена в ма­ шине в некотором такте, необходимо, чтобы к началу этого такта были произведены соединения ячеек 11 н 12 с ариф­ метическим блоком и арифметического блока с ячейкой 15;

3. Б л о к у п р а в л е н и я предназначен для выпол­ нения функций, которые в схеме рис. 10, а выполняет сам

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

5.3. Машинные команды. Для более точного описания возникающей здесь картины укажем, что каждая машина характеризуется вполне определенной системой команд (при­ казов), которые она может принимать к исполнению. При этом всякая программа, вкладываемая в машину, представ­

команд, каждая из которых является последовательностью

*) В машине БЭСМ-6 и в машинах серии «Урал» принята одно­ адресная система; в машинах серии «Минск» — двухадресная.

50

Практически каждая команда записывается в одной ячейке в виде одного числа, цифры которого разбиваются на четыре группы, имеющие соответствующие назначения. Например, на рис. 10, б в ячейке 1 запоминающего устрой­ ства записано число 1 11 12 15, которое представляет собой следующий зашифрованный приказ:

«Сложить (операция № 1) числа из ячек 11, 12 и резуль­ тат отправить в ячейку 15».

(Здесь принято разделение на группы справа налево по два разряда. Для определенности мы будем и дальше при­ держиваться такого метода записи команд.)

Обычно система команд насчитывает несколько десятков команд (хотя наблюдается общая тенденция к увеличению

ются к исполнению лишь в том случае, если выполнено со-

51

ответствующее условие, в противном случае они пропуска­ ются управляющим устройством без выполнения.

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

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

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

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

§ 6. ПРОГРАММА (МАШИННЫЙ АЛГОРИТМ)

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

52

нить реальный смысл употребляемого обычно выражения

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

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

п5.3).

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

с, d, е, f помещены подряд в ячейки памяти, начиная с номе­ ра 51:

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

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

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

53

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

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

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

После того, как первый цикл из 11 команд выработает решение первой системы, второй цикл из И команд выра­ ботает решение второй системы и так дальше п раз, (11/г -f- + 1)-й командой является команда остановки.

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

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

54

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

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

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

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

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

55

да 21 — это условная передача управления команде 1: она выполняется до тех пор, пока в ячейке 28 все еще хранится

Арифметических операций

Переадресааии

Счет циклов

Условия передачи управления

Остановка

56

6.3. Программирование алгоритма Евклида. П р и м е р 3.

ЮI 14 05 13 Пересылка числа из 14 в 13

П5 00 00 01 Безусловным переход к команде 01

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

Если а — b = 0 (т. е. а — Ь), то команды 03 и 04 условной передачи управления пропускаются и выполня­ ется команда 05, которая останавливает машину. К этому моменту в ячейке 15, действительно, уже содержится нуж­ ный результат (сравнить с указанием 3 п. 1.1).

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

67

Если же а — b > 0, т. е. а > Ь, то команда 03 пропуска­ ется, а команда 04 передает управление команде 09, кото­ рая вместе со следующей за ней командой 10 пересылает в ячейки 12 и 13 прежнее вычитаемое и остаток, т. е. 6 и а —

— b соответственно (сравните с указанием 4). Лотом команда 11 обеспечивает безусловный переход к команде 01, и тем самым начинается второй цикл работы машины.

Последовательность циклов работы машины будет по­

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

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

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

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

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

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

58

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

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

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

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

59