Решения заданий ФИПИ ЕГЭ по информатике: «Информация и кодирование» — с ответами

Вычитание в шестнадцатеричной системе

Вычислите значение выражения $9\mathrm{E}_{16} - 96_{16}$. В ответе запишите вычисленное значение в десятичной системе счисления.

1. 1
   Переведём первое число в десятичную систему. В шестнадцатеричной системе $\mathrm{E}=14$.$$9\mathrm{E}_{16}=9\cdot16+14=158$$
2. 2
   Переведём второе число в десятичную систему.$$96_{16}=9\cdot16+6=150$$

Ещё 1 шаг — в полном решении

Числа между двоичными границами

Сколько существует натуральных чисел $x$, для которых выполняется неравенство $10110111_2 < x < 10111111_2$?

1. 1
   Переведём левую границу в десятичную систему счисления:$$10110111_2 = 1\cdot2^7 + 0\cdot2^6 + 1\cdot2^5 + 1\cdot2^4 + 0\cdot2^3 + 1\cdot2^2 + 1\cdot2^1 + 1\cdot2^0 = 183$$
2. 2
   Переведём правую границу в десятичную систему счисления:$$10111111_2 = 1\cdot2^7 + 0\cdot2^6 + 1\cdot2^5 + 1\cdot2^4 + 1\cdot2^3 + 1\cdot2^2 + 1\cdot2^1 + 1\cdot2^0 = 191$$

Ещё 1 шаг — в полном решении

Числа между шестнадцатеричными значениями

Сколько существует натуральных чисел $x$, для которых выполняется неравенство $\mathrm{A7}_{16} < x < \mathrm{AF}_{16}$? В ответе укажите только количество чисел, сами числа писать не нужно.

1. 1
   Переведём левую границу в десятичную систему:$$\mathrm{A7}_{16} = 10 \cdot 16 + 7 = 167$$
2. 2
   Переведём правую границу в десятичную систему:$$\mathrm{AF}_{16} = 10 \cdot 16 + 15 = 175$$

Ещё 1 шаг — в полном решении

Единицы в двоичной записи

Сколько единиц в двоичной записи шестнадцатеричного числа $\mathrm{E1F0}_{16}$?

1. 1
   Каждой шестнадцатеричной цифре соответствует группа из четырёх двоичных разрядов.$$\mathrm{E1F0}_{16}=1110\ 0001\ 1111\ 0000_2$$
2. 2
   Подсчитаем количество единиц в каждой группе.$$3+1+4+0=8$$

Вычитание шестнадцатеричных чисел

Вычислите значение выражения $9F_{16} - 94_{16}$. В ответе запишите вычисленное значение в десятичной системе счисления.

1. 1
   В шестнадцатеричной системе цифра $F$ имеет значение 15. Переведём первое число в десятичную систему:$$9F_{16}=9\cdot16+15=159$$
2. 2
   Переведём второе число в десятичную систему:$$94_{16}=9\cdot16+4=148$$

Ещё 1 шаг — в полном решении

Числа между двоичными значениями

Сколько существует натуральных чисел $x$, для которых выполняется неравенство $10011011_2 < x < 10011111_2$?

1. 1
   Переведём левую границу неравенства в десятичную систему:$$10011011_2 = 1\cdot2^7+0\cdot2^6+0\cdot2^5+1\cdot2^4+1\cdot2^3+0\cdot2^2+1\cdot2^1+1\cdot2^0=155$$
2. 2
   Переведём правую границу неравенства в десятичную систему:$$10011111_2=159$$

Ещё 1 шаг — в полном решении

Числа между шестнадцатеричными кодами

Сколько существует натуральных чисел $x$, для которых выполняется неравенство $9B_{16} < x < 9F_{16}$?

1. 1
   Переведём границы неравенства в десятичную систему счисления.$$9B_{16}=9\cdot16+11=155,\quad 9F_{16}=9\cdot16+15=159$$
2. 2
   Натуральные числа, строго расположенные между $155$ и $159$, — это $156$, $157$ и $158$.

Ещё 1 шаг — в полном решении

Двоичные числа и неравенство

Сколько существует натуральных чисел $x$, для которых выполняется неравенство $10111101_2 < x < 10111111_2$?

1. 1
   Переведём двоичные числа в десятичную систему:$$10111101_2 = 128 + 32 + 16 + 8 + 4 + 1 = 189$$
2. 2
   Аналогично:$$10111111_2 = 128 + 32 + 16 + 8 + 4 + 2 + 1 = 191$$

Ещё 1 шаг — в полном решении

Кодовое слово по условию Фано

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для кодирования букв используются…

1. 1
   Код $00$ уже занят, а слова $01$, $10$ и $11$ не подходят как кодовые слова: они являются началами существующих кодов.
2. 2
   Проверяем слова длины 3. Слова $010$, $011$, $100$, $101$, $110$ и $111$ либо уже заняты, либо являются началами существующих кодовых слов. Ветви, начинающиеся с $00$, также недоступны из-за слова $00$.

Ещё 1 шаг — в полном решении

Кодирование слова по Фано

По каналу связи передаются сообщения, содержащие только буквы из набора: А, З, К, Л, Ч. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность…

