Ім'я файлу: науки.doc
Розширення: doc
Розмір: 508кб.
Дата: 15.12.2020
скачати
Пов'язані файли:
реферат Правила торгівлі на ринках.doc
Информатика.doc
ПК науки.doc
Zadacha_1_ (3).doc
Розширення: doc
Розмір: 508кб.
Дата: 15.12.2020
скачати
Пов'язані файли:
реферат Правила торгівлі на ринках.doc
Информатика.doc
ПК науки.doc
Zadacha_1_ (3).doc
Для осуществления автоматического перевода десятичных чисел в двоичную систему счисления необходимо вначале каким-то образом ввести их в машину, Для этой цели обычно используется двоично-десятичная запись чисел или представление этих чисел в кодах ASCII.
При двоично-десятичной записи каждая цифра десятичного числа заменяется четырехзначным двоичным числом (тетрадой):
При записи чисел в кодах ASCII цифрам от 0 до 9 поставлены в соответствие восьмиразрядные двоичные коды от 00110000 до
00111001.
ЭВМ, предназначенные для обработки экономической информации, например IBM AT, позволяют производить арифметические операции в десятичной системе счисления над числами, представленными в двоично-десятичных кодах и кодах ASCII.
Шестнадцатеричная и восьмеричная системы счисления используются только программистами и операторами ЭВМ, так как представление чисел в этих системах более компактное, чем в двоичной, и перевод из этих систем в двоичную и обратно выполняется очень просто (основания этих систем представляют собой целую степень числа
Для перевода восьмеричного числа в двоичное достаточно каждый восьмеричный разряд представить тремя двоичными (триадой), а для перевода шестнадцатиричного числа - четырьмя (тетрадой):
Формы представления чисел в ЭВМ.
Разряд двоичного числа представляется в ЭВМ некоторым техническим устройством, например, триггером, двум различным состояниям которого приписываются значения 0 и 1. Группа таких устройств, предназначенная для представления в машине многоразрядного числа, называется регистром.
Структура двоичного регистра, представляющего в машине n-разрядное слово:
┌───┬───┬───┬───┬───┐
│n-1│n-2│...│ 1 │ 0 │
└───┴───┴───┴───┴───┘
Отдельные запоминающие элементы пронумерованы от 0 до n-1. Количество разрядов регистра определяет точность представления чисел. Путем соответствующего увеличения числа разрядов регистра может быть получена любая точность вычислений, однако это сопряжено с увеличением количества аппаратуры (в лучшем случае зависимость линейная, в худшем - квадратичная).
В ЭВМ применяются две основные формы представления чисел:
полулогарифмическая с плавающей запятой и естественная с фиксированным положением запятой.
При представлении чисел с фиксированной запятой положение запятой закрепляется в определенном месте относительно разрядов числа и сохраняется неизменным для всех чисел, изображаемых в данной разрядной сетке. Обычно запятая фиксируется перед старшим разрядом или после младшего. В первом случае в разрядной сетке могут быть представлены только числа, которые по модулю меньше 1, во втором - только целые числа.
Для кодирования знака числа используется старший ("знаковый") разряд.
При выполнении арифметических действий над правильными дробями могут получаться двоичные числа, по абсолютной величине больше или равные единице, что называется переполнением разрядной сетки. Для исключения возможности переполнения приходится масштабировать величины, участвующие в вычислениях.
Диапазон представления правильных двоичных дробей:
.Числа, которые по абсолютной величине меньше единицы младшего разряда разрядной сетки, называются машинным нулем.
Диапазон представления целых двоичных чисел со знаком в n-разрядной сетке:
Использование представления чисел с фиксированной запятой позволяет упростить схемы машины, повысить ее быстродействие, но представляет определенные трудности при программировании. В настоящее время представление чисел с фиксированной запятой используется как основное только в микроконтроллерах.
В универсальных ЭВМ основным является представление чисел с плавающей запятой. Представление числа с плавающей запятой в общем случае имеет вид:
где
N - основание системы счисления,
p - целое число, называемое порядком числа A,
m - мантисса числа A (│m│<1).
Так как в ЭВМ применяется двоичная система счисления, то
причем порядок и мантисса представлены в двоичной форме.
Двоичное число называется нормализованным, если его мантисса удовлетворяет неравенству
Неравенство показывает, что двоичное число является нормализованным, если в старшем разряде мантиссы стоит единица. Например, число 0,110100*10100 - нормализованное, а 0,001101*10110 - ненормализованное.
Нормализованное представление чисел позволяет сохранить в
разрядной сетке большее количество значащих цифр и, следовательно, повышает точность вычислений. Однако современные ЭВМ позволяют, при необходимости, выполнять операции также и над ненормализованными числами.
Широкий диапазон представления чисел с плавающей запятой удобен для научных и инженерных расчетов. Для повышения точности вычислений во многих ЭВМ предусмотрена возможность использования формата двойной длины, однако при этом происходит увеличение затрат памяти на хранение данных и замедляются вычисления.
Представление отрицательных чисел в ЭВМ.
Для кодирования знака двоичного числа используется старший ("знаковый") разряд (ноль соответствует плюсу, единица - минусу).
Такая форма представления числа называется прямым кодом.
Формула для образования прямого кода правильной дроби имеет вид:
[A]пр=A, если A>=0,
[A]пр=1-A, если A<0.
Примеры:
A = 0,110111 [A]пр = 0,110111
A = -0,110111 [A]пр = 1 - (-0,110111) = 1,110111
Прямой код целого числа получается по формуле:
[A]пр=A, если A>=0,
[A]пр=10n-1-A, если A<0.
где 10 - число 2 в двоичной системе счисления, n - количество позиций в разрядной сетке.
Например, при n=8
A = 110111 [A]пр = 00110111
A = -110111 [A]пр = 10000000 - (-110111) = 10110111
В ЭВМ прямой код применяется только для представления положительных двоичных чисел. Для представления отрицательных чисел. применяется либо дополнительный, либо обратный код, так как над отрицательными числами в прямом коде неудобно выполнять арифметические операции.
Формула для образования дополнительного кода дроби:
[A]доп = 10 + А
Формула для образования обратного кода дроби:
[A]обр = 10 - 10-(n-1) + A.
Например, при n=8, A=-0,1100001
[A]доп = 10 + (-0,1100001) = 1,0011111
[A]обр = 10-10-7+(-0,1100001) = 1,1111111-0,1100001 = 1,0011110.
Формула для образования дополнительного кода целого числа:
[A]доп = 10n + A.
Формула для образования обратного кода целого числа:
[A]обр = 10n - 1 + A.
Например, при n = 8, A = -1100001
[A]доп = 100000000 + (-1100001) = 10011111
[A]обр = 100000000-1+(-1100001) = 11111111-1100001 = 10011110.
Таким образом, правила для образования дополнительного и обратного кода состоят в следующем:
для образования дополнительного кода отрицательного числа необходимо в знаковом разряде поставить единицу, а все цифровые разряды инвертировать (заменить 1 на 0, а 0 - на 1), после чего прибавить 1 к младшему разряду;
для образования обратного кода отрицательного числа необходимо в знаковом разряде поставить единицу, а все цифровые разряды инвертировать.
Примечание: при данных преобразованиях нужно учитывать размер разрядной сетки.
Замена вычитания двоичных чисел A1-A2 сложением с дополнениями [A1]пр+[-A2]доп или [A1]пр+[-A2]обр позволяет оперировать со знаковыми разрядами так же, как и с цифровыми. При этом
перенос из старшего знакового разряда, если он возникает, учитывается по разному для обратного и дополнительного кодов:
при использовании дополнительного кода единица переноса из знакового разряда отбрасывается;
при использовании обратного кода единица переноса из знакового разряда прибавляется к младшему разряду суммы (осуществляется так называемый циклический перенос).
Пример: складываем числа A1=0,10010001 и A2=-0,01100110
При использовании обратного кода получим:
[A1]пр = 0,10010001
+
[A2]обр = 1,10011001
───────────
10,00101010
└─────── +1
Результат: 0,00101011
При использовании дополнительного кода получим:
[A1]пр = 0,10010001
+
[A2]доп = 1,10011010
───────────
Результат: 0,00101011
Если знаковый разряд результата равен нулю, то получено положительное число, которое представлено в прямом коде. Если в знаковом разряде единица, то результат отрицательный и представлен в обратном или дополнительном коде.
Для того, чтобы избежать ошибок при выполнении бинарных операций, перед переводом чисел в обратные и дополнительные коды необходимо выравнивать количество разрядов прямого кода операндов.
При сложении чисел, меньших единицы, в машине могут быть получены числа, по абсолютной величине большие единицы. Для обнаружения переполнения разрядной сетки в ЭВМ применяются модифицированные прямой, обратный и дополнительный коды. В этих кодах знак кодируется двумя разрядами, причем знаку "плюс" соответствует комбинация 00, а знаку "минус" - комбинация 11.
Правила сложения для модифицированных кодов те же, что и для обычных. Единица переноса из старшего знакового разряда в модифицированном дополнительном коде отбрасывается, а в модифицированном обратном коде передается в младший цифровой разряд.
Признаком переполнения служит появление в знаковом разряде суммы комбинации 01 при сложении положительных чисел (положительное переполнение) или 10 при сложении отрицательных чисел (отрицательное переполнение). Старший знаковый разряд в этих случаях содержит истинное значение знака суммы, а младший является старшей значащей цифрой числа. Для коррекции переполнения число нужно сдвинуть в разрядной сетке на один разряд вправо, а в освободившийся старший знаковый разряд поместить цифру, равную новому значению младшего знакового разряда. После корректировки переполнения мантиссы результата необходимо увеличить на единицу порядок результата.
Система вещественных чисел, применяемая при ручных вычислениях, предполагается бесконечной и непрерывной, т.е. не существует никаких ограничений на диапазон используемых чисел и точность их представления.
Однако в компьютерах реализация такой системы на аппаратном уровне была бы нецелесообразной, хотя программно может быть реализована любая точность вычислений. Нецелесообразность аппаратной реализации вычислений с произвольной точностью вызвана тем, что такие вычисления требуют неоправданно большого расхода основных машинных ресурсов: памяти и процессорного времени.
Во всех компьютерах размеры регистров и ячеек памяти фиксированы, что ограничивает систему представления чисел. Ограничения касаются как диапазона, так и точности представления чисел, т.е. система машинных чисел оказывается конечной и дискретной.
В любой универсальной ЭВМ существует несколько различных форматов представления как для чисел с фиксированной, так и для чисел с плавающей запятой. На некоторые из форматов имеются международные стандарты, и поэтому такие форматы являются общими для ЭВМ, построенных различными фирмами на различной элементной базе. Следует отметить, что нестандартные форматы обычно являются неявно специализированными для определенных областей применения, причем разработчики аппаратуры могут не указать в документации, для чего был предназначен тот или иной формат.
С точки зрения программиста важно, какие из форматов данных обрабатываются аппаратными средствами данной ЭВМ, а какие - только программными средствами. Операции над данными любого формата, который не поддерживается аппаратурой, выполняются очень медленно. Любой формат данных, который превышает размер регистров процессора, не пригоден для быстрых вычислений.
Для представления целых чисел в ЭВМ обычно применяются 8-, 16-, 32- и 64-битовый стандартные форматы, причем интерпретация чисел как знаковых или беззнаковых обычно возлагается на программиста или на компилятор с языка высокого уровня.
Для представления чисел с плавающей запятой также существует несколько стандартных форматов, различающихся по точности, но имеющих одинаковую структуру следующего вида:
n-1 n-2 0
┌───╥───┬───┬─────┬───╥───┬───┬─────┬───┐
│ ║ │ │ ... │ ║ │ │ ... │ │
└───╨───┴───┴─────┴───╨───┴───┴─────┴───┘
│ └────────╥────────┘└────────╥───────┘
│ смещенный модуль
знак порядок мантиссы
мантиссы
Порядок p задается в так называемой смещенной форме: если для задания порядка выделено k разрядов, то к истинному значению порядка прибавляют смещение, равное (2k-1-1). Использование смещенной формы позволяет производить операции над порядками, как над беззнаковыми числами, что упрощает операции сравнения, сложения и вычитания порядков. Кроме того, использование смещенного порядка упрощает операцию сравнения нормализованных чисел с плавающей запятой, сводя ее к операции сравнения целых чисел.
Следует отметить, что вещественный формат с m-разрядной мантиссой позволяет абсолютно точно представлять m-разрядные целые числа, т.е. любое двоичное целое число, содержащее не более m разрядов, может быть без искажений преобразовано в вещественный формат.
ОСНОВНЫЕ КОМПОЗИЦИИ ДЕЙСТВИЙ И ИХ ПРАВИЛА ВЫВОДА
1. СООТНОШЕНИЯ ДЛЯ КОРРЕКТНОСТИ ПРОГРАММ
Каждый алгоритм имеет как статическую, так и динамическую структуры. Статическая структура представляется текстом (или структурной схемой) программы, описывающим действия и проверки, которые должны быть выполнены при решении данной задачи. Текст не зависит от значений исходных данных. Напротив, динамическая структура в значительной степени определяется выбором исходных данных, поскольку при выполнении алгоритма будут сделаны различные переходы в зависимости от значений входных переменных. Динамическая структура отражает процесс вычислений и состоит из последовательности состояний вычислений.
Состояние вычислений в любой момент времени включает в себя значения всех программных переменных в этот момент и, таким образом, зависит от начальных значений переменных и этапов вычислений алгоритма, которые ему предшествовали. Текущая инструкция или изменяет состояние вычисле-
Рис. 1. Алгоритм для нахождения q и r-, удовлетворяющих условиям x=q*y+r и 0 <= г < y. Таким образом, на выходе q = х div y и r=х mod y.
ний (значения некоторых переменных) и передает управление следующей инструкции в последовательности, или производит проверку состояния вычислений (сравнивает значения определенных переменных) и на основе результата этой проверки передает управление другой инструкции.
Язык программирования предоставляет как простые операторы, так и методы композиции, которые позволяют формировать структурные операторы из других простых или составных операторов. Перед нами стоят две связанные между собой задачи.
Определить виды используемых в языке Паскаль простых операторов, а также часто применяемые методы композиции решений подзадач.
2. Обеспечить правила вывода, позволяющие определить эффект воздействия простого оператора на состояние вычисления, а также вывести определенные свойства составного оператора из свойств составляющих его компонент.
Рассмотрим рис. 1, который воспроизводит алгоритм для определения х div у и х mod у. Заметим, что состояние вычислений, связанное с точкой входа, определяется значениями входных переменных х и у; но после выполнения первых двух операторов состояние вычислений расширяется, включая значения четырех переменных: х, у, q и г. (Значения х и у могут быть различными
в зависимости от применения алгоритма, но остаются постоянными в течение одного применения). Ясно, что следующая за проверкой r >= у передача управления будет зависеть от текущего состояния вычислений.
Фундаментальное свойство всех видов композиции, которые мы будем рассматривать, заключается в том, что они дают возможность объединить в одну сложную структурную схему с одним входом и одним выходом одну или более схем также с одним входом и одним выходом. Как показано на рис. 1, наша процедура проектирования объединяет с этими точками некоторые соотношения, которые описывают существенные аспекты состояний вычислений в этих точках. Каждая такая структурная схема имеет вид, приведенный на рис. 2А, где S может быть отдельным действием ЭВМ или сложной схемой. Чтобы выразить ее в более краткой форме, используем нотацию:
{Р} S {Q}. (1)
Это - спецификация программы со следующим смыслом: если соотношение Р истинно перед выполнением S, то Q будет истинно после завершения выполнения S. Другими словами, если Р истинно при входе, то Q будет истинно при выходе.
Если S — программа, чью корректность мы хотим установить, то нотация (1) в том смысле, как мы ее определили, — это то, что мы хотим доказать, причем Р — соотношение, которому должны удовлетворять начальные значения переменных, а Q — соотношение, которому должны удовлетворять конечные значения переменных. Например, если S - алгоритм, изображенный на рис. 1, то соотношение, которое мы хотим доказать, таково:
{(х >= 0)^(y > 0)} S {(х = q *у + r)^(0<= r < у)}, (2)
где знак ^ используется в качестве формальной нотации для "и".
Как уже отмечалось, соотношение {Р} S {Q} означает, что если P истинно перед выполнением S, то Q должно быть истинно при завершении S. Это означает, что {Р} S {Q} тождественно истинно, если S не завершается, т. е. если на рис. 2А точка выхода никогда не достигается. Другими словами, (1) определяет только частичную корректность S. Частично корректной является такая программа, в которой гарантируется получение требуемого результата при условии ее завершения. Но завершается ли программа действительно для некоторых исходных значений — это другой вопрос. Если дополнительно можно показать, что программа завершается для всех исходных значений, удовлетворяющих соотношению Р, то говорим, что программа полностью корректна. Чтобы доказать завершение программы, получаемой применением правил композиции, введенных ранее, необходим анализ циклов, т.е. операторов итерации.
Можно подвести итог нашему подходу к проектированию программ.
1. Проектирование должно начинаться со спецификации {Р} S {Q}, которой должна удовлетворять проектируемая нами программа. Мы начинаем, таким образом, .с ясного и недвусмысленного определения того, когда программа должна использоваться (предусловие Р), и результата ее использования при этом (постусловие Q).
2. Процесс проектирования сверху вниз определяет спецификации [Рi} Si {Qi} для компонентов Si, из которых строится программа.
3. Проектирование программы осуществляется одновременно с доказательством корректности указанных спецификаций.
2.3. ПРАВИЛА ВЫВОДА ДЛЯ ПРОСТЫХ ОПЕРАТОРОВ
Правила вывода - это схемы рассуждений, позволяющие доказывать свойства программ. Правила вывода имеют вид
Н1,…,Hn (,2.26)
H
Если H1, . . . , Hn, - истинные утверждения, то Н - также истинное утверждение.
Два простейших правила вывода формулируются в (2.27) и (2.30). Первое утверждает, что если выполнение программы S обеспечивает истинность утверждения R, то оно также обеспечивает истинность каждого утверждения, которое следует из R, т. е.
[P}S{R}, R Q
{P}S{Q}
Например, из
{(х > 0)^(у > 0)} S{(z+u *у = х *у)^(и = 0)}, (2.28)
(z+u*y=x*y)^(u=0)(z=x*y) (2.29)
заключаем, используя (2.27), что {(х > 0) ^ (у > Q)} S {z = х * у].
Второе правило утверждает, что если R - известное предусловие программы S, приводящей к результату Q после завершения своего выполнения, то это же относится к любому другому утверждению, из которого следует R:
PR, [R}S{Q}
{P}S{Q}
1 2 3 4 5 6 7