Как найти длину сообщения в битах

Все мы привыкли к тому, что все вокруг можно измерить. Мы можем определить массу посылки, длину стола, скорость движения автомобиля. Но как определить количество информации, содержащееся в сообщении? Ответ на вопрос в статье.

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

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

В слове Принтер 6 различных символов (р встречается дважды и считается один раз), далее 7-й символ пробел и девятый — тире. Так как пробел уже был, то после тире мы его не считаем. В слове устройство 10 символов, но различных — 7, так как буквы  с, т и о повторяются. Кроме того буквы т и р уже была в слове Принтер. Так что получается, что в слове устройство 5 различных символов. Считая таким образом дальше мы получим, что в сообщении 20 различных символов.

Далее вспомним формулу, которую называют главной формулой информатики:

2ⁱ=N

Подставив в нее вместо N количество различных символов, мы узнаем, сколько информации несет один символ в битах. В нашем случае формула будет выглядеть так:

2ⁱ=20

Вспомним степени двойки и поймем, что i находится в диапазоне от 4 до 5 (так как 2⁴=16, а 2⁵=32). А так как бит — минимальная единица измерения информации и дробным быть не может, то мы округляем i в большую сторону до 5. Иначе, если принять, что i=4, мы смогли бы закодировать только 2⁴=16 символов, а у нас их 20. Поэтому получаем, что i=5, то есть каждый символ в нашем сообщении несет 5 бит информации.

Осталось посчитать сколько символов в нашем сообщении. Но теперь мы будем считать все символы, не важно повторяются они или нет. Получим, что сообщение состоит из 39 символов. А так как каждый символ — это 5 бит информации, то, умножив 5 на 39 мы получим:

5 бит x 39 символов = 195 бит

Это и есть ответ на вопрос задачи — в сообщении 195 бит информации. И, подводя итог, можно написать алгоритм нахождения объема информации в сообщении:

• посчитать количество различных символов.
• подставив это значение в формулу 2i=N найти вес одного символа (округлив в большую сторону)
• посчитать общее количество символов и умножить это число на вес одного символа.

Автор:

Объяснение
заданий 10 ЕГЭ по информатике

10 тема —
«Измерение количества информации» — характеризуется, как задания базового
уровня сложности,
время выполнения – примерно 4 минуты,
максимальный балл — 1

Типичные
ошибки и рекомендации по их предотвращению:

«При
использовании способа решения со системой счисления с основанием N
следует помнить, что слова в списке нумеруются с единицы, поэтому числу 0
будет соответствовать первое слово»

Рассмотрим кратко
необходимые для решения 10 задания ЕГЭ понятия и формулы.

Измерение
количества информации

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

Единицы
измерения:

1 байт (bytе)
= 8 бит
1 Кб (килобайт) = 1024 байта
1 Мб (мегабайт) = 1024 Кб
1 Гб (гигабайт) = 1024 Мб
1 Тб (терабайт) = 1024 Гб
1 Пб (петабайт) = 1024 Тб

8 = 2³
1024 = 2¹⁰

Рассмотрим
еще несколько определений:

• Алфавит — это набор
  знаков, используемый в том или ином языке.
• Мощность алфавита —
  это количество используемых в алфавите знаков.

Мощность алфавита

• Сообщение — это любая
  последовательность символов какого-либо алфавита.

Для вычисления количества
информации применяются несколько различных формул в зависимости от ситуации:

Двоичное кодирование сообщений
(равновероятностные события)

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

N = 2^L

·        
N —
количество сообщений

·        
L — длиной
битов

*
следует иметь в виду, что также приняты следующие обозначения: Q = 2^k

Пример 2: Зашифруем
буквы А, Б, В, Г при помощи двоичного кодирования равномерным кодом и
посчитаем количество возможных сообщений:

Решение:

Таким
образом, мы получили равномерный код, т.к. длина
каждого кодового слова одинакова для всех кодовых слов (L = 2).

Количество
сообщений длиной L битов:

N = 2^L

Т.е. количество
сообщений длиной 2 бита, как в примере с нашими буквами, будет равно N
= 2² = 4

Ответ: 4

Количество
различных сообщений в алфавите разной мощности

