Методичка Теория информации

Из соотношений (3) и (4) непосредственно вытекают два способа перевода целых чисел из десятичной системы счисления в систему с произвольным основанием q.

Способ 1 является следствием соотношений (3), предполагающий следующий алгоритм перевода:

1.Целочисленно разделить исходное число (Z10) на основании новой системы счисления (q) и найти остаток от деления — это будет цифра 0-го разряда числа Zq.

2.Частное от деления снова целочисленно разделить на q с выделением остатка; процедуру продолжать до тех пор, пока частное от деления не окажется меньше q.

3.Образовавшиеся остатки от деления, поставленные в порядке, обратном порядку их получения, и представляют Zq.

Пример. Выполнить преобразование 12310 Z5

Остатки от деления (3, 4) и результат последнего целочисленного деления (4) образуют обратный порядок цифр нового числа. Следовательно, 12310 4435 .

Способ 2 вытекает из соотношения (4), действия производятся в соответствии со следующим алгоритмом:

1.Определить m 1 — максимальный показатель степени в представлении числа по форме (2) для основания q.

2.Целочисленно разделить исходное число (Z10) на основание новой системы счисления в степени m 1 ( т . е . q m - 1 ) и найти остаток от деления; результат деления определит первую цифру числа Zq.

3.Остаток от деления целочисленно разделить на gm-2, результат деления принять за вторую цифру нового числа; найти остаток; продолжать эту последовательность действий, пока показатель степени q не достигнет значения 0.

Продемонстрируем действие алгоритма на той же задаче, что была

рассмотрена выше.

Определить m 1 можно либо путем подбора (50 = 1 < 123; 51 = 5 < 123; 52 =

25< 123; 53 = 125 > 123, следовательно, m 1 2 ), либо логарифмированием с оставлением целой части логарифма (1оg5123 = 2,99, т.е. m 1 2 ). Далее:

b 123 \ 52 4			1	23 mod 52		23	i 2 1	1
2
b 23 \ 51	4			0	23 mod 51	3	i 0
1

Алгоритмы перевода Z g Z w явно вытекают из представлений (1) или (2):

необходимо Zp представить в форме многочлена и выполнить все операции по правилам десятичной арифметики.

Пример. Выполнить преобразование 4435 Z10 .

Решение: 4435 4 52 4 51 3 50 4 25 4 5 3 1 12310 .

Необходимо еще раз подчеркнуть, что приведенными алгоритмами удобно пользоваться при переводе числа из десятичной системы в какую-то иную или наоборот. Они работают и для перевода между любыми иными системами

11

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

По этой причине переход, например, Z3 Z8 проще осуществить через промежуточное преобразование к десятичной системе Z3 Z10 Z8 . Ситуация, однако, значительно упрощается, если основания исходной и конечной систем счисления оказываются связанными соотношением p qr , где r — целое число

(естественно, большее 1) или r 1n ( n 1, целое).

Контрольный тест №2:

1)Результат вычисления выражения 27 24 1 имеет в двоичной системе счисления вид …

a)10010100

b)70040001

c)20020001

d)10010001

2)Результат вычисления выражения 16 8 4 4 1 имеет в двоичной системе счисления вид …

a)112001

b)122001

c)10010001

d)10011001

3)Если числа в двоичной системе счисления имеют вид 10012 и 1012, то их разность в десятичной системе счисления равна …

a)8

b)2

c)4

d)900

4)Последняя цифра суммы чисел 578 и 568 в восьмеричной системе счисления равна

a)6

b)3

c)5

d)С

5)Последняя цифра суммы чисел 5516 и 5616 в шестнадцатеричной системе счисления равна

a)1

b)6

c)3

d)В

6)Укажите упорядоченную по возрастанию последовательность значений

a)5516 558 557

b)558 557 5516

c)557 558 5516

d)558 5516 557

7)В записи числа в двоичной системе счисления могут присутствовать

12

a)цифры от 1 до 5

b)шесть нечетных цифр

c)цифры 0 и 1

d)буквы от А до Е

3. Высказывания и предикаты

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

Алгеброй A называется некоторая совокупность определенных элементов X, с заданными над ними определенными операциями f (часто определяемые по сходству с операциями сложения и умножения чисел), которые удовлетворяют определенным свойствам – аксиомам алгебры.

