Информатика и компьютерные науки (стр. 5 из 14)

Pw. 2.7. Вычислительная схема _-:

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

Если в терме определенные идентификаторы встречаются многократно, то вместо схем типа дерева получают "Наsse"-диаграммь1 (т. е. ациклические ориентированные графы).

Пример (схема с многократно применяемым промежуточным результатом). Терм (х - у) * (х + у) обладает схемой, показанной на рис. 2.8.

Рис.2.8. Вычислительная схема

Термы могут использоваться в системах замены термов для представления алгоритмов.

2.3. Алгоритмы как системы подстановки термов

Наиболее наглядный метод описания алгоритмов как системы текстовых замен предлагают системы подстановки термов. Как было показано в предыдущем разделе, имеет место: термы могут строиться над заданной сигнатурой по определенным, четким правилам. К сигнатуре и термам над нею могут быть заданы интерпретации над вычислительной структурой, т. е. над алгеброй. Как и в случае булевских термов, возникает ин-4)ормационная система, при которой термы выступают как представления. Через интерпретацию задается семантическая эквивалентность на гермах. Правила преобразования термов могут тогда быть определены так, что термы всегда будут переводиться в семантически эквивалентные термы.

Множества правил для алгоритмов могут быть предъявлены в форме системы подстановки термов. Специальная структура термов, которая получается из их построения, может использоваться для задания правил подстановок и их применения.

2.3.1. Правила подстановки термов

Для заданной сигнатуры S и заданного семейства Х множеств идентификаторов пара (t, r) термов t, r одинакового типа с (свободными) идентификаторами из Х называется подстановкой термов (правилом подстановки термов - ППТ) или также схемой подстановки термов. Правило записывается в виде t ® г.

В большинстве случаев для ППТ требуется, чтобы все идентификаторы, встречающиеся в г, также входили в t. Если в t и г заменяют определенные идентификаторы Х1, ..., Xn на термы t1, ..., tn подходящих типов, то получают экземпляр (частный, конкретный случаи) правила. Соответственно

t [ t1/X1, ..., tn/Xn ] ® r [ t1/X1, .... tn/Xn]

называется экземпляром правила t ® г. Если t и г - основные термы, то экземпляр называется полным.

Пример (экземпляры правил подстановок термов). Для правила

pred (succ (x)) ® х примерами экземпляров являются:

pred (succ (zero)) ® zero, pred (succ (succ (у))) ® succ (у).

Из правила получаются шаги подстановки термов благодаря тому, что правило применяется к любому подтерму имеющегося терма.

Пусть t —> г есть экземпляр правила. Пусть задан терм с, в котором встречается свободный идентификатор х; тогда

С [t/Х] ® С [r/Х]

называется (безусловным) применением правила (к. терму c[t/x]). Tepм t называется редексом, а вхождение х в с - местом применения.

Пример (применение правила замены термов). К терму

succ (succ (pred (succ (zero)))) может быть применено правило предыдущего примера. Это дает:

succ (succ (pred (succ (zero)))) —> succ (succ (zero)).

Аналогом алгоритмов в виде подстановки текстов являются алгоритмы в виде систем подстановки термов (алгоритмы подстановки термов - АПТ).

2.3.2. Система подстановки термов

Множество (в общем случае конечное) R правил подстановки термов на сигнатуре S называется системой подстановки термов (СПТ) над S. Если для последовательности термов ti (0 <= i <= n) справедливо для i=0,...,n-l:

(*). ti, —> ti+1 есть применение правила из системы подстановки термов R, то последовательность термов является вычислением в R для to.

Терм t называется терминальным для системы R, если не существует герма г такого, что t ®г

есть применение правила из R.

Если в вычислении, заданном с помощью термов ti 0 <= i <= n, терм tn является терминальным, то вычисление называется терминированным (завершающимся), a tn -результатом или выходом вычисления для входа to.

