какое минимальное количество бит необходимо для кодирования
Какое минимальное количество бит необходимо для кодирования
Каждый сотрудник предприятия получает электронный пропуск, на котором записаны личный код сотрудника, код подразделения и некоторая дополнительная информация. Личный код состоит из 20 букв. Для формирования кодов используется 14 различных букв, каждая из которых может быть заглавной или строчной. Для записи кода на пропуске отведено минимально возможное целое число байт. При этом используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством бит. Код подразделения — целое четырёхзначное число, он записан на пропуске как двоичное число и занимает минимально возможное целое число байт. Всего на пропуске хранится 30 байт данных. Сколько байт выделено для хранения дополнительных сведений об одном сотруднике? В ответе запишите только целое число — количество байт.
k бит позволяют кодировать 2 k символов, поэтому для кодирования 28-символьного алфавита требуется 5 бит (ведь 
. Для хранения 20 символов требуется 
бит. Минимальное количество байт, вмещающее в себя 100 бит — 13 байт (104 бит). Номер подразделения можно закодировать 2 байтами, поскольку в 1 байт помещаются только числа от 0 до 255.
Для хранения данных об одном сотруднике требуется 30 байт данных. Из них 13 байт отводится на хранение личного кода, ещё 2 байта требуется для хранения номера подразделения. Следовательно, для хранения дополнительных сведений о сотруднике отводится 15 байт.
Какое минимальное количество бит необходимо для кодирования
Каждый объект, зарегистрированный в информационной системе, получает уникальный код, состоящий из двух частей. Первая часть определяет категорию объекта и состоит из 5 символов, каждый из которых может быть одной из 26 заглавных латинских букв. Вторая часть кода определяет уникальный идентификатор объекта и состоит из 9 символов, каждый из которых может быть латинской буквой (строчной или заглавной) или одной из 9 цифр (цифра 0 не используется). Для представления кода используют посимвольное кодирование, все символы в пределах одной части кода кодируют одинаковым минимально возможным для данной части количеством битов, а для кода в целом выделяется минимально возможное целое количество байтов. Кроме того, для каждого объекта в системе выделено 120 байт для хранения содержательной информации.
Сколько байтов потребуется для хранения данных (код и содержательная информация) о 20 объектах? В ответе запишите только целое число — количество байтов.
k бит позволяют кодировать 2 k символов, поэтому для кодирования 26-символьного алфавита требуется 5 бит (ведь 
). Для хранения 5 символов требуется 
бит. Далее, k бит позволяют кодировать 2 k символов, поэтому для кодирования 61-символьного алфавита (26 заглавных букв, 26 строчных букв и 9 цифр) требуется 6 бит (ведь 
). Для хранения 9 символов требуется 
бит. Минимальное количество байт, вмещающее в себя 25 + 54 бит = 10 байт (80 бит).
На один объект потребуется 10 + 120 = 130 байт, тогда на 20 объектов потребуется 130 · 20 = 2600 байт.
Какое минимальное количество бит необходимо для кодирования
Тема: Вычисление информационного объема сообщения.
· с помощью K бит можно закодировать Q=2 k различных вариантов (чисел)
· таблица степеней двойки, она же показывает, сколько вариантов Q можно закодировать с помощью K бит:
· при измерении количества информации принимается, что в одном байте 8 бит, а в одном килобайте (1 Кбайт) – 1024 байта, в мегабайте (1 Мбайт) – 1024 Кбайта [i]
· чтобы найти информационный объем сообщения (текста) I, нужно умножить количество символов (отсчетов) N на число бит на символ (отсчет) K: I=N*K
· две строчки текста не могут занимать 100 Кбайт в памяти
· мощность алфавита M – это количество символов в этом алфавите
· если алфавит имеет мощность M, то количество всех возможных «слов» (символьных цепочек) длиной N (без учета смысла) равно Q=M N ; для двоичного кодирования (мощность алфавита M – 2 символа) получаем известную формулу: Q=2 N
Пример задания:
Для регистрации на сайте некоторой страны пользователю требуется придумать пароль. Длина пароля – ровно 11 символов. В качестве символов используются десятичные цифры и 12 различных букв местного алфавита, причём все буквы используются в двух начертаниях: как строчные, так и заглавные (регистр буквы имеет значение!).
Под хранение каждого такого пароля на компьютере отводится минимально возможное и одинаковое целое количество байтов, при этом используется посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов.
Определите объём памяти, который занимает хранение 60 паролей.
1) 540 байт 2) 60 0 байт 3) 66 0 б ай т 4) 720 байт
1) согласно условию, в пароле можно использовать 10 цифр (0..9) + 12 заглавных букв местного алфавита + 12 строчных букв, всего 10 + 12 + 12 = 34 символа
2) для кодирования 34 символов нужно выделить 6 бит памяти (5 бит не хватает, они позволяют закодировать только 2 5 = 32 варианта)
3) для хранения всех 11 символов пароля нужно 11 × 6 = 66 бит
4) поскольку пароль должен занимать целое число байт, берем ближайшее большее (точнее, не меньшее) значение, которое кратно 8: это 72 = 9 × 8; то есть один пароль занимает 9 байт
5) тогда 60 паролей занимают 9 × 60 = 540 байт
· часто забывают, что пароль должен занимать ЦЕЛОЕ число байт
Ещё пример задания:
В велокроссе участвуют 119 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объем сообщения, записанного устройством, после того как промежуточный финиш прошли 70 велосипедистов?
1) 70 бит 2) 70 байт 3) 490 бит 4) 119 байт
7) велосипедистов было 119, у них 119 разных номеров, то есть, нам нужно закодировать 119 вариантов
8) по таблице степеней двойки находим, что для этого нужно минимум 7 бит (при этом можно закодировать 128 вариантов, то есть, еще есть запас); итак, 7 бит на один отсчет
9) когда 70 велосипедистов прошли промежуточный финиш, в память устройства записано 70 отсчетов
10) поэтому в сообщении 70*7 = 490 бит информации (ответ 3).
· дано число, которое есть в условии (неверные ответы 70 бит, 70 байт, 119 байт), чтобы сбить случайное угадывание
· указано правильное число, но другие единицы измерения (мог быть вариант 490 байт)
· расчет на невнимательное чтение условия: можно не заметить, что требуется определить объем только 70 отсчетов, а не всех 119 (мог быть вариант 119*7=833 бита)
Еще пример задания:
Объем сообщения, содержащего 4096 символов, равен 1/512 части Мбайта. Какова мощность алфавита, с помощью которого записано это сообщение?
1) 8 2) 16 3) 4096 4) 16384
Большие числа. Что делать?
Обычно (хотя и не всегда) задачи, в условии которых даны большие числа, решаются достаточно просто, если выделить в этих числах степени двойки. На эту мысль должны сразу наталкивать такие числа как
Нужно помнить, что соотношение между единицами измерения количества информации также представляют собой степени двойки:
1 байт = 8 бит = 2 3 бит,
1 Кбайт = 1024 байта = 2 10 байта
= 2 10 · 2 3 бит = 2 13 бит,
1 Мбайт = 1024 Кбайта = 2 10 Кбайта
= 2 10 · 2 10 байта = 2 20 байта
= 2 20 · 2 3 бит = 2 23 бит.
Правила выполнения операций со степенями:
· при умножении степени при одинаковых основаниях складываются
· … а при делении – вычитаются:
1) в сообщении было 4096 = 2 12 символов
1/512 Мбайта = 2 23 / 512 бита = 2 23 / 2 9 бита = 2 14 бита (= 16384 бита!)
3) место, отведенное на 1 символ:
2 14 бита / 2 12 символов = 2 2 бита на символ = 4 бита на символ
4) 4 бита на символ позволяют закодировать 2 4 = 16 разных символов
5) поэтому мощность алфавита – 16 символов
6) правильный ответ – 2.
· дано число, которое есть в условии (неверный ответ 4096), чтобы сбить случайное угадывание
· расчет на то, что увидев «правильное» число в ходе вычислений, учащийся не будет доводить расчет до конца (неверный ответ 16384)
· легко запутаться, если выполнять вычисления «в лоб», не через степени двойки
Решение (вариант 2, предложен В.Я. Лаздиным):
1 /512 Мбайт = 1024 /512 Кбайт = 2 Кбайт = 2048 байт
2) на 1 символ приходится 2048 байт / 4096 = 1/2 байта = 4 бита
3) 4 бита на символ позволяют закодировать 2 4 = 16 разных символов
4) поэтому мощность алфавита – 16 символов
5) правильный ответ – 2.
· не всегда удобно работать с дробными числами (1/2 байта)
· метод разработан специально для этой задачи, где он хорошо работает; в других задачах может быть не так гладко
Еще пример задания:
В зоопарке 32 обезьяны живут в двух вольерах, А и Б. Одна из обезьян заболела. Сообщение «Заболевшая обезьяна живет в вольере А» содержит 4 бита информации. Сколько обезьян живут в вольере Б?
1) 4 2) 16 3) 28 4) 30
1) информация в 4 бита соответствует выбору одного из 16 вариантов, …
2) … поэтому в вольере А живет 1/16 часть всех обезьян (это самый важный момент!)
3) всего обезьян – 32, поэтому в вольере А живет
4) поэтому в вольере Б живут все оставшиеся
· неверный ответ 1 (4 обезьяны) сбивает случайное угадывание «в лоб», по исходным данным
· можно сделать неверный вывод о том, что в вольере А живет 4 обезьяны (столько же, сколько бит информации мы получили), следовательно, в вольере Б живут оставшиеся 28 обезьян (неверный ответ 3)
· после п. 1 можно сделать (неверный) вывод о том, что в вольере А живет 16 обезьян, следовательно, в вольере Б – тоже 16 (неверный ответ 2)
1) обезьяна-альбинос может жить в вольере А (событие 1) или в вольере Б (событие 2)
2) по формуле Шеннона количество информации в сообщении о произошедшем событии с номером i равно
3) у нас не было никакой предварительной информации о том, где живет альбинос, поэтому можно считать, что вероятность определяется количеством обезьян в вольере – если вероятность равна 1/16, то в вольере живет 1/16 часть всех обезьян:
6) поэтому в вольере Б живут все оставшиеся
7) правильный ответ – 4.
Еще пример задания:
В корзине лежат 32 клубка шерсти, из них 4 красных. Сколько бит информации несет сообщение о том, что достали клубок красной шерсти?
1) красные клубки шерсти составляют 1/8 от всех, …
2) поэтому сообщение о том, что первый вынутый клубок шерсти – красный, соответствует выбору одного из 8 вариантов
3) выбор 1 из 8 вариантов – это информация в 3 бита (по таблице степеней двойки)
4) правильный ответ – 2.
Решение (вариант 2, использование формулы Шеннона):
1) красные клубки шерсти составляют 1/8 от всех, поэтому вероятность pk того, что первый вынутый клубок шерсти – красный, равна 1/8
2) по формуле Шеннона находим количество информации в битах:
3) правильный ответ – 2.
Еще пример задания:
В некоторой стране автомобильный номер длиной 7 символов составляется из заглавных букв (всего используется 26 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 20 автомобильных номеров.
1) 20 байт 2) 105 байт 3) 120 байт 4) 140 байт
1) всего используется 26 букв + 10 цифр = 36 символов
3) таким образом, на каждый символ нужно 6 бит (минимально возможное количество бит)
4) полный номер содержит 7 символов, каждый по 6 бит, поэтому на номер требуется 6*7=42 бита
5) по условию каждый номер кодируется целым числом байт (в каждом байте – 8 бит), поэтому требуется 6 байт на номер (5*8=40
6) на 20 номеров нужно выделить 20*6=120 байт
7) правильный ответ – 3.
· неверный ответ 1 (20 байт) сбивает случайное угадывание «в лоб», по исходным данным
· если не обратить внимание на то, что каждый номер кодируется целым числом БАЙТ, получаем неверный ответ 2 (20*42=105*8 бит = 105 байт)
· если по невнимательности считать, что каждый СИМВОЛ кодируется целым числом байт, получаем 7 байт на символ и всего 140 байт (неверный ответ 4)
· если «забыть» про цифры, получим всего 26 символов, 5 бит на символ, 35 бит (5 полных байт) на каждый номер и неверный ответ 100 байт (на 20 номеров)
Еще пример задания:
Какое наименьшее число символов должно быть в алфавите, чтобы при помощи всевозможных трехбуквенных слов, состоящих из символов данного алфавита, можно было передать не менее 9 различных сообщений?
1) здесь используется только одна формула: если алфавит имеет мощность M, то количество всех возможных «слов» длиной N равно Q=M N
2) в данном случае нужно закодировать 9 сигналов (Q>=9) с помощью трехбуквенных слов (N=3)
3) таким образом, нужно найти наименьшее целое M, такое что Q=M 3 >= 9 (куб числа не меньше 9)
5) таким образом, правильный ответ – 3.
· нас интересуют только трехбуквенные слова (одно- и двухбуквенные слова учитывать не нужно)
Еще пример задания:
Каждая ячейка памяти компьютера, работающего в троичной системе счисления, может принимать три различных значения (-1, 0, 1). Для хранения некоторой величины отвели 4 ячейки памяти. Сколько различных значений может принимать эта величина?
1) непривычность этой задачи состоит в том, что используется троичная система
2) фактически мы имеем дело с языком, алфавит которого содержит M=3 различных символа
3) поэтому количество всех возможных «слов» длиной N равно Q=3 N
4) для N= 4 получаем Q=3 4 =81
5) таким образом, правильный ответ – 81.
· если не осознать, что используется троичная (а не двоичная!) система, можно «по инерции» получить неправильный ответ
Еще пример задания:
В школьной базе данных хранятся записи, содержащие информацию об учениках:
– 16 символов: русские буквы (первая прописная, остальные строчные),
– 12 символов: русские буквы (первая прописная, остальные строчные),
– 16 символов: русские буквы (первая прописная, остальные строчные),
– числа от 1992 до 2003.
Каждое поле записывается с использованием минимально возможного количества бит. Определите минимальное количество байт, необходимое для кодирования одной записи, если буквы е и ё считаются совпадающими.
1) 28 2) 2 9 3) 46 4) 56
1) очевидно, что нужно определить минимально возможные размеры в битах для каждого из четырех полей и сложить их;
2) важно! известно, что первые буквы имени, отчества и фамилии – всегда заглавные, поэтому можно хранить их в виде строчных и делать заглавными только при выводе на экран (но нас это уже не волнует)
3) таким образом, для символьных полей достаточно использовать алфавит из 32 символов (русские строчные буквы, «е» и «ё» совпадают, пробелы не нужны)
4) для кодирования каждого символа 32-символьного алфавита нужно 5 бит (32 = 2 555 5 ), поэтому для хранения имени, отчества и фамилии нужно (16 + 12 + 16)•5=220 бит
5) для года рождения есть 12 вариантов, поэтому для него нужно отвести 4 бита (2 4 = 16 ≥ 12)
6) таким образом, всего требуется 224 бита или 28 байт
Какое минимальное количество бит необходимо для кодирования
Каждый сотрудник предприятия получает электронный пропуск, на котором записаны личный код сотрудника, код подразделения и некоторая дополнительная информация. Личный код состоит из 13 символов, каждый из которых может быть одной из 12 допустимых заглавных букв или одной из 10 цифр. Для записи личного кода используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством бит. Код подразделения состоит из двух натуральных чисел, не превышающих 1000, каждое из которых кодируется как двоичное число и занимает минимально возможное целое число бит. Личный код и код подразделения записываются подряд и вместе занимают минимально возможное целое число байт. Всего на пропуске хранится 32 байт данных. Сколько байт выделено для хранения дополнительных сведений об одном сотруднике? В ответе запишите только целое число — количество байт.
При кодировании k бит позволяют кодировать 2 k символов. Заметим, что 
поэтому для кодирования 22-символьного алфавита требуется 5 бит. Для хранения 13 символов требуется 
Минимальное число бит, необходимое для кодирования числа, не превышающего 1000, равно 10 битам, следовательно, для хранения двух таких чисел потребуется 20 бит. Личный код и код подразделения записываются подряд и вместе занимают минимально возможное целое число байт. Минимальное количество байт, вмещающее в себя 85 бит — 11 байт. Всего на пропуске хранится 32 байт данных. Значит, для хранения дополнительных сведений о сотруднике отводится 32 байта − 11 байт = 21 байт данных.
Какое минимальное количество бит необходимо для кодирования
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 12-символьного набора: А, В, C, D, Е, F, G, H, К, L, M, N. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего отведено 12 байт на одного пользователя.
Определите объём памяти (в байтах), необходимый для хранения сведений о 50 пользователях. В ответе запишите только целое число — количество байт.
На кодирование одного символа из 12-буквенного алфавита требуется 4 бита. Тогда на один пароль необходимо 
бит. Минимальное количество байт, вмещающее 60 бит — 8. Итого на одного пользователя необходимо 
байт. А на 50 пользователей нужно 
байт.
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 12-символьного набора: А, В, C, D, Е, F, G, H, K, L, M, N. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей. Для хранения сведений о 20 пользователях потребовалось 400 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число – количество байт.
Для хранения всех 15 символов пароля нужно 4 · 15 = 60 бит, а т. к. для записи используется целое число байт, то берём ближайшее не меньшее значение, кратное восьми, это число 64 = 8 · 8 бит (8 байт).
Пусть количество памяти, отведенное под дополнительные сведения равно x, тогда: