Как найти минимально возможное количество бит

Задание 1. Тип заданий 13: количество информации.

Комментарии ()

Нет комментариев. Ваш будет первым!

Формулировка задания: В соревновании участвуют N атлетов. Какое минимальное количество бит необходимо, чтобы кодировать номер каждого атлета?

Задание входит в ЕГЭ по информатике для 11 класса.

Рассмотрим, как решаются подобные задания на примере.

Поделитесь статьей с одноклассниками «Какое минимальное количество бит необходимо, чтобы кодировать номер – как решать».

При копировании материалов с сайта ссылка на источник обязательна. Уважайте труд людей, которые вам помогают.
Нашли ошибку? Выделите текст и нажмите Ctrl + Enter.

Предварительно генерируем массив степеней двойки. Cравниваем число со степенями из массива, пока не найдём первое превышающее. Индекс этого числа и есть искомый размер.

Вот код и тесты:

import org.junit.Assert;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;

import java.util.Arrays;
import java.util.Collection;

@RunWith(Parameterized.class)
public class Algorithms {

    public static int[] powersOfTwo = new int[31];

    static {
        powersOfTwo[0] = 1;
        for (int power = 1; power < powersOfTwo.length; power++) {
            powersOfTwo[power] = powersOfTwo[power - 1] * 2;
        }
    }

    @Parameterized.Parameter(0)
    public int number;
    @Parameterized.Parameter(1)
    public int size;

    @Parameterized.Parameters(name = "number:{0}, size:{1}")
    public static Collection<Object[]> data() {
        return Arrays.asList(new Object[][]{
                {0, 1},
                {1, 1},
                {3, 2},
                {((int) Math.pow(2, 10)) - 1, 10},
                {((int) Math.pow(2, 10)), 10},
                {((int) Math.pow(2, 10)) + 1, 11},
                {Integer.MAX_VALUE, 31}
        });
    }

    public static int getSizeOf(int number) {
        for (int power = 1; power < 30; power++) {
            if (powersOfTwo[power] >= number) return power;
        }
        return 31;
    }

    @Test
    public void testSizeOf() {
        Assert.assertEquals(size, getSizeOf(number));
    }
}

Этот алгоритм должен быть быстрее, чем вычисление логарифмов или деление.

Урок посвящён 11 заданию из ЕГЭ по информатике нового формата 2022. Проанализируем основные примеры и научимся решать это задание!

В 11 задании из ЕГЭ по информатике часто даются задачи на умение работать с количеством информации.

Приступим к делу! Раньше это задание было под номером тринадцать.

Задача (Демонстрационный вариант ЕГЭ по информатике, 2018)

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

Решение:

У каждого пользователя есть пароль, состоящий из 10 символов. Это значит, длина пароля 10 символов!

И в каждую ячейку мы может выбрать символ из 26 букв!

Здесь важно различать длину пароля и количество символов из которых пользователь выбирает для каждой ячейки пароля.

Теперь нужно определить: сколько бит занимает одна ячейка (1 символ пароля!).

Когда речь идёт о количестве бит, применяем формулу, которую мы использовали в 7 задании из ЕГЭ по информатике. Там мы кодировали цвета для одного пикселя, а здесь нужно закодировать 26 букв для одного поля пароля.

Применяем:

N = 2ⁱ = 26

Целого числа нету для i (количества бит), чтобы равенство было верным. Значит берём столько количество бит, сколько точно будет достаточно, чтобы закодировать 26 букв (символов).

N = 2⁵ > 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 символов. В качестве символов используют 26
прописных букв из латинского алфавита и десять цифр. В базе
данных для хранения каждого пароля отведено одинаковое и минимально
возможное целое число байт. При этом используют посимвольное
кодирование паролей, все символы кодируют одинаковым
и минимально возможным количеством бит.
Кроме собственно пароля для каждого пользователя в системе хранятся дополнительные сведения.
Для кодирования данных о 30 сотрудниках было выделено 750 байт. Сколько памяти(в байтах) выделено для хранения дополнительных сведений об одном пользователе. В ответ запишите только целое число — количество байт.

Решение:

Здесь длина пароля составляет 11 символов!

Найдём сколько бит занимает одна ячейка пароля.

