Погода
Календарь
Март 2019
Пн Вт Ср Чт Пт Сб Вс
« Сен    
 123
45678910
11121314151617
18192021222324
25262728293031
Страницы сайта

Вычисление количества информации.

ИЗМЕРЕНИЕ КОЛИЧЕСТВА ИНФОРМАЦИИ
ПРИ РАБОТЕ С ТЕКСТОМ

С помощью K бит можно закодировать Q = 2K  различных символов:

  • Q — мощность алфавита
  • K — количество бит для хранения одного символа из Q вариантов символов
  • 2 — двоичная система счисления (данные хранятся в двоичном виде)
    Также приняты другие обозначения: N = 2i
    Чтобы найти информационный объем сообщения I, нужно умножить количество символов N на число бит для хранения одного символа K:
    I = N * K
    I — информационный объем сообщения,
    — длина сообщения (количество символов),
    K — количество бит для хранения одного символа

ИЗМЕРЕНИЕ КОЛИЧЕСТВА ИНФОРМАЦИИ
ПРИ РАБОТЕ С РАЗЛИЧНЫМИ СИСТЕМАМИ

  • С помощью K бит можно закодировать 
    Q = 2K  различных (номеров) объектов некоторой системы:
    Q — общее количество объектов в некоторой системе, данные о которых хранятся в компьютере или передаются в сообщении,
    K — количество бит для хранения одного объекта из общего количества Q,
    2 — двоичная система счисления (данные хранятся в двоичном виде).
    Также приняты другие обозначения: N = 2i
    Чтобы найти информационный объем сообщения I, нужно умножить количество объектов в сообщении — N— на число бит K для хранения одного объекта:
    I = N * K
    I — информационный объем сообщения,
    — количество объектов в сообщении
    K — количество бит для хранения одного объекта системы.

Задание 1:  При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 11 символов. Из соображений информационной безопасности каждый пароль должен содержать хотя бы 2 десятичных цифры, как прописные, так и строчные латинские буквы, а также не менее 2-х символов из 6-символьного набора: «&», «#», «$», «*», «!», «@». В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей. Для хранения сведений о 30 пользователях потребовалось 900 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число – количество байт.

Решение:

  1. если бы мы знали точно, сколько цифр и сколько специальных символов содержит пароль и где точно они расположены, можно было бы использовать «раздельное» кодирование: на кодирование цифр использовать по 4 бита (24 > 10), на кодирование спецсимволов – по 3 бита (23 > 6), а на кодирование остальных символов (латинских букв) – по 6 бит (26 > 26·2=52)
  2. поскольку количество и месторасположение цифр и спецсимволов а пароле неизвестно, нужно рассматривать полный набор символов: 10 + 6 + 26·2 = 68
  3. при этом на каждый символ нужно выделить 7 бит (27 > 68)
  4. на 11 символов пароля выделяется 77 бит, округляя вверх до целого числа байт получаем 10 байт (80 бит) на пароль
  5. на одного пользователя выделяется 900 : 30 = 30 байт
  6. на дополнительную информацию остается 30 – 10 = 20 байт

Ответ: 20.

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

Решение:

  1. согласно условию, в пароле можно использовать 5 символов
  2. для кодирования номера одного из 5 символов нужно выделить 3 бита памяти (они позволяют закодировать 23 = 8 вариантов)
  3. для хранения всех 15 символов пароля нужно 15 × 3 = 45 бит
  4. поскольку пароль должен занимать целое число байт, берем ближайшее большее (точнее, не меньшее) значение, которое кратно 8: это 48 = 6 × 8; то есть один пароль занимает 6 байт
  5. тогда 30 паролей занимают 6 × 30 = 180 байт

Ответ: 180.

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

Решение:

  1. велосипедистов было 119, у них 119 разных номеров, то есть, нам нужно закодировать 119 вариантов
  2. по таблице степеней двойки находим, что для этого нужно минимум 7 бит (при этом можно закодировать 128 вариантов, то есть, еще есть запас); итак, 7 бит на один отсчет
  3. когда 70 велосипедистов прошли промежуточный финиш, в память устройства записано 70 отсчетов
  4. поэтому в сообщении 70*7 = 490 бит информации.

Ответ: 490

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

Решение:

  1. информация в 4 бита соответствует выбору одного из 16 вариантов, …
  2. … поэтому в вольере А живет 1/16 часть всех обезьян
  3. всего обезьян – 32, поэтому в вольере А живет 32/16 = 2 обезьяны
  4. поэтому в вольере Б живут все оставшиеся 32 – 2 = 30 обезьян

Ответ – 30.

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

Решение:

  1. красные клубки шерсти составляют 1/8 от всех, …
  2. поэтому сообщение о том, что первый вынутый клубок шерсти – красный, соответствует выбору одного из 8 вариантов
  3. выбор 1 из 8 вариантов – это информация в 3 бита (по таблице степеней двойки)

Ответ – 3.

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

