какое минимальное количество бит необходимо для кодирования
Какое минимальное количество бит необходимо для кодирования
Каждый сотрудник предприятия получает электронный пропуск, на котором записаны личный код сотрудника, код подразделения и некоторая дополнительная информация. Личный код состоит из 20 букв. Для формирования кодов используется 14 различных букв, каждая из которых может быть заглавной или строчной. Для записи кода на пропуске отведено минимально возможное целое число байт. При этом используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством бит. Код подразделения — целое четырёхзначное число, он записан на пропуске как двоичное число и занимает минимально возможное целое число байт. Всего на пропуске хранится 30 байт данных. Сколько байт выделено для хранения дополнительных сведений об одном сотруднике? В ответе запишите только целое число — количество байт.
k бит позволяют кодировать 2 k символов, поэтому для кодирования 28-символьного алфавита требуется 5 бит (ведь 
. Для хранения 20 символов требуется 
бит. Минимальное количество байт, вмещающее в себя 100 бит — 13 байт (104 бит). Номер подразделения можно закодировать 2 байтами, поскольку в 1 байт помещаются только числа от 0 до 255.
Для хранения данных об одном сотруднике требуется 30 байт данных. Из них 13 байт отводится на хранение личного кода, ещё 2 байта требуется для хранения номера подразделения. Следовательно, для хранения дополнительных сведений о сотруднике отводится 15 байт.
1.Какое минимальное число бит необходимо для кодирования всех символов клавиатуры?
1.Какое минимальное число бит необходимо для кодирования всех символов клавиатуры?
вопрос на экзамене
8 бит, что будет составлять 1 байт 😉 одинм байтом описывается любой символ, будь то буква, цифра, точка и даже пробел.
Кодирование будет двоичное т. е 00000001 00000010 и т. д.
при этом первые 127 символов для ЛЮБОЙ клавиатуры стандартны. Это латиница, знаки припинания цифра и арифметика.
Таблице символов от 128 до 256 можно изменить програмно, что позволяет использовать другие языки, кирилицу, азиатские языки и прочие.
Но первые 127 символов это табу
А вот и официоз из оф. источника:
Кодирование текста
Множество символов, используемых при записи текста, называется алфавитом. Количество символов в алфавите называется его мощностью.
Для представления текстовой информации в компьютере чаще всего используется алфавит мощностью 256 символов. Один символ из такого алфавита несет 8 бит информации, т. к. 28 = 256. Но 8 бит составляют один байт, следовательно, двоичный код каждого символа занимает 1 байт памяти ЭВМ.
Все символы такого алфавита пронумерованы от 0 до 255, а каждому номеру соответствует 8-разрядный двоичный код от 00000000 до 11111111. Этот код является порядковым номером символа в двоичной системе счисления.
Для разных типов ЭВМ и операционных систем используются различные таблицы кодировки, отличающиеся порядком размещения символов алфавита в кодовой таблице. Международным стандартом на персональных компьютерах является уже упоминавшаяся таблица кодировки ASCII.
Принцип последовательного кодирования алфавита заключается в том, что в кодовой таблице ASCII латинские буквы (прописные и строчные) располагаются в алфавитном порядке. Расположение цифр также упорядочено по возрастанию значений.
Стандартными в этой таблице являются только первые 128 символов, т. е. символы с номерами от нуля (двоичный код 00000000) до 127 (01111111). Сюда входят буквы латинского алфавита, цифры, знаки препинания, скобки и некоторые другие символы. Остальные 128 кодов, начиная со 128 (двоичный код 10000000) и кончая 255 (11111111), используются для кодировки букв национальных алфавитов, символов псевдографики и научных символов.
Какое минимальное количество бит необходимо для кодирования
Тема: Вычисление информационного объема сообщения.
· с помощью 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 байт
Какое минимальное количество бит необходимо для кодирования
Каждый работник предприятия получает электронный пропуск, на котором записаны личный код сотрудника, код подразделения и некоторая дополнительная информация. Личный код состоит из 15 символов, каждый из которых может быть одной из 12 допустимых заглавных букв или одной из 10 цифр. Для записи личного кода на пропуске отведено минимально возможное целое число байт. При этом используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством бит. Код подразделения состоит из двух двузначных чисел, каждое из которых кодируется как двоичное число и занимает минимально возможное целое число байт. Всего на пропуске хранится 32 байт данных. Сколько байт выделено для хранения дополнительных сведений об одном сотруднике? В ответе запишите только целое число — количество байт.
При кодировании k бит позволяют кодировать 2 k символов. Заметим, что 
поэтому для кодирования 22-символьного алфавита требуется 5 бит. Для хранения 15 символов требуется 
Минимальное количество байт, вмещающее в себя 75 бит — 10 байт.
Минимальное число байт, необходимое для кодирования двузначного числа равно 1 байту, следовательно, для хранения двух таких чисел потребуется 2 байта. Всего на пропуске хранится 32 байт данных. Значит, для хранения дополнительных сведений о сотруднике отводится 32 − 10 − 2 = 20 байт данных.
Урок посвящён 11 заданию из ЕГЭ по информатике нового формата 2021. Проанализируем основные примеры и научимся решать это задание!
В 11 задании из ЕГЭ по информатике часто даются задачи на умение работать с количеством информации.
Приступим к делу! Раньше это задание было под номером тринадцать.
Задача (Демонстрационный вариант ЕГЭ по информатике, 2018)
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 10 символов. В качестве символов используют прописные буквы латинского алфавита, т.е. 26 различных символов. В базе данных для хранения каждого пароля отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Определите объём памяти (в байтах), необходимый для хранения данных о 50 пользователях. В ответе запишите только целое число – количество байт.
У каждого пользователя есть пароль, состоящий из 10 символов. Это значит, длина пароля 10 символов!
И в каждую ячейку мы может выбрать символ из 26 букв!
Здесь важно различать длину пароля и количество символов из которых пользователь выбирает для каждой ячейки пароля.
Теперь нужно определить: сколько бит занимает одна ячейка (1 символ пароля!).
Когда речь идёт о количестве бит, применяем формулу, которую мы использовали в 7 задании из ЕГЭ по информатике. Там мы кодировали цвета для одного пикселя, а здесь нужно закодировать 26 букв для одного поля пароля.
Целого числа нету для i (количества бит), чтобы равенство было верным. Значит берём столько количество бит, сколько точно будет достаточно, чтобы закодировать 26 букв (символов).
Получаем одна ячейка (одно поле) пароля занимаем 5 бит! А в пароле их 10! Значит, весь пароль будет занимать:
Vпароля = 5 бит * 10 символов = 50 бит (в одном пароле!)
В условии сказано: для хранения каждого пароля отведено одинаковое и минимально возможное целое число байт. Это означает, что мы не может выделять память по одному биту. Память выделяется блоками по 8 бит (по одному байту).
Если взять 7 блоков по 8 бит (1 байту), то нам хватит этого на один пароль.
7 блоков (байт) * 8 бит = 56 бит > 50 бит
Таким образом, на 1 пароль потребуется 7 байт!
Тогда на 50 пользователей потребуется:
50 пользователей * 7 байт = 350 байт (для 50 пользователей).
Ответ: 350
Разберём задачу, которая была на реальном экзамене в Москве
Задача (ЕГЭ по информатике, 2020, Москва)
Здесь длина пароля составляет 11 символов!
Найдём сколько бит занимает одна ячейка пароля.
Найдём сколько бит нужно на весь пароль.
Vпароля = 6 бит * 11 символов = 66 бит (в одном пароле!)
Теперь найдём, а сколько байт нужно на 1 пароль:
9 * 8 бит = 72 бит > 66 бит
Следовательно, 9 байт достаточно, чтобы покрыть 66 бит на 1 пароль.
Сказано, что для 30 сотрудников выделено 750 байт. Подсчитаем, сколько байт будет выделено на одного сотрудника.
Vпользователя = 750 байт / 30 = 25 байт (приходится на одного пользователя)
Мы выяснили, что на пароль из этих 25 байт потребуется 9 байт. Тогда на дополнительную информацию о каждом пользователе потребуется:
Ещё один важный пример из запасов тренировочных задач ЕГЭ по информатике.
В велокроссе участвуют 48 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена.Какой объём памяти будет использован устройством, когда все спортсмены прошли промежуточный финиш? (Ответ дайте в байтах.)
Узнаем сколько бит потребуется выделить на каждого спортсмена, чтобы была возможность записать любой номер от 1 до 48.
На рисунке показано, как может происходить кодирование чисел. Например, для двух номеров потребуется 1 бит (2 1 = 2), для четырёх номеров потребуется два бита (2 2 = 4). Нам нужно закодировать 48 чисел! Причём для каждого участника отведено одинаковое количество бит!
Получается 6 бит потребуется для того, чтобы была возможность записать любой номер от 1 до 48 для каждого спортсмена. Если взять пять бит, то мы будем иметь возможность записать номера только от 1 до 2 5 = 32 для каждого спортсмена (этого не хватает).
Т.к. все участники пересекли финиш, а на каждого участника выделено по 6 бит, то получается:
6 бит * 48 = 288 бит = 36 байт
Ответ: 36
Найдём сколько бит потребуется для кодирования 4-х букв.
N = 2 i = 2 4 бита = 16 > 12
4 бита хватит для кодирования 12 букв. Всего таких ячейки 4! Поэтому в одном номере на все буквы уйдёт 4 * 4 бита = 16 бит.
Найдём сколько бит потребуется на кодирование 3 ячеек, где находятся цифры.
Для кодирования одной ячейки, где находится цифра, потребуется 3 бита.
Все цифры в одном номере будут закодированы 3 бита * 3 = 9 битами.
Всего на один номер уйдёт 16 бит + 9 бит = 25 бит.
Найдём сколько байт потребуется для кодирования одного номера.
4 * 8 бит (1 байт) = 32 бита > 25 бит
4-х байт достаточно, чтобы закодировать 25 бит. Если взять 3 байта, то 3 * 8 бит (1 байт) = 24 бита. Этого будет не достаточно.
Найдём количество байт, которое нужно для кодирования 160 автомобилей
160 автомобилей * 4 байта = 640 байт
Метеорологическая станция ведет наблюдение за влажностью воздуха. Результатом одного наблюдения является целое число от 0 до 100%, записываемое при помощи минимально возможного количества бит. Станция сделала 800 измерений. Определите информационный объем результатов наблюдений. (Ответ дайте в байтах.)
Здесь, нужно закодировать сто одно число (от 0 до 100). Ситуация похоже на ту, где мы кодировали номера спортсменов.
Получается, что 7 бит потребуется, чтобы полностью закодировать 101 число.
Всего было сделано 800 таких измерений
800 * 7 бит = 5600 бит = 700 байт
Ответ: 700
На этом всё! Удачи при решении 11 задания на ЕГЭ по информатике!