N = 2ⁱ = 36

N = 2⁶ = 64 > 36

Значит, 6 бит — минимальное количество бит, которое нужно, чтобы была возможность разместить любой из 36 символов в одной ячейке пароля.

Найдём сколько бит нужно на весь пароль.

V_пароля = 6 бит * 11 символов = 66 бит (в одном пароле!)

Теперь найдём, а сколько байт нужно на 1 пароль:

9 * 8 бит = 72 бит > 66 бит

Следовательно, 9 байт достаточно, чтобы покрыть 66 бит на 1 пароль.

Сказано, что для 30 сотрудников выделено 750 байт. Подсчитаем, сколько байт будет выделено на одного сотрудника.

V_{пользователя} = 750 байт / 30 = 25 байт (приходится на одного пользователя)

Мы выяснили, что на пароль из этих 25 байт потребуется 9 байт. Тогда на дополнительную информацию о каждом пользователе потребуется:

V_{доп. о 1 пол.} = 25 байт — 9 байт = 16 байт

Это и будет ответ.

Ответ: 16

Ещё один важный пример из запасов тренировочных задач ЕГЭ по информатике.

Задача (Номера спортсменов)

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

Решение:

Узнаем сколько бит потребуется выделить на каждого спортсмена, чтобы была возможность записать любой номер от 1 до 48.

В этой задаче сказано: записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена . Это означает что у нас есть 48 различных позиций (номеров), которые нужно закодировать с помощью определённого количества бит. В предыдущей задаче, у нас было 62 различные позиции (символа), которые нужно было закодировать с помощью определённого количества бит. Мы там использовали формулу N = 2ⁱ.

Поэтому будем опять применять формулу N = 2ⁱ.

На рисунке показано, как может происходить кодирование чисел. Например, для двух номеров потребуется 1 бит (2¹ = 2), для четырёх номеров потребуется два бита (2² = 4). Нам нужно закодировать 48 чисел! Причём для каждого участника отведено одинаковое количество бит!

Можно сказать, что здесь работает формула, которую рассматривали в 8 задании. Всего нужно составить 48 различных комбинаций (закодировать 48 номеров). В каждой ячейке можно писать либо 0, либо 1 (Свойство бита информации). Какова должна быть длина «слова» (количество бит) ?

N = 2ⁱ = 2^{6 бит} = 64 > 48

Получается 6 бит потребуется для того, чтобы была возможность записать любой номер от 1 до 48 для каждого спортсмена. Если взять пять бит, то мы будем иметь возможность записать номера только от 1 до 2⁵ = 32 для каждого спортсмена (этого не хватает).

Т.к. все участники пересекли финиш, а на каждого участника выделено по 6 бит, то получается:

6 бит * 48 = 288 бит = 36 байт

Ответ: 36

Задача (Автомобильный номер)

В некоторой стране автомобильный номер состоит из 7 символов: сначала 2 буквы, затем 3 цифры, затем ещё 2 буквы. При этом буквы могут быть выбраны только из 12 строчных букв местного алфавита. Среди цифр не используются цифры 6 и 9. Автоматизированная система хранит номера автомобилей следующим образом. Используется посимвольное кодирование. В памяти системы для кодирования каждого символа используется минимально возможное и одинаковое целое количество бит (для букв и цифр отдельно). А для номера используется минимально возможное целое количество байт. Какое количество информации (в байтах) требуется для хранения номеров 160 автомобилей ?

Решение:

Найдём сколько бит потребуется для кодирования 4-х букв.

N = 2ⁱ = 2^{4 бита} = 16 > 12

4 бита хватит для кодирования 12 букв. Всего таких ячейки 4! Поэтому в одном номере на все буквы уйдёт 4 * 4 бита = 16 бит.

Найдём сколько бит потребуется на кодирование 3 ячеек, где находятся цифры.

N = 2ⁱ = 2^{3 бита} = 8

Для кодирования одной ячейки, где находится цифра, потребуется 3 бита.

Все цифры в одном номере будут закодированы 3 бита * 3 = 9 битами.

Всего на один номер уйдёт 16 бит + 9 бит = 25 бит.

Найдём сколько байт потребуется для кодирования одного номера.

4 * 8 бит (1 байт) = 32 бита > 25 бит

