Предлагаемый справочник составлен на базе обязательного минимума содержания среднего (полного) и основного…

Предлагаемый справочник составлен на базе обязательного минимума содержания среднего (полного) и основного общего образования и стан­дарта основного общего образования по информатике и ИКТ. Однако, как при подготовке к ГИА-9, так и при его сдаче учащимся понадобятся до­полнительные сведения по алгоритмам, структурам данных, теории игр, а также базовые навыки программирования.

§ 1 Системы счисления

Определение. Система счисления — это способ наименования и представления чисел с помощью символов. Такие символы в любой си­стеме счисления называются цифрами.

Определение. Алфавит системы счисления — это совокупность сим­волов, используемых в данной системе счисления.

Все системы счисления подразделяются на два класса — позиционные и непозиционные.

В непозиционных системах счисления от положения цифры в записи числа не зависит величина, которую она обозначает.

1.1. Позиционные системы счисления

В позиционных системах счисления величина, обозначаемая цифрой в записи числа, зависит от её позиции. Количество различных цифр Р, ис­пользуемых в позиционной системе, определяет название системы счис­ления и называется основанием р-ой системы счисления. Например, си­стема счисления, в основном применяемая в современной математике, яв­ляется позиционной десятичной системой, её основание равно десяти.

Любое число NВ позиционной системе счисления с основанием Р мо­жет быть представлено в виде многочлена от Р:

N = akpk + ak-1pk~l — I————— A1p1 + a0p0 + α-ip~1 + А_2р~2H——————— ,

Где N — число, Р — основание системы счисления (р > 1), αi— цифры числа (коэффициенты при степенях Р).

Числа вр-й системе счисления записывают в виде последовательно­сти цифр:

N = QkQk-I ■ ■ ■ CllClO, Q-1Q-2 • • • •

Запятая в последовательности отделяет целую часть числа от дробной (коэффициенты при неотрицательных степенях от коэффициентов при от­рицательных степенях).

1.2. Двоичная система счисления

В двоичной системе используется две цифры: 0 и 1. В этой системе любое число может быть представлено в виде

N = Akak—ι ■ ■ ■ Qiao, A-1A-2 ■ ■ ■, где щ принимает значения либо О, либо 1. Эта запись соответствует сумме степеней числа 2, взятых с ука­занными коэффициентами:

N = o⅛2fc — T α⅛-ι2fc 1 — T… dj2^ -T αθ2θ — T α-χ2 4 — T 0—22 2 .

Например:

1011101,01 = 1∙26+0∙25 + 1∙24 + 1∙23 + 1∙22+0∙21 + 1∙2o+0∙2~1 + 1∙2-2.

1.3. — Восьмеричная система счисления

В восьмеричной системе используется восемь цифр: 0,1, 2, 3,4, 5, 6, 7. Эта система счисления в ЭВМ используется как вспомогательная для за­писи информации в сокращённом виде. Для представления одной цифры восьмеричной системы используются три двоичных разряда (триада):

Цифра	Триада	Цифра	Триада
0	000	4	100
1	001	5	101
2	010	6	110
3	Oll	7	Ill

1.4. Шестнадцатеричная система счисления

Для обозначения цифр в шестнадцатеричной системе используется де­сять цифр: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 и латинские буквы А(10), В(11), C (12), D (13), E (14) и F (15). Эта система счисления так же, как и восьмерич­ная, в ЭВМ используется как вспомогательная для записи информации в сокращённом виде. Для представления одной цифры шестнадцатеричной системы используются четыре двоичных разряда (тетрада):

Цифра	Тетрада	Цифра	Тетрада
0	0000	8	1000
1	0001	9	1001
2	0010	А	1010
3	ООП	В	1011
4	0100	C	HOO
5	0101	D	HOl
6	ОНО	E	HlO
7	Olll	F	HH

1.5. Перевод чисел в десятичную систему счисления

Для того чтобы перевести число в десятичную систему, необходимо со­ставить сумму степенного ряда с основанием системы, в которой записано число, а затем найти значение этой суммы.

Пример 1. Перевести число 110110,01 из двоичной системы в деся­тичную.

Решение.

110110, Ol2 = 1 ∙25 + 1 ∙24+ 0∙ 23 + 1 ∙ 22 +1 ∙ 21+0-2°+ 0 • 2-1+1 ∙2-2 = = 32+ 16 + 4 + 2 + 0,25 = 54,25ιo∙

Ответ: 54,25ю-

Пример 2. Перевести число A2F,4 из шестнадцатеричной системы в десятичную.

