1. Производится одноканальная (моно) звукозапись с частотой дискретизации 16 кГц и глубиной кодирования 24 бита. Запись длится 1 минуту, ее результаты записываются в файл, сжатие данных не производится. Какое из приведенных ниже чисел наиболее близко к размеру полученного файла, выраженному в мегабайтах?
1) 0,2 2) 2 3) 3 4) 4
Решение (вариант 1, «в лоб»):
1) так как частота дискретизации 16 кГц, за одну секунду запоминается 16000 значений сигнала
2) так как глубина кодирования – 24 бита = 3 байта, для хранения 1 секунды записи требуется
16000 ´ 3 байта = 48 000 байт
(для стерео записи – в 2 раза больше)
3) на 1 минуту = 60 секунд записи потребуется
60 ´ 48000 байта = 2 880 000 байт,
то есть около 3 Мбайт
4) таким образом, правильный ответ – 3.
Решение (вариант 2, через степени двойки, с сайта ege-go.ru):
1) обратите внимание, что в этой задаче не требуется ТОЧНО вычислять размер файла, нужно только выполнить прикидочные расчеты
2) в этом случае, если нет калькулятора (а на ЕГЭ его нет) удобно привести все числа к ближайшим степеням двойки, например,
1 мин = 60 сек » 64 сек = 26 сек
1000 » 1024 = 210
3) так как частота дискретизации 16 кГц, за одну секунду запоминается 16000 значений сигнала, что примерно равно
16 ´ 1000 » 16 ´ 1024 = 24 ´ 210 = 214 Гц
4) так как глубина кодирования – 24 бита = 3 байта, для хранения 1 секунды записи требуется
16000 ´ 3 байта » 214 ´ 3 байт
(для стерео записи – в 2 раза больше)
5) на 1 минуту = 60 сек » 64 сек = 26 сек записи потребуется примерно
64 ´ 214 ´ 3 байта = 26 ´ 214 ´ 3 байта = 3 ´ 220 байта
6) переводит эту величину в Мбайты:
(3 ´ 220 байта) / 220 = 3 Мбайт
7) таким образом, правильный ответ – 3.
2. Производится одноканальная (моно) звукозапись с частотой дискретизации 64Гц. При записи использовались 32 уровня дискретизации. Запись длится 4 минуты 16 секунд, её результаты записываются в файл, причём каждый сигнал кодируется минимально возможным и одинаковым количеством битов. Какое из приведённых ниже чисел наиболее близко к размеру полученного файла, выраженному в килобайтах?
1) 10 2) 64 3) 80 4) 512
Решение:
1) так как частота дискретизации 64 Гц, за одну секунду запоминается 64 значения сигнала
2) глубина кодирования не задана!
3) используется 32 = 25 уровня дискретизации значения сигнала, поэтому на один отсчет приходится 5 бит
4) время записи 4 мин 16 с = 4 ´ 60 + 16 = 256 с
5) за это время нужно сохранить
256 ´ 5 ´ 64 бит = 256 ´ 5 ´ 8 байт = 5 ´ 2 Кбайт = 10 Кбайт
6) таким образом, правильный ответ – 1.
3. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код:
А–1, Б–000, В–001, Г–011. Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования.
1) 00 2) 01 3)11 4) 010
Решение:
1) заметим, что для известной части кода выполняется условие Фано – никакое кодовое слово не является началом другого кодового слова
2) если Д = 00, такая кодовая цепочка совпадает с началом Б = 000 и В = 001, невозможно однозначно раскодировать цепочку 000000: это может быть ДДД или ББ; поэтому первый вариант не подходит
3) если Д = 01, такая кодовая цепочка совпадает с началом Г = 011, невозможно однозначно раскодировать цепочку 011: это может быть ДА или Г; поэтому второй вариант тоже не подходит
4) если Д = 11, условие Фано тоже нарушено: кодовое слово А = 1 совпадает с началом кода буквы Д, невозможно однозначно раскодировать цепочку 111: это может быть ДА или ААА; третий вариант не подходит
5) для четвертого варианта, Д = 010, условие Фано не нарушено;
6) правильный ответ – 4.
4. Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11, соответственно). Если таким способом закодировать последовательность символов БАВГ и записать результат шестнадцатеричным кодом, то получится
1) 4B16 2) 41116 3)BACD16 4) 102316
Решение:
1) из условия коды букв такие: A – 00, Б –01, В – 10 и Г – 11, код равномерный
2) последовательность БАВГ кодируется так: 01 00 10 11 = 1001011
3) разобьем такую запись на тетрады справа налево и каждую тетраду переведем в шестнадцатеричную систему (то есть, сначала в десятичную, а потом заменим все числа от 10 до 15 на буквы A, B, C, D, E, F); получаем
1001011 = 0100 10112 = 4B16
4) правильный ответ – 1.
5. Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
| A | B | C | D | E |
Определить, какой набор букв закодирован двоичной строкой 0110100011000
1) EBCEA 2) BDDEA 3) BDCEA 4) EBAEA
В данном случае самое простое и надежное – просто закодировать все ответы, используя приведенную таблицу кодов, а затем сравнить результаты с заданной цепочкой
1) получим
1) EBCEA – 01101100011000 2) BDDEA – 011010011000
3) BDCEA – 0110100011000 4) EBAEA – 01101000011000
2) сравнивая эти цепочки с заданной, находим, что правильный ответ – 3.
6. Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=10, В=110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
1) 1 2) 1110 3) 111 4) 11
Решение
1) для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, требуется, чтобы никакой код не был началом другого (более длинного) кода; это условие называют условием Фано
2) как и в первом решении, рассматриваем варианты, начиная с самого короткого кода для буквы Г; в нашем случае код Г=1 является началом кодов букв Б и В, поэтому условие Фано не выполняется, такой код не подходит
3) код Г=11 также является началом другого кода (кода буквы В), поэтому это тоже ошибочный вариант
4) третий вариант кода, Г=111, не является началом никакого уже известного кода; кроме того, ни один уже имеющийся код не является началом кода 111; таким образом, условие Фано выполняется
5) поэтому правильный ответ – 3.
7. Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0 – белый. Для компактности результат записали в шестнадцатеричной системе счисления. Выберите правильную запись кода.
1) BD9AA5 2) BDA9B5 3) BDA9D5 4) DB9DAB
Решение:
1) «вытянем» растровое изображение в цепочку: сначала первая (верхняя) строка, потом – вторая, и т.д.:
| 1 строка | 2 строка | 3 строка | 4 строка |
2) в этой полоске 24 ячейки, черные заполним единицами, а белые – нулями:
| 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | ||||||||||
| 1 строка | 2 строка | 3 строка | 4 строка |
3) поскольку каждая цифра в шестнадцатеричной системе раскладывается ровно в 4 двоичных цифры, разобьем полоску на тетрады – группы из четырех ячеек (в данном случае все равно, откуда начинать разбивку, поскольку в полоске целое число тетрад – 6):
| 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
4) переводя тетрады в шестнадцатеричную систему, получаем последовательно цифры B (11), D(13), A(10), 9, D(13) и 5, то есть, цепочку BDA9D5
5) поэтому правильный ответ – 3.
8. Для передачи чисел по каналу с помехами используется код проверки четности. Каждая его цифра записывается в двоичном представлении, с добавлением ведущих нулей до длины 4, и к получившейся последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110 ). Определите, какое число передавалось по каналу в виде 01010100100111100011?
1) 59143 2) 5971 3) 102153 4) 10273
Решение:
1) сначала разберемся, как закодированы числа в примере; очевидно, что используется код равномерной длины; поскольку 2 знака кодируются 10 двоичными разрядами (битами), на каждую цифру отводится 5 бит, то есть
2 → 00101 и 3 → 00110
2) как следует из условия, четыре первых бита в каждой последовательности – это двоичный код цифры, а пятый бит (бит четности) используется для проверки и рассчитывается как «сумма по модулю два», то есть остаток от деления суммы битов на 2; тогда
2 = 00102, бит четности (0 + 0 + 1 + 0) mod 2 = 1
3 = 00112, бит четности (0 + 0 + 1 + 1) mod 2 = 0
3) но бит четности нам совсем не нужен, важно другое: пятый бит в каждой пятерке можно отбросить!
4) разобъем заданную последовательность на группы по 5 бит в каждой:
01010, 10010, 01111, 00011.
5) отбросим пятый (последний) бит в каждой группе:
0101, 1001, 0111, 0001.
это и есть двоичные коды передаваемых чисел:
01012 = 5, 10012 = 9, 01112 = 7, 00012 = 1.
6) таким образом, были переданы числа 5, 9, 7, 1 или число 5971.
7) Ответ: 2.
9. В велокроссе участвуют 119 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объем сообщения, записанного устройством, после того как промежуточный финиш прошли 70 велосипедистов?
1) 70 бит 2) 70 байт 3) 490 бит 4) 119 байт
Решение:
1) велосипедистов было 119, у них 119 разных номеров, то есть, нам нужно закодировать 119 вариантов
2) по таблице степеней двойки находим, что для этого нужно минимум 7 бит (при этом можно закодировать 128 вариантов, то есть, еще есть запас); итак, 7 бит на один отсчет
3) когда 70 велосипедистов прошли промежуточный финиш, в память устройства записано 70 отсчетов
4) поэтому в сообщении 70*7 = 490 бит информации (ответ 3).
10. Для регистрации на сайте некоторой страны пользователю требуется придумать пароль. Длина пароля – ровно 11 символов. В качестве символов используются десятичные цифры и 12 различных букв местного алфавита, причём все буквы используются в двух начертаниях: как строчные, так и заглавные (регистр буквы имеет значение!).Под хранение каждого такого пароля на компьютере отводится минимально возможное и одинаковое целое количество байтов, при этом используется посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов.
Определите объём памяти, который занимает хранение 60 паролей.
1) 540 байт 2) 600 байт 3) 660 байт 4) 720 байт
Решение:
1) согласно условию, в пароле можно использовать 10 цифр (0..9) + 12 заглавных букв местного алфавита + 12 строчных букв, всего 10 + 12 + 12 = 34 символа
2) для кодирования 34 символов нужно выделить 6 бит памяти (5 бит не хватает, они позволяют закодировать только 25 = 32 варианта)
3) для хранения всех 11 символов пароля нужно 11 × 6 = 66 бит
4) поскольку пароль должен занимать целое число байт, берем ближайшее большее (точнее, не меньшее) значение, которое кратно 8: это 72 = 9 × 8; то есть один пароль занимает 9 байт
5) тогда 60 паролей занимают 9 × 60 = 540 байт
6) ответ: 1.
11. Объем сообщения, содержащего 4096 символов, равен 1/512 части Мбайта. Какова мощность алфавита, с помощью которого записано это сообщение?
1) 8 2) 16 3) 4096 4) 16384
Решение:
1) объем сообщения
1/512 Мбайт = 1024/512 Кбайт = 2 Кбайт = 2048 байт
2) на 1 символ приходится 2048 байт / 4096 = 1/2 байта = 4 бита
3) 4 бита на символ позволяют закодировать 24 = 16 разных символов
4) поэтому мощность алфавита – 16 символов
5) правильный ответ – 2.
12. В некоторой стране автомобильный номер длиной 7 символов составляется из заглавных букв (всего используется 26 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 20 автомобильных номеров.
1) 20 байт 2) 105 байт 3) 120 байт 4) 140 байт
Решение:
1) всего используется 26 букв + 10 цифр = 36 символов
2) для кодирования 36 вариантов необходимо использовать 6 бит, так как 
, т.е. пяти бит не хватит (они позволяют кодировать только 32 варианта), а шести уже достаточно
3) таким образом, на каждый символ нужно 6 бит (минимально возможное количество бит)
4) полный номер содержит 7 символов, каждый по 6 бит, поэтому на номер требуется 
бита
5) по условию каждый номер кодируется целым числом байт (в каждом байте – 8 бит), поэтому требуется 6 байт на номер (
), пяти байтов не хватает, а шесть – минимально возможное количество
6) на 20 номеров нужно выделить 
байт
7) правильный ответ – 3.
13. В школьной базе данных хранятся записи, содержащие информацию об учениках: <Фамилия> – 16 символов: русские буквы (первая прописная, остальные строчные), <Имя> – 12 символов: русские буквы (первая прописная, остальные строчные <Отчество> – 16 символов: русские буквы (первая прописная, остальные строчные),<Год рождения> – числа от 1992 до 2003. Каждое поле записывается с использованием минимально возможного количества бит. Определите минимальное количество байт, необходимое для кодирования одной записи, если буквы е и ё считаются совпадающими.
1) 28 2) 29 3) 46 4) 56
Решение:
1) очевидно, что нужно определить минимально возможные размеры в битах для каждого из четырех полей и сложить их;
2) важно! известно, что первые буквы имени, отчества и фамилии – всегда заглавные, поэтому можно хранить их в виде строчных и делать заглавными только при выводе на экран (но нас это уже не волнует)
3) таким образом, для символьных полей достаточно использовать алфавит из 32 символов (русские строчные буквы, «е» и «ё» совпадают, пробелы не нужны)
4) для кодирования каждого символа 32-символьного алфавита нужно 5 бит (32 = 25555), поэтому для хранения имени, отчества и фамилии нужно (16 + 12 + 16)•5=220 бит
5) для года рождения есть 12 вариантов, поэтому для него нужно отвести 4 бита (24 = 16 ≥ 12)
6) таким образом, всего требуется 224 бита или 28 байт
7) правильный ответ – 1.