Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
, 0 + 1 = 1, 1 + 0 = 1, 1 + 1 = 10; 0 · 0 = 0, 0 · 1 = 0, 1 · 0 = 0, 1 · 1 = 1. Поскольку в этой системе для изображения чисел берутся только две цифры, для построения компьютера можно использовать элементы, име- ющие лишь два различных устойчивых состояния, одно из которых соот- ветствует цифре 0, а другое — цифре 1. При этом алгебраическая система с носителем, состоящим из двоичных кодов, изоморфна соответствующей алгебраической системе, элементы которой имеют десятичную запись. 3. Восьмеричная система В восьмеричной системе счисления используются цифры 0, 1, 2, 3, 4, 5, 6, 7. Запись числа основывается на его разложении по сте- пеням числа восемь с указанными коэффициентами. Пример 3.2.2. 215 10 = 192 + 16 + 7 = 3 · 8 2 + 2 · 8 1 + 7 · 8 0 = 327 8 , 30.25 10 = 3 · 8 1 + 6 · 8 0 + 2 · 8 −1 = 36.2 8 . ¤ 4. Шестнадцатеричная система В этой системе для записи базисных чисел от нуля до пятнадцати ис- пользуются следующие символы (цифры): от 0 до 9 — те же самые арабские цифры, а для следующих чисел — от десяти до пятнадцати — символы a, b, c, d, e, f . Пример 3.2.3. ae.8 16 = 10 · 16 + 14 + 8/16 = 160 + 14 + 0.5 = 174.5 10 . ¤ 88 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ 5. Смешанные системы счисления В некоторых случаях числа, заданные в системе счисления с основани- ем P , приходится изображать с помощью цифр системы с основанием Q (Q < P ). Такая необходимость возникает, например, когда в память машины, способной воспринимать только двоичные цифры, нужно ввести десятичные числа для их последующей переработки. В таких случаях используют сме- шанные системы счисления, в которых каждый коэффициент разложения числа по степеням P записывается в Q-ичной системе. Такая смешанная система называется Q-P -ичной. При этом для записи каждого из упомя- нутых выше коэффициентов используется одно и то же количество Q-ичных разрядов, минимально необходимое для записи любого из допустимых коэф- фициентов. Пример 3.2.4. Представим число 8903 10 в смешанной двоично- десятичной системе. Поскольку 8 10 = 1000 2 , 9 10 = 1001 2 , 3 10 = 0011 2 , имеем 8903 10 = 1000 1001 0000 0011 2−10 . ¤ Отметим, что запись в двоично-десятичной системе отличается от за- писи данного числа в двоичной системе счисления. Например, 8903 10 = = 10001011000111 2 , что отличается от записи этого же числа в смешанной двоично-десятичной системе. Особый интерес представляет случай, когда P = Q l (l ∈ ω). При этом запись любого числа в смешанной Q-P -ичной системе совпадает с записью этого числа в Q-ичной системе. Пример 3.2.5. Если P = 8, Q = 2 (8 = 2 3 ), то 2763 8 = 010 111 110 011 2−8 = 010 111 110 011 2 . ¤ Таким образом, запись числа в P -ичной системе счисления в случае P = Q l является просто сокращенной записью изображения этого же числа в Q-ичной системе: для такой сокращенной записи Q-ичные цифры в изоб- ражении числа объединяются вправо и влево от точки в группы по l раз- рядов (дополняя, в случае необходимости, нужное количество нулей справа и слева), и каждое число, представленное в Q-ичной системе этой группой разрядов, записывается одной P -ичной цифрой. Пример 3.2.6. 1011011011.111011 2 = 0010 1101 1011.1110 1100 2 = = 0010 1101 1011.1110 1100 2−16 = 2db.ea 16 . ¤ 3.2. СИСТЕМЫ СЧИСЛЕНИЯ 89 6. Перевод чисел из одной системы счисления в другую В связи с использованием различных систем счисления возникает необхо- димость перевода чисел из одной системы в другую. Задача перевода состоит в следующем. Пусть известна запись числа x в системе счисления с основа- нием P : x = (p n p n−1 . . . p 0 .p −1 p −2 . . . p −k ) P , где p i — цифры P -ичной систе- мы. Требуется найти запись числа x в системе счисления с основанием Q: x = (q m q m−1 . . . q 0 .q −1 q −2 . . . q −1 ) Q , где q i — цифры Q-ичной системы. При этом можно ограничиться рассмотрением положительных чисел, поскольку перевод любого числа сводится к переводу его абсолютной величины с по- следующим приписыванием соответствующего знака. Для определенности будем считать, что в процессе перевода должны ис- пользоваться только средства P -ичной арифметики. В связи с этим необхо- димо рассмотреть перевод из Q-ичной системы в P -ичную (Q → P ) и из P - ичной в Q-ичную (P → Q). Перевод Q → P . Если известна запись числа x в Q-ичной системе x = (q m q m−1 . . . q 0 .q −1 q −2 . . . q −1 ) Q , перевод в P -ичную систему сводится к вы- числению значения многочлена x = q m Q m + q m−1 Q m−1 + . . . + q 0 + q −1 Q −1 + q −2 Q −2 + . . . + q −l Q −l , что следует из правил записи числа x в Q-ичной системе. Пример 3.2.7. Переведем число x = ba.8 16 в десятичную систему сред- ствами десятичной арифметики. Здесь Q = 16, P = 10. Имеем x = 11 · 16 + 10 + 8 · 16 −1 = 186.5 10 . ¤ Перевод P → Q. Рассмотрим перевод целых чисел и правильных дробей. В общем случае перевод любого числа сводится к независимому переводу его целой и дробной частей. Перевод целых чисел. Пусть дана запись целого числа N в системе счис- ления с основанием P . Поскольку N — целое число, его запись в Q-ичной системе будет иметь вид N = (q k q k−1 . . . q 0 ) Q , где q i (0 6 q i < Q) — иско- мые цифры Q-ичной системы. Эта запись является сокращенной записью многочлена N = q k Q k + q k−1 Q k−1 + . . . + q 0 90 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ Для определения q 0 разделим обе части последнего равенства на Q: N/Q = q k Q k−1 + . . . + q 1 + q 0 /Q. Приравнивая между собой целые и дробные части в левой и правой частях (учитывая, что q i < Q), получим, что q 0 есть остаток от деления N на Q. Целочисленное частное от деления N на Q обозначим через N 1 Тогда N 1 = q k Q k−1 + . . . + q 1 . Поскольку N 1 есть целое число, к нему можно применить тот же прием для определения значения q 1 , которое равно остат- ку от деления N 1 на Q. Полученное при этом частное обозначим через N 2 и т. д. Этот процесс заканчивается, когда очередное частное окажется рав- ным нулю. Для окончательной записи числа N в Q-ичной системе нужно в соответствующем порядке записать коэффициенты q i , изображая каждый из них одной Q-ичной цифрой. Пример 3.2.8. 1. Переведем десятичное число N = 23 в двоичную систему средствами десятичной арифметики (P = 10, Q = 2): 23/2 = 11 + 1/2, q 0 = 1, N 1 = 11, 11/2 = 5 + 1/2, q 1 = 1, N 2 = 5, 5/2 = 2 + 1/2, q 2 = 1, N 3 = 2, 2/2 = 1 + 0/2, q 3 = 0, N 4 = 1, 1/2 = 0 + 1/2, q 4 = 1, N 5 = 0. Поскольку числа нуль и единица в каждой из этих систем обозначаются цифрами 0 и 1, то в процессе деления сразу получены искомые двоичные цифры: N = 10111 2 2. Переведем число N = 175 10 в шестнадцатеричную систему: 175/16 = 10 + 15/16, q 0 = 15, N 1 = 10, 10/16 = 0 + 10/16, q 1 = 10, N 2 = 0. Таким образом, N = 10 · 16 1 + 15 · 16 0 . Число 10 соответствует шестнадцате- ричной цифре a, число 15 — цифре f , следовательно, N = af 16 . ¤ Перевод дробных чисел. Пусть требуется перевести в P -ичную систему правильную дробь x (0 6 x < 1), заданную в ее P -ичной записи: x = 0.p −1 p −2 . . . p −k . Запись этого числа в Q-ичной системе будет иметь вид x = 0.q −1 q −2 . . . q −m . . . Значит, x = q −1 Q −1 + q −2 Q −2 + . . . + q −m Q −m + . . . , где q i — коэффициенты Q-ичного разложения, подлежащие определению. Нетрудно убедиться, что эти коэффициенты можно получить путем после- довательного умножения на Q сначала исходного числа x, а затем дробной 3.3. КОМПЬЮТЕРНАЯ АЛГЕБРА И ЧИСЛЕННЫЙ АНАЛИЗ 91 части очередного полученного произведения. Этот процесс продолжается до тех пор, пока дробная часть очередного произведения не окажется рав- ной нулю либо не будет достигнута требуемая точность изображения числа x в Q-ичной системе. Пример 3.2.9. Перевод числа x = 0.1 10 в двоичную систему приводит к такой последовательности действий: 0.1 · 2 = 0.2, q −1 = 0, дробная часть = 0.2, 0.2 · 2 = 0.4, q −2 = 0, дробная часть = 0.4, 0.4 · 2 = 0.8, q −3 = 0, дробная часть = 0.8, 0.8 · 2 = 1.6, q −4 = 1, дробная часть = 0.6, 0.6 · 2 = 1.2, q −5 = 1, дробная часть = 0.2, . . . Очевидно, что дальше результаты будут повторяться, и поэтому x = (0.0001100110011 . . .) 2 = 0.0(0011) 2 . ¤ § 3.3. Компьютерная алгебра и численный анализ Термин компьютерная алгебра объясняется способностью компьюте- ров манипулировать математическими выражениями, заданными символь- но, а не численно. Системы компьютерной алгебры освобождают от рутин- ной работы, связанной с численными ошибками (усечение и округление). Прежде чем рассматривать точную арифметику, реализуемую в систе- мах компьютерной алгебры, отметим неотъемлемые недостатки численных расчетов с использованием компьютеров. Компьютер — это машина с конеч- ной памятью, состоящей из слов конечной длины алфавита {0, 1}. Элементы компьютерного слова называются битами. Обычно длина компьютерного слова составляет 16 или 32 бита, при этом максимальное целое число, кото- рое можно разместить в слове (в двоичной системе счисления), составляет 2 16 −1 или 2 32 −1, что соответствует пятизначным или десятизначным числам в десятичной системе счисления. При выполнении численных расчетов на компьютере обычно возникает проблема представления бесконечного множества вещественных чисел в ко- нечной памяти. Наиболее распространенным способом решения этой пробле- мы в численном анализе является приближение (округление) вещественных чисел с использованием конечного множества с плавающей точкой. 92 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ 0 1 4 1 2 1 2 3 3 1 2 − 1 4 − 1 2 −1 −2 −3 −3 1 2 Рис. 3.1 Множество F чисел с плавающей точкой характеризуется основанием счисления P , точностью t и областью значений экспоненты [L, U ], где пара- метры P, t, L, U зависят от компьютера. Каждое число f ∈ F представляется в виде f = ± µ d 1 P + d 2 P 2 + . . . + d t P t ¶ P e , где целые числа d i , i = 1, 2, . . . , t, удовлетворяют неравенствам 0 6 d i 6 P −1, L 6 e 6 U. Если d 1 6= 0, число f ∈ F называется нормализованным числом с плавающей точкой. Отметим, что при использовании чисел с плавающей точкой или целых чисел, помещающихся в одном компьютерном слове, арифметические опера- ции выполняются очень быстро, поскольку они производятся не программ- ным обеспечением, а электронными схемами компьютера. Нетрудно подсчитать, что множество F содержит 2(P − 1)P t−1 · (U − L + 1) + 1 нормализованных чисел с плавающей точкой (включая нуль). Эти числа размещены на числовой прямой равномерно не на всей области значений, а только между последовательными степенями P . Пример 3.3.1. На рис. 3.1 изображено 33-элементное множество норма- лизованных чисел с параметрами P = 2, t = 3, L = −1, U = 2. ¤ Приведенный пример показывает, что сумма (или произведение) данных чисел f 1 и f 2 из F может не принадлежать F и должна быть приближена ближайшим числом с плавающей точкой. Разность между истинным и при- ближенным значениями суммы (или произведения) является ошибкой округ- ления. Отметим также, что частичные операции сложения и умножения в F не удовлетворяют законам ассоциативности и дистрибутивности. Например, в 33-элементном множестве F справедливо 5/4 + (3/8 + 3/8) = 2, где 5/4, 3.4. СПИСОЧНОЕ ПРЕДСТАВЛЕНИЕ ЧИСЕЛ 93 3/8, 2 ∈ F . Однако (5/4 + 3/8) + 3/8 6= 2, поскольку в F не определена сумма (5/4+3/8) и это выражение должно быть приближено в F либо числом 3/2, либо числом 7/4. Ошибки округления могут возникать и при работе с це- лыми числами, например, при вычислении произведения двух s-значных чисел на компьютере, который не может обрабатывать числа, содержащие больше s цифр. Таким образом, в численном анализе нужно тщательно оценивать ошиб- ки округления, возникающие при работе любого алгоритма. Это указывает на необходимость построения и использования программных систем, способ- ных обрабатывать выражения в символьном виде и производить безошибоч- ные вычисления. Опишем два подхода к построению таких систем, первый из которых использует списочное представление чисел, а второй — много- модульную арифметику. § 3.4. Списочное представление чисел 1. Списки и базисные операции над списками Определим по индукции понятие списка над множеством S: 1) любой элемент a ∈ S является списком над множеством S; 2) если a 1 , . . . , a n — списки над множеством S, n > 0, то (a 1 , . . . , a n ) — список над множеством S; 3) никаких списков над множеством S, кроме построенных по пп. 1 и 2, нет. Список, соответствующий n = 0 в п. 2, называется пустым и обозна- чается так же, как и пустое слово, через Λ. По определению каждое слово непустого алфавита S является списком над S. Определим основные операции над списками. Если a = (a 1 , . . . , a n ) — список, то длина(a) l(a) n; первый(a) π 1 (a) a 1 ; последний(a) π n (a) a n ; хвост(a) π 2,...,n (a) (a 2 , . . . , a n ); развернутый(a) π n,...,1 (a) (a n , . . . , a 1 ); если b = (b 1 , . . . , b k ) — список, то присоединение(b, a) bˆa (b 1 , . . . , b k , a 1 , . . . , a n ); отсоединение(b, bˆa) a. 94 Глава 3. ЧИСЛОВЫЕ СИСТЕМЫ 2. Списочное представление целых и рациональных чисел Как уже отмечалось, компьютерное представление целых чисел ограни- чено длиной машинного слова. Для расширения возможностей такого пред- ставления и выполнения точных арифметических действий можно исполь- зовать задание целых чисел в виде списков. При этом, однако, необходи- мо разработать специальное программное обеспечение, позволяющее выпол- нять арифметические операции над списками. Пусть P — такое основание счисления, что P − 1 — наибольшее значение, хранимое в компьютерном слове. Рассмотрим два типа целых чисел. Если |