Курс: Элементы компьютерной математики компьютерной математики Лектор – Склярова Елена Александровна
Тема: Элементы компьютерной математики (ЭКМ) I. Элементы систем счисления 1. Позиционные и непозиционные системы счисления 2. Двоичная система счисления 3. Восьмеричная и шестнадцатеричная системы счисления Лекция 4
«Математика также открывает свои тайны только тому, кто приближается к ней с чистой любовью, ради ее собственной красоты. И те, кто делает так, вознаграждаются результатами практической важности. Но если спрашивать себя на каждом шагу: какая польза от этого? то невозможно достичь многого. Ты помнишь, я сказал тебе, что римляне никогда не смогут добиться успеха в прикладной математике. Теперь ты видишь, почему: они слишком практичны». А Реньи. «Диалоги о математике»
Дискретная математика Понятие предмета компьютерной (дискретной) математики широко и неоднозначно. «Дискретный», далее - «цифровой» («числовой»), - это качество свойственно слишком большому многообразию объектов.
Позиционные и непозиционные системы счисления Система счисления- это совокупность приемов наименования и записи чисел с помощью специальных знаков - символов (цифр). Известны позиционные и непозиционные системы счисления (СС). Наиболее представительным примером непозиционной системы счисления является римская СС. В ней используется такие цифры: I - единица;С - сто; V – пять;D - пятьсот; X - десять;М - тысяча. L - пятьдесят; МСМХLI
Позиционные и непозиционные системы счисления Например, запись МСМХLI означает ( ) + ( ) + I = В непозиционной системе цифры не зависят от ее позиции - положения в записи числа (в примере такова цифра М, ее значение всегда 1000).
Позиционные и непозиционные системы счисления В римской системе действуют два простых правила: а) значение младшей цифры, стоящей слева, берется со знаком «минус»: СМ = = 900, ХL = = 40; б) значение младшей цифры, стоящей справа, берется со знаком «плюс»: VI = = 6 и т.п.
Позиционные и непозиционные системы счисления В позиционной системе числа также записываются в виде последовательности цифр, но значение каждой цифры теперь зависит от ее положения - позиции (разряда) в этой последовательности. Обычно значение цифры возрастает при ее перемещении справа налево (арабский порядок) на один разряд в целое число раз, называемое основанием системы счисления (q = 2, 3,...).
Позиционные и непозиционные системы счисления Позиционной является привычная десятичная система: q = 10. Цифр в этой системе тоже десять: 0, 1,..., 9. Вообще, в позиционной СС количество цифр равно ее основанию. При этом суть позиционности системы наглядно отображается в записи числа как суммы степеней основания (своего рода «реструктуризация»). Например: 13,141 = 1· · · · ·10 -3.
Двоичная система счисления В математической логике, теории вероятности, теории информации и вычислительной технике широко используется двоичная система счисления: q = 2, множество цифр - {0, 1}. Например, 10101,01 2 = 1·2 4 +1· ·2 -2 = 21,25.
Двоичная система счисления Правило перевода целых чисел из десятичной системы в двоичную (10 2): число делят на 2 в десятичной системе счисления; получившийся остаток (0 или 1) соответствует младшей цифре двоичной записи числа; частное от первого деления снова делят на 2 и т.д. Действительно, при первом делении целого N на 2 получаем N = 2 ·N 1 + а 0, здесь N 1 - количество «двоек», а 0 - младшая цифра двоичной записи.
Двоичная система счисления Пример = Проверка = 1· · · · = = = 157. Совершенно аналогично выглядит правило перевода целых чисел q 1 q 2. Надо делить на q 2 в системе с основанием q
Двоичная система счисления Правило перевода дробных чисел Число, т.е. правильную дробь (абсолютная величина ее меньше 1), умножают на 2 в десятичной системе. Целая часть первого произведения соответствует старшей цифре двоичной записи, т.е. имеющей вес 2 и стоящей сразу после запятой. Дробную часть первого произведения снова умножают на 2 и т.д.
Двоичная система счисления Процесс заканчивается автоматически (дробная часть очередного произведения получается полностью нулевой) или по достижении требуемой точности Например, при определении девяти двоичных знаков после запятой точность составляет 2 -9 = 1/512 = 0,00195
Двоичная система счисления Пример 2. 0,357 = 0, Проверка. 0, = = · 2 -9 = = (1 · · · · · 2 1 ) · 2 -9 = ( ) · 2 -9 = 182 / 512 = 0, Ошибка D = | 0, ,35700 | = = 0,00153 < 0, , ……
Двоичная система счисления Обоснование правила перевода дробных чисел очевидно: при умножении дроби на 2 запятая в двоичной записи числа смешается вправо на 1 разряд, в результате чего очередная старшая двоичная цифра оказывается в разряде целой части. В двоичной (как и в любой другой позиционной) системе счисления выполнение арифметических действий над многоразрядными числами сводится к действиям над числами одноразрядными - благодаря связи по переносу (в соседний левый разряд).
Двоичная система счисления «Таблицы» сложения, вычитания и умножения в двоичной системе предельно просты: = = 00 * 0 = = = 10 *1 = = 11 – 0 = 11 * 0 = = – 1 = 01 * 1 = 1 Здесь значение 10 2 = 2 отражает как раз перенос при сложении и заем (займ) при вычитании. Наиболее простой выглядит таблица умножения. Кстати, деление сводится к вычитанию и сдвигу (так же, как умножение - к сложению и сдвигу).
Двоичная система счисления Пример 3. Сложение Х = 157 = У = 182 = Z = 339 = Проверка = = = = 339. В записи примера верхняя строка показывает единицы переноса. +
Двоичная система счисления Пример 4. Вычитание. X = 182 = Y = 157 = Z = 25 = = =
Двоичная система счисления Пример 5. Умножение. X = 157 = Y = 182 = ЧП ЧП ЧП ЧП ЧП ЧП ЧП ЧП
Двоичная система счисления Проверка: = = = Действительно, ЧП ЧП ЧП ЧП - это частичное произведение. * +
Двоичная система счисления Пример 6. Деление. X = 157 = Y = 18 = Z = 8 = (частное) R = 13 = (остаток) (частное) (остаток) /
Восьмеричная система счисления Системы с основанием 8 и 16 просто связаны с двоичной системой, поскольку 8 = 2 3, а 16 = 2 4. Эти системы позволяют удобно представлять двоичные числа косвенно. Можно называть их даже «двоично- кодированные системы».
Восьмеричная система счисления Действительно, каждая восьмеричная цифра может быть заменена 3 разрядным двоичным эквивалентом (триадой) и наоборот: 0 = 000 2,4 = 100 2, 1 = 001 2,5 = 101 2, 2 = 010 2,6 = 110 2, 3 = =
Восьмеричная система счисления Тогда действует простое правило перехода от восьмеричной записи числа к двоичной и обратно. Например, 362, = , (левый незначащий нуль в двоичной записи может быть опущен). Или: , = 235,44 8 (здесь нули добавлены и слева, и справа). В двоичной записи осуществляется разбиение на триады влево и вправо от запятой. Затем каждая триада заменяется соответствующей ей восьмеричной цифрой Доказательство правила 8 2 очевидно (например, делить целое на 8 - то же самое, что и трижды последовательно делить на 2).
Восьмеричная система счисления При выполнении арифметических действий в восьмеричной системе полезно использовать две таблицы - сложения (табл. 1.1) и умножения (табл. 1.2.) Сложение восьмеричных чисел Таблица
Восьмеричная система счисления Пример 1. Сложение. 11 Х = 157 = У = 182 = Z = 339 = Проверка = 5 · · = 5 ·
Восьмеричная система счисления Пример 2. Вычитание. X = 182 = Y = 157 = Z = 25 = 31 8 = 3 ·
Восьмеричная система счисления Умножение восьмеричных чисел Таблица 1.2. *
Восьмеричная система счисления Пример 3. Умножение. Х = 157 = У = 182 = ЧП ЧП2 47 2ЧП Проверка = 6 · · · · = = 6 · · · = = *
Восьмеричная система счисления Пример 4. Деление. X = 157 = Y = 18 = 22 8 Z = 8 = 10 8 (частное) R = 13 = 15 8 (остаток) /
Восьмеричная система счисления Восьмеричную систему удобно использовать как промежуточную при переводе чисел 10 2 (делить и умножать на 8 быстрее, чем на 2). Пример = =
Шестнадцатеричная система счисления С появлением понятия байта как 8-разрядного двоичного элемента, содержащего две 4- разрядных тетрады, на смену восьмеричной системе приходит шестнадцатеричная. Здесь 16 цифр: 0 = , 8 = , 1 = , 9 = , 2 = , A = , 3 = , B = , 4 = , C = , 5 = , D = , 6 = , E = , 7 = , F = Теперь перевод 162 осуществляется путем группировки двоичных разрядов в четверки - тетрады.
Шестнадцатеричная система счисления Пример = 9D 16 = Пример , = 72,
Шестнадцатеричная система счисления В шестнадцатеричной системе, конечно, можно выполнять любые арифметические действия. С этой целью составляются таблица сложения и таблица умножения (для одноразрядных шестнадцатеричных чисел). Эти таблицы значительно более громоздкие, чем для восьмеричной системы (16 х 16 = 256 клеток). Поэтому пример таблиц в сокращении (табл. 1.3, 1.4).
Шестнадцатеричная система счисления Сложение шестнадцатеричных чисел Таблица 1.3. *0123…DEF 00123…DEF 11234…EF …F … ……………...……… DDEF10…1A1B1C EEF1011…1B1C1D FF101112…1C1D1E
Шестнадцатеричная система счисления Умножение шестнадцатеричных чисел Таблица 1.4. *0123…DEF 00000… …DEF 20246…1A1A1C1C1E1E 30369…272A2D2D ……………...……… D0D1A1A27…A9B6C3 E0E1C1C2A2A…B6C4D2 F0F1E1E2D2D…C3D2E1
Восьмеричная система счисления Пример 8. Сложение. Х = 157 = 9D 16 У = 182 = B6 16 Z = 339 = Проверка = 1 · · =
Восьмеричная система счисления Пример 9. Вычитание. X = 182 = B6 16 Y = 157 = 9D 16 Z = 25 = = 1 ·
Восьмеричная система счисления Пример 10. Умножение. Х = 157 = 9D 16 У = 182 = B6 16 3AEЧП1 6 BF ЧП2 Z = 6 F9E 16 Проверка. 6 F9E 16 = 6 · · · = = 6 · · = = = *
Восьмеричная система счисления Пример 11. Деление. X = 157 = 9D 16 Y = 18 = Z = 8 R = 13 = D 16 9D (частное) D (остаток) /
Задание Самостоятельно!!! Представить 2 числа в двоичной, восьмеричной и шестнадцатеричной системе счисления. Произвести операции сложения, вычитания, умножения и деления.
Лекция окончена Нажмите клавишу для выхода