Задания
Версия для печати и копирования в MS Word
Тип 4 № 69882
i

По ка­на­лу связи пе­ре­да­ют­ся шиф­ро­ван­ные со­об­ще­ния, со­дер­жа­щие толь­ко де­сять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для пе­ре­да­чи ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный код. Для де­вя­ти букв ис­поль­зу­ют­ся ко­до­вые слова. Для буквы А  — 00, Е  — 010, И  — 011, К  — 1111, Л  — 1101, Р  — 1010, С  — 1110, Т  — 1011, У  — 100.

Ука­жи­те крат­чай­шее ко­до­вое слово для буквы Б, при ко­то­ром код будет удо­вле­тво­рять усло­вию Фано. Если таких кодов не­сколь­ко, ука­жи­те код с наи­мень­шим чис­ло­вым зна­че­ни­ем.

 

При­ме­ча­ние. Усло­вие Фано озна­ча­ет, что ни­ка­кое ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова. Это обес­пе­чи­ва­ет воз­мож­ность од­но­знач­ной рас­шиф­ров­ки за­ко­ди­ро­ван­ных со­об­ще­ний.

Спрятать решение

Ре­ше­ние.

Пе­ре­чис­лим воз­мож­ные коды (не ис­поль­зу­ю­щи­е­ся для ко­ди­ров­ки дру­гих букв) в по­ряд­ке воз­рас­та­ния длины и чис­ло­во­го зна­че­ния.

0  — нель­зя, А, Е, И на­чи­на­ют­ся с 0.

1  — нель­зя, буквы К, Л, Р, С, Т, У на­чи­на­ют­ся с 1.

01  — нель­зя из-⁠за Е и И.

10  — нель­зя из-⁠за Р, Т и У.

11  — нель­зя из-⁠за К, Л, С.

000  — нель­зя из-⁠за А.

001  — нель­зя из-⁠за А.

101  — нель­зя из-⁠за Р и Т.

110  — нель­зя из-⁠за Л.

111  — нель­зя из-⁠за К.

1000  — нель­зя из-⁠за У.

1001  — нель­зя из-⁠за У.

1100  — можно ис­поль­зо­вать.

 

Таким об­ра­зом, крат­чай­шее ко­до­вое слово для буквы Б  — 1100.

 

Ответ: 1100.


-------------
Дублирует задание № 13732.
Источники: