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

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

Формула Шеннона Количество информации для событий с различными вероятностями определяется по формуле: где I – количество информации, N – количество возможных событий, pi- вероятности отдельных событий.

Если события равновероятны, то количество информации определяется по формуле: I = log 2 N N = 2 I

Пример 1. После экзамена по информатике, который сдавали ваши друзья, объявляются оценки («2», «3», «4» или «5»). Какое количество информации будет нести сообщение об оценке учащегося A, который выучил лишь половину билетов, и сообщение об оценке учащегося B, который выучил все билеты.

РЕШЕНИЕ: Опыт показывает, что для учащегося A все четыре оценки (события) равновероятны и тогда количество информации, которое несет сообщение об оценке можно вычислить по формуле 2.2: I = log 2 4 = 2 бит На основании опыта можно также предположить, что для учащегося B наиболее вероятной оценкой является «5» (p 1 = 1/2), вероятность оценки «4» в два раза меньше (p 2 = 1/4), а вероятности оценок «2» и «3» еще в два раза меньше (p 3 = p 4 = 1/8). Так как события неравновероятны, воспользуемся для подсчета количества информации в сообщении формулой 2.1: I = -(1/2 log 2 1/2 + 1/4 log 2 1/4 + 1/8 log 2 1/8 + 1/8 log 2 1/8) бит Для вычисления воспользуемся компьютерным калькулятором Wise Calculator.

Пример 2. В непрозрачном мешочке хранятся 10 белых, 20 красных, 30 синих и 40 зеленых шариков. Какое количество информации будет содержать зрительное сообщение о цвете вынутого шарика.

РЕШЕНИЕ: Так как количество шариков различных цветов неодинаково, то зрительные сообщения о цвете вынутого из мешочка шарика также различаются и равны количеству шариков данного цвета деленному на общее количество шариков: p б = 0,1;p к = 0,2;p з = 0,3;p с = 0,4 События неравновероятны, поэтому для определения количества информации, содержащимся в сообщении о цвете шарика, воспользуемся формулой 2.1: I = -(0,1 log 2 0,1+ 0,2 log 2 0,2 + 0,3 log 2 0,3 + 0,4 log 2 0,4) бит Для вычисления этого выражения, содержащего логарифмы, воспользуемся компьютерным калькулятором Wise Calculator.

Пример 3. Какое количество вопросов достаточно задать вашему собеседнику, чтобы наверняка определить месяц, в котором он родился?

Будем рассматривать 12 месяцев как 12 возможных событий. Если спрашивать о конкретном месяце рождения, то, возможно, придется задать 11 вопросов (если на 11 первых вопросов был получен отрицательный ответ, то 12-й задавать не обязательно, так как он и будет правильным). Правильно задавать «двоичные» вопросы, т.е. вопросы, на которые можно ответить только «Да» или «Нет». Например, «Вы родились во второй половине года?». Каждый такой вопрос разбивает множество вариантов на два подмножества: одно соответствует ответу «Да», а другое ответу «Нет». Правильная стратегия состоит в том, что вопросы нужно задавать так, чтобы количество возможных вариантов каждый раз уменьшалось вдвое. Тогда количество возможных событий в каждом из полученных подмножеств будет одинаково и их отгадывание равновероятно. В этом случае на каждом шаге ответ («Да» или «Нет») будет нести максимальное количество информации (1 бит). По формуле 2.2 и с помощью калькулятора получаем: I = log ,6 бит Количество полученных бит информации соответствует количеству заданных вопросов, однако количество вопросов не может быть нецелым числом. Округляем до большего целого числа и получаем ответ: при правильной стратегии необходимо задать не более 4 вопросов.

Пример 4. Вероятность первого события составляет 0.5, а второго и третьего – Какое количество информации мы получим после реализации одного из них? Ответ: 1.5 бит

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

Все системы счисления делятся на две большие группы: позиционные; непозиционные.

Позиционные системы счисления В позиционных системах счисления количественное значение цифры зависит от ее позиции в числе. Сюда относятся: Десятичная СС; Двоичная СС; Восьмеричная СС; Шестнадцатеричная СС.

Таблица систем счислений ДесятичнаяДвоичнаяВосьмеричнаяШестнадцатеричная А В С D E F

