По каналу связи передаются сообщения, содержащие только буквы из набора: А, К,… (информатика)

№ Условие Фано, кодирование слова

По каналу связи передаются сообщения, содержащие только буквы из набора: А, К, Л, Н, О, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Кодовые слова для некоторых букв известны: Л — 1, Я — 01. Для четырёх оставшихся букв А, К, Н и О кодовые слова неизвестны. Какое количество двоичных знаков потребуется для кодирования слова КОЛОННА, если известно, что оно закодировано минимально возможным количеством двоичных знаков?

Решение

Коды букв А, К, Н, О не могут начинаться с (это код Л) и с (это код Я). Значит, все они начинаются с .

После префикса нужно разместить кодовых слова так, чтобы ни одно не было началом другого. Возможны два набора длин после префикса: , , , или , , , . Полные длины кодов будут , , , или , , , .

В слове КОЛОННА буквы встречаются так: К — , О — , Л — , Н — , А — .

Вариант (длины , , , ): .

Вариант (длины , , , ): самые частые буквы получают короткие коды. О — , Н — , К — , А — . Тогда .

В обоих вариантах получается .

💡 Почему так

Условие Фано: никакое кодовое слово не является началом другого. Минимальная длина всего слова определяется тем, как можно построить оставшиеся коды.

Ответ

№ Комбинаторика

Вася составляет 4-буквенные слова, в которых есть только буквы К, О, М, А, Р, причём буква А используется в них не более 3-х раз (или не используется совсем). Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Решение

Всего -буквенных слов из букв: .

Недопустимо только слово ААAА, где А стоит раза. Оно одно.

Ответ

№ Комбинаторика, системы счисления

Определите количество шестизначных двенадцатеричных чисел, в записи которых менее двух цифр В.

Решение

Цифра В в двенадцатеричной системе равна . Всего цифр : от до . Без В остаётся цифр, а на первом месте не может стоять .

Нужно посчитать числа без В и числа ровно с одной В.

Нет цифры В. На первом месте может стоять любая из цифр .., то есть вариантов. На остальных пяти местах по вариантов.
Ровно одна цифра В.

В стоит на первом месте. Остальные пять цифр выбираются по способов: .
В стоит на одном из пяти остальных мест. Это вариантов. Первая цифра выбирается способами, остальные четыре цифры по способов:

Складываем:

Ответ

№ Количество информации

Каждому изготовленному на заводе двигателю присваивается уникальный серийный номер, содержащий десятичные цифры и символы из 70-символьного специального алфавита. В базе данных каждый серийный номер занимает одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что 1 234 567 серийных номеров занимают более 24 Мбайт памяти. Определите минимально возможную длину серийного номера. В ответе запишите только целое число.

Решение

Всего символов . Так как , на один символ нужно бит.

Мбайт байт.

На один номер приходится больше байт. Так как число байт целое, нужно не менее байта, то есть не менее бит.

Длина номера L должна удовлетворять условию (при этом число байт ).

При : бит, это байт. Этого мало.
При : бит, это байт. Этого достаточно.

Ответ

№ Количество информации

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 10 символов, содержащий только символы из набора Н, Е, П, Р, И, Д, У, М, А, Л, десятичные цифры и специальные символы #, $, @, _, %. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения. Для хранения как пароля, так и дополнительных сведений отведено одинаковое для каждого пользователя целое количество байт. Известно, что для хранения пароля выделено в байтах РОВНО в 1,5 раза меньше памяти, чем для хранения дополнительных сведений. Какое минимальное количество байт необходимо выделить, чтобы сохранить информацию о 22 пользователях? В ответе запишите только целое число – количество байт.

Решение

Символов в наборе: . Так как , на один символ нужно бит.

Пароль занимает бит, то есть не менее байт.

Пусть на пароль выделено байт, а на дополнительные сведения байт. Оба числа целые, поэтому чётно. Также , значит .

Дополнительные сведения: байт.

На одного пользователя: байт.

На пользователей: байт.

Ответ

№ Комбинаторика, позиции слов

Все 4-буквенные слова, составленные из букв М, А, Р, Т, записаны в алфавитном порядке. Какое количество слов находятся между словами МАРТ и РАМТ (не включая эти слова)? Вот начало списка:

АААА
АААМ
АААР
АААТ
……

Решение

Алфавитный порядок букв: А < М < Р < Т. Сопоставим им цифры четверичной системы: А — , М — , Р — , Т — . Номер слова в списке равен значению числа в этой системе плюс .

МАРТ .

РАМТ .

Между ними лежат слова с номерами от до включительно (от до не включая концы):

Ответ

№ Системы счисления

Значение арифметического выражения: $2\cdot27^{7}+3^{10}-9$ записали в системе счисления с основанием 3. Сколько цифр «0» содержится в этой записи?

Решение

Приведём всё к степеням тройки: , .

Разность . Число в троичной системе записывается как восемь двоек. Умножение на дописывает два нуля справа. Получаем , то есть цифры стоят в разрядах с -го по -й, а в разрядах и стоят нули.

Слагаемое даёт цифру в разряде .

Итоговая запись: цифра в разряде , нули в разрядах с -го по -й (всего нулей), цифры в разрядах с -го по -й, нули в разрядах и (ещё нуля).

Нулей: .

Ответ

Помогло?