Обратный и дополнительный коды двоичных чисел
Пример перевода
x1=10101-[x1]пр=010101
x2=-11101-[x2]пр=111101
x3=0,101-[x3]пр=0,101
x4=-0,111-[x4]пр=1,111
2) Обратный код числа, используется для выполнения арифметических операций вычитания, умножения, деления, через сложение. Обратный код положительного числа совпадает с его прямым кодом, обратный код отрицательного числа формируется по правилам: в знаковом разряде записывается “1”; цифровые значения меняются на противоположные.
3) Дополнительный код числа, имеет такое же назначение, как и обратный код числа. Формируется по следующим правилам: положительные числа в дополнительном коде выглядят также как и в обратном и в прямом коде, т.е. не изменяются. Отрицательные числа кодируются следующим образом: к обратному коду отрицательного числа (к младшему разряду) добавляется 1, по правилу двоичной арифметики.
Пример перевода
x1=10101-[x1]доп=010101
x2=-11101-[x2]обр=100010+1-[x2]доп=100011
x3=0,101-[x3]доп=0,101
x4=-0,111-[x4]обр=1,000+1-[x4]доп=1,001
Для выявления ошибок при выполнении арифметических операций используются также модифицированные коды: модифицированный прямой; модифицированный обратный; модифицированный дополнительный, для которых под код знака числа отводится два разряда, т.е. “+”=00; ”-”=11. Если в результате выполнения операции в знаковом разряде появляется комбинация 10 или 01 то для машины это признак ошибки, если 00 или 11 то результат верный.
Представление чисел в двоичном коде с плавающей запятой
Часто приходится обрабатывать очень большие числа (например, расстояние между звёздами) или наоборот очень маленькие числа (например, размеры атомов или электронов). При таких вычислениях пришлось бы использовать числа с очень большой разрядностью. В то же время нам не нужно знать расстояние между звёздами с точностью до миллиметра. Для вычислений с такими величинами числа с фиксированной запятой неэффективны.
В десятичной арифметике для записи таких чисел используется алгебраическая форма. При этом число записывается в виде мантиссы, умноженной на 10 в степени, отображающей порядок числа, Например:
Для записи двоичных чисел тоже используется такая форма записи. Она позволяет работать с числами с большим диапазоном значений Эта форма записи называется запись числа с плавающей точкой. Напомним, что мантисса не может быть больше единицы и после запятой в мантиссе не можетзаписываться ноль.
Для записи числа в формате с плавающей запятой одинарной точности требуется тридцатидвухбитовое слово. Для записи чисел с двойной точностью требуется шестидесятичетырёхбитовое слово. Чаще всего числа хранятся в нескольких соседних ячейках памяти процессора. Форматы числа в формате с плавающей запятой одинарной точности и числа в формате с плавающей запятой удвоенной точности приведены на рисунке
Рисунок 1. Форматы числа с плавающей запятой
На рисунке буквой S обозначен знак числа, 0 — это положительное число, 1 — отрицательное число.
Группа бит, обозначенная e предназначена для записи смещённого порядка числа. Смещение потребовалось, чтобы не вводить в двоичный код числа с плавающей запятой еще один знак. Смещённый порядок всегда является положительным числом. В двоичном коде одинарной точности float для записи порядка числа выделено восемь бит. Для него смещение порядка числа принято 127. Для смещённого порядка в двоичном коде числа с плавающей запятой двойной точности double отводится 11 бит. В нем смещение порядка числа составляет — 1023.
В десятичной мантиссе после запятой могут присутствовать цифры 1. 9, а в двоичной — только 1. Поэтому для хранения единицы после двоичной запятой не выделяется отдельный бит в числе с плавающей запятой. Единица подразумевается, как и двоичная запятая. Кроме того, в формате чисел с плавающей запятой принято, что мантисса всегда больше 1. То есть диапазон значений мантиссы лежит в диапазоне от 1 до 2.
Рассмотрим несколько примеров:
1) Определить число с плавающей запятой, лежащее в четырёх соседних байтах:
11000001 01001000 00000000 00000000
— Знаковый бит, равный 1 показывает, что число отрицательное.
— Экспонента 10000010 в десятичном виде соответствует числу 130. Вычтя число 127 из 130, получим число 3.
— Теперь запишем мантиссу: 1,100 1000 0000 0000 0000 0000
— И, наконец, определим десятичное число: 1100,1b = 12,5d
2) Определить число с плавающей запятой, лежащее в четырёх соседних байтах:
11000011 00110100 00000000 00000000
— Знаковый бит, равный 1 показывает, что число отрицательное.
— Экспонента 10000110 в десятичном виде соответствует числу 134. Вычтя число 127 из 134, получим число 7.
— Теперь запишем мантиссу: 1,011 0100 0000 0000 0000 0000
— И, наконец, определим десятичное число: 10110100b=180d
Для того чтобы записать ноль, в двоичном представлении числа с плавающей запятой достаточно записать в смещенный порядок число 00000000b. Значение мантиссы при этом не имеет значения. Число, в котором все байты равны 0, тоже попадает в этот диапазон значений.
Бесконечность в числе с плавающей запятой соответствует смещенному порядку 11111111b и мантиссе, равной 1,0. При этом существует минус бесконечность и плюс бесконечность (переполнение и антипереполнение), которые часто отображаются на экран монитора компьютера или дисплей микропроцессорного устройства как +INF и -INF.
Все остальные комбинации битов мантиссы числа с плавающей запятой (в том числе и все единицы) при смещенном порядке 11111111b воспринимаются языками программирования как не числа и отображаются на экран: NaN.
Понравился материал? Поделись с друзьями!
Другие виды двоичных кодов:
Целочисленные двоичные коды Представление двоичных чисел в памяти компьютера или микроконтроллера
https://digteh.ru/proc/IntCod.php
Двоично-десятичный код Иногда бывает удобно хранить числа в памяти процессора в десятичном виде
https://digteh.ru/proc/DecCod.php
Запись текстов двоичным кодом Представление текстов в памяти компьютеров и микроконтроллеров
https://digteh.ru/proc/text.php
Системы счисления В настоящее время и в технике и в быту широко используются как позиционные, так и непозиционные системы счисления.
https://digteh.ru/digital/SysSchis.php
Предыдущие версии сайта:
http://neic.nsk.su/
Об авторе:
к.т.н., доц., Александр Владимирович Микушин
Кандидат технических наук, доцент кафедры САПР СибГУТИ. Выпускник факультета радиосвязи и радиовещания (1982) Новосибирского электротехнического института связи (НЭИС).
А.В.Микушин длительное время проработал ведущим инженером в научно исследовательском секторе НЭИС, конструкторско технологическом центре «Сигнал», Научно производственной фирме «Булат». В процессе этой деятельности он внёс вклад в разработку систем радионавигации, радиосвязи и транкинговой связи.
Научные исследования внедрены в аппаратуре радинавигационной системы Loran-C, комплексов мобильной и транкинговой связи «Сигнал-201», авиационной системы передачи данных «Орлан-СТД», отечественном развитии системы SmarTrunkII и радиостанций специального назначения.
Фатальные ошибки двоичной арифметики при работе с числами с плавающей точкой
Среди всего разнообразия форматов представления действительных чисел в компьютерной технике особое место отведено формату чисел с плавающей точкой (ЧПТ), который запротоколирован в стандарте IEEE754. Главные достоинства чисел с плавающей точкой, как известно, заключаются в том, что они позволяют производить вычисления в большом диапазоне значений и при этом вычисления организуются инструментарием двоичной арифметики, легко реализуемой на вычислительном устройстве. Однако последнее обстоятельство таит в себе подводные камни, которые являются причиной того, что расчеты, сделанные с использованием этого формата, могут приводить к совершенно непредвиденным результатам.
Ниже мы приводим примеры арифметических операций над некоторыми числами с плавающей точкой, которые приводят к неверным результатам. Эти результаты не зависят от платформы, на которой реализованы вычисления.
В настоящей статье мы не приводим теоретических выкладок, которые объясняют причину появления этих ошибок. Это тема следующего топика. Здесь мы только постараемся привлечь внимание специалистов к проблеме катастрофической неточности вычислений, возникающей при проведении арифметических операций над десятичными числами при использовании двоичной арифметики. Рассматриваемые здесь примеры неумолимо наталкивают на мысль о целесообразности использования формата с плавающей точкой в том виде, как его трактует стандарт IEEE754.
Отметим, что причина ошибочных вычислений с ЧПТ, главным образом, обусловлена ни ошибками округления, устранению которых в стандарте уделяется большое внимание, а самой природой конвертации десятичных и двоичных чисел.
Будем рассматривать два основных формата для ЧПТ — float и double. Напомним, что формат float позволяет представлять до 7 верных десятичных цифр в двоичной мантиссе, содержащей 24 разряда. Формат double представляетдо 15 верных десятичных цифр в мантиссе, содержащей 53 двоичных разряда.
Непредставимые в двоичном машинном слове десятичные числа, после приведения их к десятичному виду, содержат как верные цифры так и «хвосты» из неверных цифр. Эти «хвосты» и являются источником ошибочных вычислений десятичных действительных ЧПТ с помощью двоичной арифметики. Покажем это на примерах.
СУММА
Итак, сначала рассмотрим сумму двух следующих действительных чисел, представленных в формате float, каждое из которых имеет по 7 верных значащих цифр:
0,6000006 + 0,03339874=0,6333993 4≈0,6333993
Все вычисления будем проводить в формате float. Для наглядности будем использовать числа в распакованном виде. Представим наши десятичные числа в нормализованном двоичном виде:
0.6000006 ≈ 1.001100110011001101001*2^(-1)
0.03339874≈1.00010001100110100011110*2^(-5)
Если полученные двоичные коды наших чисел опять представить в десятичном виде, то получим следующие значения:
0.6000006 ≈ 0.6000006 198883056640625≈0.6000006 2
0.03339874≈0.03339873 9993572235107421875≈0.0333987 4
Здесь каждое число, округленное до 7 верных цифр мы отделили от «хвоста» пробелом. Эти «хвосты» получились в результате обратной конвертации чисел из двоичного кода, записанного в машинной мантиссе, в десятичный код.
Сумма наших чисел в двоичном 24-х разрядном виде даст следующий результат:
1.001100110011001101001*2^(-1) + 1.00010001100110100011110*2^(-5)≈ 1.0100010001001100111011*2^(-1) ≈0,6333994
Тот же результат будет получен, если просуммировать десятичные числа с «хвостами»:
0,6000006 2+ 0,0333987 4= 0,6333993 6≈ 0,6333994
Как мы видим, после округления до 7 значащих цифр, здесь получен результат, отличный от того, который получился при суммировании десятичных чисел на калькуляторе. Правила округления двоичного представления чисел, заложенные в стандарте IEEE754, не решают проблему точного вычисления, рассмотренных здесь чисел. В нашем случае причина ошибки кроется в сочетании цифр, стоящих после последних верных цифр десятичных слагаемых, о которых, априори, ничего не известно.
Приведем еще один пример сложения. Просуммируем на калькуляторе два следующих действительных числа, каждый из которых содержит по 7 верных десятичных значащих цифр:
Приведем наши десятичные слагаемые к двоичному нормализованному виду:
6543.455=1.10011000111101110100100*2^12=6543.455 078
12.3454810 = 1.10001011000011100010110*2^3 ≈ 12.345 48
Сумма этих слагаемых в двоичном виде даст следующее двоичное число:
Здесь мы снова получили результат, отличающийся от того, который вычислен на калькуляторе для неконвертированных десятичных чисел.
УМНОЖЕНИЕ
Такая же проблема неточных вычислений возникает при нахождении произведения некоторых ЧПТ, представленных в двоичном коде в формате float. Для примера рассмотрим произведение следующих действительных чисел:
Представим в этом выражении сомножители в нормализованном двоичном виде:
Результатом перемножения наших чисел в двоичном виде будет число:
1.00001100000001010001101*2^(-4) × 1.0001011*2^10 = 1001.00011000011011000101 ≈9.095403
Мы получили ошибку в младшем разряде произведения, которую невозможно исправить путем округления числа, представленного в двоичном коде. Такие ошибки принято называть фатальными.
ДЕЛЕНИЕ
Аналогично умножению, операция деления в формате float для некоторых ЧПТ также приводит к фатальным ошибкам. Рассмотрим следующий пример:
Представим делимое и делитель в двоичном формате, в нормализованном виде:
13110 = 1.0000011*2^7
0.066= 1.00001110010101100000010*2^(-4)
Частное от деления наших чисел будет следующим:
1.0000011*2^7/1.00001110010101100000010*2^(-4)=
= 1.11110000001101100100111*2^10 = 1984.848 5107421875≈1984.849
Мы видим, что полученный здесь результат не соответствует правильному значению, вычисленному на калькуляторе или вручную.
ВЫЧИТАНИЕ
Вычитание — это та операция, которая полностью дискредитирует идею использования двоичной арифметики для вычисления десятичных значений ЧПТ. В результате этой операции, в некоторых случаях, можно получить результат даже близко не соответствующий действительности. Продемонстрируем это на примере.
Пусть уменьшаемое у нас будет равно 105.3256. Вычтем из него число 105.32. Разность этих чисел, вычисленная вручную, будет равна:
Представим десятичное уменьшаемое и десятичное вычитаемое в нормализованном двоичном виде:
105.3256 = 1.10100101010011010110101*2^6≈105.3255 997 041015625
105.32= 1.10100101010001111010111*2^6≈105.32
Найдем разность этих чисел в двоичном виде:
После преобразования этого числа в десятичный вид получим:
Мы получили результат, существенно отличающийся от того, который ожидали.
ОШИБКИ В ФОРМАТЕ ДАБЛ
Ситуацию с фатальными ошибками не спасает и формат более высокой точности, например double. Как мы выше уже отмечали, это объясняется самой природой конвертации чисел из одной системы счисления в другую. Покажем это на примерах.
В качестве инструмента для проверки правильности наших рассуждений будем использовать Excel 2009, в котором реализованы вычисления в строгом соответствии со спецификацией стандарта IEEE754.
Проведем следующие вычисления, используя средства Excel 2009. Формат ячеек выберем числовой, с 18 знаками после запятой. Для нахождения суммы запишем в ячейки таблицы Excel следующие числа:
В ячейке А3Excel получим сумму этих чисел:
Если посчитать эту сумму вручную или на калькуляторе, то получится число:
Которое в младшем разряде не совпадает с тем, что получено в Excel.
Посмотрим, к чему приводит операция вычитания в Excel. Запишем в ячейки следующие числа:
В ячейке А3 найдем разность этих чисел. Она будет равна:
А мы ожидали получить число:
В заключении приведем пример того, как быстро может расти ошибка, если использовать двоичную арифметику для вычисления десятичных действительных чисел даже без операции вычитания.
Запишем в ячейки таблицы Excel следующие числа:
А1= 0,500000000660006
А2 = 0,0000213456548763
А3 = 0,00002334565487363
А4 = 0,000013345654873263
В ячейке А6 запишем формулу =A1/5+A2. После чего в ней будет получен результат.
В ячейке A7 произведем следующие вычисления:
Проведем те же вычисления на калькуляторе. Вычисления будем производить с точностью до 15 десятичных значащих цифр. Цифры, которые стоят правее младшего значащего разряда, согласно правилам арифметики, будем округлять до ближайшего целого. В результате будем иметь:
A1/5=0,500000000660006/5=0,100000000132001 2≈0,100000000132001
A1/5+A2=0,100000000132001+0,0000213456548763≈ 0,100021345786877
( A1/5+A2)/3=0,100021345786877/3≈0,0333404485956257
( A1/5+A2)/3+A3=0,0333404485956257+0,00002334565487363≈ 0,0333637942504993
[( A1/5+A2)/3+A3]/4=0,0333637942504993/4≈0,00834094856262483
[( A1/5+A2)/3+A3]/4+A4=0,00834094856262483+0,000013345654873263=0,00835429421749809
Представление вещественных чисел в двоичной системе счисления с плавающей запятой.
При представлении вещественных чисел в любой системе счисления используют запись с плавающей точкой. Любое число в любой системе счисления можно предстваит в виде:
,
Q – основание системы счисления;
Например в десятичной системе счисления число 3,14 можно представить в виде:
Здесь мантисса равна 0,314, а порядок равен 1.
Такое представление чисел далеко не однозначно. Число 3,14 можно представить как:
3,14=3,14*10 0 =0,314*10 1 =0,0314*10 2 =…
Порядок числа определяет положение запятой и записи мантиссы. При изменении порядка соответствующим образом меняется положение запятой. Запятая как бы «плавает». Это изменение запятой и дало название способу представления чисел.
Число с плавающей точкой представляется неоднозначно. Одно из этих представлений называется нормализованным. В этом случае для десятичной системы счисления мантисса должна удовлетворять требованию:
Другими словами, первая цифра мантиссы после запятой должна быть отличной нуля. Для числа 3,14 представление в нормализованной форме будет иметь следующий вид:
Точно также в любой системе счисления с основанием Q число a неравное нулю записывается в форме с плавающей точкой. Число a называется нормализованным, если выполняется условие:
Пример 1.
Пример 1.
Сначала переводим целую часть B(10)=43
Затем дробную C(10)=97
Теперь приводим число к нормализованному виду. Для этого сдвигаем запятую на шесть разрядов 6(10)= 110(2).
Получили мантиссу равную 0,1010111100001 и порядок равный 110.
Арифметические операции в системах счисления используемых вычислительной техникой.
Все правила вычислений любой позиционной системы счисления совпадают с правилами десятичной системы счисления.
Арифметические операции с целыми числами в двоичной системе счисления.
Как и в десятичной системе счисления, все арифметические операции с целыми числами в двоичной системе счисления основаны на таблице сложения и умножения, приведенных в таблицах 6 и 7.
| Таблица 6. Сложение двоичных чисел | Таблица 7. Умножение двоичных чисел |
Пример 1.
Пример 2.
| *1010 |
| +1101 +0000 +1101 |
В двоичной системе счисления частичные произведения (произведения множимого на числа разрядов множителя) либо равны множимому, если значение разряда множителя равно единицы, либо равны нулю, если значение разряда множителя равно нулю.
Вычитание и деление в двоичной системе счисления производиться аналогично десятичной системе счисление. Вычитание – это сложение с обратным знаком, а деления – это умножение на обратное значение числа.
Арифметические операции с целыми числами в восьмеричной и шестнадцатеричной системах счисления.
Как и в десятичной или двоичной системах счисления все арифметические операции с целыми числами в восьмеричной или шестнадцатеричной системах счисления основаны на таблицах сложения и умножения. Таблицы сложения и умножения в восьмеричной и шестнадцатеричной системах счисления приведены в таблицах 8, 9, 10 и 11.
Таблица сложения целых чисел в восьмеричной системе счисления.
Таблица умножения целых чисел в восьмеричной системе счисления.
Таблица сложения целых чисел в шестнадцатеричной системе счисления.
| A | B | C | D | E | F | |
| A | B | C | D | E | F | |
| A | B | C | D | E | F | |
| A | B | C | D | E | F | |
| A | B | C | D | E | F | |
| A | B | C | D | E | F | |
| A | B | C | D | E | F | |
| A | B | C | D | E | F | |
| A | B | C | D | E | F | |
| A | B | C | D | E | F | |
| A | B | C | D | E | F | |
| A | A | B | C | D | E | F |
| B | B | C | D | E | F | 1A |
| C | C | D | E | F | 1A | 1B |
| D | D | E | F | 1A | 1B | 1C |
| E | E | F | 1A | 1B | 1C | 1D |
| F | F | 1A | 1B | 1C | 1D | 1E |
Таблица сложения целых чисел в шестнадцатеричной системе счисления.
| A | B | C | D | E | F | ||||||
| A | B | C | D | E | F | ||||||
| A | C | E | 1A | 1C | 1E | ||||||
| B | F | 1B | 1E | 2A | 2D | ||||||
| B | 1C | 2C | 3C | ||||||||
| A | F | 1E | 2D | 3C | 4B | ||||||
| C | 1E | 2A | 3C | 4E | 5A | ||||||
| E | 1C | 2A | 3F | 4D | 5B | ||||||
| 1B | 2D | 3F | 5` | 5A | 6C | 7E | |||||
| A | A | 1E | 3C | 5A | 6E | 8C | |||||
| B | B | 2C | 4D | 6E | 8F | 9A | A5 | ||||
| C | C | 3C | 6C | 9C | A8 | B4 | |||||
| D | D | 1A | 4E | 5B | 8F | 9C | A9 | B6 | C3 | ||
| E | E | 1C | 2A | 7E | 8C | 9A | A8 | B6 | C4 | D2 | |
| F | F | 1E | 2D | 3C | 4B | 5A | A5 | B4 | C3 | D2 | E1 |
Арифметические операции с вещественными числами в двоичной системе счисления.
Арифметические операции с вещественными числами в двоичной системе счисления аналогичны операциям в десятичной системе счисления. Рассмотрим процесс выполнения действий на примерах.
Пример 1.
Дано A(2)=10011,01. B(2)=1,0101 представленные в форме записи с фиксированной запятой. Найти C(2)= A(2)+B(2).
Выравниваем количество знаков после запятой: A(2)=10011,0100. B(2)=1,0101
Выполняем операцию сложения
| 10011,0100 +1,0101 |
| 10100,1001 |
Пример 2.
Выравниваем порядки чисел:
Для этого выравниваем количество знаков после запятой: A(2)=0,100110100, B(2)= 0,000010101
Выполняем операцию сложения мантисс чисел представленных в двоичной системе счисления так же как и в случае представления чисел в форме записи с фиксированной запятой
| 0,100110100 +0,000010101 |
| 0,101001001 |
В результате сложения мантисс получили результат: 0,101001001. Дописываем показатель и получаем ответ.
Операции умножения вычитания и деления производятся по аналогичному алгоритму.
Логические операции.
В информатике под понятием логическим операции понимают результат сравнения по какому либо правилу заданных величин и выдачу ответа имеющего всего два значения истина и лож. Вся работа любой вычислительной техники основана на выполнении логически операций и операций переноса. Правила, определяющие результат выполнения логической операции, то есть результаты, которые получаться в результате выполнения функции с конкретными исходными данными называются таблицами истинности.
Существует три основных закона логического сравнения величин это И(and), ИЛИ(or) и НЕ(not). Схематическое представление элементов выполняющих логические операции и соответствующие им таблицы истинности представлено в таблице 12.
Таблица 12. Описание логических элементов вычислительной техники.
| Операция | Элемент | Таблица истинности | ||
| Логическое произведение (конъюнкция). Операция «И». Результат логической суммы совпадает с результатом арифметического произведения. Результат будет равен истина, только в случае, если оба аргумента равны единице. |  | A | B | A И Б |
| Логическая сумма (дизъюнкция). Операция «ИЛИ». Результат логической суммы, отличается от результата суммы двух одноразрядных двоичных чисел. Результатом будет истина, если хотя бы один входной аргумент равен единице. |  | A | B | A ИЛИ B |
| Логическое отрицание(инверсия). Операция «НЕ» Результатом логической операции отрицание будет изменение значения входного аргумента: истина на лож и обратно. |  | A | НЕ A |
Этих трех элементов логических функций и операций переноса(сдвига) достаточно, для тог, чтобы организовать любую операцию арифметического вычисления или сравнения чисел в двоичной системе счисления.
Пример 1.
Дано A(10)=123. Умножить число с помощью операции сдвига на 100(10).
100=10 2 следовательно для умножения заданного числа на 100 необходимо выполнить сдвиг на два разряда в лево
Пример 3.
Дано A(2)=11010. Умножить число с помощью операции сдвига на 100(2).
100=2 2 следовательно для умножения заданного числа на 100 необходимо выполнить сдвиг на два разряда в лево
Поскольку двоичная система счисления состоит всего из двух чисел <0,1>принято считать, что 0(2) в логических функциях представляет собой лож, а 1(2) истину. Исходя из этого при помощи логических элементов можно организовать любой вычислительный процесс. Рассмотрим процесс сложения двоичных чисел на примере двухразрядного сумматора рисунок 9.
Для понимания принципа использования логических функций построим таблицу истинности получающуюся при выполнении процесса сложения для всех элементов таблица 13.
Таблица 13. Процессы происходящие в двухразрядном сумматоре.
| X | Y | (не X) | (не Y) | (Y и 1) | (X и 2) | (XиY) | (3или4) | S | P |
На схеме приведенной на рисунке 10 на вход сумматора поступает два одноразрядных числа записанных в двоичной системе счисления. На выходу получаем одно двухразрядное число представляющее собой сумму одноразрядных чисел записанных на входе. Преобразуем таблицу 13 в таблицу истинности для сложения одноразрядных чисел, записанных в двоичной системе счислении, таблица 14.
Результат работы сумматора, основанного на выполнении логических операций.
В результате получили таблицу истинности, аналогичную таблице выполнения операции сложения в двоичной системе счисления таблица 6.
Аналогичным образом организованы и другие математические операции в устройствах вычислительной техники.
Введение в алгоритмизацию.
Понятие алгоритма.
В повседневной жизни, для достижения какой либо цели нам постоянно приходиться сталкиваться с различными правилами, определяющими последовательность действий. Подобные правила очень многочисленны. Например, для того, чтобы позвонить по телефону –автомату нежно выполнить определенную последовательность действий (опустить монету, снять трубку, набрать номер), вычислить результат какой либо функции или решить уравнение. Правила такого рода встречаются нам на каждом шагу, такие правила называют алгоритмами.
Решение любой задачи из любой области в основном представляет собой нахождение правил, то есть последовательности решения, или по другому алгоритма.
Первым свойством алгоритма, является то, что он носит пошаговый(дискретный) характер определяемого им процесса.
Вторым свойством алгоритма является массовость, то есть существует некоторое множество объектов, которые могут служить исходными данными для рассматриваемого алгоритма. Например, для алгоритмов выполнения арифметических операций – сложения, вычитания умножения и деления, такими данными являются все действительные числа.
Например, для того, чтобы сложить два числа 15 и 17 используется алгоритм сложения в столбик.
Суть этого алгоритма заключается в поразрядном сложении всех разрядов чисел, а если в результате сумм разрядов получается числа большее 9, то старший разряд полученной суммы переноситься в следующий разряд числа. Если записать последовательность действий, которые мы выполняем при сложении двух то это и будет алгоритм выполнения операции сложения:
Попробуем проделать операцию сложения тех же чисел (15 и 17) по представленному алгоритму:
Заметим, что алгоритм сложения является одним и тем же для любой пары чисел, что и определяет его массовость.
Аналогичным образом можно составить алгоритм умножения, деления, вычитания и так далее.
Третьим свойством алгоритма, является то, что алгоритм должен быть понятен для исполнителя, то есть исполнитель знает как его выполнять. При этом исполнитель алгоритма выполняет «механически». Очевидно, что формулировка алгоритма должна восприниматься однозначно, а следовательно должна быть на столько точна, чтобы полностью определять все действия исполнителя.
Если применять один и тот же алгоритм к одним и тем же исходным данным, то мы всегда должны получать один и тот же результат. Например сколько бы раз мы не складывали числа «15» и «17», всегда будем получать один и тот же результат «32». И если при этом сравнивать результаты на каждом шаге выполнения алгоритма, то они так же будут идентичны. Таким образом можно говорить об однозначности алгоритмов.
Исходя из выше изложенного можно сформулировать определение алгоритма. Алгоритм – это система правил, сформулированная на языке понятном исполнителю и определяющая последовательность действий, в результате выполнения которых, исполнитель придет от исходных данных к конечному результату. Механический характер алгоритм, его определенность и однозначность позволяют в качестве исполнителя использовать не только человек, но и устройства вычислительной техники. Нет разницы, кто является исполнителем, человек или устройства вычислительной техники. Алгоритм остается идентичным, различен лишь язык, на котором формулируются правила.
Последовательность действий, алгоритма называется алгоритмическим процессом, а каждое действие шагом. Число шагов, для достижения результата обязательно должно быть конечно. Кроме того, алгоритм должен обладать свойствами массовости, определенности и однозначности.
Для любой задачи может как существовать несколько алгоритмов решения, так и не существовать ни одного. Так для подсчета количества зрителей на трибунах стадиона существует как минимум два алгоритма, первый это посчитать всех зрителей отдельно, а второй подсчитать количество зрителей в секторе и умножить на количество секторов. Или для поиска простого числа (числа, которое можно разделить нацело только на себя и на единицу) пока не существует алгоритма (если не учитывать перебор), и задача древности об удвоении куда (с помощью циркуля и линейки требуется построить куб, объем которого в два раза больше исходного объема куба), так же не существует алгоритма.
Существует три основных вида шагов алгоритмов это:
1. действие(процесс) – выполнение какой либо операции, например вычисление суммы a=15+17 или положить монету в телефон автомат или набрать номер телефона, эти операции называются шагами действия – требуется что либо сделать.
2. условие(развилка) – сравнение каких либо исходных данных и определение на основе результата сравнения дальнейших действий, например если после набора номера телефон, по которому вы звонили занят, то появляется шаг условия повторить или нет, если повторить, то следует повторно набрать номер, а если нет, то перестать звонить.
3. повтор(цикл) – повторение каких либо операций, до тех пор, пока не выполнится какое либо условие, например – набирать номер телефона до тех пор, пока не дозвонитесь.
Основным назначение блок-схем является однозначная передача информации от одного человека другому, то есть если цепочка от разработчик алгоритма до исполнителя имеет промежуточные звенья, например: алгоритм разрабатывает специалист в области математики, а исполнителем является устройство вычислительной техники, и при этом разработчик алгоритма(как чаще всего бывает), не знает языка, понятного данному устройству (поскольку элементы вычислительной техники достаточно разнообразны, они встречаются в компьютерах, телефонах, телевизорах, микроволновых печах и т.д., причем в основном каждое устройство говорит на своем языке), то для ввода алгоритма в это устройство используется специалист, переводящий математические формулы на язык устройства вычислительной техники(кодер) и для его однозначного понимания алгоритма и правильного перевода оптимальным представлением алгоритма является его графическое изображение, тое есть блок-схема. Основные элементы блок-схем приведены в таблице 15.
Основные элементы графического изображения алгоритма.
| Элемент | Назначение |
 | Начало алгоритма, говорит о том, что с этой точки начинается процесс решения какой-либо задачи. |
 | Завершение алгоритма, говорит о том, что в этой точке процесс решения задачи завершен. |
 | Ввод исходных данных, говорит о том, что здесь необходимо заменить символическое представление переменных, используемых в алгоритме, конкретными исходными данными. |
 | Вывод результатов, говорит о том, что здесь необходимо прочитать результаты работы алгоритма. |
 | Выполнение шага, говорит о том, что здесь необходимо выполнить какое либо действие предусмотренные в алгоритме на данном шаге. |
 | Условие, говорит о том, что дальнейшие шаги алгоритма определяются тем, что выполнится условие или нет. |
Алгоритмические системы.
При построении алгоритма решения какой либо задачи, предполагается, что известны виды объектов, которые будут являться исходными данными и виды объектов, которые будут являться результатами решения. Например, при делении отрезка пополам в качестве исходных данных будут выступать отрезки, длина которых при построении алгоритма не имеет ни какого значения, и в качестве результата решения, так же будут выступать отрезки, именно то, что это отрезки а не окружности и не квадраты мы будем учитывать при построении алгоритма. То есть при построении алгоритма данные должны быть типизированы, то есть отнесены к тому или иному классу объектов, при этом их свойства (размеры, цвет и т.д.) для нас не имеет никакого значения.
При построении алгоритма предполагается, что действия, с помощью которых строятся шаги алгоритма известны исполнителю. Например при делении отрезка с помощью циркуля и линейки мы определяем только действия с циркулем и линейкой, а при делении того же самого отрезка исходя из численного значения координат его концов, мы определяем действия с числами.
После построения алгоритма, мы должны определить правила для исполнителя, причем сформулировать их на понятном ему языке. Если это человек, то на языке понятном конкретному человеку, если это устройство вычислительной техники, то на языке, понятном именно этому устройству. С другой стороны, при определении правил выполнения алгоритма, следует учитывать возможности исполнителя. Так например для выполнения алгоритма деление отрезка пополам с помощью циркуля и линейки исполнитель должен обладать возможностью пользоваться обеими предметами, а при делении отрезка пополам с исходя из координат концов отрезка исполнитель должен иметь возможность выполнять арифметические операции. Следовательно при задании алгоритма исполнителю, следует учитывать его функциональные возможности.
Набор средств и правил(понятий), позволяющих строить множество алгоритмов для решения различных задач называется алгоритмической системой. Алгоритмическая система определяет:
Очень часто множество типов входных объектов (исходных данных) и множество типов результатов совпадают. Например, в алгоритмах математики исходные данные являются числа, и результатом тоже является число. В задачах управления, исходными данными так же являются числа, а результатом могут быть в полнее материальные объекты. Кроме того, результатом работы алгоритма, может оказаться информация, определяющая новую задачу.
Язык, на котором написаны правила алгоритмической системы определяется возможностями исполнителя и недолжен включать указания, которые неизвестны исполнителю, или могут восприняться им неоднозначно.
Если исполнителем алгоритма является человек, владеющий русским языком, то в качестве языка правил, описывающих алгоритм должен использоваться русский язык, а если устройства вычислительной техники, то необходимо использовать язык, понятный этим устройствам.
Еще одним параметром алгоритмической системы является требуемая точность конечного результата. Например, в алгоритмической системе предназначенной для обработки числовой информации, при определенных исходных данных на каком либо шаге может появиться необходимость деления единицы на тройку. Из арифметики известно, что результатом выполнения этой операции будет 0,33333…. То есть операцию деления единицы на тройку не возможно выполнить за конечное число шагов, возникает неопределенной или зацикливание процесса. Для того, чтобы избежать этой ситуации необходимо ввести параметр, определяющий требуемую точность, в данном случае количество знаков после запятой.
При вводе параметра, определяющего точность вычислений мы подразумеваем невозможность получения абсолютно точного результата, и кроме того, чем выше точность, тем сложней будут вычисления, кроме того, при достижении высокой степени точности резко возрастает число операций. И если мы знаем, что алгоритм решения конкретной задачи не единственный, то есть задачу можно решить другим способом, то следует попытаться улучшить(оптимизировать) алгоритм решения задачи, упростить ход решения. Однако при этом новый алгоритм должен оставаться эквивалентным исходному.
Один алгоритм является эквивалентным другому, если:
1. Множество допустимых исходных данных одного алгоритма является множеством допустимых исходных данных другого алгоритма, из возможности применения к каким либо исходным данным одного алгоритма следует возможность применения к этим же исходным данным другого алгоритма;
2. Применение к одним и те же исходным данным одного алгоритма дает то же самый результат, что и применение к этим же исходным данным другого алгоритма.
Эквивалентны, например алгоритмы подсчета зрителей на трибунах стадиона, по секторам и по рядам трибун.
И так, алгоритмическая система это набор типов исходных и результирующих объектов, а так же методов и средств их обработки, описанных на языке понятном исполнителю.