Бесконечная последовательность (ti)iÎN термов, удовлетворяющих приведенному выше условию (*), называется нетерминированным (незавершающимся) вычислением R для to. Система R называется в общем случае терминированной, если не существует незавершающихся вычислений.

Терминальные основные термы определяют нормальную форму. Они часто также называются термами в нормальной форме относительно R. Над системой R мы можем терму t поставить в соответствие терминальный терм г в качестве нормальной формы, если г есть результат вычислений с входом t. Как правило, система нормальных форм, индуцированных через СПТ, не является ни однозначной, ни полной. Термы, для которых существуют только бесконечные вычисления, не имеют нормальных форм. Для определенных термов могут существовать вычисления с различными результатами.

Пример (СПТ для вычислительной структуры BOOL). Ниже символы

функций ~, v, ^ будут использоваться в скобочной префиксной и инфиксной формах записи. Правила подстановок термов гласят:

(~true) ® false, (~false) ® true, (false v x) ® x, (x v false) ® x, (true v true) ® true Эта СПТ редуцирует каждый основной терм типа bool к терму true или false.

Снова повторное применение ППТ из заданного множества правил мы можсм трактовать как алгоритм, который работает с термами в качестве входа и выхода.

2.3.3. Алгоритмы подстановки термов

Пусть задана система подстановок R; R определяет алгоритм в силу следующего предписания (алгоритм получает в качестве входного слова основной терм t):

(1) Если R содержит правило подстановки с применением t ® г, то далее алгоритм продолжается с использованием г вместо t.

(2) Если R не содержит правила подстановки с применением t ® г, то алгоритм закашивается с г в качестве результата.

Алгоритм подстановки термов (АПТ) тем самым выполняет вычисление в R для каждого основного терма t. Часто вычисление состоит в решении задачи преобразовать заданный основной терм в определенную заранее заданную нормальную форму.

Если АПТ начинает работать с заданным основным термом t, то t называют также входом для алгоритма; если алгоритм завершается основным термом г, то г называется также выходом или результатом.

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

ОСНОВЫ МАШИННОЙ АРИФМЕТИКИ

Системы счисления и способы перевода чисел из одной системы в другую.

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

В зависимости от способа изображения чисел с помощью цифр системы счисления делятся на позиционные и непозиционные.

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

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

В позиционной системе счисления любое число записывается в виде последовательности цифр:

Позиции, пронумерованные индексами k (-l < k < m-1) называются разрядами числа. Сумма m+l соответствует количеству разрядов числа (m - число разрядов целой части числа, l - дробной части).

Каждая цифра

в записываемой последовательности может принимать одно из N возможных значений. Количество различных цифр (N), используемых для изображения чисел в позиционной системе счисления, называется основанием системы счисления. Основание N указывает, во сколько раз единица k+1-го разряда больше единицы k-го разряда, а цифра соответствует количеству единиц k–го разряда, содержащихся в числе.

Таким образом, число может быть представлено в виде суммы:

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

В двоичной системе счисления используются только две цифры: 0 и 1.Любое двоичное число может быть представлено в следующей форме:

(1)

Например, двоичное число

В восьмеричной системе счисления для записи чисел используется восемь цифр (0, 1, 2, 3, 4, 5, 6, 7), а в шестнадцатеричной - шестнадцать (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F).

Таблица для перевода чисел из одной системы счисления в другую.

Двоичные числа	Восьмеричные числа	Десятичные числа	Шестнадцатиричные числа
0,0001	0,04	0,0625	0,1
0,001	0,1	0,125	0,2
0,01	0,2	0,25	0,4
0,1	0,4	0,5	0,8
1	1	1	1
10	2	2	2
11	3	3	3
100	4	4	4
101	5	5	5
110	6	6	6
111	7	7	7
1000	10	8	8
1001	11	9	9
1010	12	10	A
1011	13	11	B
1100	14	12	C
1101	15	13	D
1110	16	14	E
1111	17	15	F
10000	20	16	10

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