Задание 11

15 7 минут

Чтобы успешно справиться с экзаменом, тебе нужно разбираться не только в алгоритмах и программировании. Задание 11 проверяет твои знания в области кодирования информации. На первый взгляд оно может показаться сложным, но все не так страшно. Давай разбираться вместе.

О чем это задание?

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

Информация 

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

 

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

 

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

 

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

 

Мощность алфавита – количество символов в алфавите. 

 

При алфавитном подходе к измерению информации количество информации зависит не от содержания, а от размера текста и мощности алфавита. 

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

Любая информация в компьютере кодируется с помощью двоичного кода, то есть в виде нулей и единиц. 

 

Электронный сигнал, который может принимать два значения (0 или 1), называется битом (binary digit). Одним битом можно кодировать два состояния: 0 и 1 (да и нет, чёрный и белый, 2 символа и т.д.). При увеличении количества битов на один получится в два раза больше кодов.

 

Пример: если нам необходимо закодировать 3 состояния лампочки (горит, не горит и мигает), потребуется уже 2 бита (например, 00, 01 и 10). 

Перевод между единицами измерения информации

Алгоритм перевода

Лови запоминалку: белка бежит к миндалю, громко топая

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

Нужна для определения количества информации, содержащейся в сообщении 

 

  • i = log2 N 
  • N = 2i 

 

N — количество символов в используемом алфавите (мощность алфавита), 

i — количество информации в одном символе алфавита в битах. 

 

Чтобы посчитать количество информации во всем сообщении, нужно умножить длину сообщения (количество символов в нем) на i.

 

При помощи i бит можно закодировать 2i разных вариантов. 

 

Пример: имея 3 бита, мы можем закодировать максимум 8 символов. 

 

Для нахождения информационного объёма сообщения нужно умножить количество символов в сообщении на количество бит на символ (глубину кодирования): I = k*i 

 

Пример: Статья содержит 16 страниц, на каждой странице 32 строки, в каждой строке 64 символа. Каждый символ кодируется 8 битами. Найти информационный объём статьи в Кбайтах. 

 

Мощность алфавита равна N = 2i 

 

Если мощность алфавита равна N, то количество различных сообщений длиной K (без учёта смысла) равно NK. При двоичном кодировании — 2К (так как мощность алфавита равна 2).

Алгоритм решения задания 11

  1. Определи алфавит: выясни, какие символы используются в тексте (буквы, цифры, знаки препинания и т.д.).
  2. Рассчитай мощность алфавита: посчитай количество уникальных символов.
  3. Определи количество бит на символ: используй формулу Хартли и найди минимальное целое i, удовлетворяющее условию.
  4. Рассчитай объем текста в битах: умножь количество символов в тексте на количество бит на символ.
  5. Переведи объем в байты (если требуется): раздели объем в битах на 8.
  6. Преобразуй в килобайты, мегабайты и т.д. (если требуется): используй соотношения: 1 Кб = 1024 байта, 1 Мб = 1024 Кб и т.д.

Не попадись в ловушку!

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

 

Мы рассказали все, что тебе нужно знать для решения задания 11: тщательно разберись в теории и попрактикуйся в решении задач! Тогда на экзамене тебя точно будет ждать успех. Желаем удачи!

Читайте также: