Задание 13 (презентация по типам задач к ЕГЭ)

Ege 13

Умение подсчитывать информационный объем сообщения

Что нужно знать :

• с помощью K бит можно закодировать различных вариантов (чисел)
• таблица степеней двойки, она же показывает, сколько вариантов Q можно закодировать с помощью K бит:

K, бит

1

Q, вариантов

2

2

3

4

8

4

5

16

32

6

7

64

8

128

9

256

10

512

1024

• при измерении количества информации принимается, что в одном байте 8 бит, а в одном килобайте (1 Кбайт) – 1024 байта, в мегабайте (1 Мбайт) – 1024 Кбайта

• чтобы найти информационный объем сообщения (текста) I, нужно умножить количество символов (отсчетов) N на число бит на символ (отсчет) K :

количество всех возможных «слов» (символьных цепочек) длиной N

мощность двоичного алфавита

Пример I:

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы Ш, К, О, Л, А (таким образом, используется 5 различных символов). Каждый такой пароль в компьютерной системе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит). Укажите объём памяти в байтах, отводимый этой системой для записи 30 паролей. В ответе запишите только число, слово «байт» писать не нужно.

Решение:

• для кодирования номера одного из 5 символов нужно выделить 3 бита памяти (они позволяют закодировать 2 3 = 8 вариантов)

• для хранения всех 15 символов пароля нужно 15  3 = 45 бит

• поскольку пароль должен занимать целое число байт, берем ближайшее большее (точнее, не меньшее) значение, которое кратно 8: это 48 = 6  8; то есть один пароль занимает 6 байт

тогда 30 паролей занимают 6  30 = 180 байт

Ответ: 180

Пример II:

Для регистрации на сайте некоторой страны пользователю требуется придумать пароль. Длина пароля – ровно 11 символов . В качестве символов используются десятичные цифры и 12 различных букв местного алфавита, причём все буквы используются в двух начертаниях: как строчные , так и заглавные (регистр буквы имеет значение!). Под хранение каждого такого пароля на компьютере отводится минимально возможное и одинаковое целое количество байтов, при этом используется посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов. Определите объём памяти в байтах, который занимает хранение 60 паролей.

Решение:

• Алфавит: 10 + 12 + 12 = 34 символа

• для кодирования номера одного из 34 символов нужно выделить 6 бит памяти

• для хранения всех 11 символов пароля нужно 11  6 = 66 бит

• поскольку пароль должен занимать целое число байт, берем ближайшее большее (точнее, не меньшее) значение, которое кратно 8: это 72 = 9  8; то есть один пароль занимает 9 байт

Ответ: 540

тогда 60 паролей занимают 9  60 = 540 байт

Пример III:

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

Решение:

• велосипедистов было 119, у них 119 разных номеров, то есть, нам нужно закодировать 119 вариантов

• по таблице степеней двойки находим, что для этого нужно минимум 7 бит (при этом можно закодировать 128 вариантов, то есть, еще есть запас); итак, 7 бит на один отсчет

• когда 70 велосипедистов прошли промежуточный финиш, в память устройства записано 70 отсчетов

• поэтому в сообщении 70*7 = 490 бит информации.

Ответ: 490

Пример IV:

Объем сообщения, содержащего 4096 символов, равен 1/512 части Мбайта. Какова мощность алфавита, с помощью которого записано это сообщение?

Решение:

• в сообщении было 4096 = 2 12 символов объем сообщения

• 1/512 Мбайта=2 23 /512 бита=2 23 /2 9 бита 2 14 бита(=16384 бита!)

• место, отведенное на 1 символ:

2 14 бита / 2 12 символов = 2 2 бита на символ = 4 бита на символ

• 4 бита на символ позволяют закодировать 2 4 = 16 разных символов

поэтому мощность алфавита – 16 символов

Ответ: 16

Пример V:

В зоопарке 32 обезьяны живут в двух вольерах, А и Б. Одна из обезьян заболела. Сообщение «Заболевшая обезьяна живет в вольере А» содержит 4 бита информации. Сколько обезьян живут в вольере Б?

Решение:

• информация в 4 бита соответствует выбору одного из 16 вариантов, …