4-х байт достаточно, чтобы закодировать 25 бит. Если взять 3 байта, то 3 * 8 бит (1 байт) = 24 бита. Этого будет не достаточно.

Найдём количество байт, которое нужно для кодирования 160 автомобилей

160 автомобилей * 4 байта = 640 байт

Это и будет ответ.

Ответ: 640

Задача (Закрепление формулы)

Метеорологическая станция ведет наблюдение за влажностью воздуха. Результатом одного наблюдения является целое число от 0 до 100%, записываемое при помощи минимально возможного количества бит. Станция сделала 800 измерений. Определите информационный объем результатов наблюдений. (Ответ дайте в байтах.)

Решение:

Здесь, нужно закодировать сто одно число (от 0 до 100). Ситуация похоже на ту, где мы кодировали номера спортсменов.

N = 2ⁱ = 2^{7 бит} = 128 > 101

Получается, что 7 бит потребуется, чтобы полностью закодировать 101 число.

Всего было сделано 800 таких измерений

800 * 7 бит = 5600 бит = 700 байт

Ответ: 700

На этом всё! Удачи при решении 11 задания на ЕГЭ по информатике!

Измерение информации, алфавитный подход

Методика преподавания темы в 10-11 классах и подготовки к ЕГЭ

В данной методике рассматривается алфавитный подход к измерению информации.

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

При этом знание таблиц является необходимым условием для максимально быстрого и точного решения, без потери времени и математических ошибок.

Ниже приведена таблица степеней двойки, где k – это степень, а 2k — результат возведения числа 2 в степень k. При алфавитном подходе эта таблица показывает, сколько вариантов всевозможных «слов» Q= 2^k можно закодировать с помощью k бит на символ.

n	0	1	2	3	4	5	6	7	8	9	10	11	12
2n	1	2	4	8	16	32	64	128	256	512	1024	2048	4096

Бит — наименьшая единица измерения количества информации, может принимать только два значения – 0 или 1.

Байт содержит 8 бит (23 бит). При этом байт является неделимой единицей и всегда отображается целым числом.

Во второй таблице даны укрупненные единицы информации и их соответствие.

В России правила образования укрупненных единиц в информатике подтверждены постановлением № 879 Правительства РФ от 31 октября 2009г. Это постановление гласит:

«Наименование и обозначение единицы количества информации «байт» применяются с двоичными приставками «Кило», «Мега», «Гига», которые соответствуют множителям 210, 220 и 230 (1 Килобайт = 1024 байт, 1 Мегабайт = 1024 Килобайт,

1 Гигабайт = 1024 Мегабайт). Эти приставки пишутся с большой буквы».

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

Наименование ед.изм.	В бит=	В бит / байт	Примечание
1 Кбит (один Килобит)	210 бит	1 024 бит	более 1 тыс.бит
бит (один Мегабит)	220 бит	1 048 576 бит	более 1 млн.бит
1 Гбит (один Гигабит)	230 бит	более 109 бит	более 1 млрд.бит
1 Кбайт (один Килобайт)	213 бит	210 байт = 1024 байт	более 1 тыс.байт
1 Мбайт (один Мегабайт)	223 бит	220 байт = 1 048 576 байт	более 1 млн.байт
1 Гбайт (один Гигабайт)	233 бит	230 байт = 109 байт	более 1 млрд.байт

Таблицы не нужно учить наизусть! Рекомендуется пользоваться ими при решении задач, но при этом заглядывать в них все реже и реже, пытаясь сначала вспомнить значения, приведенные в них. Тогда эти таблицы сами «улягутся» в Вашей голове, и очень поможет Вам на экзамене в этой и в других темах!

Отцом-основателем теории информации, нашедшей применение в современных высокотехнологических системах связи, является американский инженер, криптоаналитик и математик Клод Шеннон. Именно он в 1948 году предложил использовать слово «бит» для обозначения наименьшей единицы измерения информации (в статье «Математическая теория связи»). Кроме того, понятие энтропии было важной особенностью теории Шеннона. Он продемонстрировал, что введённая им энтропия эквивалентна мере неопределённости информации в передаваемом сообщении, что и лежит в основе содержательного подхода к измерению информации, который в данной разработке нами не рассматривается. Статьи Шеннона «Математическая теория связи» и «Теория связи в секретных системах» считаются основополагающими для теории информации и криптографии.

