2.1.1 Системы счисления

1.

Дискретная математика
в программировании
Часть I
Костюк Ю.Л.
доктор технических наук, профессор
[email protected]

2.

Зачем нужна дискретная математика?
Если нужно понять некоторую задачу реального мира, первое,
что требуется – представить её модель и перевести решение
этой задачи в рамках модели. Именно дискретная математика даёт средства
и способы создания и описания таких моделей.
Дискретная математика – это математика
вычислительных процессов, её средствами создаются алгоритмы
решения задач в модели. Все вычисления современной
компьютерной науки практически полностью основаны
на дискретной математике.
Без элементарных знаний дискретной математики невозможно
не только создавать алгоритмы решения различных задач на
компьютере, но и осознанно использовать созданные алгоритмы.

3.

Изучаемые разделы
дискретной математики
Представление чисел в различных системах счисления
Кодирование данных различных видов
Элементы математической логики
Элементы теории множеств
Элементы теории графов

4.

Представление чисел
в различных системах
счисления
Число A в десятичной системе счисления:
am am-1 … a1 a0
A = am ·10m + am-1 ·10m – 1 + … a1 ·10 + a0
В системе счисления с основанием q:
bn bn-1 … b1 b0
A = bn ·qn + bn-1 ·qn – 1 + … b1 ·q + b0
(*)
Примеры:
101810 = 3FA16 = 17728 = 11111110102
«Цифры» больше 9 записывают буквами:
10 – A, 11 – B, 12 – C, 13 – D, 14 – E, 15 – F

5.

Задача перевода чисел из одной
системы счисления в другую
Преобразуем (*) в формулу Горнера:
A = (…(bn ·q + b n-1 )·q + … + b1 )·q + b0.
(**)
Вычисления для числа 3FA16 :
(3∙16 + 15)∙16 + 10 = 1018.
Преобразование числа А в систему счисления с основанием q (по формуле (**)):
1) деление А на q – остаток b0, частное - выражение в скобках,
2) деление частного на q – остаток b1 , частное – аналогично
процесс продолжается, пока частное >0
Вычисления для числа 1018 при q = 7 (остаток в скобках):
1018:7→145(3):7→20(5):7→2(6):7→0(2)→ 26537

6.

Числа в двоичной системе
счисления
Цифровая позиция в двоичной системе называется
двоичным разрядом или битом
010 = 02
410 = 1002
810 = 10002
1210 = 11002
110 = 12
510 = 1012
910 = 10012
1310 = 11012
210 = 102
610 = 1102
1010 = 10102
1410 = 11102
310 = 112
710 = 1112
1110 = 10112
1510 = 11112
Перевод из двоичной системы в шестнадцатеричную и обратно:
Каждые 4 бита двоичной записи, начиная справа, соответствуют
одной шестнадцатеричной цифре, а 3 бита – восьмеричной цифре.
3FA16 = 11 1111 1010 = 1 111 111 010 = 17728

7.

Числа в двоичной системе –
представление в памяти компьютера
Максимальное беззнаковое значение в m битах (m единиц):
2m – 1 + 2m – 2 + … + 22 + 21 + 1 = 2m – 1
Для отрицательных чисел - дополнительный код.
Из 0 (m бит нулей) вычитается положительное число, заём для старшего бита
из несуществующего бита, например:
00000000
– 00001010
11110110
Для проверки можно сложить эти два числа. Получится 0.
Максимальное число в дополнительном коде: 2m – 1 –1
Минимальное число в дополнительном коде: – 2m – 1
Примеры (m=8):
110 = 000000012
–110 =111111112
12710 = 011111112
–12810 = 100000002

8.

Задания для самостоятельной
работы
1
2
3
4 в дополнительном коде длиной 16 бит
Преобразовать число 2555 в 16-ричную систему.
Преобразовать число 2555 в 8-ричную систему
Преобразовать число 2555 в двоичную систему
Записать число -2555 в двоичной системе
Ответы на задания (числа) записывать цифрами:
0, 1, 2, . . . 9, A, B, . . ., F без пробелов.

9.

Спасибо за внимание