Решение. A2F,4ι6 = 10 ∙ 162 + 2 ∙ 161+ 15 • 16° + 4 ∙ 16~1 = = 2560 + 32 + 15 + 0,25 = 26O7,25lo.

Ответ: 2607,25ι0÷

1.6. Перевод чисел из десятичной системы счисления

1. Для того чтобы перевести целое десятичное число в другую систему счисления, необходимо осуществлять последовательное деление десятич­ного числа и затем получаемых целых частных на основание той системы, в которую оно переводится, до тех пор, пока не получится частное, мень­шее делителя. Число в новой системе записывается в виде остатков отде­ления, начиная с последнего.

Пример 1. Перевести число 344 из десятичной системы в двоичную.

Решение. См. рис. 1.

Ответ: 10101IOOO2.

Рис. 1.

 

Пример 2. Перевести число 936 из десятичной системы в шестнадца­теричную.

Решение.

928 58 Ий

^⅛148 3

\Ю /

Рис. 2.

Ответ: 3A8ιβ∙

2. Для того чтобы перевести правильную десятичную дробь из деся­тичной системы счисления в другую, необходимо последовательно умно­жать эту дробь, а затем получаемые дробные части на основание той си­стемы, в которую она переводится. Умножение производится до тех пор, пока дробная часть не станет равной нулю или не будет достигнута требу­емая точность. В новой системе дробь записывается в виде целых частей произведений, начиная с первого.

Пример 1. Перевести число 0,532 из десятичной системы в двоичную с точностью до тысячных.

Решение.

128

2

Рис. 3.

Пример 2. Перевести число 0,974 из десятичной системы в шестнад­

Цатеричную с точностью до тысячных.

Рис. 4.

Ответ: 0,F95ιβ.

3. Для того чтобы перевести число, содержащее и целую, и дробную части, из десятичной системы счисления в другую, необходимо сначала перевести его целую часть, затем отдельно дробную часть. В ответе перед запятой следует записать целую часть, а после запятой — дробную часть.

Пример 1. Перевести число 344,532 из десятичной системы в двоич­ную с точностью до тысячных.

Решение. Переводим целую часть числа (см. рис. 1). Получаем 344ιo = 101011000г. Переводим с указанной точностью дробную часть (см. рис. 3). Получаем O,532ι0 = 0,100г — Дописываем после целой части дробную: 344,532ιo = 101011000,100г.

Ответ: 101011000,IOO2.

Пример 2. Перевести число 936,974 из десятичной системы в шест­надцатеричную с точностью до тысячных.

Решение. Переводим целую часть числа (см. рис. 2). Получаем 936ιo = 3A8i6∙ Переводим с указанной точностью дробную часть (см. рис. 4). Получаем O,974ι0 = 0,F95i6∙ Дописываем после целой части дробную: 936,974ιo = 3A8,F95ι6.

Ответ: 3A8,F95ι6.

1.7. Перевод чисел из двоичной системы счисления в восьме­ричную, шестнадцатеричную и обратно

1. Для того чтобы перевести число из двоичной системы в восьмерич­ную, необходимо выполнить следующие действия. Двигаясь от запятой влево и вправо, разбить двоичное число на группы по три разряда, допол­няя при необходимости нулями крайние левую и правую группы. Затем триаду заменить соответствующей восьмеричной цифрой.

Пример 1. Перевести число 10011001111,0101 из двоичной системы в восьмеричную.

Решение. OlOOll 001 Ill,010 100 = 2317,248

2 3 17 2 4

Ответ: 2317,248.

2. Для того чтобы перевести число из двоичной системы в шестнадца­теричную, необходимо выполнить следующие действия. Двигаясь от запя­той влево и вправо, разбить двоичное число на группы по четыре разряда, дополняя при необходимости нулями крайние левую и правую группы. За­тем тетраду заменить соответствующей шестнадцатеричной цифрой.

Пример 2. Перевести число 10111111011,100011 из двоичной системы в шестнадцатеричную.

Решение. 0101 1111 1011 , 1000 1Ю0 = 5FB,8C16

5 F В 8 C

Ответ: 5FB,8C16.

3. Для перевода числа из восьмеричной системы в двоичную доста­точно заменить каждую цифру этого числа соответствующим трёхразряд­ным двоичным числом (триадой), при этом отбрасывают незначащие нули в старших и младших (после запятой) разрядах.

Пример 3. Перевести число 204,4 из восьмеричной системы в двоич­ную.

Решение. 2 0 4,4 = 10000100,12

010 000 100 100