В начале 60-х гг. русский советский математик, один из крупнейших математиков XX века Андрей Николаевич Колмогоров начал искать пути построения теории информации и теории вероятностей на принципиально новой, алгоритмической основе. В свое первой статье по алгоритмической теории информации «Три подхода к определению понятия «количество информации», вышедшей в первом выпуске первого тома журнала «Проблемы передачи информации», в 1965г, А.Н.Колмогоров указал способ измерения сложности конечного объекта (слова), для чего он ввел понятие, называемое сейчас «колмогоровской сложностью». Свое новое понятие он применил для построения алгоритмического варианта теории информации, позволяющего измерять информацию в конечной строке знаков.

Согласно Колмогорову, количество информации, содержащейся в тексте, определяется минимально возможной длиной двоичного кода, необходимого для представления этого текста.

Общей формулой, применяемой в двух различных подходах к измерению информации является формула Хартли — логарифмическая мера информации, которая определяет количество информации, содержащееся в сообщении (объем сообщения):

I = N *log₂М

Здесь М — количество символов в используемом алфавите (мощность алфавита), N — длина сообщения (количество символов в сообщении), I — количество информации в сообщении в битах.

Формула была предложена Ральфом Хартли в 1928 году как один из научных подходов к оценке сообщений.

Для случая определения количества информации k в одном символе (бит на символ) алфавита мощности М, формула Хартли принимает вид:

k = log₂М

Соответственно, мощность алфавита равна:

M= 2^k

Из формулы Хартли следует, что алфавит, содержащий только 1 символ, не может быть использован для передачи информации, так как

log₂1 = 0.

Пусть, имеется алфавит, из M букв которого составляется сообщение.

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

Q = М^k

где М — количество букв в алфавите, k — информационный вес символа (количество бит, необходимое для его кодирования, бит на символ).

Для простоты понимания и решения задач, за М мы будем принимать значения терминов, наиболее часто применяемых в условиях задач – виды, типы, состояния символов. Это упростит понимание и решение задач в алфавитном подходе.

Отметим, что формулы вычисления объема информации I = N * k и подсчета количества вариантов Q=M^k взаимодействуют друг с другом через величину k (бит на символ).

Алфавитный подход к измерению информации

Основные понятия и термины:

Алфавит – это набор символов, используемых в языке, на котором передается сообщение. При этом символом алфавита могут быть буквы, цифры и прочие символы, входящие в сообщение.

Мощность алфавита — это количество символов в алфавите.

Например, мощность русского алфавита равна 32 при Е =Ё и 33 – в противном случае. Мощность английского алфавита равно 26.0

Для упрощения понимания и легкости запоминания различий в рассматриваемых далее задачах, разобьем их на 5 типов и будем рассматривать решения соответственно этим типам.

Для быстрого и точного вычисления количества информации следует применять таблицу степеней двойки, которая показывает, сколько вариантов всевозможных «слов» Q можно закодировать с помощью k бит на символ.

Так же при решении задач следует обязательно привести единицы измерения количества информации к одному виду. При этом помним, что значение k – это бит на символ, другого измерения здесь быть не может!

Задача 1 типа.

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

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

Рекомендации к решению.

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

Читаем условие очень внимательно, находим хотя бы один синоним – и задача практически решена, остается только подставить формулы и получить ответ!

Чтобы легче запомнить задачи 1 типа, будем называть их общим термином «велосипедисты».

Решение.

Есть 119 спортсменов с различными номерами, т.е. 119 вариантов различных номеров, тогда Q=119.

Так как Q = М^k, то для одного номера получаем Q = 119 ≤ 128=27, откуда k=7.

Тогда для N = 70 номеров получаем информационный объем сообщения

I = N * k = 70 * 7 = 490 бит.

Также для вычисления значения бита на символ можно использовать математическое решение формулы Хартли:

k= log₂N

В данном случае k= log₂8 = 3.

Ответ: 490

Задача 2 типа.

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

Рекомендации к решению.

