Общая схема решения задач на количество информации

Разделы: Информатика


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

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

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

Оттолкнемся от одной из главных формул информатики – формулы Хартли N=2i. При ее использовании учащиеся могут еще не знать понятия логарифма, достаточно вначале иметь перед глазами, а затем запомнить таблицу степеней числа 2 хотя бы по 10-й степени.

При этом формула может применяться в решении задач разного типа, если правильно определить систему обозначений.

Выделим в системе задач на количество информации задачи следующих типов:

  1. Количество информации при вероятностном подходе;
  2. Кодирование положений;
  3. Количество информации при алфавитном подходе (кодирование текста);
  4. Кодирование графической информации;
  5. Кодирование звуковой информации

Все задачи группы 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 сек

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