Ответ: 10000100,12-

4. Для перевода числа из шестнадцатеричной системы в двоичную до­статочно заменить каждую цифру этого числа соответствующим четырёх­разрядным двоичным числом (тетрадой), при этом отбрасывают незнача­щие нули в старших и младших (после запятой) разрядах.

Пример 4. Перевести число 6C3,A из шестнадцатеричной системы в двоичную.

Решение. 6 C 3 , А = 11011000011, IOl2

ОНО HOO ООП 1010

Ответ: 11011000011,IOl2.

5. Перевод из восьмеричной в шестнадцатеричную систему и обратно осуществляется через двоичную систему с помощью триад и тетрад.

Пример 5. Перевести число 135,14 из восьмеричной системы счисле­ния в шестнадцатеричную.

Решение.

1 3 5,14 = 1011101,OOll2= OlOl 1101 ,000 =5D,3,6

OθT 011 101 001 100 5 ~iΓ 3

Ответ: 5D,3iβ∙

1.8. Арифметические операции в позиционных системах счисления

1. При сложении чисел в произвольной позиционной системе счис­ления с основанием Р в каждом разряде производится сложение цифр слагаемых и цифры, переносимой из соседнего младшего разряда, если она имеется. При этом необходимо учитывать, что если при сложении чи­сел получилось число, большее или равное Р, то его представляют в виде Рк + Ь, где К ∈ N, B∈ Nq, 0 ≤ B ≤ р — 1 — остаток от деления полученно­го числа на основание системы счисления. Число BЯвляется количеством единиц в данном разряде, а число К — количеством единиц переноса в следующий разряд.

Пример 1. Выполнить сложение двоичных чисел:

X = 1011,1, Y = 1101,01 и Z = 11101,11.

Решение.

121J 21 1

+ 1011,1

+ 1101,01

11101,11

110110.10

Ответ: 110110, I2.

Пример 2. Выполнить сложение шестнадцатеричных чисел: X = 5A,B, Y = 9F3,C1 и Z = A58,F.

Решение.

1112

Ответ: 14A7,61i6∙

2. При вычитании чисел в р-ой системе счисления цифры вычитают­ся поразрядно. Если в рассматриваемом разряде необходимо от меньше­го числа отнять большее, то занимается единица следующего (большего) разряда. Занимаемая единица равна р единицам этого разряда (аналогич­но, когда мы занимаем единицу в десятичной системе счисления, то зани­маемая единица равна 10).

Пример 1. Найти разность двоичных чисел:

11001001,01 — 111011,11.

Решение. См. рис. 5 а.

С9,4

ЗВ. С

8D,8

∣16 + 4-12 = 8

16 + (9-1)- 11=13=D

(12-1)-3 = 8

Б)

Рис. 5.

Ответ: 10001101,12-

Пример 2. Найти разность шестнадцатеричных чисел: C9,4-3β,C.

Решение. См. рис. 5 б.

Ответ: 8Γ>,8I6∙

3. При умножении чисел Вр — ой системе счисления каждая цифра вто­рого множителя умножается последовательно на цифру каждого из раз­рядов первого множителя (так же, как и в десятичной системе счисле­ния). При этом необходимо учитывать, что если в результате умножения чисел получилось число, большее или равное Р, то его представляют в ви­де Рк + Ь, где К ∈ N, B ∈ N0, O≤δ≤p-l(b — остаток от деления полученного числа на основание системы счисления Р). Число BЗаписы­ваем в единицы данного разряда, а число К запоминаем и добавляем его к результату произведения в следующем разряде.

Полученные результаты умножения складываем согласно описанию, представленному в п. 1, и отделяем количество знаков после запятой, рав­ное сумме знаков после запятой у сомножителей.

Пример. Найти произведение восьмеричных чисел: 37,27 • 4,6. Решение.

X 37,27

4.6 + 27412 175 34 224,752

17+5=12=7-8+4

2+7+7=10=7-8+2

Ответ: 224,7528.

4. Деление чисел Вр — ой системе счисления производится так же, как и десятичных чисел, при этом используются правила умножения, сложения и вычитания чисел в Р -ой системе счисления (см. пп. 1 —3).

Пример. Найти частное отделения В2В,8 : 4, CВ шестнадцатеричной системе счисления.

Решение.

.B2B8∣ 4С

98_ |25Х

_ IAB

17С

2F8

2F8
О

Ответ: 25Λι6.

§ 2 Кодирование информации

2.1. Количество информации

Существует несколько подходов к измерению информации. Выделим два из них.