Рассмотрим вариант
с 5 буквами (мощность алфавита = 5), которые надо
разместить в сообщении длиной 2 символа:

Найдем формулу
для нахождения количества различных сообщений в алфавите различной мощности:

Если
мощность некоторого алфавита составляет N, то количество
различных сообщений длиной L знаков:

o    N – мощность алфавита

o    L – длина сообщения

o    Q – количество различных сообщений

Пример: Сколько существует всевозможных
трехбуквенных слов в английском языке?

Решение:

В
английском алфавите 26 букв. Значит, мощность алфавита = 26. Длина
сообщения = 3. Найдем по формуле количество трехбуквенных слов:
Q = 26³
или
26 * 26 * 26 = 17576

Ответ: 17576

·  Таким, образом,
если слово состоит из L букв, причем есть n1 вариантов выбора
первой буквы, n2 вариантов выбора второй буквы и т.д., то число
возможных слов вычисляется как произведение:

N = n1 *
n2 * … * nL

Количество
сообщений при различном вхождении (встречаемости) букв

Иногда в заданиях 10 приходится использовать формулу
комбинаторики для проверки полученных результатов перебора. Число
сочетаний из n элементов по k элементов:

·  I –
количество информации в битах

·  N –
количество вариантов

Факториал
числа n:

n! = 1 * 2
* 3 * … * n

Пример: Сколько существует всевозможных четырехбуквенных
слов в алфавите из 4 букв: А, Б, В, Г, если известно, что буква
А встречается ровно два раза?

Решение:

·        
Длина
сообщения = 4. Мощность алфавита = 4. Но мешает условие: буква
А встречается ровно два раза.

·        
В
таких заданиях можно использовать способ перебора всевозможных вариантов:

два раза буква А, на остальных местах — одна из трех
оставшихся букв:

А А 3
3     = 3 * 3 = 3² = 9

А 3 А
3     = 9

А 3 3
А     = 9

3 А А
3     = 9

3 А 3
А     = 9

3 3 А
А     = 9

·        
Получили 6 вариантов, каждый из которых равен 9.

·        
Проверим формулой числа сочетаний:

Число сочетаний из n элементов по k элементов:

C(kn)=n!k!(n−k)!

·        
В задаче:

C(24)=4!2!(4−2)!=242∗2=6

* Факториал числа n! = 1 * 2 * 3 *..* n

·        
Т.е. проверка прошла успешно, мы получили 6 вариантов.

·        
Осталось
посчитать количество всех сообщений:

6 * 9 = 54

Дополнительные
формулы

Количество
информации и равновероятные события

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

Формула Шеннона:

x = log₂(1/p)

·        
x —
количество информации в сообщении о событии

·        
p — ве­ро­ят­ность
со­бы­тия

Формула
вероятности случайного события:

p(A) = m / n

·        
m —
количество благоприятных исходов (число случаев, способствующих событию А)

·        
n —
количество общих исходов (общее число равновозможных случаев)

Количество
информации и неравновероятные события

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

i = -[log₂p]

*квадратные скобки
означают ближайшее целое, меньшее или равное значению выражения в скобках

Формула
Хартли:

Формула Хартли

·        
I –
количество информации в битах

·        
N –
количество вариантов

Алфавитный
подход:

Информационный
объем сообщения длиной L:

Алфавитный подход

·        
N —
мощность алфавита

·        
L — длина
сообщения

ЕГЭ по
информатике 2017 задание 10 ФИПИ вариант 1 (Крылов С.С., Чуркина Т.Е.):

Шифр
кодового замка представляет собой последовательность из пяти символов,
каждый из которых является цифрой от 1 до 6.

Сколько различных
вариантов шифра можно задать, если известно, что цифра 1 должна встречаться в коде ровно 1 раз, а каждая из других допустимых цифр может встречаться
в шифре любое количество раз или не встречаться совсем?

Решение:

·        
Формула
нахождения количества различных сообщений:

Q = N^L

·        
Итак,
что у нас дано из этой формулы:

·        
Длина
сообщения (L) = 5 символов

·        
Мощность
алфавита (N) = 6 (цифры от 1 до 6).