Решение:

  1. всего используется 26 букв + 10 цифр = 36 символов
  2. для кодирования 36 вариантов необходимо использовать 6 бит, так как 25 = 32 < 36 <= 26 = 64, т. е. пяти бит не хватит (они позволяют кодировать только 32 варианта), а шести уже достаточно
  3. таким образом, на каждый символ нужно 6 бит (минимально возможное количество бит)
  4. полный номер содержит 7 символов, каждый по 6 бит, поэтому на номер требуется 6 * 7 = 42 бита
  5. по условию каждый номер кодируется целым числом байт (в каждом байте – 8 бит), поэтому требуется 6 байт на номер (5 * 8 = 40 < 42 <= 6 * 8 = 48), пяти байтов не хватает, а шесть – минимально возможное количество
  6. на 20 номеров нужно выделить 20 * 6 = 120 байт

Ответ – 120.

Задание 7:  Выбор ре­жи­ма ра­бо­ты в не­ко­то­ром устрой­стве осу­ществ­ля­ет­ся уста­нов­кой ручек тум­бле­ров, каж­дая из ко­то­рых может на­хо­дить­ся в од­ном из пяти по­ло­же­ний. Ка­ко­во ми­ни­маль­ное ко­ли­че­ство не­об­хо­ди­мых тум­бле­ров для обес­пе­че­ния ра­бо­ты устрой­ства на 37 ре­жи­мах.

Решение: Пред­ста­вим, что одно по­ло­же­ние есть один сим­вол, а т. к. тум­бле­ров N, то надо со­ста­вить N-бук­вен­ное слово.
Име­ет­ся 5 раз­лич­ных по­ло­же­ний, зна­чит, 5 сим­во­лов. Из M = 5 раз­лич­ных сим­во­лов можно со­ста­вить Q = MN слов дли­ной N, т. е. по усло­вию 5N ≥ 37 слов. На­хо­дим наи­мень­шее целое N: N = 3.

Ответ – 3.

Задание 8:  B не­ко­то­рой стра­не ав­то­мо­биль­ный номер дли­ной 6 сим­во­лов со­став­ля­ют из за­глав­ных букв (ис­поль­зу­ют­ся толь­ко 33 раз­лич­ных буквы) и де­ся­тич­ных цифр в любом по­ряд­ке. Каж­дый такой номер в ком­пью­тер­ной про­грам­ме за­пи­сы­ва­ет­ся ми­ни­маль­но воз­мож­ным и оди­на­ко­вым целым ко­ли­че­ством бай­тов (при этом ис­поль­зу­ют по­сим­воль­ное ко­ди­ро­ва­ние и все сим­во­лы ко­ди­ру­ют­ся оди­на­ко­вым и ми­ни­маль­но воз­мож­ным ко­ли­че­ством битов). Опре­де­ли­те объём па­мя­ти, от­во­ди­мый этой про­грам­мой для за­пи­си 125 но­ме­ров. (Ответ дайте в бай­тах.)

Решение: Со­глас­но усло­вию, в но­ме­ре могут быть ис­поль­зо­ва­ны 10 цифр (0..9) и 33 буквы, всего 10 + 33 = 43 сим­во­лов. Из­вест­но, что с по­мо­щью N бит можно за­ко­ди­ро­вать 2N раз­лич­ных ва­ри­ан­тов. По­сколь­ку 25 < 43 < 26, то для за­пи­си каж­до­го из 43 сим­во­лов не­об­хо­ди­мо 6 бит.
Для хра­не­ния всех 6 сим­во­лов но­ме­ра нужно 6 * 6 = 36 бит, а т. к. для за­пи­си ис­поль­зу­ет­ся целое число байт, то берём бли­жай­шее не мень­шее зна­че­ние, крат­ное вось­ми, это число 40 = 5 * 8 бит (5байт).
Тогда 125 но­ме­ров за­ни­ма­ют 5 * 125 = 625 байт.


Ответ – 625.

Задание 9. Демоверсия ЕГЭ 2018 информатика (ФИПИ). 
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 10 символов. В качестве символов используют прописные буквы латинского алфавита, т.е. 26 различных символов. В базе данных для хранения каждого пароля отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит.
Определите объём памяти (в байтах), необходимый для хранения данных о 50пользователях. В ответе запишите только целое число – количество байт.

Решение:

  • Основной формулой для решения данной задачи является: Q= 2где Q — количество вариантов символов, которые можно закодировать с помощью N бит.
  • Чтобы найти количество бит, необходимое для хранения одного пароля, для начала нужно найти количество бит, необходимых для хранения 1 символа в пароле. По формуле получаем: 26 = 2N -> N ~ 5 бит
  • Пароль состоит из 10 символов. Значит на пароль необходимо выделить бит: 10 * 5 = 50 бит всего на пароль
  • Поскольку сведения о пароле сохраняются в байтах, то переведем : 50 бит / 8 ~ 7 байт (берем ближайшее число большее 50 и кратное 8: 57/8 = 7)
  • Теперь найдем сколько байт отводится для хранения информации о 50 пользователях: 7 байт * 50 (пользователей) = 350 байт
    Ответ: 350
Top