Методическое пособие 166

Покажем, как с помощью сдвигов и сложений выполняется умножение целых чисел. Пусть, например, требуется выполнить перемножение чисел 710 = 000001112 и 1110 = 000010112. Разложим одно из чисел на сумму степеней числа 2: 11=8+2+1. Т.е. 7 11 = 7 8 + 7 2 + 7 1. Умножение 7 на 8 означает арифметический сдвиг влево числа 7 на 3 разряда (получим 00111000), умножение 7 на 2 – сдвиг влево на 1 разряд (получим 00001110). Сложив эти числа, получим 01000110, к чему приплюсуем 7 1,

т.е. 00000111, получим ответ: 010011012. Сделав проверку, по-

лучим: 010011012 = 26 + 23 + 22 + 20 = 64 + 8 + 4 + 1 = 77.

Задания для самостоятельной работы

1. Выполнить сдвиги 1-3 вправо и влево на 1 и 2 разряда для следующих чисел (перевести число в двоичную систему, выполнить операцию и записать результат в 16-ричной системе):

19

Занятие 7 Логические операции

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

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

Логическое высказывание – это повествовательное предложение, в отношении которого имеет смысл утверждать, что оно истинно или что оно ложно. Высказывание должно удов-

летворять закону исключенного третьего, т.е. каждое выска-

зывание или истинно, или ложно, и не может быть одновременно и истинным, и ложным.

Примеры высказываний: «Сейчас идет снег» – может быть истинным и ложным одновременно; «Вашингтон – столица США» – истинное высказывание; «Частное от деления 10 на 2 равно 3» – ложное высказывание.

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

скими связками.

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

Чтобы обращаться к высказываниям, им назначают имена. Пусть через А обозначено высказывание «Тимур поедет летом на море», а через В – высказывание «Тимур летом отправится в горы». Тогда составное высказывание «Тимур летом побывает и на море, и в горах» можно кратко записать как «А и В». Здесь

20

«и» – логическая связка, А, В – логические переменные, которые могут принимать только два значения – «ложь» или «истина», обозначаемые, соответственно, «0» и «1».

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение. Таким образом, в алгебре логики значения всех операций и их операндов (т.е. логических высказываний) определены в двухэлементном множестве: {ложь; истина} (или

{false; true}, или {0; 1}).

В большинстве языков программирования реализован ограниченный набор логических операций, с помощью которого можно записать любое логическое выражение:

1. Операция, выражаемая словом «не», называется отрицанием (инверсией) и обозначается чертой над высказыванием или знаком . Высказывание истинно, когда A ложно, и ложно, когда A истинно. Данная операция является унарной, так как определена только для одного операнда (высказывания).

2. Операция, выражаемая связкой «и», называется конъ-

юнкцией (лат. conjunctio – соединение) или логическим умно-

тогда, когда оба высказывания А и В истинны.

3. Операция, выражаемая связкой «или» (в неразделительном, неисключающем смысле этого слова), называется

дизъюнкцией (лат. disjunctio – разделение) или логическим сложением и обозначается знаком (или плюсом). Высказывание А В ложно тогда и только тогда, когда оба высказывания А и В ложны.

4. Операция, выражаемая связкой «или» в исключающем смысле слова, называется строгой дизъюнкцией, сложением по модулю 2 или неравнозначностью и обозначается знаком .

Высказывание А В истинно тогда и только тогда, когда высказывания А и В не равны (А истинно, В ложно, или наоборот).

Операции 2-4 относятся к бинарным, т.е. определенным для двух операндов.

21

Результат логических операций принято записывать в виде так называемых таблиц истинности («истина» и «ложь» обозначаются, соответственно, «1» и «0»):

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

рядными (или побитовыми).

Пример. Выполнить поразрядные логические операции над числами С616, 9А16. Результаты записать в 16-ричной системе.

Решение.

Имеем: С616 = 110001102, 9А16 = 100110102.

Задания для самостоятельной работы

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

а) С916, A716; б) 8616, D516; в) 4A16, С216; г) 3E16, CA16;

д) 6116, В716; е) D716, E616; ж) C616, 4516; з) 4F16, 5D16.

22

Занятие 8 Измерение количества информации в сообщении

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

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

Если подбросить монету и проследить, какой стороной она упадет, то мы получим определенную информацию. Обе стороны монеты «равноправны», поэтому одинаково вероятно, что выпадет как одна, так и другая сторона. В таких случаях говорят, что событие несет информацию в 1 бит. Если положить в мешок два шарика разного цвета, то, вытащив вслепую один шар, мы также получим информацию о цвете шара в 1 бит.

23

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

События, о которых нельзя сказать, произойдут они или нет, пока не будет осуществлен эксперимент, называются слу-

чайными.

Раздел математики, в котором строится понятийный и математический аппарат для описания случайных событий, на-

зывается теорией вероятности.

Введем некоторые определения. Осуществление некоторого комплекса условий называется опытом, а интересующий нас исход этого опыта – благоприятным исходом. Тогда, если N – общее число опытов, а NA – количество благоприятных исходов (событие А произошло), то отношение NA/N называется относительной частотой появления события А. Очевидно, однако, что в разных сериях значение частоты может оказаться различным. Действительно, например, в серии из трех опытов по бросанию монеты может 2 раза выпасть орел и 1 раз решетка. Если благоприятным событием считать выпадение орла, то частота получается равно 2/3. Очевидно, что в другой серии она может быть равно 0 или 1 или 1/3. Однако, оказывается, что при увеличении количества опытов значение относительной частоты все меньше и меньше отклоняется от некоторой константы. Скачки могут быть, но все реже и реже. Это явле-

ние называется статистической устойчивостью частот, а

сама константа – вероятностью случайного события А. В случае, если все исходы опыта имеют равные шансы, то их вероятность равна p=1/n, где n – число возможных исходов.

Например, вероятность выпадения орла при бросании монеты – 1/2, вероятность вытянуть из урны белый шар (при условии, что там три шара – красный, синий, белый) – 1/3.

Таким образом, когда мы имеем дело со случайными событиями, имеется некоторая неопределенность. Введем в рас-

24

смотрение численную величину, измеряющую неопределенность опыта.

Энтропия – мера неопределенности опыта, в котором проявляются случайные события. Обозначим ее H.

Очевидно, что величины H и n (число возможных исходов опыта) связаны функциональной зависимостью: H=f(n), то есть мера неопределенности есть функция числа исходов. Некоторые свойства этой функции:

1.f(1)=0, так как при n=1 исход не является случайным

инеопределенность отсутствует.

2.f(n) возрастает с ростом n, так как чем больше возможных исходов, тем труднее предсказать результат, и, следовательно, больше неопределенность.

3. если и – два независимых опыта с количеством равновероятных исходов nи n , то мера их суммарной неопределенности равна сумме мер неопределенности каждого из опытов:

f (n n ) f (n ) f (n ) .

Всем трем этим свойствам удовлетворяет единственная функция – logаn. То есть за меру неопределенности опыта с n равновероятными исходами можно принять число logаn. Вопрос – чему равно основание а? В силу известной формулы logb n logb a loga n выбор основания значения не имеет, от

этого зависит только единица измерения энтропии. Если основание а = 2, то единица измерения энтропии – бит, если а = 3, то трит, если а = 10, то дит, если а = е, то нат. Чаще всего в качестве основания логарифма используют 2. Таким образом:

Hlog2 n

–это формула Хартли. Научный подход к оценке сообщений

был предложен еще в 1928 г. Р. Хартли. Преобразовывая, получим: 2H =n.

Очень приближенно можно считать, что количество информации в сообщении о каком-то событии совпадает с количеством вопросов, которые необходимо задать. Чтобы полу-

25

чить ту же информацию, ответ на эти вопросы должен быть лишь «да» или «нет». Причем событие, о котором идет речь должно иметь равновероятностные исходы.

