- •Конспект лекций по дисциплине «основы дискретной математики»
- •Лекция № 1. Дискретное и непрерывное
- •Лекция № 2. Системы счисления
- •Лекция № 3. Фракталы
- •3.1. Канторово множество
- •3.2. Ковер Серпинского и снежинка Коха
- •3.3. Стохастические фракталы
- •3.4. Энтропийная размерность
- •3.5. Фрактал Мандельброта
- •Лекция № 4. Основы математической логики
- •Набор истинностных значений 0001 в первой строке таблицы соответствует результатам операций:
- •Основные эквивалентности:
- •X(баскетболист(X)высокий(X))
- •X(личность(х)любит(х, грибы))
- •X любит(х, платить(налоги))
- •X(человек(X)смертный(X)),
- •Лекция № 5. Множества и подмножества
- •Лекция № 6. Математическая индукция
- •Лекция № 7. Комбинаторика
- •Лекция № 8. Числа фибоначчи и простые числа
- •Лекция № 9. Кодирование
- •Лекция № 10. Шифрование
Лекция № 2. Системы счисления
Позиционные и непозиционные системы
Системой счисления называется метод записи чисел в виде комбинаций графических символов. Число – это некоторая абстрактная сущность для описания количества, а цифры – знаки, используемые для записи чисел. В наше время самыми распространёнными являются арабские цифры, менее распространены римские цифры. Система римских цифр основана на употреблении особых знаков для десятичных разрядов: I=1, X=10, C=100, M=1000 и их половин: V=5, L=50, D=500. Существует множество других способов записи чисел. Например, древние греки использовали для этой цели буквы своего алфавита, а древние шумеры – клинописные знаки. Существуют позиционные и непозиционные системы счисления.
Позиционная система счисления – система записи чисел в виде последовательности символов, в которой численное значение каждого символа зависит от его положения в записи.
Примером позиционной системы является хорошо известная десятичная система счисления. Примером непозиционной системы – римская система. Выполнение арифметических действий над числами в непозиционной системе весьма неудобно. Поэтому позиционные системы в настоящее время получили наибольшее распространение.
Изобретение позиционной системы приписывается шумерам и вавилонянам. Затем она была развита индусами. В средневековой Европе позиционная десятичная система появилась благодаря итальянским купцам, которые заимствовали её у мусульман. В 9 веке великий арабский математик Мухаммед ибн Мусе Аль Хорезми впервые описал десятичную систему исчисления и правила выполнения простых арифметических действий в ней. В 12 веке его работы были переведены на латинский язык, благодаря чему Европа смогла познакомиться с этим изобретением человеческого ума.
Десятичная система
Существуют различные позиционные системы исчисления, отличающиеся между собой количеством используемых знаков. Чтобы различать числа в разных системах исчисления, в конце числа ставят индекс – символ системы. Например, запись означает обычное число 483,56 в десятичной системе счисления, а записьозначает совсем другое число (хотя и похожее по виду) вшестнадцатеричной системе счисления (в десятичной оно равно 1155,335938). Если из контекста понятно, что используется только десятичная система (или только шестнадцатеричная, или какая-нибудь другая), то при записи числа индекс обычно опускают.
Десятичная система использует десять различных знаков: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 – которые обозначают натуральные числа в порядке их возрастания от нуля до девяти. Число 10 является основанием десятичной системы. Оно не имеет специального знака, а обозначается с помощью двух первых символов этой системы.
Например, запись 483,56 в десятичной системе означает, что данное число складывается из четырех сотен (), восьми десяток (), трех единиц (), пяти десятых частей единицы () и шести сотых частей единицы (). Другими словами, мы можем записать:
. (2.1)
Двоичная система
Двоичная (бинарная) система счисления является самой простой из всех позиционных систем. Она содержит только два символа 0 и 1, и используется в компьютерной технике благодаря своей простоте и высокой надежности. Двоичная система была изобретена великим немецким ученым Готфридом Вильгельмом Лейбницем (1646-1716), который использовал ее в созданной им механической счетной машине. В первом столбце табл. 2.1 приведены десятичные числа, а во втором – соответствующие им двоичные числа.
Таблица 2.1
Десятичное число
|
Бинарный код |
Код Грея |
Десятичное число
|
0 1 2 3 = 2 + 1 4 5 = 4 +1 6 = 4 + 2 7 = 4 + 2 + 1 8 9 = 8 + 1 10 = 8 + 2 11 = 8 + 2 + 1 12 = 8 + 4 13 = 8 + 4 + 1 14 = 8 + 4 + 2 15 = 8 + 4 + 2 + 1 |
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 |
0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000 |
0 1 2 = 3 – 1 3 4 = 7 – 3 5 = 7 – 3 +1 6 = 7 – 1 7 8 = 15 – 7 9 = 15 – 7 + 1 10 = 15 – 7 + 3 – 1 11 = 15 – 7 + 3 12 = 15 – 3 13 = 15 – 3 + 1 14 = 15 – 1 15 |
Предположим, что нам нужно преобразовать двоичное число с дробной частью 1100,1011 в более привычное десятичное число. В табл. 2.2 показано, как осуществляется такое преобразование.
Таблица 2.2
Двоичное число |
Десятичное число | |||||||
Целая часть |
Дробная часть | |||||||
1 |
1 |
0 |
0, |
1 |
0 |
1 |
1 | |
+ |
+ |
+ |
+ |
+ |
+ |
+ |
= |
Обратное преобразование десятичного числа d в двоичное число (бинарный код) осуществляется в соответствии со следующим алгоритмом. Присваиваем числу d индекс (), и ищем целое число, удовлетворяющее неравенству
, . (2.2)
Если , то задача выполнена – искомое двоичное число содержит единицу в старшем разряде инулей за ней.
Если , то вычисляем разность, и ищем для нее соответствующее число, пользуясь формулой (2.2) с. Операцию вычисления разницыи нахожденияповторяем до тех пор, пока при каком-либоне выполнится условие:.
Очевидно, что (т.е.). При построении искомого бинарного числа используют правило: численные значениясоответствуют разрядам бинарного кода, в котором стоят единицы. Остальные разряды заполняются нулями.
Используем это правило для нахождения бинарного кода десятичного числа 108,5. Согласно формуле (2.2), получаем: .
Искомое двоичное число равно: 1101100,1. Первая единица слева в записи числа соответствует 6 разряду, вторая за ней – пятому разряду. Четвертого разряда нет, поэтому за двумя первыми единицами записываем ноль. Третий и второй разряды есть – после нуля записываем две единицы. Единичного и нулевого разрядов также нет – после двух единиц записываем два нуля. Минус первый разряд есть – поэтому после запятой записываем единицу.
Арифметические операции в двоичной системе осуществляются так же, как и в десятичной («столбиком»). Например, возьмем числа 0111 () и 0101 (), и произведем операции сложения и умножения:
,
В результате получим 1100 () и 100011 (), что и следовало ожидать.
Код Грея
Помимо двоичных чисел на практике применяются и другие коды, использующие два знака: 0 и 1. В этом разделе мы познакомимся с кодом Грея. При сортировке данных естественным представлением является обычное целочисленное описание, поскольку среди десяти цифр каждая на 1 больше предыдущей. При переходе к двоичному описанию эта естественность исчезает. Рассмотрим битовое представление чисел 6, 7, 8 и 9:
0110 0111 1000 1001.
Числа 6 и 7, а также 8 и 9 отличаются друг от друга на один бит. Однако числа 7 и 8 не имеют между собой ничего общего! Это свойство представления может вызвать большие проблемы при решении задач, требующих систематизации числовых данных. Для решения проблемы неоднородности представления используется код Грея.
Код Грея – система нумерации, в которой два соседних значения различаются только в одном разряде.
Код Грея показан в третьем столбце табл. 2.1. Наиболее часто на практике применяется рефлексивный двоичный код Грея, хотя в общем случае существует бесконечное множество кодов Грея для систем счисления с любым основанием. В большинстве случаев, под термином «код Грея» понимают именно рефлексивный бинарный код Грея. Название рефлексный (отражённый) двоичный код происходит от факта, что вторая половина значений в коде Грея эквивалентна первой половине, только в обратном порядке, за исключением старшего бита, который просто инвертируется. Если же разделить каждую половину ещё раз пополам, свойство будет сохраняться для каждой из половин половины и т.д.
Код Грея был разработан Фрэнком Греем, исследователем Bell Labs. Он использовал этот код в своей импульсной системе связи (на него был получен патент № 2632058).
При преобразовании бинарного кода в десятичное число мы умножаем ноль или единицу на , где – номер позиции бита в бинарном коде (; и т.д.), а затем суммируем полученные результаты.
При преобразовании кода Грея в десятичное число мы умножаем ноль или единицу на (), где – номер позиции бита в коде Грея (; и т.д.). Дальше вычитаем из результата, соответствующего старшей единице, результат, соответствующий единице меньшего разряда, прибавляем результат, соответствующий единице еще более меньшего разряда и т.д. (смотри последний столбец табл. 2.1).
Троичная система счисления
Троичная система счисления – позиционная система счисления с целочисленным основанием равным 3. Она существует в двух вариантах: несимметричная и симметричная троичные системы. Несимметричная система обычно использует символы: 0, 1 и 2. Симметричная: –1, 0, +1. В табл. 2.3 показаны десятичные числа и соответствующие им числа в троичной системе счисления.
Таблица 2.3
Десятичная |
-3 |
-2 |
-1 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
Троичная несимметричная |
-10 |
-2 |
-1 |
0 |
1 |
2 |
10 |
11 |
12 |
20 |
21 |
22 |
100 |
Троичная симметричная |
11 |
100 |
Элементы троичной системы существовали еще у древних шумеров. Полноценную симметричную троичную систему впервые предложил итальянский математик Фибоначчи (Леонардо Пизанский) (1170–1250). Симметричная троичная система позволяет изображать отрицательные числа, не используя отдельный знак минуса.
В момент зарождения компьютерной техники троичная система составляла серьезную конкуренцию двоичной системе. Ее преимущество заключается в том, что она обеспечивает наибольшую плотность записи чисел по сравнению с другими целочисленными системами. Поясним это на следующем примере.
Предположим, что в компьютере мы используем числа в позиционной системе с целочисленным основанием . При этом каждое число имеет максимумразрядов. Значит, для сохранения числа в памяти компьютера требуетсяячеек памяти, причем каждая ячейка должна быть способна находиться всостояниях. Аппаратные затраты составляют:.
Используя систему с основанием иразрядов, мы способны представитьразличных чисел. Эффективность применяемой в компьютере системы счисления можно оценить с помощью следующего числового критерия:
. (2.3)
Чем больше чисел мы можем представить в данной системе счисления, и чем меньше при этом аппаратные затраты, тем эффективнее система по данному критерию.
Чаще критерий эффективности используют в такой форме
. (2.4)
Практически критерий (2.4) равнозначен критерию (2.3), однако удобнее в использовании. Равнозначность основана на факте: если , то. График функциипоказан на рис. 2.1.
Рис.2.1. График функции
Эта функция имеет максимум для . При целых значенияхмаксимум достигается для= 3.
;
;
;
.
Таким образом, наиболее эффективной по критерию (2.4) является троичная система счисления (используемая в троичных компьютерах), следом за которой идут двоичная система счисления (традиционно используемая в большинстве распространённых компьютеров) и четверичная система счисления.
В 1958 году Николай Петрович Брусенцов из МГУ построил первую серийную электронную троичную ЭВМ «Сетунь» на ячейках из ферритдиодных магнитных усилителей переменного тока, работавших в двухбитном троичном коде, четвёртое состояние двух битов не использовалось. В 1970 году Брусенцов построил вторую серийную электронную троичную ЭВМ «Сетунь-70».
В 1973 году в США впервые был создан экспериментальный троичный компьютер, а в 2008 году там же была построена троичная цифровая компьютерная система TCA2 на 1484-х интегральных транзисторах.
Тем не менее, в настоящее время двоичные компьютеры доминируют в компьютерной технике благодаря своей простоте и высокой надежности.
Восьмеричная и шестнадцатеричная системы счисления
Позиционную систему счисления можно построить по любому основанию. Однако наибольшее практическое значение имеют: двоичная, десятичная, восьмеричная и шестнадцатеричная. Причем, последние две используются, в основном, не для вычислений, а для представления двоичного кода в форме, удобной для человека.
В табл. 2.4 представлено 24-битное двоичное слово и соответствующие ему 8-ричный и 16-ричный коды.
Таблица 2.4
Двоичный код |
1011001111000101100010112 |
Восьмеричный код |
547426138 |
Шестнадцатеричный код |
B3C58B16 |
Очевидно, что человеку легче воспринимать двоичный код в форме 8-ричного или 16-ричного кодов. При использовании 8-ричного кода три бита двоичного слова преобразуются в один символ. При использовании 16-ричного слова каждые четыре бита двоичного слова преобразуются в один символ. В табл. 2.5 показано, как осуществляется это преобразование. Как можно видеть, шестнадцатеричные числа обозначаются с помощью 10 арабских цифр и шести букв латинского алфавита.
Таблица 2.5
8-ричное число
|
Бинарный код |
16-ричное число
|
Бинарный код |
0 1 2 3 4 5 6 7
|
000 001 010 011 100 101 110 111
|
0 1 2 3 4 5 6 7 8 9 A B C D E F |
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 |