Десятичная система счисления 555,55 10 =5* * * * * , =1* * * * * * * , =1* * * * *10 -4

Двоичная система счисления 101,01 2 =1* *2 1 +1*2 0 +0* * , =1*2 4 +1*2 3 +1*2 2 +1*2 1 +1*2 0 +0* * * *2 -4

Восьмеричная и шестнадцатеричная системы счисления 673,2 8 =6*8 2 +7*8 1 +3*8 0 +2*8 -1 8А,F 16 = 8* * *16 -1

Римская система счисления В основе римской системы счисления лежали знаки: I (один палец) для числа 1; V (раскрытая ладонь) для числа 5; X (две сложенные ладони) для 10; L - 50; С 100; D 500; М XXVIII= =28 XCIХ= =99 МСМХСVIII=1000+( )+(100-10) =1998

Домашнее задание 1. Записать числа в развернутой форме: 19,99 10 ; 10,10 2 ; 64,5 8 ; 39,F 16 2.Какое минимальное основание может иметь система счисления, если в ней записаны числа 23 и 67? 3.Записать числа и в римской системе счисления.

Перевод целых чисел из одной системы счисления в другую

Можно сформулировать алгоритм перевода целых чисел из системы с основанием p в систему с основанием q: 1. Основание новой системы счисления выразить цифрами исходной системы счисления и все последующие действия производить в исходной системе счисления. 2. Последовательно выполнять деление данного числа и получаемых целых частных на основание новой системы счисления до тех пор, пока не получим частное, меньшее делителя. 3. Полученные остатки, являющиеся цифрами числа в новой системе счисления, привести в соответствие с алфавитом новой системы счисления. 4. Составить число в новой системе счисления, записывая его, начиная с последнего остатка.

Пример 1. Перевести десятичное число в восьмеричную систему счисления: Пример 2. Перевести десятичное число в шестнадцатеричную систему счисления: Ответ: =255 8 Ответ: =AD 16 Пример 3. Перевести десятичное число в двоичную систему счисления. Ответ:11 10 =

Перевод дробных чисел из одной системы счисления в другую

Можно сформулировать алгоритм перевода правильной дроби с основанием p в дробь с основанием q: 1. Основание новой системы счисления выразить цифрами исходной системы счисления и все последующие действия производить в исходной системе счисления. 2. Последовательно умножать данное число и получаемые дробные части произведений на основание новой системы до тех пор, пока дробная часть произведения не станет равной нулю или будет достигнута требуемая точность представления числа. 3. Полученные целые части произведений, являющиеся цифрами числа в новой системе счисления, привести в соответствие с алфавитом новой системы счисления. 4. Составить дробную часть числа в новой системе счисления, начиная с целой части первого произведения.

Пример. Перевести число 0, в восьмеричную систему счисления. Ответ:0, =0,52 8 Пример. Перевести число 0, в шестнадцатеричную систему счисления. Ответ:0, =0,А8 16 Пример. Перевести десятичную дробь 0, в двоичную систему счисления. Ответ:0, =0,1001 2

Перевод произвольных чисел

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

Пример. Перевести число 17,25 10 в двоичную систему счисления. Ответ:17,25 10 =1001,01 2 Пример. Перевести число 124,25 10 в восьмеричную систему. Ответ:124,25 10 =174,2 8

Домашнее задание 1. Переведите десятичные дроби в двоичную систему счисления (ответ записать с шестью двоичными знаками): а)0,4622; в)0,5198; д)0,5803; ж)0,6124; б)0,7351; г)0,7982; е)0,8544; з)0, Переведите смешанные десятичные числа в двоичную систему счисления: а)40,5; б)31,75; в)124,25; г)125,125.

Перевод чисел из системы счисления с основанием 2 в систему счисления с основанием 2 n и обратно

Для того, чтобы целое двоичное число записать в системе счисления с основанием q=2 n, нужно: 1. Двоичное число разбить справа налево на группы по n цифр в каждой. 2. Если в последней левой группе окажется меньше n разрядов, то ее надо дополнить слева нулями до нужного числа разрядов. 3. Рассмотреть каждую группу как n- разрядное двоичное число и записать ее соответствующей цифрой в системе счисления с основанием q=2 n.

