Файл: Трахтенброт, Б. А. Алгоритмы и вычислительные автоматы.pdf

«ами хранящими решение предыдущей системы, необходи­ мо увеличить каждый из последних адресов в десятой и один­ надцатой командах на два. Такое изменение адресов может быть осуществлено посредством так называемых команд пе­ реадресации, которых в нашем случае будет 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