Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 14
Текст из файла (страница 14)
Пусть требуется в коде прямого замещения найти сумму чисел 205 и 768. Выполним необходимые операции: 205 — 0010 0000 0101 кодирование 1001 0110 1101 первое суммирование 0000 0000 0110 поправка Код прямого замещения удовлетворяет всем требованиям Рутистлузера, креме четвертого. Нарушение этого требования не позволяет вводить дополнительный или обратный код, чта в свою очередь не позволяет заменить вычитание операцией сложения. Для выполнения свойства дополнительности будем кодировать десятичную цифру х тетрадой Т(х), равной х+ 3.
Полученный кад называется кодом с избытком 3, или кодом Штибитца. В этом случае сумма тетрад принимает следующий вид: к+у<10, Т(х) + Т(у) = х + 3+ у+ 3 = х + у+ 6, Т(х+ у) = х+ у+ 3, следовательно, поправка равна -3 (в обратном коде — 1100, в до- полнительном — 1101), т. е. Т(х+ у) — (Т(х)+Т(у)) = -3; х+у>10, Т(х)+Т(у) =х+3+у+3'= х+у+6, Т(х+ у) = х+ у — 10+16+3 = х+ у+ 9, следовательно, поправка равна +3, т. е. Т(х+ у) — (Т(х)+ Т(у)) = 3. Таким образом, получаем (Т(х+у)+ 3, х+у < 10, ),Т(х+у) — 3, х+у>10.
Приведем пример суммирования чисел -471 и 607 с использо- ванием допалнительнога кода: -471 — 1000 0101 1100 кодирование 607 — 1001 0011 1010 + 10001 1001 0110 0001 1001 0110 первое суммирование, отбрасывание переноса из левого разряда 0011 1101 ООП поправка 136 — 0100 0110 1001 получение результата после поправок Кодирование с избыткам 3 не обладает свойством весомозна'чимости. Единственным кодированием, которое обладает всеми пятью свойствами, является кодирование Абкена — Эмери.
Зто кодирование с весами (2, 4, 2, 1). Вычислим эти коды при р; > О. Для кодирования 1 необходимо, чтобы один из весов был равен 1. Для определенности будем считать, что рв — — 1, тогда р) + рэ+ +рз = 8. Возможные комбинации весов (р), рэ, рз) с точностью до их перестановки: (1) 1, 6), (2, 1, 5), (2, 2, 4)) (2, 3, 3), (1, 3, 4). В системе с весами (6, 1, 1, 1): 0 — 0000, 1 — 0001, 2 — 0011, 3 — 0111, 4— 5 —, 6 — 1000, 7 — 1001, 8 — 1011, 9 — 1111. Ге. 1. Основы многосортных множеств Для случая (1,1,6) нарушается первое требование Рутнсхаузера: для цифр 4 и 5 отсутствуют соответствующие тетрады. В системе с весами (5,2,1,1): 0 — 0000, 1 — 0001, 2 — 0100, 3 — 0101, 4 — 0111, 5 — 1000, 6 — 1010, 7 — 1011, 8 — 1110, 9 — 1111; не выполняется требование четности для цифр 4 и 5. В системе с весами (3, 3, 2, 1): 0 — 0000, 1 — 0001, 2 — 0010, 3 — 0011, 4 — 0101, 5 — 1010, 6 — 1100, 7 — 1101, 8 — 1110, 9 — 1111; не выполняется требование четности для цифр 4 и 5.
В системе с весами (4,3,1,1): Π— 0000, 1 — 0001, 2 †'0011, 3 — 0100, 4 — 0110, 5 — 1001, 6 — 1011, 7 — 1100, 8 — П10, 9 — 1111; не выполняется требование четности цифр для цифр 2, 3, 6, 7. В системе с весами (2,4,2, 1): 0 — 0000, 1 — 0001, 2 — 0010, 3 — 0011, 4 — 0100, 5 1011~ 6 1100з 7 1101т 8 — 1110~ 9 — 1111~ все пять требований выполнены, соответствуюшая арифметика является совершенной и называется в честь авторов — арифме- тпикой Айкена — Эмери. Анализируя коды, замечаем, что у х, х < 5, т(х) = ) х'+ 6 х > 5' Для определения правил суммирования тетрад необходимо рас- смотреть следующие случаи: 1) х < 5, у < 5, х + у < 5; Т(х) + Т(у) = х+ у, Т(х+ у) = = х + у, Ь = Т(х + у) — (Т(х) + Т(у)), Ь = 0; 2) х < 5, у < 5,5 < х+у < 10; Т(х)+Т(у) = х+у, Т(х + у) = х + у+ 6, сь = 6; 3) х < 5, у > 5, 5 < х+ у < 10, "Т(х) + Т(у) = х + (у+ 6), Т(х+ у) = х + у+ 6, вь = 0; 4) х < 5, у > 5, 10 < х+ у < 15; Т(х) + Т(у) = х + (у+ 6), Т(х+ у) + 6 (6 нз-за переноса) = х+ у+ 6, Ь = 0; 5) х > 5, у > 5, 10 < х+у < 15; Т(х) +Т(у) = (х+6) + (у+6), Т(х + у) + 6 = (х + у) + 6, Ь = -6; 6) х > 5, у > 5, х+ у > 15; Т(х) + Т(у) = (х+ 6) + (у+ 6), Т(х + у) + 6 = (х + у + 6) + 6, Ь = О.
Таким образом, при суммировании х+ у в коде Айкена — Эмери необходима поправка+6 в тетрадах, когда х < 5, у < 5, 5 < х+у < < 10, и поправка -6, когда х > 5, у > 5, 10 < х + у < 15. $1.8. Компьютерные арифметики Просуммируем в зтом коде рассмотренную выше лару чисел 471 и 607, используя при атом дополнительный код. Имеем -471 — 1000 0101 1100 +607 — 1001 0011 1010 10111 0111 1010 сл ай 5 0011 0011 0000 сл ай 1 1100 1100 ОООО сл ай 6 +136 — 0001 0011 1100 Производительность процессора существенно повышается, если обработать каждый разряд независимо ат других.
Эту возможность предоставляет код в остатках. Системой счисления, позволяющей производить вычисления в каждом разряде независима от результатов, полученных в других разрядах, является код в остпатках. Множестпвом модулей кода в остпатпкох называется множества Я взаимно простых натуральных чисел: ет, дт,..., д,. Обозначим через гее (х/д;) остаток от целочисленного деления х на д;. Кодом в остпатках числа х по множеству модулей вт, дю ..., е, называется выражение вида х х х тее — гее — ° ° ° тее тт Чт вв Если тев (х/д;) = а и гев(х/дт) = 1у, то х = пут + а и у = = тпет+ ~3.
Проведем алгебраическое суммирование последних двух равенств. В результате получаем х ~ у = (и ~ тп) ° йт + (а ~,6). Теперь перемножим соответственно правые и левые части исходных равенств: х у=(пь и д;+п /1+та а) е;+а 19. Если а+ 1у и а Д меньше д;, то можне утверждать, что прн суммировании и умножении двух чисел их остатки ат деления в; также складываются или перемнажаются. Если же а+ 1у и а.,6 больше д;, то, разделив нх на ут и определив целое частное, получим, что утверждение а суммировании и перемножении остатков совпадает с ранее высказанным, если считать, чта после выполнения зтих операций происходит деление на модуль данного разряда и выделение истинного остатка.
Подобная операция может имеп место для каждого разряда независимо ат других, позтому код в остатках позволяет суммировать и перемножать поразрядно, что позволяет увеличить скорость выполнения операций ЭВМ. Пусть, например, имеется система из трех модулей: 7, 8, 9. Тогда коды в остатках для чисел х = 11 и у = 6 имеют соответственно виды 432 и 666. Прасуммируем и перемножим поразрядно 11,9. Нечеткие подмможества Гл. 1.
Осмовы ммогосортмых мможеств 74 коды х и у; тогда получаем 10 9 8 и 24 18 12. После деления в каждом разряде результата на модуль этого разряда и выделения истинного остатка получим соответственно 318 и 323. Сумма н произведение х и у, равные 17 и 66, имеют коды в остатках 318 и 323. Для получения взаимно однозначного представления чисел в коде в остатках следует учитывать, что если произведение всех модулей д<, используемых для кодирования, есть Ж, то взаимно однозначно в коде в остатках с этими модулями можно кодировать лишь М различных чисел (от 0 до Ж вЂ” 1, от Ж до 2Ж вЂ” 1 и т.
д.). Рис. 1.24 Число У называется мои1мастью системы мадулеб. Недостатком этой арифметики является трудность реализации операции деления, которая обычно заменяется умножением на обратную величину. Арифметика как многосортное множество (М, +, —, х,: ), где М вЂ” носитель арифметики, представляющий собой множество чисел, а операции +, —, х,: — сигнатура арифметики, в информатике имеет фундаментальное значение. Арифметика является яа,аем над числами. Дискретную математику, являющуюся основой информационной математики, можно определить как науку а многосортных множествах (совокупностях) (М, (ОД, Щ1, (О„-'1), где М вЂ” множество, в котором заданы операции (О;); (ЯД— отношения и (0„11 — кооперации, определяющие соответственно законы композиции, свойства и законы декомпозиции. Вложение друг в друга основных понятий дискретной математики показано на рис.
1.24, где песетам названа частично упорядоченное множество (рагс)аПу огдег аеФ), комплектом — множество, в котором найдутся хотя бы два одинаковых элемента. 9 1.9. Нечеткие подмножества Расширим понятие подмножества, введя свойство нечеткости (размытости). Принадлежность элемента х подмножеству А: хЕА, АСМ, будем задавать с помощью хароктеристическаб функции (1, если х Е А, 1"~(х) )~0 в противном случае. Представим теперь, что характеристическая функция может принимать любое значение в интервале [О, 1]. В соответствии с этим элемент х множества М может не принадлежать А (1сд(х) = = 0), может быть элементом А в небольшой степени (ус,~ близко к О) или, наконец, может быть элементом А (11,~ = 1). Таким обра- зом, понятие принадлежности получает интересное обобщение при решении практических задач.
Математический объект, определяемый выражением А= ((хд$0.2), (х2$0) (хз$0 3) (хв$1), (хв$0 8)~, где х; — элемент универсального множества М, а числа после вертикальной черты дает значение характеристической функции на этом элементе, будем называть нечетким подмножествам А множества М и обозначать А С М. При этом нечеткое подмно- жество А: содержит в небольшой степени х1, не содержит хт, со- держит хз в немного большей степени, чем хэ, полностью содер- жит хв, в значительной мере содержит хэ. Таким образом, мы можем создать математическую структуру, которая позволяет опе- рировать с относительно неполно определенными элементами н принадлежность которой к данному подмножеству упорядочена.
К таким структурам можне, например, отнести: в заданном мно- жестве людей — некоторое подмножество очень высоких людей; во множестве основных цветов — нечеткое подмножество темна- зеленых цветов; во множестве решений — нечеткое подмножество Гл. 1. Основм мнвгосортных мнохсвств 77 11.9. Нснензнив подмнохсвсвзвв хороших решений и т. д. Далее мы увидим, как обращаться с такими понятиями, которые особенно хорошо подходят к описанию неточности, присущей моделям искусственного интеллекта.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
