Решение задач

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

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

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

Решение к задаче 2: 1. в сообщении было 4096 = 2 12 символов 2. объем сообщения 1/512 Мбайта = 2 23 / 512 бита = 2 23 / 2 9 бита = 2 14 бита (= бита!) 3. место, отведенное на 1 символ: 2 14 бита / 2 12 символов = 2 2 бита на символ = 4 бита на символ 4. 4 бита на символ позволяют закодировать 2 4 = 16 разных символов 5. поэтому мощность алфавита – 16 символов 6. правильный ответ – 2.

Задача 3: В зоопарке 32 обезьяны живут в двух вольерах, А и Б. Одна из обезьян – альбинос (вся белая). Сообщение «Обезьяна-альбинос живет в вольере А» содержит 4 бита информации. Сколько обезьян живут в вольере Б? 1) 4 2) 16 3) 28 4) 30

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

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

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

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

Решение к задачи 5: 1. всего используется 26 букв + 10 цифр = 36 символов 2. для кодирования 36 вариантов необходимо использовать 6 бит, так как 2 5 = 32

Задача 6: Какое наименьшее число символов должно быть в алфавите, чтобы при помощи всевозможных трехбуквенных слов, состоящих из символов данного алфавита, можно было передать не менее 9 различных сообщений? 1) 1 2) 2 3) 3 4) 4

Решение к задачи 6: 1. здесь используется только одна формула: если алфавит имеет мощность M, то количество всех возможных «слов» длиной N равно Q = M N 2. в данном случае нужно закодировать 9 сигналов (Q 9 ) с помощью трехбуквенных слов ( N = 3 ) 1. таким образом, нужно найти наименьшее целое M, такое что Q = M 3 9 (куб числа не меньше 9) 2. проще всего использовать метод подбора: при M = 2 получаем 2 3 = 8 < 9 (с помощью трех двоичных сигналов можно закодировать только 8 вариантов), но уже при N = 3 имеем 3 3 = 27 9, поэтому нужно брать M 3 3. таким образом, правильный ответ – 3.

Задача 7: Каждая ячейка памяти компьютера, работающего в троичной системе счисления, может принимать три различных значения (-1, 0, 1). Для хранения некоторой величины отвели 4 ячейки памяти. Сколько различных значений может принимать эта величина?

Решение к задачи 7: 1. непривычность этой задачи состоит в том, что используется троичная система 2. фактически мы имеем дело с языком, алфавит которого содержит M=3 различных символа 3. поэтому количество всех возможных «слов» длиной N равно Q = 3 N 4. для N = 4 получаем Q = 3 4 = таким образом, правильный ответ – 81.

Задача 8: В школьной базе данных хранятся записи, содержащие информацию об учениках: – 16 символов: русские буквы (первая прописная, остальные строчные), – 12 символов: русские буквы (первая прописная, остальные строчные), – 16 символов: русские буквы (первая прописная, остальные строчные), – числа от 1992 до Каждое поле записывается с использованием минимально возможного количества бит. Определите минимальное количество байт, необходимое для кодирования одной записи, если буквы е и ё считаются совпадающими. 1) 28 2) 29 3) 46 4) 56

Решение к задачи 8: 1. очевидно, что нужно определить минимально возможные размеры в битах для каждого из четырех полей и сложить их; 2. важно! известно, что первые буквы имени, отчества и фамилии – всегда заглавные, поэтому можно хранить их в виде строчных и делать заглавными только при выводе на экран (но нас это уже не волнует) 3. таким образом, для символьных полей достаточно использовать алфавит из 32 символов (русские строчные буквы, «е» и «ё» совпадают, пробелы не нужны) 4. для кодирования каждого символа 32-символьного алфавита нужно 5 бит (32 = ), поэтому для хранения имени, отчества и фамилии нужно ( )5=220 бит 5. для года рождения есть 12 вариантов, поэтому для него нужно отвести 4 бита (2 4 = 16 12) 6. таким образом, всего требуется 224 бита или 28 байт 7. правильный ответ – 1.

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

Решение к задачи 9: 1. согласно условию, в пароле можно использовать 10 цифр (0..9) + 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 байт 6. ответ: 1.

Задачи для тренировки: 1. Световое табло состоит из лампочек. Каждая лампочка может находиться в одном из трех состояний («включено», «выключено» или «мигает»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 18 различных сигналов? 1) 6 2) 5 3) 3 4) 4 2. Метеорологическая станция ведет наблюдение за влажностью воздуха. Результатом одного измерения является целое число от 0 до 100 процентов, которое записывается при помощи минимально возможного количества бит. Станция сделала 80 измерений. Определите информационный объем результатов наблюдений. 1) 80 бит 2) 70 байт 3) 80 байт 4) 560 байт

3. Обычный дорожный светофор без дополнительных секций подает шесть видов сигналов (непрерывные красный, желтый и зеленый, мигающие желтый и зеленый, красный и желтый одновременно). Электронное устройство управления светофором последовательно воспроизводит записанные сигналы. Подряд записано 100 сигналов светофора. В байтах данный информационный объем составляет 1) 37 2) 38 3) 50 4) 100 (Условие некорректно, имеется в виду количество целых байтов.) 4. Сколько существует различных последовательностей из символов «плюс» и «минус», длиной ровно в пять символов? 1) 64 2) 50 3) 32 4) 20

5. Шахматная доска состоит 8 столбцов и 8 строк. Какое минимальное количество бит потребуется для кодирования координат одного шахматного поля? 1) 4 2) 5 3) 6 4) 7 6. Два текста содержат одинаковое количество символов. Первый текст составлен в алфавите мощностью 16 символов, а второй текст – в алфавите из 256 символов. Во сколько раз количество информации во втором тексте больше, чем в первом? 1) 12 2) 2 3) 24 4) 4 7. Какое минимальное количество бит потребуется для кодирования положительных чисел, меньших 60? 1) 12 2) 2 3) 24 4) 4

Ответы: