Задачи, связанные с определением количества информации, занимают довольно большое место как в общем курсе 9-11 классов, так и при итоговой аттестации разного типа.
Обычно решение подобных задач не представляет трудности для учащихся с хорошими способностями к анализу ситуаций. Но большинство учеников поначалу путаются в понятиях и не знают, как приступить к решению.
Тем не менее, к 9-му классу учащиеся уже имеют определенный опыт решения задач по другим предметам (более всего – физика) с применением формул. Определить, что в задаче дано, что необходимо найти, и выразить одну переменную через другую – действия довольно привычные, и с ними справляются даже слабые ученики. Представляется возможным ввести некоторые дополнительные формулы в курсе информатики и найти общий стиль их применения в решении задач.
Оттолкнемся от одной из главных формул информатики – формулы Хартли N=2i. При ее использовании учащиеся могут еще не знать понятия логарифма, достаточно вначале иметь перед глазами, а затем запомнить таблицу степеней числа 2 хотя бы по 10-й степени.
При этом формула может применяться в решении задач разного типа, если правильно определить систему обозначений.
Выделим в системе задач на количество информации задачи следующих типов:
- Количество информации при вероятностном подходе;
- Кодирование положений;
- Количество информации при алфавитном подходе (кодирование текста);
- Кодирование графической информации;
- Кодирование звуковой информации
Все задачи группы A (в случае, если мы имеем дело с равновероятными событиями) решаются непосредственно по формуле Хартли с ее привычными обозначениями:
- N – количество равновероятных событий;
- i – количество бит в сообщении о том, что событие произошло,
Причем в задаче может быть определена любая из переменных с заданием найти вторую. В случае если число N не является непосредственно числом, представляющим ту или иную степень числа 2, количество бит нам необходимо определить «с запасом». Так для гарантированного угадывания числа в диапазоне от 1 до 100 необходимо задать минимально 7 вопросов (27=128).
Решение задач для случаев неравновероятных событий в этой статье не рассматривается.
Для решения задач групп B-E дополнительно введем еще одну формулу:
Q=k*i
и определим систему обозначений для задач разного типа.
Для задач группы B значение переменных в формуле Хартли таково:
- i – количество «двоичных элементов», используемых для кодирования;
- N – количество положений, которые можно закодировать посредством этих элементов.
Так:
- два флажка позволяют передать 4 различных сообщения;
- с помощью трех лампочек можно потенциально закодировать 8 различных сигналов;
- последовательность из 8 импульсов и пауз при передаче информации посредством электрического тока позволяет закодировать 256 различных текстовых знаков;
и т.п.
Рассмотрим структуру решения по формуле:
Задача 1: Сколько существует различных последовательностей из символов «плюс» и «минус» длиной ровно в пять символов?
Дано: i = 5
Найти: N
Решение: N = 25
Ответ: 5
Каждый элемент в последовательности для кодирования несет один бит информации.
Очевидно, что при определении количества элементов, необходимых для кодирования N положений, нас всегда интересует минимально необходимое для этого количество бит.
При однократном кодировании необходимого количества положений мы определяем необходимое количество бит и ограничиваемся формулой Хартли. Если кодирование проводится несколько раз, то это количество мы обозначаем как k и, определяя общее количество информации для всего кода (Q), применяем вторую формулу.
Задача 2: Метеорологическая станция ведет наблюдение за влажностью воздуха, результатом которых является целое число от 1 до 100%, которое кодируется посредством минимально возможного количества бит. Станция сделала 80 измерений. Какой информационный объем результатов наблюдений.
Дано: N = 100; k = 80
Найти: Q
Решение:
По формуле Хартли i = 7 (с запасом); Q = 80 * 7 = 560
Ответ: 560 бит
(Если в задаче даны варианты ответов с использованием других единиц измерения количества информации, осуществляем перевод: 560 бит = 70 байт).
Отметим дополнительно, что, если для кодирования используются нe «двоичные», а скажем, «троичные» элементы, то мы меняем в формуле основание степени.
Задача 3: Световое табло состоит из лампочек. Каждая из лампочек может находиться в одном из трех состояний («включено», «выключена» или «мигает»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 18 различных сигналов.
В данном случае N = 18, основание степени – 3. Необходимо найти i. Если логарифмы еще не знакомы, определяем методом подбора – 5. Ответ: 5 лампочек
Далее рассмотрим решение задач на кодирование текстовой, графической и звуковой информации.
Здесь важно провести параллели:
Информация, которая обрабатывается на компьютере, должна быть представлена в виде конечного множества элементов (символ для текста, точка – для графики, фрагмент звуковой волны – для звука), каждый из которых кодируется отдельно с использованием заданного количества бит. Зависимость количества элементов, которые могут быть закодированы, от количества бит, отводимых, на кодирование одного элемента, как и раньше, определяем по формуле Хартли.
А путем умножения количества элементов (k) на «информационный вес» одного из них, определяем общее количество информации в текстовом, графическом, звуковом фрагменте (Q).
Каждую задачу можно решить, обозначив заданными переменными известные данные, и выразив одну переменную через другую. Только необходимо помнить, что непосредственно расчеты чаще всего производятся в минимальных единицах измерения (битах, секундах, герцах), а потом, если необходимо, ответ переводится в более крупные единицы измерения.
Рассмотрим конкретные примеры:
Алфавитный подход позволяет определить количество информации, заключенной в тексте. Причем под «текстом» в данном случае понимают любую конечную последовательность знаков, несущую информационную нагрузку. Поэтому обозначения переменных для задач группы C одинаково применимы как для задач на передачу обычной текстовой информации посредством компьютера (i = 8, N = 256 или i = 16, N = 16256) так и для задач на передачу сообщений посредством любых других алфавитов (здесь и далее используются разные названия, встречающиеся в задачах):
- i – количество бит, используемое для кодирования одного текстового знака, равнозначно: количество информации (в битах), в нем содержащееся, информационный «вес», информационный «объем» одного знака;
- N – полное количество знаков в алфавите, используемом для передачи сообщения, мощность алфавита;
- k – количество знаков в сообщении;
- Q – количество информации в сообщении (информационный «вес», «объем» сообщения), количество памяти, отведенное для хранения закодированной информации;
Задача 4: Объем сообщения – 7,5 кбайт. Известно, что данное сообщение содержит 7680 символов. Какова мощность алфавита?
Дано:
Q = 7,5 Кбайт = 7680 байт ( в данном случае нет необходимости перевода в биты);
k = 7680
Найти: N
Решение: i = Q / k = 1 байт = 8 бит; N = 28 = 256
Ответ: 256 знаков
Задача 5: Дан текст из 600 символов. Известно, что символы берутся из таблицы размером 16 на 32. Определите информационный объем текста в битах.
Дано:
k = 600; N = 16 * 32
Найти: Q
Решение:
N = 24 * 25 = 29; i = 9; Q = 600 * 9 = 5400 бит;
Ответ: 5400 бит
Задача 6: Мощность алфавита равна 64. Сколько кбайт памяти потребуется, чтобы сохранить 128 страниц текста, содержащего в среднем 256 символов на каждой странице?
Дано:
N = 64; k = 128 * 256
Найти: Q
Решение:
64 = 2i; i = 6; Q = 128 * 256 * 6 = 196608 бит = 24576 байт = 24 Кбайт;
Ответ: 24 Кбайт
Задача 7: Для кодирования нотной записи используется 7 значков-нот. Каждая нота кодируется одним и тем же минимально возможным количеством бит. Чему равен информационный объем сообщения, состоящего из 180 нот?
Дано:
N = 7; k = 180
Найти: Q
Решение:
7 = 2i; i = 3 (с запасом); Q = 180 * 3 = 540 бит;
Ответ: 540 бит
Рассматривая задачи групп D и E, вспоминаем, что при кодировании графики и звука производится дискретизация, то есть разбиение изображения на конечное множество элементов (пикселей) и звуковой волны на конечное множество отрезков, количество которых зависит от количества измерений в секунду уровня звука (частоты дискретизации) и времени звучания звукового файла.
То есть –
- общее количество элементов в графическом файле (k) равно разрешению изображения или разрешению экрана монитора, если изображение формируется на весь экран,
- общее количество элементов в звуковом файле (k) равно произведению частоты дискретизации на время звучания (важно при этом использовать в качестве единиц измерения минимальные единицы – герцы и секунды).
Рассмотрим всю систему обозначений для данного типа задач:
- i – количество бит, используемое для кодирования одного элемента изображения или звукового фрагмента, равнозначно: глубина цвета, звука;
- N – насыщенность цвета, равнозначно: количество цветов в палитре изображения, цветовое разрешение изображения; насыщенность звука (в задачах обычно не используется);
- k – количество точек в изображении, равнозначно: разрешение изображения (или экрана) или количество фрагментов дискретной звуковой волны (равно произведению частоты дискретизации на время звучания);
- Q – количество информации, содержащееся в графическом (звуковом) файле, равнозначно: информационный «объем», «вес» графического (звукового) файла, объем памяти (видеопамяти), необходимый для хранения заданного файла.
Задача 8: Для хранения растрового изображения размером 64 на 64 пикселя отвели 512 байтов памяти. Каково максимально возможное число цветов в палитре изображения?
Дано:
k = 64 * 64 = 212; Q = 512 байтов = 29 * 23 = 212 бит;
Найти: N
Решение:
i = Q / k = 212 / 212 = 1; N = 21 = 2
Ответ: 2 цвета
Задача 9: Сколько памяти нужно для хранения 64-цветного растрового графического изображения размером 32 на 128 точек?
Дано:
N = 64; k = 32 * 128;
Найти: Q
Решение:
i = 6 (по формуле Хартли); Q = 32 * 128 * 6 = 24576 бит = 3072 байт = 3 Кбайт
Ответ: 3 Кбайт
Задача 10: Оцените информационный объем моноаудиофайла длительностью звучания 1 минута, если глубина кодирования равна 16 бит при частоте дискретизации 8 кГц
Дано:
k = 60 * 8000; i = 16;
Найти: Q
Решение:
Q = 60 * 8000 * 16 = 7680000 бит = 960000 байт = 937,5 Кбайт
Ответ: 937,5 Кбайт
(Если файл стерео, Q будет больше в 2 раза).
Задача 11: Рассчитайте время звучания моноаудиофайла, если при 16-битном кодировании и частоте дискретизации 32 кГц его объем равен 625 Кбайт
Дано:
i = 16; k = 32000 * t; Q = 625 кбайт = 640000 байт = 5120000 бит;
Найти: t
Решение:
k = Q / i; k = 5120000 / 16 = 320000; t = 320000 / 32000 = 10 сек
Ответ: 10 секунд
В эту же схему укладывается решение задач на скорость передачи информации любого типа, если в хорошо известной учащимся формуле:
S = V * t принять S = Q (количество переданной информации вместо расстояния).
Задача 12: Сколько секунд потребуется обычному модему, передающему сообщения со скоростью 28800 бит/сек, чтобы передать цветное растровое изображение размером 640 на 480 пикселей, при условии, что цвет каждого пикселя кодируется тремя байтами?
Дано:
V = 28800 бит/сек; k = 640 * 480; i = 3 байт = 24 бит;
Найти: t
Решение:
t = S (Q) / V; Q = k * i = 640 * 480 * 24 = 7372800 бит; t = 7372800 / 28800 = 256 сек.
Ответ: 256 сек
В заключение отметим, что после определенной тренировки решения задач по формулам, многие учащиеся перестают нуждаться в их прописывании в задаче, сразу определяя порядок необходимых арифметических действий для ее решения.
Задачи на определение информационного объема текста
Проверяется умение оценивать количественные параметры информационных объектов.
Теоретический материал:
N = 2i , где N – мощность алфавита (количество символов в используемом
алфавите),
i – информационный объем одного символа (информационный
вес символа), бит
I = K*i, где I – информационный объем текстового документа (файла),
K – количество символов в тексте
Задача 1.
Считаем количество символов в заданном тексте (перед и после тире – пробел, после знаков препинания, кроме последнего – пробел, пробел – это тоже символ). В результате получаем – 52 символа в тексте.
Дано:
i = 16 бит
K = 52
I – ?
Решение:
I = K*i
I = 52*16бит = 832бит (такой ответ есть – 2)
Ответ: 2
Задача 2.
Дано:
K = 16*35*64 – количество символов в статье
i = 8 бит
I – ?
Решение: Чтобы перевести ответ в Кбайты нужно разделить результат на 8 и на 1024 (8=23, 1024=210)
I=16*35*64*8 бит=
=35Кбайт Ответ: 4
Задача 3.
Пусть x – это количество строк на каждой странице, тогда K=10*x*64 – количество символов в тексте рассказа.
Дано:
I = 15 Кбайт
K =10*x*64
i = 2 байта
x – ?
Решение:
Переведем информационный объем текста из Кбайт в байты.
I = 15 Кбайт = 15*1024 байт (не перемножаем)
Подставим все данные в формулу для измерения количества информации в тексте.
I = K*i
15*1024 = 10*x*64*2
Выразим из полученного выражения x
x = 
– количество строк на каждой странице – 4
Ответ: 4
Задачи для самостоятельного решения:
Задача 1.
Задача 2.
Задача 3.
Задача 4.
Задача 5.
Задача 6.
Задача 7.
Задачи взяты с сайта fipi.ru из открытого банка заданий (с.1-7)
Мы ежедневно работаем с информацией из разных источников. При этом каждый из нас имеет некоторые интуитивные представления о том, что означает, что один источник является для нас более информативным, чем другой. Однако далеко не всегда понятно, как это правильно определить формально. Не всегда большое количество текста означает большое количество информации. Например, среди СМИ распространена практика, когда короткое сообщение из ленты информационного агентства переписывают в большую новость, но при этом не добавляют никакой «новой информации». Или другой пример: рассмотрим текстовый файл с романом Л.Н. Толстого «Война и мир» в кодировке UTF-8. Его размер — 3.2 Мб. Сколько информации содержится в этом файле? Изменится ли это количество, если файл перекодировать в другую кодировку? А если заархивировать? Сколько информации вы получите, если прочитаете этот файл? А если прочитаете его второй раз?
По мотивам открытой лекции для Computer Science центра рассказываю о том, как можно математически подойти к определению понятия “количество информации”.
В классической статье А.Н. Колмогорова “Три подхода к определению понятия количества информации” (1965) рассматривают три способа это сделать:
-
комбинаторный (информация по Хартли),
-
вероятностный (энтропия Шеннона),
-
алгоритмический (колмогоровская сложность).
Мы будем следовать этому плану.
Комбинаторный подход: информация по Хартли
Мы начнём самого простого и естественного подхода, предложенного Хартли в 1928 году.
Пусть задано некоторое конечное множество 
. Количеством информации в 
будем называть 
.
Можно интерпретировать это определение следующим образом: нам нужно 
битов для описания элемента из 
.
Почему мы используем биты? Можно использовать и другие единицы измерения, например, триты или байты, но тогда нужно изменить основание логарифма на 3 или 256, соответственно. В дальшейшем все логарифмы будут по основанию 2.
Этого определения уже достаточно для того, чтобы измерить количество информации в некотором сообщении. Пусть про 
стало известно, что 
. Теперь нам достаточно 
битов для описания 
, таким образом нам сообщили 
битов информации.
Пример
Загадано целое число
от
от 
до 
. Нам сообщили, что 
делится на 
. Сколько информации нам сообщили?Воспользуемся рассуждением выше.
(Тот факт, что некоторое сообщение может содержать нецелое количество битов, может показаться немного неожиданным.)
Можно ещё сказать, что сообщение, уменшающее пространство поиска в 
раз приносит 
битов информации. В данном примере пространство поиска уменьшилось в 1000/166 раз.
Интересно, что одного этого определения уже достаточно для того, чтобы решать довольно нетривиальные задачи.
Применение: цена информации
Загадано целое число
от 
до 
. Разрешается задавать любые вопросы на ДА/НЕТ. Если ответ на вопрос “ДА”, то мы должны заплатить рубль, если ответ “НЕТ” — два рубля. Сколько нужно заплатить для отгадывания числа Любой вопрос можно сформулировать как вопрос о принадлежности некоторому множеству, поэтому мы будем считать, что все вопросы имеют вид “
?” для некоторого множества 
.
Каким образом нужно задавать вопросы? Нам бы хотелось, чтобы вне зависимости от ответа цена за бит информации была постоянной. Другими словами, в случае ответа “НЕТ” и заплатив два рубля мы должны узнать в два больше информации, чем при ответе “ДА”. Давайте запишем это формально.
Потребуем, чтобы
Пусть 
, тогда 
. Подставляем и получаем, что
Это эквивалентно квадратному уравнению 
Положительный корень этого уравнения 
. Таким образом, при любом ответе мы заплатим 
рублей за бит информации, а в сумме мы заплатим примерно
рублей (с точностью до округления).
Осталось понять, как выбирать такие множества . Будем выбирать в качестве 
непрерывные отрезки прямой. Пусть нам известно, что 
принадлежит отрезку ![[a,b]](https://habrastorage.org/getpro/habr/upload_files/9a0/3e7/b69/9a03e7b69911956ef048f0e4f6496a6c.svg)
(изначально это отрезок ![[1,n]](https://habrastorage.org/getpro/habr/upload_files/6a5/ba8/1c6/6a5ba81c6f282d08594b053eb740e8a7.svg)
). В следующего множества 
возмём отрезок ![[a, a+ alphacdot(b-a)]](https://habrastorage.org/getpro/habr/upload_files/9cc/487/bdb/9cc487bdbefd53d5e81016a203868ef7.svg)
, где. Тогда за каждый заплаченный рубль текущий отрезок будет уменьшаться в 
раз. Когда длина отрезка станет меньше единицы, мы однозначно определим 
. Поэтому цена отгадывания не будет превосходить
Приведённое рассуждение доказывает только верхнюю оценку. Можно доказать и нижнюю оценку: для любого способа задавать вопросы будет такое число , для отгадывания которого придётся заплатить не менее 
рублей.
Вероятностный подход: энтропия Шеннона
Вероятностный подход, предложенный Клодом Шенноном в 1948 году, обобщает определение Хартли на случай, когда не все элементы множества являются равнозначными. Вместо множества в этом подходе мы будем рассматривать вероятностное распределение на множестве и оценивать среднее по распределению количество информации, которое содержит случайная величина.
Пусть задана случайная величина 
, принимающая 
различных значений с вероятностями 
. Энтропия Шеннона случайной величины 
определяется как
(По непрерывности тут нужно доопределить 
.)
Энтропия Шеннона оценивает среднее количество информации (математическое ожидание), которое содержится в значениях случайной величины.
При первом взгляде на это определение, может показаться совершенно непонятно откуда оно берётся. Шеннон подошёл к этой задаче чисто математически: сформулировал требования к функции и доказал, что это единственная функция, удовлетворяющая сформулированным требованиям.
Я попробую объяснить происхождение этой формулы как обобщение информации по Хартли. Нам бы хотелось, чтобы это определение согласовывалось с определением Хартли, т.е. должны выполняться следующие “граничные условия”:
Будем искать 
в виде математического ожидания количества информации, которую мы получаем от каждого возможного значения .
Как оценить, сколько информации содержится в событии 
? Пусть 
— всё пространство элементарных исходов. Тогда событие 
соответствует множеству элементарных исходов меры 
. Если произошло событие 
, то размер множества согласованных с этим событием элементарных исходов уменьшается с 
до 
, т.е. событие 
сообщает нам 
битов информации. Тут мы пользуемся тем, что количество информации в сообщении, которое уменьшает размер пространство поиска в 
раз приносит 
битов информации.
Примеры
Свойства энтропии Шеннона
Для случайной величины 
, принимающей 
значений с вероятностями 
, выполняются следующие соотношения.
-
.
-
распределение вырождено.
-
.
-
распределение равномерно.
.
распределение 
вырождено.
.
распределение 
равномерно.Чем распределение ближе к равномерному, тем больше энтропия Шеннона.
Энтропия пары
Понятие энтропии Шеннона можно обобщить для пары случайных величин. Аналогично это обощается для тройки, четвёрки и т.д.
Пусть совместно распределённые случайные величины 
и 
принимают значения 
и 
, соответственно. Энтропия пары случайных величин 
и 
определяется следующим соотношением:
![H(X,Y) = sum_{i=1}^ksum_{j=1}^mPr[X = a_i, Y=b_j]cdot logfrac{1}{Pr[X = a_i, Y = b_j]}.](https://habrastorage.org/getpro/habr/upload_files/bdb/a99/dd1/bdba99dd141ec64b0456fb6ef5f765e6.svg)
Примеры
Рассмотрим эксперимент с выбрасыванием двух игральных кубиков — синего и красного.
Свойства энтропии Шеннона пары случайных величин
Для энтропии пары выполняются следующие свойства.
Условная энтропия Шеннона
Теперь давайте научимся вычислять условную энтропию одной случайной величины относительно другой.
Условная энтропия 
относительно 
определяется следующим соотношением:
Примеры
Рассмотрим снова примеры про два игральных кубика.
Свойства условной энтропии
Условная энтропия обладает следующими свойствами
Взаимная информация
Ещё одна информационная величина, которую мы введём в этом разделе — это взаимная информация двух случайных величин.
Информация в 
о величине 
(взаимная информация случайных величин 
и 
) определяется следующим соотношением
Примеры
И снова обратимся к примерам с двумя игральными кубиками.
Свойства взаимной информации
Выполняются следующие соотношения.
-
. Т.е. определение взаимной информации симметрично и его можно переписать так:
. Т.е. определение взаимной информации симметрично и его можно переписать так:
-
Или так:
. -
и .
-
.
-
.
.
и 
.
.
.Все информационные величины, которые мы определили к этому моменту можно проиллюстрировать при помощи кругов Эйлера.
Мы пойдём дальше и рассмотрим информационную величину, зависящую от трёх случайных величин.
Пусть 
, 
и 
совместно распределены. Информация в 
о 
при условии 
определяется следующим соотношением:
Свойства такие же как и обычной взаимной информации, нужно только добавить соответствующее условие ко всем членам.
Всё, что мы успели определить можно удобно проиллюстрировать при помощи трёх кругов Эйлера.
Из этой иллюстрации можно вывести все определения и соотношения на информационные величины.
Мы не будем продолжать дальше и рассматривать четыре случайные величины по трём причинам. Во-первых, рисовать четыре круга Эйлера со всеми возможными областями — это непросто. Во-вторых, для двух и трёх случайных величин почти все возможные соотношения можно вывести из кругов Эйлера, а для четырёх случайных величин это уже не так. И в третьих, уже для трёх случайных величин возникают неприятные эффекты, демонстрирующие, что дальше будет хуже.
Рассмотрим треугольник в пересечении всех трёх кругов 
, 
и 
. Этот треугольник соответствуют взаимной информации трёх случайных величин 
. Проблема с этой информационной величиной заключается в том, что ей не удаётся придать какой-то “физический” смысл. Более того, в отличие от всех остальных величин на картинке 
может быть отрицательной!
Рассмотрим пример трёх случайных величин равномерно распределённых на 
. Пусть 
и 
будут независимы, а 
. Легко проверить, что 
. При этом 
. В то же время 
. Получается следующая картинка.
Мы знаем, что 
. При этом 
. Получается, что 
, а 
, т.е. для таких случайных величин
.
Применение энтропии Шеннона: кодирование
В этом разделе мы обсудим, как энтропия Шеннона возникает в теории кодирования. Будем рассматривать коды, которые кодируют каждый символ по отдельности.
Пусть задан алфавит 
. Код — это отображение из 
в 
. Код 
называется однозначно декодируемым, если любое сообщение, полученное применением 
к символам некоторого текста, декодируется однозначно.
Код называется префиксным (prefix-free), если нет двух символов 
и 
таких, что 
является префиксом 
.
Префиксные коды являются однозначно декодируемыми. Действительно, при декодировании префиксного кода легко понять, где находятся границы кодов отдельных символов.
Теорема [Шеннон]. Для любого однозначно декодируемого кода существует префиксный код с теми же длинами кодов символов.
Таким образом для изучения однозначно декодируемых кодов достаточно рассматривать только префиксные коды.
Задача об оптимальном кодировании.
Дан текст 
. Нужно найти такой код 
, что
Пусть 
. Обозначим через 
частоту, с которой символ 
встречается в 
. Тогда выражение выше можно переписать как
Следующая теорема могла встречаться вам в курсе алгоритмов.
Теорема [Хаффман]. Код Хаффмана, построенный по 
, является оптимальным префиксным кодом.
Алгоритм Хаффмана по набору частот эффективно строит оптимальный код для задачи оптимального кодирования.
Связь с энтропией
Имеют место две следующие оценки.
Теорема [Шеннон]. Для любого однозначно декодируемого кода выполняется
Теорема [Шеннон]. Для любых значений 
существует префиксный код 
, такой что
Рассмотрим случайную величину 
, равномерно распределённую на символах текста 
. Получим, что 
. Таким образом, эти две теоремы задают оценку на среднюю длину кода символа при оптимальном кодировании, т.е. и для кодирования Хаффмана.
Следовательно, длину кода Хаффмана текста 
можно оценить, как
Применение энтропии Шеннона: шифрования с закрытым ключом
Рассмотрим простейшую схему шифрования с закрытым ключом. Шифрование сообщения 
с ключом шифрования 
выполняется при помощи алгоритма шифрования 
. В результате получается шифрограмма 
. Зная 
получатель шифрограммы восстанавливает исходное сообщение 
: 
.
Мы будем анализировать эту схему с помощью аппарата энтропии Шеннона. Пусть 
и 
являются случайными величинами. Противник не знает 
и 
, но знает 
, которая так же является случайной величиной.
Для совершенной схемы шифрования (perfect secrecy) выполняются следующие соотношения:
-
, т.е. шифрограмма однозначно определяется по ключу и сообщению.
-
, т.е. исходное сообщение однозначно восстанавливается по шифрограмме и ключу.
-
, т.е. в отсутствие ключа из шифрограммы нельзя получить никакой информации о пересылаемом сообщении.
, т.е. шифрограмма однозначно определяется по ключу и сообщению.
, т.е. исходное сообщение однозначно восстанавливается по шифрограмме и ключу.
, т.е. в отсутствие ключа из шифрограммы нельзя получить никакой информации о пересылаемом сообщении.Теорема [Шеннон]. 
, даже если условие 
нарушается (т.е. алгоритм 
использует случайные биты).
Эта теорема утверждает, что для совершенной схемы шифрования длина ключа должна быть не менее длины сообщения. Другими словами, если вы хотите зашифровать и передать своему знакомому файл размера 1Гб, то для этого вы заранее должны встретиться и обменяться закрытым ключом размера не менее 1Гб. И конечно, этот ключ можно использовать только однажды. Таким образом, самая оптимальная совершенная схема шифрования — это “одноразовый блокнот”, в котором длина ключа совпадает с длиной сообщения.
Если же вы используете ключ, который короче пересылаемого сообщения, то шифрограмма раскрывает некоторую информацию о зашифрованном сообщении. Причём количество этой информации можно оценить, как разницу между энтропией сообщения и энтропией ключа. Если вы используете пароль из 10 символов при пересылке файла размера 1Гб, то вы разглашаете примерно 1Гб – 10 байт.
Это всё звучит очень печально, но не всё так плохо. Мы ведь никак не учитываем вычислительную мощь противника, т.е. мы не ограничиваем количество времени, которое противнику потребуется на выделение этой информации.
Современная криптография строится на предположении об ограниченности вычислительных возможностей противника. Тут есть свои проблемы, а именно отсутствие математического доказательства криптографической стойкости (все доказательства строятся на различных предположениях), так что может оказаться, что вся эта криптография бесполезна (подробнее можно почитать в статье о мирах Рассела Импальяццо, которая переведена на хабре), но это уже совсем другая история.
Доказательство. Нарисуем картинку для трёх случайных величин и отметим то, что нам известно.
-
.
-
, следовательно , а значит .
-
(по свойству взаимной информации), следовательно , а значит .
-
. Таким образом,
, следовательно 
, а значит 
.
(по свойству взаимной информации), следовательно 
, а значит 
.
. Таким образом,
В доказательстве мы действительно не воспользовались тем, что .
Алгоритмический подход: колмогоровская сложность
Подход Шеннона хорош для случайных величин, но если мы попробуем применить его к текстам, то выходит, что количество информации в тексте зависит только от частот символов, но не зависит от их порядка. При таком подходе получается, что в “Войне и мире” и в тексте, который получается сортировкой всех знаков в “Войне и мире”, содержится одинаковое количество информации. Колмогоров предложил подход, позволяющий измерять количество информации в конкретных объектах (строках), а не в случайных величинах.
Внимание. До этого момента я старался следить за математической строгостью формулировок. Для того, чтобы двигаться дальше в том же ключе, мне потребовалось бы предположить, что читатель неплохо знаком с математической логикой и теорией вычислимости. Я пойду более простым путём и просто буду махать руками, заметая под ковёр некоторые подробности. Однако, все утверждения и рассуждения дальше можно математически строго сформулировать и доказать.
Нам потребуется зафиксировать способ описания битовой строки. Чтобы не углубляться в рассуждения про машины Тьюринга, мы будем описывать строки на языках программирования. Нужно только сделать оговорку, что программы на этих языках будут запускаться на компьютере с неограниченным объёмом оперативной памяти (иначе мы получили бы более слабую вычислительную модель, чем машина Тьюринга).
Сложностью 
строки 
относительно языка программирования 
называется длина кратчайшей программы, которая выводит 
.
Таким образом сложность “Войны и мира” относительноя языка Python — это длина кратчайшей программы на Python, которая печатает текст “Войны и мира”. Естественным образом сложность отсортированной версии “Войны и мира” относительно языка Python получится значительно меньше, т.к. её можно предварительно закодировать при помощи RLE.
Сравнение языков программирования
Дальше нам потребуется научиться любимой забаве всех программистов — сравнению языков программирования.
Будем говорить, что язык 
не хуже языка программирования 
и обозначать 
, если существует константа 
такая, что для для всех 
выполняется 
Исходя из этого определения получается, что язык Python не хуже (!) этого вашего Haskell! И я это докажу. В качестве константы 
мы возьмём длину реализации интепретатора Haskell на Python. Таким образом, любая программа на Haskell переделывается в программу на Python просто дописыванием к ней интерпретатора Haskell на Python.
Соломонов и Колмогоров пошли дальше и доказали существования оптимального языка программирования.
Теорема [Соломонова-Колмогорова]. Существует способ описания (язык программирования) 
такой, что для любого другого способа описания 
выполняется 
.
И да, некоторые уже наверное догадались, что — это JavaScript. Или любой другой Тьюринг полный язык программирования.
Это приводит нас к следующему определению, предложенному Колмогоровым в 1965 году.
Колмогоровской сложностью строки 
будем называть её сложность относительно оптимального способа описания и будем обозначать 
.
Важно понимать, что при разных выборах оптимального языка программирования колмогоровская сложность будет отличаться, но только на константу. Для любых двух оптимальных языков программирования 
и 
выполняется 
и 
, т.е. существует такая константа 
, что 
Это объясняет, почему в этой науке аддитивные константы принято игнорировать.
При этом для конкретной строки и конкретного выбора колмогоровская сложность определена однозначно.
Свойства колмогоровской сложности
Начнём с простых свойств. Колмогоровская сложность обладает следующими свойствами.
Первое свойство выполняется потому, что мы всегда можем зашить строку в саму программу. Второе свойство верно, т.к. из программы, выводящей строку 
, легко сделать программу, которая выводит эту строку дважды.
Примеры
Несжимаемые строки
Важнейшее свойство колмогоровской сложности заключается в существовании сложных (несжимаемых строк). Проверьте себя и попробуйте объяснить, почему не бывает идеальных архиваторов, которые умели бы сжимать любые файлы хотя бы на 1 байт, и при этом позволяли бы однозначно разархивировать результат.
В терминах колмогоровской сложности это можно сформулировать так.
Вопрос. Существует ли такая длина строки
, что для любой строки 
колмогоровская сложность 
меньше 
?Следующая теорема даёт отрицательный ответ на этот вопрос.
Теорема. Для любого 
существует 
такой, что 
.
Доказательство. Битовых строк длины 
всего 
. Число строк сложности меньше 
не превосходит число программ длины меньше 
, т.е. таких программ не больше чем
Таким образом, для какой-то строки гарантированно не хватит программы.
Верна и более сильная теорема.
Теорема. Существует 
такое, что для 
слов длины 
верно
Другими словами, почти все строки длины 
имеют почти максимальную сложность.
Колмогоровская сложность: вычислимость
В этом разделе мы поговорим про вычислимость колмогоровской сложности. Я не буду давать формально определение вычислимости, а буду опираться на интуитивные предствления читателей.
Теорема. Не существует программы, которая по двоичной записи числа 
выводит строку 
, такую что 
.
Эта теорема говорит о том, что не существует программы-генератора, которая умела бы генерировать сложные строки по запросу.
Доказательство. Проведём доказетельство от противного. Пусть такая программа 
существует и 
. Тогда с одной стороны сложность 
не меньше 
, а с другой стороны мы можем описать 
при помощи 
битов и кода программы
.
Это приводит нас к противоречию, т.к. при достаточно больших значениях 
неизбежно станет больше, чем 
.
Как следствие мы получаем невычислимость колмогоровской сложности.
Следствие. Отображение 
не является вычислимым.
Опять же, предположим, что это нет так и существует программа 
, которая по строку вычисляет её колмогоровскую сложность. Тогда на основе программы 
можно реализовать программу 
из теоремы выше: она будет перебирать все строки длины не более 
и находить лексикографически первую, для которой сложность будет не меньше 
. А мы уже доказали, что такой программы не существует.
Связь с энтропией Шеннона
Теорема. Пусть 
длины 
содержит 
единиц и 
нулей, тогда
Я надеюсь, что вы уже узнали энтропию Шеннона для случайной величины с двумя значениями с вероятностями 
и 
.
Для колмогоровской сложности можно проделать весь путь, который мы проделали для энтропии Шеннона: определить условную колмогоровскую сложность, сложность пары строк, взаимную информацию и условную взаимную информацию и т.д. При этом формулы будут повторять формулы для энтропии Шеннона с точностью до 
. Однако это тема для отдельной статьи.
Применение колмогоровской сложности: бесконечность множества простых чисел
Начнём с довольно игрушечного применения. С помощью колмогоровской сложности мы докажем следующую теорему, знакомую нам со школы.
Теорема. Простых чисел бесконечно много.
Очевидно, что для доказательства этой теоремы никакая колмогоровская сложность не нужна. Однако на этом примере я смогу продемонстрировать основные идеи применения колмогоровской сложности в более сложных ситуациях.
Доказательство. Проведём доказательство от обратного. Пусть существует всего 
простых чисел: 
. Тогда любое натуральное 
раскладывается на степени простых:
т.е. определяется набором степеней 
. Каждое 
, т.е. задаётся 
битами. Поэтому любое 
можно задать при помощи 
битов (помним, что 
— это константа).
Теперь воспользуемся теоремой о существовании несжимаемых строк. Как следствие, мы можем заключить, что существуют 
-битовые числа 
сложности не менее 
(можно взять сложную строку и приписать в начало единицу). Получается, что сложное число можно задать при помощи небольшого числа битов.
Противоречие.
Применение колмогоровской сложности: алгоритмическая случайность
Колмогоровская сложность позволяет решить следующую проблему из классической теории вероятностей.
Пусть в лаборатории живёт обезьянка, которую научили печатать на печатной машинке так, что каждую кнопку она нажимает с одинаковой вероятность. Вам предлагается посмотреть на лист печатного текста и сказать, верите ли вы, что его напечатала эта обезьянка. Вы смотрите на лист и видите, что это первая страница “Гамлета” Шекспира. Поверите ли вы? Очевидно, что нет. Хорошо, а если это не Шекспир, а, скажем, текст детектива Дарьи Донцовой? Скорей всего тоже не поверите. А если просто какой-то набор русских слов? Опять же, очень сомневаюсь, что вы поверите.
Внимание, вопрос. А как объяснить, почему вы не верите? Давайте для простоты считать, что на странице помещается 2000 знаков и всего на машинке есть 80 знаков. Вы можете резонно заметить, что вероятность того, что обезьянка случайным образом породила текст “Гамлета” порядка 
, что астрономически мало. Это верно.
Теперь предположим, что вам показали текст, который вас устроил (он с вашей точки зрения будет похож на “случайный”). Но ведь вероятность его появления тоже будет порядка . Как же вы определяете, что один текст выглядит “случайным”, а другой — не выглядит?
Колмогоровская сложность позволяет дать формальный ответ на этот вопрос. Если у текста отстутствует короткое описание (т.е. в нём нет каких-то закономерностей, которые можно было бы использовать для сжатия), то такую строку можно назвать случайной. И как мы увидели выше почти все строки имеют большую колмогоровскую сложность. Поэтому, когда вы видите строку с закономерностями, т.е. маленькой колмогоровской сложности, то это соответствует очень редкому событию. В противоположность наблюдению строки без закономерностей. Вероятность увидеть строку без закономерностей близка к 1.
Это обобщается на случай бесконечных последовательностей. Пусть 
. Как определить понятие случайной последовательности?
(неформальное определение)
Последовательность случайна по Мартину–Лёфу, если каждый её префикс является несжимаемым.
Оказывается, что это очень хорошее определение случайных последовательностей, т.к. оно обладает ожидаемыми свойствами.
Свойства случайных последовательностей
-
Почти все последовательности являются случайными по Мартину–Лёфу, а мера неслучайных равна
. -
Всякая случайная по Мартину-Лёфу последовательность невычислима.
-
Если
случайная по Мартин-Лёфу, то
.
случайная по Мартин-Лёфу, то
Заключение
Если вам интересно изучить эту тему подробнее, то я рекомендую обратиться к следующим источникам.
-
Верещагин Н.К., Щепин Е.В. Информация, кодирование и предсказание. МЦНМО. (нет в свободном доступе, но pdf продаётся за копейки)
-
В.А. Успенский, А.Х. Шень, Н.К. Верещагин. Колмогоровская сложность и алгоритмическая случайность.
-
Курс “Введение в теорию информации” А.Е. Ромащенко в Computer Science клубе.
Если вам интересны подобные материалы, подписывайтесь в соцсетях на CS клуб и CS центр, а так же на наши каналы на youtube: CS клуб, CS центр.
Решение задач на измерение информации
Для решения задач нам понадобится формула, связывающая между
собой информационный вес каждого символа, выраженный в битах (b), и мощность
алфавита (N):
N = 2b
Задача
1:
Алфавит содержит 32 буквы. Какое количество информации несет
одна буква?
|
|
Дано: Мощность Какое |
Решение:
1. 32 = 2 5, значит
вес одного символа b = 5 бит.
Ответ:
одна буква несет 5 бит информации.
Задача
2:
Сообщение, записанное буквами из 16 символьного алфавита,
содержит 10 символов. Какой объем информации в битах оно несет?
|
|
Дано: Мощность Определить |
Решение:
1. 16 = 2 4, значит
вес одного символа b = 4 бита.
2. Всего символов 10, значит объем
информации 10 * 4 = 40 бит.
Ответ:
сообщение несет 40 бит информации (8 байт).
Задача
3:
Информационное сообщение объемом 300 бит содержит 100 символов.
Какова мощность алфавита?
|
|
Дано: Объем Какова |
Решение:
1. Определим вес одного символа: 300
/ 100 = 3 бита.
2. Мощность алфавита определяем по
формуле: 2 3 = 8.
Ответ:
мощность алфавита N = 8.
Попробуйте следующие задачи решить самостоятельно.
Задача
4:
Объем сообщения, содержащего 20
символов, составил 100 бит. Каков размер алфавита, с помощью которого
записано сообщение?
Задача
5:
Сколько символов содержит сообщение,
записанное с помощью 8 символьного алфавита, если объем его составил 120
бит?
Задача
6:
В книге 100 страниц. На каждой странице 60 строк по 80 символов
в строке. Вычислить информационный объем книги.
Урок
“Вычисление
объема графического файла”
Кодирование
графической информации
|
RGB-модель |
Если посмотреть на экран работающего монитора посмотреть Каждый видеопиксель на цветном экране Таким образом, соседние разноцветные точки сливаются, |
|
Вычисление объема графического
файла
Информации о состоянии каждого пикселя
хранится в закодированном виде в памяти ПК. Из основной формулы информатики
можно подсчитать объем памяти, необходимый для хранения одного пикселя:
|
|
N = где i – глубина кодирования |
|
Для получения черно-белого изображения пиксель может находится в 2 = 2 i , i = Следовательно, для его хранения требуется 1 бит. |
|
Вычисление
объема растрового изображения
Задача 1. Вычислить объем
растрового черно-белого изображения размером 100 х 100.
Решение: V = K * i = 100 x 100 x 1 бит = 10
000 бит / 8 бит = 1250 байт / 1024 = 1,22 Кбайт.
Ответ: 1,22 Кбайт
Задача 2. Вычислить объем
растрового изображения размером 100 х 100 и палитрой 256 цветов.
Решение: 1) 256 = 2 i , i = 8
2) V = K * i = 100 x 100 x 8 бит
= 100 x 100 x 1
байт = 10 000 байт / 1024 = 9,76 Кбайт.
Ответ: 9,76 Кбайт
Вычисление объема векторного изображения
Задача
3. Вычислить
объем векторного изображения.
Решение: Векторное
изображение формируется из примитивов и хранится в памяти в виде формулы:
RECTANGLE 1, 1, 100, 100,
Red, Green
Подсчитаем количество символов в этой формуле: 36 символов (букв, цифр, знаков
препинания и пробелов)
36 символов х 2 байта = 72 байт (Unicode 1
символ – 1 байт)
Ответ: 72 байт
|
|
Несжатое растровое |
Урок
“Определение объема графического файла”
Задача
2. Какой объем информации занимает черно-белое изображение
размером 600 х 800?
Решение: 600
х 800 = 480 000 точек 480 000 точек х 1 бит = 480
000 бит
480
000 бит / 8 бит / 1024 байт ≈ 58, 59 Кбайт
Ответ: 58, 59 Кбайт
Задача 3. Определить объем
растрового изображения размером 600 х 800 при глубине цвета 24 бита.
Решение: 600
х 800 = 480 000 точек 480 000 точек х 24 бит = 11 520
000 бит
11 520
000 бит / 8 бит / 1024 байт = 1406,25 Кбайт / 1024 байт ≈ 1,37 Мбайт
Ответ: ≈ 1,37 Мбайт
Задача 3. Определить объем видеопамяти компьютера, который
необходим для реализации графического режима монитора с разрешающей
способностью 1024×768 и палитрой 65536 цветов.
Решение: N
= 2i = 65536 i = 16 бит
Количество точек изображения равно:
1024 х 768 = 786432
16 бит х 786432 = 12582912 бита / 8 бит / 1024 байт
= 1536 Кбайт / 1024 байт = 1,5 М байта
Ответ: 1,5
М байта
Задача
4. Определить объем растрового изображения размером 200 х 200
и 256 цветами.
Решение: 200
х 200 х 8 бит = 320 000 бит / 8 бит / 1024 байт = 39,0625 Кбайт ≈ 39 Кбайт
Ответ: 39 Кбайт
Самостоятельное
решение задач:
Задача 1. Сколько цветов будет в
палитре, если каждый базовый цвет кодировать в 6 битах?
Задача 2. Для хранения
растрового изображения размером 1024 х 512 пикселей отвели 256 Кбайт памяти.
Каково максимально возможное число цветов в палитре изображения?
Задача 3. Сколько
памяти компьютера требуется для двоичного кодирования 256-цветного рисунка
размером 10 х 10 точек?
Задача 4. Разрешение
экрана монитора – 1024 х 768 точек, глубина цвета – 16 бит. Каков необходимый
объем видеопамяти для данного графического режима?
Задача 5. Объем
видеопамяти равен 512 Кбайт, разрешающая способность дисплея – 800 х 600. Какое
максимальное количество цветов можно использовать при таких условиях?
Задача 6. Сравнить размеры
видеопамяти, необходимые для хранения изображений:
– 1-е изображение: черно-белое размером 200 х 400
– 2-е изображение: 4 цветное размером 100 х 200
1) первое изображение занимает
памяти больше чем второе на 40000 байтов
2) первое изображение занимает
памяти меньше чем второе на 500 байтов
3) первое изображение занимает
в два раза больше памяти, чем второе
4) первое изображение занимает
в два раза меньше памяти, чем второе
5) оба изображения имеют
одинаковый объем памяти
Домашнее
задание – решить задачи:
Задача 1. Каждой
точке экрана монитора (пикселю) поставлены в соответствие четыре бита, что
позволит отобразить n цветов.
Задача 2. Объём видеопамяти равен 4 Мб,
битовая глубина – 24, разрешающая способность дисплея – 640 х 480. Какое
максимальное количество страниц можно использовать при этих условиях?
Здравствуйте! С вами Елена TeachYOU, и сегодня мы разберем задачи 11 из ЕГЭ по информатике. Задачи несложные, но почему-то у многих учеников с ними возникают проблемы.
Что такое равномерное кодирование
Для того, чтобы работать с какими-то объектами с помощью компьютера, необходимо их закодировать. Так как подавляющее большинство современных ЭВМ использует двоичную логику, разумно кодировать объекты с использованием двоичного кодирования.
Двоичное кодирование можно разделить на равномерное (когда кодовые слова, или коды, имеют одинаковую длину), и неравномерное (когда длина кодовых слов разная). Тема неравномерного кодирования поднимается в 4 задании ЕГЭ, можете посмотреть материал по нему в этой статье. Там разобраны примеры с разными вариантами кодирования. Если вам все еще непонятно, чем равномерное кодирование отличается от неравномерного, то перед тем, как читать материал по 11 заданию дальше, советую сначала просмотреть материал по ссылке выше.
Перевод битов в байты и далее
Прежде чем двигаться дальше, напомню правила перевода между единицами измерения информации. Основное:
- 1 байт = 8 бит
- 1 Кбайт = 1024 байт = 2^10 байт = 2^13 бит
- 1 Мбайт = 1024 Кбайт = 2^10 Кбайт = 2^23 бит
1. Сначала переводим 5 Мбайт в Кбайты, домножая на 1024: 5 Мбайт = 5 * 1024 Кбайт.
2. Затем переводим Кбайты в байты домножением на 1024: 5 * 1024 Кбайт = 5 * 1024 * 1024 байт.
3. Для перевода в биты домножаем на 8: 5 * 1024 * 1024 байт = 5 * 1024 * 1024 * 4 бит.
Переведем 24576 бит в килобайты:
1. Делим на 8, чтобы перевести в байты: 24576 / 8 = 3072 (байт).
2. Делим на 1024, чтобы перейти к Кбайтам: 3072 / 1024 = 3 (Кбайт).
Что нужно знать про равномерное двоичное кодирование
Кодирование равномерное => все кодовые слова имеют одинаковую, минимально возможную, длину. Кодирование двоичное => кодовые слова состоят только из 0 и 1.
Сколько объектов можно закодировать, используя кодовые слова имеют длины i ?
Например, буква А может кодироваться кодовым словом 01101. В нем пять знаков (0 или 1). Говорят, что кодовое слово 01101 состоит из пяти бит. Бит – это ячейка, принимающая значение 0 или 1 (тире или точка, вкл или выкл и пр.).
Тогда кодовое слово 0110 состоит из 4 бит, слово 110011 – из 6 бит и т.д.
Посмотрим, сколько разных кодовых слов можно составить, если брать кодовые слова определенной длины (здесь нам поможет теория по теме “Комбинаторика” для 8 номера).
- Кодовые слова длины 1 – это 0 и 1. Их два (каждое занимает 1 бит).
- Кодовые слова длины 2 – это 00, 01, 10 и 11. Их четыре (каждое занимает 2 бит).
- Кодовые слова длины 3 я перечислять не буду. Их количество равно 2*2*2 = 2^3 = 8 (если непонятно, загляните в материал по комбинаторике). Каждое кодовое слово занимает 3 бита.
- ….
- Кодовые слова длины i – их 2^i. Каждое занимает i бит.
Получается, что, если для кодирования мы выберем кодовые слова длины i (i-битные), то сможем закодировать 2^i объектов.
Если в сообщении используется N символов, сколько бит нужно для кодирования каждого символа?
Количество i-битных кодовых слов равно 2^i.
Похоже, что, нужно подобрать такое i, чтобы N = 2^i.
Но на практике не всегда число N является степенью двойки. Поэтому для кодирования N объектов нужно взять такое минимальное i, чтобы выполнялось условие N <= 2^i.
Например:
- N = 14: 14 <= 16 = 2^4. Получается, что при кодировании 14 объектов с использованием равномерного двоичного кодирования на каждый объект будет приходиться 4 бита.
- N = 250: 250 <= 256 = 2^8 => 8 бит на объект.
- N = 2050: 2050 <= 4096 = 2^12 => 12 бит на объект.
Рассмотрим задачи 11 из ЕГЭ
Задача 1 (номер 1964 с компегэ)
При регистрации в компьютерной системе каждому объекту сопоставляется идентификатор, состоящий из 15 символов и содержащий только символы из 8-символьного набора: А, В, C, D, Е, F, G, H. В базе данных для хранения сведений о каждом объекте отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование идентификаторов, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно идентификатора, для каждого объекта в системе хранятся дополнительные сведения, для чего отведено 24 байта на один объект.
Определите объём памяти (в байтах), необходимый для хранения сведений о 20 объектах. В ответе запишите только целое число – количество байт.
Из задачи следует, что нужно сохранить данные о 20 объектах. Для каждого из них хранится идентификатор (его информационный вес нужно вычислить) и дополнительные сведения (известны, 24 байта на один объект).
Начнем с вычисления количества байт, которое занимает один идентификатор.
Длина идентификатора 15 символов, а мощность алфавита равна восьми. Вспоминаем основную формулу информатики: N = 2^i, где N – количество кодируемых равномерным кодированием объектов, i – количество бит, которое приходится на один объект. N = 8 (нужно закодировать все символы из набора, поэтому N = мощности алфавита). Из 8 = 2^i находим i=3 бита. Каждый символ кодируется 3 битами, а идентификатор состоит из 15 символов. Получается, на один идентификатор приходится 15 * 3 = 45 бит = 5,625 байт.
Обращаем внимание, что в задаче говорится, что для хранения сведений о каждом объекте отведено одинаковое и минимально возможное целое число байт. Необходимо округлить 5,625 байт до целого значения. Но в большую или меньшую сторону?
Если округлим в меньшую, то получим 5 байт = 40 бит. Но для хранения идентификатора нужно 45 бит! 45 бит не помещаются в “коробочку” из 5 байт. Значит, нужно округлять в большую. Итого, на идентификатор приходится 6 байт.
Для вычисления информационного объема, необходимого для хранения сведений об одном объекте, найдем сумму байт, приходящихся на идентификатор и на дополнительные сведения:
6 + 24 = 30 (байт) – на 1 объект.
Вычислим объем информации для хранения сведений о 20 объектах:
30 (байт) * 20 (объектов) = 600 (байт).
Задача 2 (номер 212 с компегэ)
Для регистрации на сайте необходимо продумать пароль, состоящий из 9 символов. Он может содержать десятичные цифры, строчные или заглавные буквы латинского алфавита (алфавит содержит 26 букв) и символы из перечисленных: «.», «$», «#», «@», «%», «&». В базе данных для хранения сведения о каждом пользователе отведено одинаковое и минимальное возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственного пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт одинаковое для каждого пользователя. Для хранения сведений о двадцати пользователях потребовалось 500 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе. В ответе запишите только целое число – количество байт.
Сайт хранит данные о 20 пользователях. Они занимают 500 байт. Для каждого пользователя хранятся пароль (его информационный объем нужно вычислить) и дополнительные сведения (эту величину нужно найти и взять в качестве ответа).
Начнем с поиска количества байт, приходящихся на одного пользователя:
500 (байт) / 20 (польз.) = 25 (байт на 1 польз.)
Разберемся с паролем. Мощность алфавита символов, которые используются для его записи:
N = 10 (цифр) + 26 (строчных букв) + 26 (заглавных букв) + 6 (символов «.», «$», «#», «@», «%», «&») = 68 (символов).
Сколькими битами можно закодировать каждый из 78 символов при использовании равномерного кодирования?
68 <= 2^i, i = 7 (бит).
Тогда пароль занимает
7 (бит) * 9 (символов) = 63 (бит) = 8 (байт).
Для одного пользователя хранится пароль (8 байт) и доп. сведения. Всего на пользователя приходится 25 байт. Тогда доп. сведения занимают
25 – 8 = 17 (байт).
Задача 3 (номер 463 с компегэ)
Очень люблю эту задачу авторства Евгения Джобса за нацеленность на понимание темы
Автомобильный номер состоит из одиннадцати букв русского алфавита A, B,C, E, H, K, M, O, P, T, X и десятичных цифр от 0 до 9. Каждый номер состоит из двух букв, затем идет 3 цифры и еще одна буква. Например, АВ901С.
В системе каждый такой номер кодируется посимвольно, при этом каждая буква и каждая цифра кодируются одинаковым минимально возможным количеством бит.
Укажите, сколько бит на один номер можно сэкономить, если кодировать с помощью одинакового минимально возможного количества бит каждую из трех групп – первые две буквы, три цифры и последняя буква.
В этой задаче есть “до” и “после”.
“До”: каждая буква и каждая цифра кодируются отдельно.
“После”: кодируются отдельно первые две буквы, три цифры и последняя буква.
Разберемся, сколько бит занимал автомобильный номер при выборе способа кодирования “до”.
- Буквы: N = 11 <= 16 = 2^4 => i = 4.
- Цифры: N = 10 <= 16 = 2^4 => i = 4.
- Весь номер состоит их трех цифр и трех букв, это 3 (буквы) * 4 (бита) + 3 (цифры) * 4 (бита) = 24 (бит на один номер)
Как кодируем номер “после”?
- Первые две буквы. Букв 11. Количество пар букв (АА, АВ, … , ХХ) равно 11*11 = 121. Нашли объекты – это пары букв. Их количество N = 121 <= 128 = 2^7 => i=7 бит. Раньше каждую букву мы кодировали 4 битами и две буквы занимали 8 бит. А теперь 7. Э – экономия!
- Три цифры. Цифр 10. Количество троек цифр (000, 001, … , 999) равно 10*10*10 = 1000. В этом случае кодируемые объекты – это тройки цифр. N = 1000 <= 1024 = 2^10 => i = 10 бит. “До” каждую цифру кодировали 4 битами, три цифры занимали 12 бит. А сейчас 10. И здесь сэкономили.
- Последняя буква. N = 11 <= 16 = 2^4 => i=4. Тут ничего не изменилось: “до” кодировали объекты-буквы и здесь поступили так же.
- Количество бит на номер “после”: 7 + 10 + 4 = 21 (бит).
Итого сэкономили 24 – 21 = 3 (бита).
Какие еще задачи посмотреть, чтобы закрепить материал?
Сайт kompege.ru покорил мое сердце, и теперь я считаю себя его амбассадором)
Если вы только знакомитесь с 11 номерами, решайте любые задачи (на сайте компегэ их можно отсортировать по сложности, начните с простых).
Для более продвинутых настоятельно советую прорешать задачи из списка ниже, так как в каждой есть свои тонкости.
Номера 11: 4468, 4323, 2119, 5433.