·        
Но
так как цифра 1 встречается по условию ровно один раз, а остальные 5
цифр — любое количество раз, то будем считать, что N = 5 (цифры от 2 до
6, исключая 1). Т.е. возьмем вариант, когда 1 стоит на первом месте, а
остальные 5 цифр размещаем на 4 позиции:

1 5 5 5 5 — 1 *
Q = 5⁴ = 625

1 способ.
Найдем количество вариантов методом перебора:

·        
Методом
перебора найдем количество вариантов размещения:

1 5 5 5 5 - 1 * Q=54 = 625

5 1 5 5 5 - 1 * Q=54 = 625

5 5 1 5 5 - 1 * Q=54 = 625

5 5 5 1 5 - 1 * Q=54 = 625

5 5 5 5 1 - 1 * Q=54 = 625

• получили 5
  вариантов;

2
способ. Найдем количество вариантов при помощи формулы комбинаторики:

C(45)=5!4!(5−4)!=5

• получили 5
  вариантов;
• В итоге
  получим:

625
* 5 = 3125

Результат: 3125

Определить объём текста

§ 1.6. Измерение информации

Информатика. 7 класса. Босова Л.Л. Оглавление

Ключевые слова:

• бит
• информационный вес символа
• информационный объём сообщения
• единицы измерения информации

1.6.1. Алфавитный подход к измерению информации

Одно и то же сообщение может нести много информации для одного человека и не нести её совсем для другого человека. При таком подходе количество информации определить однозначно затруднительно.

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

Для количественного выражения любой величины необходима, прежде всего, единица измерения. Измерение осуществляется путём сопоставления измеряемой величины с единицей измерения. Сколько раз единица измерения «укладывается» в измеряемой величине, таков и результат измерения.

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

Обратите внимание, что название единицы измерения информации «бит» (bit) происходит от английского словосочетания binary digit — «двоичная цифра».

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

1.6.2. Информационный вес символа произвольного алфавита

Ранее мы выяснили, что алфавит любого естественного или формального языка можно заменить двоичным алфавитом. При этом мощность исходного алфавита N связана с разрядностью двоичного кода i, требуемой для кодирования всех символов исходного алфавита, соотношением: N = 2ⁱ.

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

Информационный вес символа алфавита i и мощность алфавита N связаны между собой соотношением: N = 2ⁱ.

Задача 1. Алфавит племени Пульти содержит 8 символов. Каков информационный вес символа этого алфавита?

Решение. Составим краткую запись условия задачи.

Известно соотношение, связывающее величины i и N : N = 2ⁱ.

С учётом исходных данных: 8 = 2ⁱ. Отсюда: i = 3.

Полная запись решения в тетради может выглядеть так:

1.6.3. Информационный объём сообщения

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

Информационный объём сообщения I равен произведению количества символов в сообщении К на информационный вес символа алфавита i;I = К • i.

Задача 2. Сообщение, записанное буквами 32-символьного алфавита, содержит 140 символов. Какое количество информации оно несёт?

Задача 3. Информационное сообщение объёмом 720 битов состоит из 180 символов. Какова мощность алфавита, с помощью которого записано это сообщение?

1.6.4. Единицы измерения информации

В наше время подготовка текстов в основном осуществляется с помощью компьютеров. Можно говорить о «компьютерном алфавите», включающем следующие символы: строчные и прописные русские и латинские буквы, цифры, знаки препинания, знаки арифметических операций, скобки и др. Такой алфавит содержит 256 символов. Поскольку 256 = 2⁸, информационный вес каждого символа этого алфавита равен 8 битам. Величина, равная восьми битам, называется байтом. 1 байт — информационный вес символа алфавита мощностью 256.

1 байт = 8 битов

Бит и байт — «мелкие» единицы измерения. На практике для измерения информационных объёмов используются более крупные единицы:

1 килобайт = 1 Кб = 1024 байта = 2¹⁰ байтов
1 мегабайт = 1 Мб = 1024 Кб = 2¹⁰ Кб = 2²⁰ байтов
1 гигабайт = 1 Гб = 1024 Мб = 2¹⁰ Мб = 2²⁰ Кб = 2³⁰ байтов
1 терабайт = 1 Тб = 1024 Гб = 2¹⁰ Гб = 2²⁰ Мб = 2³⁰ Кб = 2⁴⁰ байтов

Задача 4. Информационное сообщение объёмом 4 Кбайта состоит из 4096 символов. Каков информационный вес символа используемого алфавита? Сколько символов содержит алфавит, с помощью которого записано это сообщение?

Ответ: 8 битов, 256 символов.

Задача 5. В велокроссе участвуют 128 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер цепочкой из нулей и единиц минимальной длины, одинаковой для каждого спортсмена. Каков будет информационный объём сообщения, записанного устройством после того, как промежуточный финиш пройдут 80 велосипедистов?

Решение. Номера 128 участников кодируются с помощью двоичного алфавита. Требуемая разрядность двоичного кода (длина цепочки) равна 7, так как 128 = 2⁷. Иначе говоря, зафиксированное устройством сообщение о том, что промежуточный финиш прошёл один велосипедист, несёт 7 битов информации. Когда промежуточный финиш пройдут 80 спортсменов, устройство запишет 80 • 7 = 560 битов, или 70 байтов информации.

Ответ: 70 байтов.

Самое главное.

При алфавитном подходе считается, что каждый символ некоторого сообщения имеет опредёленный информационный вес — несёт фиксированное количество информации.

1 бит — минимальная единица измерения информации.

Информационный вес символа алфавита i и мощность алфавита N связаны между собой соотношением: N = 2ⁱ.

Информационный объём сообщения I равен произведению количества символов в сообщении К на информационный вес символа алфавита i: I = K•i.

1 байт = 8 битов.

Байт, килобайт, мегабайт, гигабайт, терабайт — единицы измерения информации. Каждая следующая единица больше предыдущей в 1024 (210) раза.

Вопросы и задания.

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

2. В чём суть алфавитного подхода к измерению информации?

3. Что принято за минимальную единицу измерения информации?

4. Что нужно знать для определения информационного веса симво­ла алфавита некоторого естественного или формального языка?

5. Определите информационный вес i символа алфавита мощ­ностью N, заполняя таблицу

6. Как определить информационный объём сообщения, представлен­ного символами некоторого естественного или формального языка?

7. Определите количество информации в сообщении из Ксимво­лов алфавита мощностью N, заполняя таблицу

8. Племя Мульти пишет письма, пользуясь 16-символьным алфави­том. Племя Пульти пользуется 32-символьным алфавитом. Вож­ди племён обменялись письмами. Письмо племени Мульти содер­жит 120 символов, — а письмо племени Пульти — 96. Сравните информационные объёмы сообщений, содержащихся в письмах

9. Информационное сообщение объёмом 650 битов состоит из 130 символов. Каков информационный вес каждого символа этого сообщения?

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

11. Информационное сообщение объёмом 375 байтов состоит из 500 символов. Каков информационный вес каждого символа этого сообщения? Какова мощность алфавита, с помощью кото­рого было записано это сообщение?

12. Для записи текста использовался 64-символьный алфавит. Какое количество информации в байтах содержат 3 страницы текста, если на каждой странице расположено 40 строк по 60 символов в строке?

13. Сообщение занимает 6 страниц по 40 строк, в каждой строке за­писано по 60 символов. Информационный объём всего сообще­ния равен 9000 байтам. Каков информационный вес одного сим­вола? Сколько символов в алфавите языка, на котором записано это сообщение?

14. Метеорологическая станция ведёт наблюдение за влажностью воздуха. Результатом одного измерения является целое число от 0 до 100 процентов, которое записывается цепочкой из нулей и единиц минимальной длины, одинаковой для каждого изме­рения. Станция сделала 8192 измерения. Определите информа­ционный объём результатов наблюдений.

15. Племя Пульти пользуется 32-символьным алфавитом. Свод основных законов племени хранится на 512 глиняных таблич­ках, на каждую из которых нанесено ровно 256 символов. Какое количество информации содержится на каждом носителе? Какое количество информации заключено во всём своде законов?

Оглавление

§ 1.5. Двоичное кодирование

§ 1.6. Измерение информации

Тестовые задания для самоконтроля

Введите текст (любой набор символов) *

Текст

Укажите символы, которые следует убрать из текста

Выберите информацию, которую хотите получить

* — обязательно заполнить