Если же вероятности исходов не равны между собой, то формула Хартли неприменима. Здесь количество информации будет зависеть от вероятности получения того или иного ответа. Причем, чем больше вероятность события, тем меньше количество информации в сообщении о таком событии.

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

где pi – вероятность i-го исхода.

Легко заметить, что если вероятности p1, ..., pn равны, то каждая из них равна 1/n, и формула Шеннона превращается в формулу Хартли.

Какова же связь энтропии с информацией?

Из определения энтропии следует, что энтропия – это числовая характеристика, отражающая ту степень неопределенности, которая исчезает после проведения опыта, то есть после получения информации. То есть после проведения опыта мы получаем определенную информацию. Следовательно, энтропия опыта равна той информации, которую мы получаем в результате его осуществления. То есть, информация I – это содержание сообщения, понижающего неопределенность некоторого опыта с неоднозначным исходом; убыль связанной с ним энтропии является количественной мерой информации.

Значит, если H1 – начальная энтропия (до проведения опыта), H2 – энтропия после проведения опыта, то информация

26

Очевидно, что в случае, когда получен конкретный результат, H2 =0, и, таким образом, количество полученной информации совпадает с начальной энтропией и подсчитывается при помощи формулы Хартли.

Итак, мы ввели меру неопределенности – энтропию и показали, что начальная энтропия (или убыль энтропии) равна количеству полученной в результате опыта информации. Важным при введении какой-либо величины является вопрос о том, что принимать за единицу ее измерения. Очевидно, значение H будет равно 1 при n=2. Иначе говоря, в качестве единицы принимается количество информации, связанное с проведением опыта, состоящего в получении одного из двух равновероятных исходов (например, бросание монеты). А такая единица количества информации называется «бит».

Пример. Найти количество информации в сообщении, что карта, наугад извлеченная из колоды в 32 листа, оказалась тузом.

Решение. Вероятности извлечения карт из колоды равны: p=1/32, следовательно, можем использовать формулу Хартли. Число возможных исходов до опыта n1 =32, а после опыта n2 =4 (масть туза в сообщении не указана). Значит, сообщение содержит

I H1 H2 log2 32 log2 4 5 2 3 бита информации.

Задания для самостоятельной работы

1.В колоде 32 карты. Из колоды случайным образом вытянули карту, которая оказалась тузом, потом ее положили обратно и перетасовали колоду. После этого из колоды вытянули короля той же масти, что и туз. Какое количество бит информации содержит сообщение об этом?

2.В колоде 32 карты. Из колоды случайным образом вытянули карту, которая оказалась цифрой, потом ее положили обратно и перетасовали колоду. После этого из колоды вытянули туза той же масти, что и первая карта. Какое количество бит информации содержит сообщение об этом?

27

3.В колоде 32 карты. Из колоды случайным образом вытянули карту, которая оказалась черной масти, потом ее положили обратно и перетасовали колоду. После этого из колоды вытянули карту того же достоинства, что и первая карта. Какое количество бит информации содержит сообщение об этом?

4.В колоде 32 карты. Из колоды случайным образом вытянули карту, которая оказалась королем, потом ее положили обратно и перетасовали колоду. После этого из колоды вытянули карту того же цвета, что и первая. Какое количество бит информации содержит сообщение об этом?

5.В колоде 32 карты. Из колоды случайным образом вытянули карту, которая оказалась красным тузом, потом ее положили обратно и перетасовали колоду. После этого из колоды вытянули карту той же масти, что и туз. Какое количество бит информации содержит сообщение об этом?

6.В колоде 32 карты. Из колоды случайным образом вытянули карту, которая оказалась черной цифрой, потом ее положили обратно и перетасовали колоду. После этого из колоды вытянули туза той же масти, что и первая карта. Какое количество бит информации содержит сообщение об этом?

7.В колоде 32 карты. Из колоды случайным образом вытянули карту, которая оказалась цифрой, потом ее положили обратно и перетасовали колоду. После этого из колоды вытянули короля того же цвета, что и первая карта. Какое количество бит информации содержит сообщение об этом?

28