Задание 11
Чтобы успешно справиться с экзаменом, тебе нужно разбираться не только в алгоритмах и программировании. Задание 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
- Определи алфавит: выясни, какие символы используются в тексте (буквы, цифры, знаки препинания и т.д.).
- Рассчитай мощность алфавита: посчитай количество уникальных символов.
- Определи количество бит на символ: используй формулу Хартли и найди минимальное целое i, удовлетворяющее условию.
- Рассчитай объем текста в битах: умножь количество символов в тексте на количество бит на символ.
- Переведи объем в байты (если требуется): раздели объем в битах на 8.
- Преобразуй в килобайты, мегабайты и т.д. (если требуется): используй соотношения: 1 Кб = 1024 байта, 1 Мб = 1024 Кб и т.д.
Не попадись в ловушку!
- Не забывай про пробелы и знаки препинания. Их тоже нужно учитывать при подсчете мощности алфавита.
- Внимательно читай условие задания. Иногда требуется округлить полученный результат до целого числа. Проверь, в каких единицах требуется ответ (биты, байты, килобайты и т.д.).
Мы рассказали все, что тебе нужно знать для решения задания 11: тщательно разберись в теории и попрактикуйся в решении задач! Тогда на экзамене тебя точно будет ждать успех. Желаем удачи!