Системы счисления при подготовке к ЕГЭ по информатике

Работая с информацией  на современных компьютерах, следует  знать следующие единицы, производные  от байта, при составлении которых  используется число 1024 = 2¹⁰. .

Для измерения информации используются не только биты и байты, но и более крупные единицы: ..

1 Кбайт (килобайт) = 2¹⁰ байт = 1024 байт.

1 Мбайт (мегабайт) = 2¹⁰ Кбайт = 1024 Кбайт.

1 Гбайт (гигабайт) = 2¹⁰ Мбайт = 1024 Мбайт.

1 Тбайт (терабайт)= 2¹⁰ Гбайт = 1024 Гбайт.

1 Пбайт (петабайт)= 2¹⁰ Тбайт = 1024 Тбайт.

Заполним таблицу с  коэффициентами перевода производных единиц от байта друг в друга. Например, 1 Мб = = 2¹⁰ Кб, 1 Кб = 2^-10 Мб.

 

	Байт	Кило-байт	Мега-байт	Гига-байт	Тера-байт	Пета-байт
Б	1	2-10	2-20	2-30	2-40	2-50
Кб	210	1	2-10	2-20	2-30	2-40
Мб	220	210	1	2-10	2-20	2-30
Гб	230	220	210	1	2-10	2-20
Тб	240	230	220	210	1	2-10
Пб	250	240	230	220	210	1

 

Пример 7. Считая, что каждый символ кодируется одним байтом, оцените информационный объем следующего предложения: Белеет Парус Одинокий В Тумане Моря Голубом! ..

1) 352 бита

2) 44 бита

3) 352 байта

4) 88 байт

Решение. Так как в предложении 44 символа (считая знаки препинания и пробелы), то информационный объем вычисляется по формуле:

V= 44 • 1 байт = 44 байта =44 • 8 бит = 352 бита.

Верный ответ: 1).  

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

1. 80 бит 3) 80 байт
2. 70 байт 4) 560 байт

Решение. Любое значение влажности воздуха, выраженное в процентах, равновероятно. Количество информации о результате одного измерения влажности воздуха определяется из уравнения 2^х = 101 (101 — количество целых чисел в диапазоне от 0 до 100), или после поиска ближайшей степени числа 2 из неравенства 2^х = 128 = 2⁷. Таким образом, получаем х = 7 бит. Поскольку было сделано 80 измерений, то информационный объем сообщения равен ..

V= 80 • 7 бит = 560 бит = 70 байт.

Верный ответ: 2).

 

ГЛАВА 2. РАЗБОР ЗАДАНИЙ ЕГЭ ПО ТЕМЕ «КОДИРОВАНИЕ ИНФОРМАЦИИ»

A8. Кодирование звука

 

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, через степени двойки):

1. обратите внимание, что в этой задаче не требуется ТОЧНО вычислять размер файла, нужно только выполнить прикидочные расчеты ..
2. в этом случае, если нет калькулятора (а на ЕГЭ его нет) удобно привести все числа к ближайшим степеням двойки, например, …

1 мин  = 60 сек » 64 сек = 2⁶ сек

1000 » 1024 = 2¹⁰ 

3. так как частота дискретизации 16 кГц, за одну секунду запоминается 16000 значений сигнала, что примерно равно ..

16 ´ 1000 » 16 ´ 1024 = 2⁴ ´ 2¹⁰ = 2¹⁴ Гц

4. так как глубина кодирования – 24 бита = 3 байта, для хранения 1 секунды записи требуется ..

16000 ´ 3 байта » 2¹⁴ ´ 3 байт

(для стерео записи  – в 2 раза больше)

5. на 1 минуту = 60 сек » 64 сек = 2⁶ сек записи потребуется примерно

64 ´ 2¹⁴ ´ 3 байта = 2⁶ ´ 2¹⁴ ´ 3 байта = 3 ´ 2²⁰   байта

6. переводит эту величину в Мбайты:

(3 ´ 2²⁰  байта) / 2²⁰ = 3 Мбайт

7. таким образом, правильный ответ – 3.

2. Производится  одноканальная (моно) звукозапись  с частотой дискретизации 64Гц. При записи использовались 32 уровня  дискретизации. Запись длится 4 минуты 16 секунд, её результаты записываются  в файл, причём каждый сигнал  кодируется минимально возможным  и одинаковым количеством битов.  Какое из приведённых ниже  чисел наиболее близко к размеру  полученного файла, выраженному  в килобайтах? ..

1) 10  2) 64 3)  80  4)  512

Решение:

1. так как частота дискретизации 64 Гц, за одну секунду запоминается 64 значения сигнала
2. глубина кодирования не задана!
3. используется 32 = 2⁵ уровня дискретизации значения сигнала, поэтому на один отсчет приходится 5 бит
4. время записи 4 мин 16 с = 4 ´ 60 + 16 = 256 с
5. за это время нужно сохранить

256 ´ 5 ´ 64 бит = 256 ´ 5 ´ 8 байт  =  5 ´ 2 Кбайт = 10 Кбайт

6. таким образом, правильный ответ – 1.

А9.  Кодирование и декодирование информации

 