Операция f называется n-местной, если она связывает n операндов (объектов – участников этой операции).

Совокупность операций алгебры A называется ее сигнатурой, а совокупность элементов алгебры – носителем алгебры.

Утверждение (высказывательная форма) – основная единица, неделимая с точки зрения отражения смысла информации (семантики).

Высказывание – некоторое повествовательное утверждение, про которое можно однозначно сказать ("сразу посмотрев на него"), истинно оно или ложно. Эти два значения всевозможных высказываний обозначаются "истина" и "ложь", "true" и "fаlse" или "1" и "0".

Переменная, значениями которой могут быть лишь значения "1" или "0",

называется логической переменной или булевой переменной.

Предикат – высказывательная форма с логическими переменными (множество значений этих переменных вполне определено), имеющая смысл при любых допустимых значениях этих переменных. Количество переменных в записи предиката называется его местностью.

Простые высказывания или предикаты не зависят от других высказываний или предикатов ("не разбиваемы на более простые"), а сложные – зависят хотя бы от двух простых.

Пример. Выражение "х = у" – предикат, "х > 5" – предикат, а "7 > 5" – высказывание.

Логической (булевой) функцией f(х) называется некоторая функциональная зависимость, в которой аргумент х – логическая переменная с заданным множеством изменений аргумента, а значения функции f(x) берутся из двухэлементного множества R(f) = {1,0}.

Пример. Заданы предикаты вида р = "число х делится нацело на 3" и q = "у – день недели". Найдем множество истинности предикатов р и q, если x {1,4,6,16,20,24}, y {первый, второй, четверг, 1999, зима, выходной, праздник, воскресенье}. Получаем, что R(p) = {6, 24}; R(q) ={четверг, воскресенье}.

13

Множество логических переменных		x, y X	с определенными над ним
операциями:	x – отрицания или инверсии,	x y	– логического сложения или
дизъюнкции,	x y – логического умножения или конъюнкции называется алгеброй

предикатов (и высказываний), если эти операции удовлетворяют следующим

аксиомам:

1.Аксиома двойного отрицания: x x .

2.Аксиомы переместительности операндов (относительно операций дизъюнкции и

конъюнкции): x y y x ,			x y y x .
3.	Аксиомы	переместительности		операций дизъюнкции		и	конъюнкции
(относительно операндов): (x y) z x y z , (x y) z x							y z .
4.	Аксиомы одинаковых операндов: x x x , x x x .
5.	Аксиомы поглощения (множителем — множителя-суммы или слагаемым —
слагаемого-произведения): x x y x ,					x x y x .
6.	Аксиомы распределения операции (дизъюнкции относительно конъюнкции и
наоборот):
	x y z x y x z ,			x y z x y x z .
7.	Аксиомы	де Моргана	(перенесения		бинарной операции	на	операнды):

x y x y , x y x y .

8. Аксиомы нейтральности (взаимноинверсных множителей или слагаемых): x y y x , x y y x .

9. Аксиома существования единицы (истина, true, 1) и нуля (ложь, false, 0), причем,

0 1, 1 0 , x x 1, x x 0 .

Из этих аксиом следует ряд полезных соотношений, например,

x 1 x,	x 0 0,	x x 0,
x 1 1,	x 0 x,	x x 1.

Три базовые операции алгебры предикатов определяются таблицей их значений, так как в алгебре предикатов из-за дискретности значений логических функций часто используется табличная форма задания функции. Булеву функцию n переменных можно полностью определить таблицей из 2n строк.

Итак, эти операции определяются совмещенной таблицей значений вида

x	y	x	x y	x y
0	0	1	0	0
0	1	1	0	1
1	0	0	0	1
1	1	0	1	1

Такая таблица всех значений некоторой логической функции называется

таблицей истинности этой функции.
								z
Пример. Составим таблицу истинности функции										x x y . Эта
таблица имеет вид
	x	y	x			y	x x y		z
					x						x x y
	0	0	1	0			0		1
	0	1	1	1			0		1
	1	0	0	0			0		1
	1	1	0	0			0		1
				14

самостоятельно таблицу истинности для

Следовательно, функция тождественно-истинна. Это можно было доказать (проверить) и с помощью аксиом:

z x x y x x y x x y 1 y 1.

Кроме указанных трех базовых операций можно с их помощью ввести еще следующие важные операции алгебры предикатов (можно их назвать небазовыми

операциями):	x y – принимает значение “ложно”, тогда и только тогда,
1. Импликация

когда первое высказывание x (посылка, причина) “истина”, а второе у (заключение,

следствие) – “ложно”. Формула перехода: x y x y . (!) Составьте

x y x y .

2. Эквивалентность формул x y означает совпадение их значений истинности для всех возможных наборов входящих в них переменных. Формула перехода: x y x y x y . (!) Составьте самостоятель-но таблицу истинности для x y x y x y .

3.Тавтология – это формула, истинная при любой интерпретации входящих в нее переменных. (!) Составьте таблицу истинности для x x .

4.Противоречие – это формула, ложная при любой интерпретации входящих в

нее переменных. (!) Составьте самостоятельно таблицу истинности для

x x .

Операции импликации и эквивалентности, хотя и являются часто используемыми, но не базовые, ибо они определяемы через три введенные выше базовые операции. Нетрудно определить их таблицы истинности (проделайте это самостоятельно с помощью правых частей приведенных равенств).

В логических формулах определено старшинство операций, например:

скобки, отрицание, конъюнкция, дизъюнкция.

Всегда истинные формулы называют тавтологиями.

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

Задача упрощения логического выражения состоит в преобразовании его к более простому (по числу переменных, операций или операндов) эквивалентному выражению. Наиболее простой вид получается при сведении функции к постоянной – 1 (истина) или 0 (ложь).

Пример. Упростим:

f x, y x y x y x y x y x y x y

=(аксиома дистрибутивности)=

x x y x y

=(аксиома нейтральности)=

y x y

=(аксиома дистрибутивности)=

y x y y y x 1 y x x y

15

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

Пример.	Докажем равенство логических выражений: x y x y x x .
Используя	аксиомы	алгебры	предикатов,	получаем			равенства

x y x y x x y x y x x y x x .

Левая часть равенства приведена к правой части, то есть данное равенство доказано полностью.

Такие задачи решаются с помощью аксиом алгебры предикатов одним из следующих способов:

правая часть равенства приводится к левой части;

левая часть равенства приводится к правой части;

обе части равенства приводятся к третьему выражению.

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

Информационно-логическая (инфологическая) задача – это задача, в

которой необходимо установить некоторые информационные или логические связи и сделать необходимые причинно-следственные логические выводы. Эти задачи возникают в различных областях и часто являются плохо формализованными и структурированными. Их нужно хорошо формализовать и структурировать. Насколько хорошо будет возможно это сделать – настолько хорошо и полно будет решена рассматриваемая проблема или задача. Рассмотрим пример информационно-логической задачи (например, решаемой следователем, знакомым с алгеброй предикатов).

Пример. Операции конъюнкции, дизъюнкции, отрицания алгебры высказываний – аналоги союзов "и", "или", приставки "не", используемых (возможно, интуитивно) при выражении мысли человеком.

Законы алгебры высказываний и предикатов сходны с правилами, по которым человек делает умозаключения, доказывает, мыслит. Чтобы переложить на ЭВМ работы мыслительного характера, эти правила необходимо строго сформулировать, формализовать. Это позволяет осуществить алгебра логики. Приведем некоторые аксиомы логики – науки, изучающей методы доказательства и опровержения утверждений.

1. Аксиома исключения третьего: либо имеет место высказывание, либо его отрицание.

2. Аксиома противоречия: высказывания и его отрицание не могут иметь места одновременно.

3. Аксиома двойного отрицания: двукратное отрицание какого-либо утверждения равносильно исходному утверждению.

4. Аксиома тождества: всякое высказывание тождественно самому себе.

Если высказывания x и y связаны друг с другом отношением x y , то

говорят, что высказывание y следует из высказывания x (или y – следствие x); если множество истинности Х высказывания х содержит множество истинности Y высказывания y, то высказывание x – условие, высказывание y – заключение, а само соотношение x y – вывод.

Доказательство формальных математических утверждений (теорем) – последовательность корректных выводов, ведущих от условия к заключению.

16