Задачи данного типа – чисто математические (так и запомним их определение), и здесь очень полезно использовать таблицы степеней двойки и соответствия единиц измерения количества информации.

Подставляем числовые значения в формулы, заменяем числа степенями числа 2 и упрощаем. При этом не забываем привести единицы измерения к одному виду и помнить, что k – это бит на символ!

Решение.

Воспользовавшись таблицей степеней двойки, имеем: N = 4096 = 212 символов, тогда I =1/512 Мбайта = 223/29=214 бит. Отсюда k = I/N = 214/212=22=4 бита на символ.

Тогда мощность алфавита (количество различных вариантов символов)

М=24 = 16 символов.

Ответ: 16

Задача 3 типа.

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

Определите объем памяти, необходимый для хранения 20 автомобильных номеров.

Рекомендации к решению.

Решая задачи данного типа, необходимо обратить внимание на слова «каждый символ» и «каждый номер», которые подразумевают разделение информации при решении. Поэтому при решении задач 3 типа следует сначала считать объем одного номера в битах, перевести его в байты (с округлением до целого числа в большую сторону!) и только потом искать общий объем на несколько номеров.

Округление в большую сторону при вычислении объема одного номера необходимо, чтобы не потерять ни одного символа кодируемой информации.

Запомним, что округление при вычислении объемов информации всегда будем выполнять в большую сторону!

Будем так и называть этот тип задач – «автомобильные номера», хотя здесь встречаются и задачи на нахождение паролей (решение задач от этого не зависит).

Решение.

Особенность решения данной задачи – решение в два шага, т.е. поиск двух видов объема:

I₁ — отдельно для каждого номера, I₂ – для всех номеров.

Шаг 1. Мощность используемого алфавита Q = 26 + 10 = 36 ≤26, откуда k=6 бит на символ. Тогда I1 = 7*6=42 бита = 6 байт на один номер.

Шаг 2.Следовательно, на 20 номеров требуется I2 = 20 * 6 = 120 байт.

Ответ: 120

Для проверки правильности рассуждений пересчитаем объем без учета рекомендаций, данных ранее, и сравним итоги.

Мощность используемого алфавита и значение k=6 бит на символ остаются. Тогда объем одного номера I₁ = 7*6=42 бита, а 20 номеров I₂ = 42 * 20 = 840 бит = 105 байт.

В итоге потеряны 15 байт информации, а это значит, что не все номера были бы закодированы.

Задача 4 типа.

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

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

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

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

• — числа от 1992 до 2003.

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

Рекомендации к решению.

Перед решением задач данного типа вспомним, что базы данных (далее – БД) состоят из записей, которые делятся на поля.

И преимущество БД перед другим способом хранения информации в том, что поля в одной записи могут иметь разные форматы данных(числовые, символьные, даты и др.), которые кодируются соответственно их форматам.

Поэтому для подсчета общего объема одной записи следует считать объем каждого поля отдельно, а затем сложить их.

При этом помним, что в таблице ASCII (так как таблица кодировки в условии задачи не указана, берем ее по умолчанию) каждый символ занимает один байт памяти. Число (до определенного значения) – тоже кодируется одним байтом памяти.

Запомним определение задач 4 типа как «базы данных».

Решение.

Определяем минимально возможные размеры в битах для каждого из полей (в данном случае – четырех) с учетом их типов отдельно.
Так как по условию задачи первые буквы имени, отчества и фамилии – всегда заглавные, то будем хранить их в виде строчных и делать заглавными только при выводе на экран.

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

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

Для года рождения есть 12 вариантов чисел, поэтому для него нужно отвести 4 бита

(12 ≤ 16 = 24).

Таким образом, всего требуется 220+4 = 224 бита или 28 байт.

Ответ: 28

Задача 5 типа (1).

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

Сколько обезьян живут в вольере Б?

Рекомендации к решению.

Заметим, что условие этой задачи отличается от задачи 1 типа только тем, что там все номера считались как единая информация, а здесь требуется выбор мотка определенного цвета, т.е. вся информация разделена на части.

Поэтому в решении задач 5 типа делается один дополнительный шаг — определяется, какую часть от общего количества составляет выделенная информация.

Решение.

По условию, красные клубки составляют 1/8 часть от целого (от всех клубков).

