СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости




Задания
Версия для печати и копирования в MS Word
Задание 5 № 15100

По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, Г, Е, И, М, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:

 

БукваКодовое слово
А11
Б0010
Г100
Е0011

 

БукваКодовое слово
И
М01
Р000
Т

 

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

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Решение.

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

0 — нельзя, Б, Е, М и Р начинаются с 0.

1 — нельзя, А и Г начинаются с 1.

00 — нельзя из-за Б и Р.

01 — нельзя из-за М.

10 — нельзя из-за Г.

11 — нельзя из-за А.

000 — нельзя из-за Р.

001 — нельзя из-за Е.

010 — нельзя из-за М.

011 — нельзя из-за М.

100 — нельзя из-за Г.

101 — нельзя, поскольку, если закодировать букву И кодовым словом 101, для буквы Т не будет кодовых слов, удовлетворяющих условию Фано.

110 — нельзя из-за А.

111 — нельзя из-за А.

0000 — нельзя из-за Р.

0001 — нельзя из-за Р.

0010 — нельзя из-за Б.

0011 — нельзя из-за Е.

0100 — нельзя из-за М.

0101 — нельзя из-за М.

0110 — нельзя из-за М.

0111 — нельзя из-за М.

1000 — нельзя из-за Г.

1001 — нельзя из-за Г.

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

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

1100 — нельзя из-за А.

1101 — нельзя из-за А.

1110 — нельзя из-за А.

1111 — нельзя из-за А.

 

Таким образом, наименьшее числовое значение у кодового слова 1010 для буквы И.

 

Ответ: 1010.