Алгебра логики помогает доказывать теоремы (дает общие подходы и методы доказательства).

Общий подход к доказательству теорем методом от противного, обратных и противоположных теорем можно формализовать с помощью алгебры логики.

Контрольный тест №3:

1)Из заданных логических функций тождественно истинной является

a)А и не А или не А

b)А и не В или А

c)А или не А или А

d)А и не А или В

2)Из заданных логических функций тождественно истинной является

a)А и не А или В

b)А и не В или А

c)А и не А или не А

d)А или не В или не А

3)Из заданных логических функций эквивалентной А является

a)А и не А или не А

b)А и не В или А

c)А и не А или В

d)А и не В и А

4)Для простого высказывания В логическое отрицание обозначается

a)B

b)B

c)& B

d)B

5)Высказыванию «А не является max (A,B,C) и не является min (A,B,C)» соответствует логическое выражение

a)(A < B) или (A > C) и (A < C) или (A > B)

b)(A > B) или (A > C)

c)(A < B) и (A > C) или (A < C) и (A > B)

d)(A < B) и (A < C)

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

Любые сообщения измеряются в байтах, килобайтах, мегабайтах, гигабайтах, терабайтах, петабайтах и эксабайтах, а кодируются, например, в компьютере, с помощью алфавита из нулей и единиц, записываются и реализуются в ЭВМ в битах.

Приведем основные соотношения между единицами измерения сообщений: 1 бит (binary digit – двоичное число) = 0 или 1,

1 байт = 8 бит, 1 килобайт (1Кб) = 210 байт = 213 бит,

1 мегабайт (1Мб) = 220 байт = 223 бит, 1 гигабайт (1Гб) = 230 байт = 233 бит,

17

1 терабайт (1Тб) = 240 байт = 243 бит, 1 петабайт (1Пб) = 250 байт = 253 бит, 1 эксабайт (1Эб) = 260 байт = 263 бит.

Пример. Найти неизвестные х и у, если верны соотношения:

128y Kб 32x бит ;
		Мб 2		байт .
	x		y
2

Выравниваем единицы измерения информации:

27y Kб 27y 13 бит ;
	x	Мб 2	x 20	байт .
2

Подставляя в уравнения и отбрасывая размерности информации, получаем:

27y 13 25x ;

2x 20 2y .

Отсюда получаем систему двух алгебраических уравнений:

7 y 13 5x;

x 20 y.

или, решая эту систему, окончательно получаем, x = –76,5, у = –56,5.

Для измерения информации используются различные подходы и методы, например, с использованием меры информации по Р. Хартли и К. Шеннону.

Количество информации – число, адекватно характеризующее разнообразие (структурированность, определенность, выбор состояний и т.д.) в оцениваемой системе. Количество информации часто оценивается в битах, причем такая оценка может выражаться и в долях бит (так речь идет не об измерении или кодировании сообщений).

Мера информации – критерий оценки количества информации. Обычно она задана некоторой неотрицательной функцией, определенной на множестве событий и являющейся аддитивной, то есть мера конечного объединения событий (множеств) равна сумме мер каждого события.

Рассмотрим различные меры информации.

Возьмем меру Р. Хартли. Пусть известны N состояний системы S (N опытов с различными, равновозможными, последовательными состояниями системы). Если каждое состояние системы закодировать двоичными кодами, то длину кода d необходимо выбрать так, чтобы число всех различных комбинаций было бы не меньше, чем N:

2d N .

Логарифмируя это неравенство, можно записать: d log 2 N .

Наименьшее решение этого неравенства или мера разнообразия множества состояний системы задается формулой Р. Хартли:

H log 2 N (бит).

Пример. Чтобы определить состояние системы из четырех возможных состояний, то есть получить некоторую информацию о системе, необходимо задать 2 вопроса. Первый вопрос, например: "Номер состояния больше 2?". Узнав ответ ("да", "нет"), мы увеличиваем суммарную информацию о системе на 1 бит

18

( I log 2 2). Далее необходим еще один уточняющий вопрос, например, при ответе

"да": "Состояние – номер 3?". Итак, количество информации равно 2 битам

( I log 2 4).

Если во множестве X x1, x2 ,...,xn искать произвольный элемент, то для его нахождения (по Хартли) необходимо иметь не менее log 2 n (единиц)

