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

Каждая позиция в коде может содержать точку или тире, то есть имеет 2 варианта.

Количество кодов длины 5 равно $2^5 = 32$, а количество кодов длины 6 равно $2^6 = 64$.

Буква С должна встретиться ровно один раз. Выбираем одну из пяти позиций для этой буквы.$$5$$

Оставшиеся четыре позиции можно заполнить любой из трёх букв: Т, У или Л.$$3^4$$

В алфавитном порядке буквы расположены так: И, Н, О, П, Т. До буквы Т идут четыре буквы.

Для каждого фиксированного первого символа остальные три позиции можно заполнить пятью способами.$$5^3 = 125$$

Первая цифра не может быть нечётной и не может быть нулём, поэтому для неё доступны цифры $2, 4, 6$: всего 3 варианта. Последняя цифра не может быть равна 2 или 6, поэтому доступны 6 вариантов: $0, 1, 3, 4, 5, 7$. Каждая из трёх средних…$$N_0=3\cdot6\cdot8^3=9216$$

Вычтем числа, содержащие не менее трёх цифр 7. Первая цифра не может быть равна 7. Если последняя цифра не равна 7, то все три средние цифры равны 7: $3\cdot5=15$ чисел.$$N_1=3\cdot5=15$$

Единственную букву П можно разместить на одной из трёх позиций.$$3$$

На каждую из двух оставшихся позиций можно поставить одну из пяти допустимых букв, отличных от П. Повторения разрешены.$$5^2$$

Алфавитный порядок букв имеет вид А, Е, К, Н, Т, Ц. Всего используется 6 букв.

Слово не должно содержать А, а первая буква не может быть Е или К. Поэтому минимальная возможная первая буква — Н.

В порядке возрастания буквы имеют номера: А — 0, К — 1, О — 2, Р — 3, С — 4, Т — 5.

Подходящее слово с последним чётным номером — КСКТА. Оно не начинается с Р, С или Т и содержит ровно одну букву А.

После исключения цифры 1 остаются чётные цифры 0, 2, 4, 6 и нечётные цифры 3, 5, 7.

Цифры должны чередоваться по чётности. Рассмотрим шаблон чётная–нечётная–чётная–нечётная–чётная. Всего способов выбрать и расставить цифры: $4 \cdot 3 \cdot 2 \cdot 3 \cdot 2 = 144$. Из них 36 начинаются с нуля…

Единственную букву В можно расположить на любой из 5 позиций.$$5$$

На каждую из оставшихся 4 позиций можно поставить одну из 3 букв: О, Л или К.$$3^4$$

Упорядочим буквы и сопоставим им номера от нуля: А — $0$, В — $1$, Е — $2$, Н — $3$.

Слово ННЕЕ рассматривается как число в системе счисления с основанием $4$ с цифрами $3, 3, 2, 2$.

Буквы расположены в алфавитном порядке: А, П, Р, С, У. Чтобы получить последнее подходящее слово, выбираем максимально возможную первую букву — У. Остальные буквы У использовать нельзя, поэтому в каждой следующей позиции выбираем…$$УСССС$$

В пятибуквенных словах каждая позиция соответствует разряду пятеричной системы счисления. Буквам соответствуют цифры: А — 0, П — 1, Р — 2, С — 3, У — 4.$$УСССС = 43333_5$$

По приведённому началу списка порядок букв такой: И, Н, О, П, Т.

До слов, начинающихся с О, идут все слова, начинающиеся с И или Н. Для каждой фиксированной первой буквы остальные три позиции можно заполнить пятью способами.$$2 \cdot 5^3 = 250$$

Сопоставим буквам их порядковые номера, начиная с нуля: А = 0, Б = 1, З = 2, И = 3.

Позиции букв в слове ИЗБА имеют веса $4^3$, $4^2$, $4^1$ и $4^0$.$$3 \cdot 4^3 + 2 \cdot 4^2 + 1 \cdot 4^1 + 0 \cdot 4^0 = 192 + 32 + 4 = 228$$

Подходящее слово не может начинаться с Е, И или О. Минимальная возможная первая буква — Р.

До слов, начинающихся с Р, идут все слова с первыми буквами Е, И и О. Их количество равно:$$3 \cdot 6^5 = 23328$$

Сначала рассмотрим слова, в которых буква В не используется. На последней позиции можно поставить одну из двух согласных букв, а на остальные позиции — любую из четырёх букв.$$N_1 = 2 \cdot 4^5 = 2048$$

Теперь рассмотрим слова, в которых буква В встречается ровно один раз. Если В стоит на первой позиции, остальные позиции дают $2 \cdot 4^4$ вариантов. Если В стоит на одной из четырёх внутренних позиций, получаем $4 \cdot 2 \cdot 4^4$…$$N_2 = 2 \cdot 4^4 + 4 \cdot 2 \cdot 4^4 + 4^4 = 2304$$

Определим мощность алфавита идентификаторов: 10 десятичных цифр и 240 специальных символов.$$N = 10 + 240 = 250$$

Найдём минимальное одинаковое количество бит для кодирования одного символа. Так как $2^7 = 128 < 250$, а $2^8 = 256 \geq 250$, требуется 8 бит на символ.$$i = 8$$

Определим общее количество символов алфавита:$$N = 16 + 10 = 26$$

Минимальное одинаковое количество бит для кодирования одного символа:$$i = \lceil\log_2 26\rceil = 5\ \text{бит}$$

Для кодирования одной цифры нужно минимальное число бит $n$, такое что $2^n \geq 10$. Получаем 4 бита.

Для кодирования одной буквы нужно минимальное число бит $n$, такое что $2^n \geq 25$. Получаем 5 бит.

Всего используется 30 различных символов: 20 заглавных букв и 10 цифр.$$20 + 10 = 30$$

Минимальное одинаковое количество бит для кодирования одного символа определяется условием $2^i \geq 30$. Получаем 5 бит, так как $2^4 < 30 \leq 2^5$.$$i = 5$$

Для кодирования 10 различных символов необходимо минимальное число бит $i$, такое что $2^i \geq 10$. Получаем $i = 4$.$$2^3 < 10 \leq 2^4$$

Объём одного пароля длиной 15 символов равен:$$15 \cdot 4 = 60\ \text{бит} = 7{,}5\ \text{байт}$$