Методические указания
к выполнению контрольной работы
по
Дискретной математике
Екатеринбург 2003
Министерство образования Российской Федерации
Российский государственный профессионально-
педагогический университет
Инженерно-педагогический институт
Машиностроительный факультет
Кафедра высшей математики
Методические указания
к выполнению контрольной работы
по дисциплине
ДИСКРЕТНАЯ МАТЕМАТИКА
Для студентов заочной формы обучения специальности
030500 – профессиональное обучение
Екатеринбург 2003
Дискретная математика: Метод. указания к выполнению контр. работы. Екатеринбург: Российский гос. проф.-пед. ун-т, 2003. 40 с.
Составители: Конышева Людмила Константиновна,
Мешков Владислав Витальевич
Рецензент к. ф.-м. н., доц. Реймер Владимир Андреевич
В методических указаниях приведены основные положения теории и решения типовых задач, предлагаемые студентам заочной формы обучения для самостоятельного изучения курса «Дискретная математика».
Одобрены на заседании кафедры Высшей математики от 26.02.2003, протокол № 6
| Заведующий кафедрой высшей математики | Л. С. Чебыкин |
Одобрены методической комиссией машиностроительного факультета 17.03.2003, протокол № 7.
| Председатель методической комиссии машиностроительного факультета | В. П. Подогов |
© Российский государственный
профессионально-педагогический
университет, 2003.
© Конышева Л. К., Мешков В. В.
Двоичная система счисления
Система счисления – это правила записи чисел и алгоритмы выполнения арифметических операций с числами.
Двоичная система счисления так же, как и десятичная, является позиционной системой. Перечислим основные правила записи неотрицательных целых чисел в этой системе:
1. Запись числа – это последовательность особых знаков – цифр.
2. Для записи любого числа используются две цифры: 0 и 1.
3. Значение каждой цифры определяется в записи числа ее местом, которое называют разрядом. Счет разрядов ведется справа налево.
4. Единица каждого следующего разряда в 2 раза больше единицы предшествующего разряда.
Любое число в позиционной системе счисления может быть представлено в виде суммы разрядных слагаемых. Так в двоичной системе:
.
Запишем первые десять натуральных чисел в двоичной системе и их разложения на разрядные слагаемые:
| 02 | =010 | 1102 | =0+1·2+1·22=610 |
| 12 | =110 | 1112 | =1+1·2+1·22=710 |
| 102 | =0+1·2=210 | 10002 | =0+0·2+0·22+1·23=810 |
| 112 | =1+1·2=310 | 10012 | =2+0·2+0·22+1·23=910 |
| 1002 | =0+0·2+1·22=410 | 10102 | =0+1·2+0·22+1·23=1010 |
| 1012 | =1+0·2+1·22=510 |
Перевод из двоичной системы в десятичную выполняется по следующему правилу: надо записать двоичное число в виде суммы разрядных слагаемых и выполнить сложение в десятичной системе.
Рассмотрим пример обратного перехода, то есть перевод числа из десятичной системы в двоичную.
Пример
3910= X 2?
 |
В дальнейшем индексы, учитывающие основание системы, будем опускать, если это не приводит к путанице.
Действия сложения и умножения в двоичной системе выполняются по алгоритмам сложения и умножения “в столбик” в десятичной системе.
В основе этих действий лежат таблицы сложения и умножения однозначных двоичных чисел:
| + | ´ | |||||
Пример. Выполнить действия в двоичной системе счисления. Результат проверить в десятичной системе: 1011·(111+1001)+10011
Р е ш е н и е.
П р о в е р к а.
10112=1+1 2+0 22+1 23=1110
1112=1+1 2+1 22=710
10012=1+0 2+0 22+1 23=910
100112=1+1 2+0 22+0 23+1 24=1910
110000112=1+1 2+0 22+0 23+0 24+0 25+1 26+1 27=1+2+64+128=19510
11 (7+9)+19=19510