Пример. Число переведем в восьмеричную систему счисления. Разбиваем число справа налево на триады и под каждой из них записываем соответствующую восьмеричную цифру: Получаем восьмеричное представление исходного числа:

Пример. Число переведем в шестнадцатеричную систему счисления. Разбиваем число справа налево на тетрады и под каждой из них записываем соответствующую шестнадцатеричную цифру: F 8 7 Получаем шестнадцатеричное представление исходного числа: 400F87 16.

Перевод дробных чисел. Для того, чтобы дробное двоичное число записать в системе счисления с основанием q=2 n, нужно: 1. Двоичное число разбить слева направо на группы по n цифр в каждой. 2. Если в последней правой группе окажется меньше n разрядов, то ее надо дополнить справа нулями до нужного числа разрядов. 3. Рассмотреть каждую группу как n- разрядное двоичное число и записать ее соответствующей цифрой в системе счисления с основанием q=2 n.

Пример. Число 0, переведем в восьмеричную систему счисления. Разбиваем число слева направо на триады и под каждой из них записываем соответствующую восьмеричную цифру: 000, , Получаем восьмеричное представление исходного числа: 0,542 8.

Перевод произвольных чисел. Для того, чтобы произвольное двоичное число записать в системе счисления с основанием q=2 n, нужно: 1. Целую часть данного двоичного числа разбить справа налево, а дробную слева направо на группы по n цифр в каждой. 2. Если в последних левой и/или правой группах окажется меньше n разрядов, то их надо дополнить слева и/или справа нулями до нужного числа разрядов; 3. Рассмотреть каждую группу как n- разрядное двоичное число и записать ее соответствующей цифрой в системе счисления с основанием q=2 n

Пример. Число , переведем в восьмеричную систему счисления. Разбиваем целую и дробную части числа на триады и под каждой из них записываем соответствующую восьмеричную цифру: , , 3 4 Получаем восьмеричное представление исходного числа: 745,34 8.

Пример. Число , переведем в шестнадцатеричную систему счисления. Разбиваем целую и дробную части числа на тетрады и под каждой из них записываем соответствующую шестнадцатеричную цифру: , , D 2 Получаем шестнадцатеричное представление исходного числа: 748,D2 16.

Перевод чисел из систем счисления с основанием q=2 n в двоичную систему

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

Пример. Переведем шестнадцатеричное число 4АС35 16 в двоичную систему счисления. В соответствии с алгоритмом: 4 А С Получаем:

Домашнее задание Переведите двоичные числа в восьмеричную систему счисления: а) ; в) ; д) ; б)1010, ; г)1110, ; е)1000, Переведите двоичные числа в шестнадцатеричную систему счисления: а) ; в) ; д) ; б)1010, ; г)1110, ; е)100,

Арифметические операции в двоичной системе счисления

Правила сложения, вычитания и умножения в двоичной системе счисления 0+0=1 0-0=0 0*0=0 0+1=1 1-0=1 0*1=0 1+0=1 0-1=11 1*0=0 1+1=01 1-1=0 1*1=1

Сложение Пример. Рассмотрим несколько примеров сложения двоичных чисел: , , ,101

Вычитание Примеры , ,1=101100, = , , ,

Умножение 11001*1101= ,01*11,01= , ,01 * 1101 * 11, ,0001

Деление :1101=

Решение примеров Расставьте знаки арифметических операций так, чтобы были верны следующие равенства в двоичной системе: а) 1100 ? 11 ? 100 = ; б) 1100 ? 10 ? 10 = 100; в) 1100 ? 10 ? 10 = ; г) 1100 ? 10 ? 10 = 1011; д) 1100 ? 11 ? 100 = 0.

Решение примеров Какое число следует за каждым из данных: а) ; в)AF 16 ; б) ; г) Ответ для каждого числа запишите в указанной и десятичной системах счисления.

Решение примеров Вычислите выражения: а) ( AF 16 )/36 8 ; б) *A

Домашнее задание Выполните операцию деления над двоичными числами: а) 1110:11д) : б) 1000:10е) : в) 1111:11ж) : г) 1010:10з) :111100