информации.

Уменьшение Н говорит об уменьшении разнообразия состояний N системы. Увеличение Н говорит об увеличении разнообразия состояний N системы. Мера Хартли подходит лишь для идеальных, абстрактных систем, так как в

реальных системах состояния системы не одинаково осуществимы (не равновероятны).

Для таких систем используют более подходящую меру К. Шеннона. Мера Шеннона оценивает информацию отвлеченно от ее смысла:

n

I pi log 2 pi ,

i 1

где n – число состояний системы; рi – вероятность (относительная частота) перехода системы в i-е состояние, а сумма всех pi должна равняться 1.

Если все состояния рассматриваемой системы равновозможны, равновероятны, то есть pi 1/ n , то из формулы Шеннона можно получить (как

частный случай) формулу Хартли:

I log 2 n.

Пример. Если положение точки в системе из 10 клеток известно, например, если точка находится во второй клетке, то есть рi = 0, i = 1, 3, 4, …, 10, р2 = 1. Получаем количество информации, равное нулю, т.е. I log 2 1 0 .

Обозначим величину fi nlog 2 pi .

Тогда из формулы К. Шеннона следует, что количество информации I можно понимать как среднеарифметическое величин fi , то есть величину fi можно интерпретировать как информационное содержание символа алфавита с индексом i и величиной pi вероятности появления этого символа в любом сообщении (слове), передающем информацию.

Положительная сторона формулы Шеннона – ее отвлеченность от смысла информации. Кроме того, в отличие от формулы Хартли, она учитывает различность состояний, что делает ее пригодной для практических вычислений. Основная отрицательная сторона формулы Шеннона – она не распознает различные состояния системы с одинаковой вероятностью.

Контрольный тест №4:

1)Минимально необходимое для записи целого числа 224 количество байт, равно

a)4

b)3

c)24

d)5

2)Количество информации, содержащееся в одном разряде двоичного числа, равно…

19

a)2 бита

b)2 байта

c)1 байт

d)1 бит

3)Укажите упорядоченную по убыванию последовательность значений

a)4 байта, 3 байта, 30 бит

b)3 байта, 30 бит, 4 байта

c)4 байта, 30 бит, 3 байта

d)30 бит, 4 байта, 3 байта

4)Укажите упорядоченную по возрастанию последовательность значений

a)2 байта, 10 бит, 20 бит

b)10 бит, 20 бит, 2 байта

c)10 бит, 2 байта, 20 бит

d)20 бит, 10 бит, 2 байта

5)Выберите вариант, в котором объемы памяти расположены в порядке убывания.

a)1010 байт, 2 байта, 1 Кбайт, 20 бит, 10 бит

b)1 Кбайт, 1010 байт, 20 бит, 2 байта, 10 бит

c)1010 байт, 1 Кбайт, 2 байта, 20 бит, 10 бит

d)1010 байт, 1 Кбайт, 20 бит, 2 байта, 10 бит

6)Выберите вариант, в котором объемы памяти расположены в порядке возрастания.

a)15 бит, 20 бит, 2 байта, 1 Кбайт, 1010 байт

b)15 бит, 2 байта, 20 бит, 1 Кбайт, 1010 байт

c)15 бит, 2 байта, 20 бит, 1010 байт, 1 Кбайт

d)15 бит, 20 бит, 2 байта, 1010 байт, 1 Кбайт

7)Выберите вариант, в котором единицы измерения информации расположены в порядке возрастания.

a)гигабайт, мегабайт, терабайт

b)терабайт, мегабайт, гигабайт

c)мегабайт, терабайт, гигабайт

d)мегабайт, гигабайт, терабайт

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

a)гигабайт, мегабайт, килобайт

b)килобайт, гигабайт, мегабайт

c)килобайт, мегабайт, гигабайт

d)мегабайт, гигабайт, килобайт

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

a)килобайт, гигабайт, терабайт

b)терабайт, мегабайт, килобайт

c)гигабайт, мегабайт, терабайт

d)мегабайт, терабайт, килобайт

5. Информационная безопасность

Информационный процесс – процесс получения, создания, сбора, обработки, накопления, хранения, поиска, распространения и использования

20