Поэтому сообщение о том, что первый вынутый клубок шерсти – красный, соответствует выбору одного из 8 вариантов, и это будет: Q = 8 = 23, что дает нам k = 3 бит.

(Можно запомнить решение задач 5 типа без дробей и дополнительных объяснений: в дополнительном по отношению к задачам 1 типа шаге находим Q = 32/4 = 8 вариантов, а затем решаем, как и задачи 1 типа: Q = 8 = 23, что дает нам k = 3 бит).

Ответ: 3

Задача 5 типа (2).

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

Сколько обезьян живут в вольере Б?

Решение.

Почему эта задача относится к 5 типу? Потому что информация разделена на части – обезьяны здоровые и больные.

Решается она в порядке, обратном решению предыдущей задачи.

Итак, информация в 4 бита соответствует выбору одного из 16 вариантов, поэтому в вольере А живет 1/16 часть всех обезьян: 32/16 = 2 обезьяны

Тогда в вольере Б живут все оставшиеся 32 – 2 = 30 обезьян.

Описание задач 5 типа можно определить и запомнить как задачи «про шары и обезьян».

Ответ: 30

Задачи смешанных типов.

Усвоив решение каждого типа задач отдельно, можно рассмотреть задачи смешанных типов.

Для их успешного решения необходимо прежде всего внимательно рассмотреть условие задачи, чтобы не пропустить это смешивание, а потом уже решать с учетом всех тонкостей, описанных ранее.

Разберем две из таких задач.

Задача 1.

При регистрации в компьютерной системе каждому пользователю выдаётся идентификатор, состоящий из 8 символов, первый и последний из которых – одна из 18 букв, а остальные – цифры (допускается использование 10 десятичных цифр.

Каждый такой идентификатор в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование; все цифры кодируются одинаковым и минимально возможным количеством бит, все буквы также кодируются одинаковым и минимально возможным количеством бит).

Определите объём памяти в байтах, отводимый этой программой для записи 500 паролей.

Решение.

Рассмотрим условие и разделим его на части, относящиеся к разным типам задач.

В первом абзаце говорится, что идентификатор состоит из букв и цифр в определенном порядке, а они кодируются по-разному. Это подтверждается и во-втором абзаце, где способ кодировки для цифр и букв описывается отдельно. Следовательно, каждый идентификатор рассматривается как запись из БД, то есть эта часть задачи относится к типу 4.

Во втором абзаце условия так же сказано, что каждый идентификатор записывается минимально возможным и одинаковым целым количеством байт, а посимвольное (т.е. для каждого символа отдельно) кодирование выполняется минимальным количеством бит для каждого вида символов. Следовательно, эта часть задачи относится к типу 3.

Тогда решение будет следующим:

В идентификаторе шесть цифр из алфавита мощностью 10 символов.

Тогда k₁=4 и I1=6*k₁=24 бита.

Вторая часть идентификатора длиной 2 символа состоит из алфавита мощностью 18 символов. Тогда k₂=5 и I₂=2*k2=10 бит.
Значит, объем одного идентификатора равен I₁ + I₂ = 24 + 10 = 34 бита.

Далее решаем задачу соответственно решению, описанному в 3 типе задач:

34 бита = 5 байт,

Общий объем 500 идентификаторов равен I = 5*500=2500 байт.

Ответ: 2500

Задача 2.

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 15 символов и содержащий только символы из 12-символьного набора. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит.

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

Определите объём памяти (в байтах), необходимый для хранения сведений о 50 пользователях. В ответе запишите только целое число – количество байт.

Решение.

В условии сказано, что сведения о пользователях хранятся в БД, где запись состоит из двух полей – собственно идентификатора и дополнительных сведений (тип 4).

При этом идентификатор рассчитывается как в задачах 1 типа, а дополнительные сведения заданы конкретным значением и расчет их не нужен.

Тогда решение будет следующим:

Мощность используемого алфавита Q = 12 ≤24, откуда k=4 бита на символ. Тогда I₁ = 15*4 = 60 бит = 8 байт на один идентификатор.

Объем одной записи равен I₁+2 = 8 + 12 = 20 байт.

Следовательно, для 50 записей требуется I50 = 20 * 50 = 1000 байт.

Ответ: 1000