• … поэтому в вольере А живет 1/16 часть всех обезьян (это самый важный момент !)

• всего обезьян – 32, поэтому в вольере А живет

32/16 = 2 обезьяны

• поэтому в вольере Б живут все оставшиеся

32 – 2 = 30 обезьян

Ответ: 30

Пример VI:

В корзине лежат 32 клубка шерсти, из них 4 красных. Сколько бит информации несет сообщение о том, что достали клубок красной шерсти?

Решение:

• красные клубки шерсти составляют 1/8 от всех, …

• поэтому сообщение о том, что первый вынутый клубок шерсти – красный, соответствует выбору одного из 8 вариантов

• выбор 1 из 8 вариантов – это информация в 3 бита

Ответ: 3

Пример VII:

В некоторой стране автомобильный номер длиной 7 символов составляется из заглавных букв (всего используется 26 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным целым количеством байт. Определите объем памяти, необходимый для хранения 20 автомобильных номеров .

Решение:

• Мощность алфавита 26 букв + 10 цифр = 36 символов

• для кодирования 36 вариантов необходимо использовать 6 бит, так как

• полный номер содержит 7 символов, каждый по 6 бит, поэтому на номер требуется бита

• по условию каждый номер кодируется целым числом байт (в каждом байте – 8 бит), поэтому требуется 6 байт на номер

Тогда на 20 номеров нужно выделить байт

Ответ: 120

– 16 символов: русские буквы (первая прописная, остальные строчные),      Имя – 12 символов: русские буквы (первая прописная, остальные строчные),      Отчество – 16 символов: русские буквы (первая прописная, остальные строчные),      Год рождения – числа от 1992 до 2003 . Каждое поле записывается с использованием минимально возможного количества бит. Определите минимальное количество байт , необходимое для кодирования одной записи, если буквы е и ё считаются совпадающими. Решение: для символьных полей достаточно использовать алфавит из 32 символов (русские строчные буквы, «е» и «ё» совпадают, пробелы не нужны) для кодирования каждого символа 32-символьного алфавита нужно 5 бит (32 = 2 5 ), поэтому для хранения имени, отчества и фамилии нужно (16 + 12 + 16)•5=220 бит для года рождения есть 12 вариантов, поэтому для него нужно отвести 4 бита (2 4 =16≥12) таким образом, всего требуется 224 бита или 28 байт Ответ: 28 " width="640"

Пример VIII:

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

     Фамилия – 16 символов: русские буквы (первая прописная, остальные строчные),

     Имя – 12 символов: русские буквы (первая прописная, остальные строчные),

     Отчество – 16 символов: русские буквы (первая прописная, остальные строчные),

     Год рождения – числа от 1992 до 2003 .

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

Решение:

• для символьных полей достаточно использовать алфавит из 32 символов (русские строчные буквы, «е» и «ё» совпадают, пробелы не нужны)

• для кодирования каждого символа 32-символьного алфавита нужно 5 бит (32 = 2 5 ), поэтому для хранения имени, отчества и фамилии нужно (16 + 12 + 16)•5=220 бит

• для года рождения есть 12 вариантов, поэтому для него нужно отвести 4 бита (2 4 =16≥12)

таким образом, всего требуется 224 бита или 28 байт

Ответ: 28

ДЕМО 2016

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 12-символьного набора : А, В, C, D, Е, F, G, H, K, L, M, N. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей.

Для хранения сведений о 20 пользователях потребовалось 400 байт . Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число – количество байт.

Ответ: 12

Вариант 1.

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 12-символьного набора : А, В, C, D, Е, F, G, H, К, L, M, N. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения , для чего отведено 12 байт на одного пользователя. Определите объём памяти (в байтах), необходимый для хранения сведений о 50 пользователях . В ответе запишите только целое число – количество байт.

Ответ: 1000

Вариант 2.

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 8-символьного набора : А, В, C, D, Е, F, G, H. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения , для чего отведено 24 байта на одного пользователя. Определите объём памяти (в байтах), необходимый для хранения сведений о 30 пользователях . В ответе запишите только целое число – количество байт.

Ответ: 900