1. 1
   Кодовое слово Ч равно 1, поэтому ни одно другое кодовое слово не может начинаться с 1. Кодовое слово Л равно 011, поэтому в ветви, начинающейся с 0, оно также занимает соответствующую часть дерева.
2. 2
   Чтобы закодировать три оставшиеся буквы и сохранить условие Фано, им можно назначить кодовые слова 000, 001 и 010. Все они имеют длину 3 и не являются префиксами друг друга.

Ещё 2 шага — в полном решении

Минимальная длина двоичного кода

По каналу связи передаются сообщения, содержащие только буквы из набора А, З, К, Н, Ч. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв…

1. 1
   Определим частоты букв в слове КАЗАЧКА: буква А встречается 3 раза, К — 2 раза, З и Ч — по 1 разу.
2. 2
   Для минимизации длины сообщения более частым буквам назначаются более короткие кодовые слова при соблюдении условия Фано.$$l(К)=1,\quad l(А)=2,\quad l(З)=3,\quad l(Ч)=3$$

Ещё 1 шаг — в полном решении

Кратчайшее кодовое слово

Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М, Н использовали…

1. 1
   Кодовое слово для П не может быть 1 или 10, поскольку они являются началами кодовых слов 100 и 110.
2. 2
   Слова 00 и 01 уже заняты, поэтому среди слов длины 3 проверяем варианты 101 и 111. Ни одно из них не является началом или продолжением заданных слов.

Ещё 1 шаг — в полном решении

Минимальная сумма длин кодов

По каналу связи передаются шифрованные сообщения, содержащие только шесть букв: А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код. Для букв А, Б, В и Г используются кодовые…

1. 1
   Кодовые слова длины 1 и 2 использовать нельзя, поскольку любое такое слово будет началом одного из заданных слов.
2. 2
   Среди слов длины 3 можно выбрать, например, 001 и 011. Ни одно из них не является началом или продолжением слов 000, 010, 100 и 1110, поэтому условие Фано выполняется.

Ещё 1 шаг — в полном решении

Минимальная сумма длин кодов

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово…

1. 1
   Кодовые слова 00 и 01 занимают две вершины второго уровня двоичного дерева и не могут быть префиксами других кодовых слов.$$l(А)=2,\quad l(Б)=2$$
2. 2
   Для букв В, Г, Д, Е выбираем свободные вершины дерева так, чтобы кодовые слова не являлись началами друг друга и суммарная длина была минимальной.$$l(В)+l(Г)+l(Д)+l(Е)=12$$

Ещё 1 шаг — в полном решении

Минимальная сумма длин кодов

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 0…

1. 1
   Кодовое слово буквы А равно 0, поэтому ни одно из кодовых слов для букв Б, В, Г и Д не может начинаться с 0: иначе слово 0 было бы началом другого слова.$$A=0$$
2. 2
   Чтобы соблюсти условие Фано и получить минимальные длины, оставшиеся слова размещают в ветви, начинающейся с 1. Их минимально возможные длины дают сумму $2+3+4+4$.$$2+3+4+4=13$$

Ещё 1 шаг — в полном решении

Кодовое слово по Фано

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для девяти букв используются…

1. 1
   Проверяем кодовые слова меньшей длины. Код длины 1 невозможен, так как 0 и 1 являются началами существующих кодов.
2. 2
   Коды длины 2 также невозможны: 00 уже занято, 01 является началом кодов 010 и 011, 10 — началом кодов 1000, 1001 и 101, а 11 — началом кодов 1100, 1101 и 1110.

Ещё 2 шага — в полном решении

Количество лампочек для сигналов

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

1. 1
   Каждая лампочка имеет два состояния, поэтому $n$ лампочек могут образовать $2^n$ различных комбинаций.$$N = 2^n$$
2. 2
   Найдём минимальное $n$, при котором число комбинаций не меньше 50: $2^5 = 32 < 50$, а $2^6 = 64 \geq 50$.$$n = 6$$

Кодовое слово по Фано

По каналу связи передаются шифрованные сообщения, содержащие только 10 букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для девяти букв используются кодовые…

1. 1
   Кодовое слово для буквы С не может быть длины 1: слова $0$ и $1$ были бы началами других кодовых слов.
2. 2
   Слова длины 2 также не подходят: $00$ уже занято, а $01$, $10$ и $11$ являются началами известных кодовых слов.

Ещё 2 шага — в полном решении

Кодовое слово по Фано

По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для девяти букв используются…

1. 1
   Кодовое слово для буквы К не может быть началом уже заданного кодового слова. Поэтому слова $0$ и $1$ невозможны, так как являются началами других кодов.
2. 2
   Двухбитные варианты также невозможны: $00$, $01$, $10$ и $11$ либо уже заняты, либо являются началами существующих кодовых слов.

Ещё 2 шага — в полном решении

Построение кода по Фано

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали…

1. 1
   Кодовые слова 00 и 01 занимают всю ветвь, начинающуюся с 0, а слова 100 и 101 — две ветви после 10.
2. 2
   Код 11 длины 2 использовать для буквы Д нельзя: после него не останется отдельной ветви для кодового слова буквы Е, не нарушающего условие Фано.

Ещё 2 шага — в полном решении