книги из ГПНТБ / Сафонов, С. Ф. Вычислительная техника в инженерных и экономических расчетах (конспект лекций)

МИНИСТЕРСТВО ВЫСШЕГО И СРЕДНЕГО СПЕЦИАЛЬНОГО ОБРАЗОВАНИЯ РСФСР КУЙБЫШЕВСКИЙ ИНЖЕНЕРНО-СТРОИТЕЛЬНЫЙ ИНСТИТУТ им. А. И. МИКОЯНА

КАФЕДРА ТЕОРЕТИЧЕСКОЙ И СТРОИТЕЛЬНОЙ МЕХАНИКИ

С. Ф. САФОНОВ

\в ы ч и с л и т е л ь н а я ' т е х н и к а

/- В ИНЖЕНЕРНЫХ

i' и ЭКОНОМИЧЕСКИХ РАСЧЕТАХ

(Конспект лекций)

Утверждено советом института 9 июля 1973 г.

ЙБЫШЕВ\1974

Р а з д е л I

§ 1. ПОНЯТИЯ, ПРЕДШЕСТВУЮЩИЕ ПРОГРАММИРОВАНИЮ

Системы счисления. Системами счисления называют способы наименования и записи чисел. Перед изучением курса вычисли­ тельной техники, и в частности программирования, рекоменду­ ется познакомиться с этим разделом элементарной математики, изложенным в | 1], [2].

Большое значение в вычислительной технике имеют двоичная

и(в некоторых случаях) .восьмеричная системы счисления. Достоинства двоичной системы счисления, используемые в вы­

числительной технике, следующие:

а) простая реализация для двоичной системы счисления электронных, схем;

б) замена действия вычитания действием сложения (исполь­ зованием дополнительного или модифицированно-дополнитель- ного кода);

в) замена действия умножения сдвигами двоичных наборов с последующим их сложением;

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

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

Пример. Алгоритм Ньютоца вычисления квадратного корня из данного числа N с любой степенью точности:

Ш аг п ервы й . В качестве первого приближения для VNбе­ рем произвольное число Аь А2, А3..., Ап. Общий член этой после­ довательности задается формулой

3

Лп = ~Y (^n-l +5 An—!) •

Учащийся, знакомый с основными результатами теории пре­ делов, сможет доказать, что выбор числа А произволен — ведь

lim АП=УЛГ, но такой выбор влияет на скорость процесса. Этот алгоритм обладает весьма важной особенностью: в нем все ша­ ги по операциям аналогичны. Такой алгоритм называется цикли­ ческим.

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

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

Понятие алгоритма можно определить и так — алгоритмами в современной математике принято называть конструктивно за­ даваемые соответствия между словами в абстрактных алфавитах.

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

Слова в таком алфавите определим как любые конечные упо­ рядоченные последовательности букв. Число букв в слове опре­ делит длину слова.

Алфавитным оператором или алфавитным отображением на­ зывается всякое соответствие, сопоставляющее словам в том или ином алфавите слова в том же самом или в некотором другом фиксированном алфавите.

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

Содержательную и подробную информацию об алгоритмах можно почерпнуть в [14].

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

Обозначим все условия задачи, перерабатываемые алгорит­ мом а, в виде последовательности с целыми неотрицательными индексами — номерами: А0, А ь А2..., Ап,...

Решения можно представить занумерованной последователь­ ностью В0, В и В2...,Вт...

После введения нумерации будем оперировать уже не запи­ сями условий и решений, а их номерами. Теперь можно предста­ вить алгоритм, ■который перерабатывает номер записи условий в номер записи решения. Этот алгоритм осуществляет вычисле­ ние значений числовой функции т — <р{п), т. е. он является чи­ сленным алгоритмом.

.4

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

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

Рассмотрим широко применяющийся для нумерации метод Геделя.

Представим некоторое число я в следующем виде:

множители только единственным способом, можно утверждать, что каждому числу однозначно соответствует набор ад, а2..., ат и, наоборот, каждому набору щ, а2,..., ат однозначно соответствует число я.

Н а п р н м е р: если, я = 60, то 60= 22. З1. 51, т. е. at =2, а2= 1,

из— 1-

Этим способом можно нумеровать любые упорядоченные по­ следовательности т чисел.

Пример. С помощью метода Геделя можно перенумеровать все слова в некотором алфавите А, где каждой букве ставится в соответствие некоторое число. Тогда любому слову в алфавите А соответствует ’последовательность чисел, от которой легко пе­ рейти к Геделевскому номеру, зависящему от выбранной систе­ мы соответствий букв и чисел. Далее можно перенумеровать все последовательности слов, например, дедуктивные цепочки. .^По­ следовательность номеров, полученная таким образом, даст воз­ можность провести анализ дедукции с помощью ЭВМ.

Упорядоченные сочетания т чисел можно пронумеровать по

где я — номер сочетания (без повторений)

Оь Ог, аз..., ат‘>

К — количество элементов (букв в алфавите описания), из ко­ торых составляются сочетания;

тх— количество элементов в нумеруемом сочетании; бг — значение буквы (цифры), стоящей в разряде г, счет раз­

рядов сочетания ведется справа налево, начиная с едини­ цы, упорядоченного так: большая цифра стоит в млад­ шем разряде.

5

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

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

Сочетания с повторениями возможно свести к сочетаниям без повторений по следующему алгоритму:

=h

а2 = “l + Рз+ 1

ctg = аз-|- Рз 1

ал ~ <*я—1+ Рл+ 1

где а* г'-й элемент сочетания, к которому приводится исходное сочетание с повторениями;

Рг—г-й элемент исходного сочетания с повторениями. Счет элементов ведется слева направо.

Приме р . Привести сочетание с повторениями 3645tj к сочета­ нию без повторений

Таким образом, набор 36456 свелся к сочетанию без повторе­ ний 3 10 15 21 28.

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

Обратная задача, т. е. получение сочетания из его порядко­ вого номера, легко решается, см., например, [12].

Заметим, что формула нумерации сочетаний может служить в качестве математического описания широко используемого в кибернетике устройства—дешифратора.

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

Естественный ход выполнения команд. В отечественных ма­ шинах принят естественный ход выполнения команд, т. е. коман­ ды выполняются в том порядке, в каком они расположены в ячеи-

6

ках памяти машины. После выполнения очередной команды уп­ равление передается следующей.

С этим не следует смешивать те случаи, в которых сама ис­ полняемая команда производит передачу управления. В ЭВМ «Наири» команда, например, и 400 а (идти к 400 ячейке) переда­ ет управление команде, записанной в 400 ячейке запоминающего

устройства.

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

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

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

Характеристика ЭВМ «Наири». Электронно-цифровая вычи­ слительная машина «Наири» — малая универсальная вычисли­ тельная машина с небольшой емкостью оперативно запоминаю­ щего устройства. Универсальная потому, что она может решать любые задачи известных алгоритмов, которые могут быть разме­ щены в памяти машины.

Вбе электронные устройства машины выполнены на полупро­ водниках, что делает ее компактной и более надежной в эксплу­ атации.

«Наири» —двухадресная машина, потому что в ее командах наибольшее количество адресов (см. ниже) обрабатываемой информации равно двум. (При этом адреса команд, по которым проверяются условия [см. ниже], не принимаются во внимание).

«Наири» обрабатывает информацию в двоичной системе счи­ сления и имеет 36 двоичных разрядов для хранения и обработ­ ки информации.

Ее быстродействие от 100 до 2000 операций в секунду.

Общение с машиной может происходить на нескольких язы-

7

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

X 353i S3 3 2 Л зогзэз27 26 2S2K23 гг. 12219/ 3 J ;/5, '721

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

Емкость оперативного запоминающего устройства (ОЗУ) ма­ шины — 1024 36-разрядные ячейки. Каждая ячейка предназна­ чена для хранения одного числа или одной команды.

Машина имеет долговременное запоминающее устройство (ДЗУ) (см. ниже), емкость которого— 16384 ячейки. Для обще­ ния с машиной имеются внешние устройства. Малая скорость вво­ да информации—пока существенный недостаток вычислительных машин. Информация может вводиться в машину в буквенной и цифровой формах, однако ЭВМ способна запоминать тоЛько цифры. Поэтому вводимые в машину буквы автоматически коди­ руются цифрами. Машина имеет четыре языка общения. ЭВМ для общения имеет в своем ДЗУ программу дешифрации исходной информации (программу ДИИ). Эта программа анализирует вводимую на простом языке информацию и выполняет предписы­ ваемые машине, таким образом, различные действия. Обраще­ ние к этой программе производится с пульта сигнализации про­ стым нажатием клавиши «Пуск-1». Программа ДИИ также не­ прерывно анализирует вводимую информацию на ошибочность и в случае ввода информации, не имеющейся в словарном запасе машины, печатает с помощью телетайпа символ >1<, помогая этим программисту. Разумеется, программой ДИИ не могут разли­ чаться семантические ошибки, т. е. использование одного слова, имеющегося в ДЗУ, вместо другого, находящегося там же. ДИИ различает лишь синтаксические ошибки.

Например, если оператор вместо функции синуса станет оши­ бочно вводить функцию косинуса, то машина не сможет попра­ вить оператора — ведь оба слова верны с точки зрения машины. Но если оператор станет вводить слово, которого нет в словаре машины, то ЭВМ сразу же отпечатает признак ошибки. Это слу­ чится в том случае, если оператор начнет путать последователь­ ность действий при «разговоре» с машиной.

Программа ДИИ осуществляет во время общения, перевод

8

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

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

«Наири» имеет/в своем ДЗУ тестирующую (проверяющую работоспособность машины) программу, с помощью которой лег­ ко определить исправность машины.

ЭВМ «Наири» выполнена в виде красиво оформленного пись­ менного стола, потребляет 1,6 квт и может питаться of обычной электрической сети. Вес, машины около 600 кг. Машина обслу­ живается одним пнженером-электроником и одним техником. ЭВМ может работать круглосуточно.

Такие малые вычислительные машины с небольшой емкостью оперативной памяти иногда называют инженерными вычисли­ тельными машинами.

Функции некоторых устройств машины и их характеристика. ОЗУ служит для приема информации от других устройств маши­ ны, а также для хранения и выдачи этой информации другим устройствам.

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

.При ручном программировании на «Наири» можно использо­ вать следующие ячейки ОЗУ: 0,1, 11—15, 29—980, 991—997, 1004—101.7, 1021—1023. При этом сохраняется возможность пользоваться режимами выдачи памяти. При чтении из ячеек па­ мяти информация не стирается.

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

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

В ДЗУ невозможно записать информацию, так же как и сте­ реть ее с телетайпа или сделать это же программным путем. Вся

9