Файл: Сафонов, С. Ф. Вычислительная техника в инженерных и экономических расчетах (конспект лекций).pdf

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

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

С. Ф. САФОНОВ

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

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

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