3. По каналу связи передаются сообщения, содержащие только 4 буквы: А, И, С, Т. В любом сообщении больше всего букв А, следующая по частоте буква – С, затем – И. Буква Т встречается реже, чем любая другая. Для передачи сообщений нужно использовать неравномерный двоичный код, допускающий однозначное декодирование; при этом сообщения должны быть как можно короче. Шифровальщик может использовать один из перечисленных ниже кодов. Какой код ему следует выбрать? ..

1) А – 0, И –  1, С – 00, Т – 11  

2) С – 1, И –  0, А – 01, Т – 10

3) А – 1, И –  01, С – 001, Т – 000

4) С – 0, И –  11, А – 101, Т – 100

Решение:

1. сначала выберем коды, допускающие однозначное декодирование: это коды 3 и 4 (для них выполняется условие Фано), коды 1 и 2 не подходят
2. для того, чтобы длина сообщения была как можно короче, должно выполнять правило: «чем чаще встречается буква, тем короче её код»;
3. к сожалению, правило, приведённое выше, не совсем «хорошо» выполняется для кодов 3 и 4: в коде 3 длина кодового слова для буквы С больше, чем длина кодового слова буквы И (а хочется наоборот); для кода 4 длина кодового слова для буквы А – не самая маленькая из всех
4. сравним коды 3 и 4, предполагая, что в сообщении буква А встречается a раз, буква С – b раз, буква И – g раз и буква Т – d раз; причём по условию задачи a > b > g > d
5. при кодировании кодом 3 получаем сообщение длиной

L₃ = a + 3b + 2g +3 d ..

6. при кодировании кодом 3 получаем сообщение длиной

L₄ = 3a + b + 2g +3 d

7. находим разность: L₄ – L₃ = (3a + b + 2g +3 d) – (a + 3b + 2g +3 d) = 2a – 2b
8. поскольку a > b, получаем L₄ – L₃ > 0, то есть код 3 более экономичный
9. Ответ: 3.

4. По  каналу связи передаются сообщения,  содержащие только 4 буквы: Е, Н,  О, Т. Для кодирования букв  Е, Н, О используются 5-битовые  кодовые слова: Е - 00000, Н - 00111, О - 11011. Для этого набора кодовых  слов выполнено такое свойство: любые два слова из набора  отличаются не менее чем в  трёх позициях. Это свойство важно  для расшифровки сообщений при  наличии помех. Какое из перечисленных  ниже кодовых слов можно использовать  для буквы Т, чтобы указанное  свойство выполнялось для всех  четырёх кодовых слов? ..

1) 11111   2) 11100 3) 00011 4) не подходит ни одно из указанных выше слов

Решение:

1. код, рассмотренный в условии задачи, относится к помехоустойчивым кодам, которые позволяют обнаружить и исправить определенное количество ошибок, вызванных помехами при передаче данных;  
2. количество позиций, в которых отличаются два кодовых слова одинаковой длины, называется расстоянием Хэмминга
3. код, в котором расстояние Хэмминга между каждой парой кодовых слов равно d, позволяет обнаружить до d-1 ошибок; для исправления r ошибок требуется выполнение условия

d  ≥ 2r + 1   ..

поэтому код с d = 3 позволяет обнаружить одну или две ошибки, и исправить одну ошибку.

4. легко проверить, что для заданного кода (Е - 00000, Н - 00111, О - 11011) расстояние Хэмминга равно 3; в таблице выделены отличающиеся биты, их по три в парах Е-Н и Н-О и четыре в паре Е-О:

Е – 00000  Е – 00000  Н – 00111 

Н – 00111  О – 11011   О – 11011

5. теперь проверяем расстояние между известными кодами и вариантами ответа; для первого ответа 11111 получаем минимальное расстояние 1 (в паре О-Т), этот вариант не подходит:

Е – 00000  Н - 00111  О - 11011

Т - 11111          Т - 11111  Т - 11111

6. для второго ответа 11100  получаем минимальное расстояние 3 (в парах Е-Т и О-Т):

Е – 00000 Н - 00111  О - 11011

Т - 11100          Т - 11100  Т – 11100  

7. для третьего ответа 00011 получаем минимальное расстояние 1 (в паре Н-Т), этот вариант не подходит:  

Е – 00000  Н - 00111  О - 11011

Т - 00011          Т - 00011  Т - 00011

8. таким образом, расстояние Хэмминга, равное 3, сохраняется только для ответа 2
9. Ответ: 2.

5. Для  кодирования некоторой последовательности, состоящей из букв А, Б, В,  Г и Д, используется неравномерный  двоичный код, позволяющий однозначно  декодировать полученную двоичную  последовательность. Вот этот код:  А–00, Б–010, В–011, Г–101, Д–111. Можно ли  сократить для одной из букв  длину кодового слова так, чтобы  код по-прежнему можно было  декодировать однозначно? Коды остальных  букв меняться не должны. Выберите  правильный вариант ответа.

1) для буквы Б  – 01  2) это невозможно

3) для буквы В  – 01  4) для буквы Г – 01  

Решение (1 способ, проверка условий Фано):

1. для однозначного декодирования достаточно, чтобы выполнялось условие Фано или обратное условие Фано;  
2. проверяем последовательно варианты 1, 3 и 4; если ни один из них не подойдет, придется выбрать вариант 2 («это невозможно»);
3. проверяем вариант 1: А–00, Б–01, В–011, Г–101, Д–111.  

«прямое» условие  Фано не выполняется (код буквы Б  совпадает с началом кода буквы  В);