По каналу связи передаются сообщения, содержащие только шесть букв: А, Б, В, Е, С, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: Б — 100, С — 101. Какое наименьшее количество двоичных знаков потребуется для кодирования слова АТТЕСТАТ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Буква Т повторяется в слове АТТЕСТАТ чаще всего, поэтому закодируем её кодовым словом 0. Следующую букву невозможно закодировать кодовым словом длиной 2, так как будет невозможно закодировать другие буквы так, чтобы выполнялось условие Фано. Букву А закодируем кодовым словом длиной 3, например, 111. Буквы Е и В закодируем кодовыми словами 1100 и 1101. Таким образом, в слове АТТЕСТАТ буква Т кодируется кодовым словом длиной 1, буквы А и С кодируются кодовыми словами длиной 3 и буква Е кодируется кодовым словом длиной 4, тогда количество двоичных знаков, которые потребуются для кодирования слова АТТЕСТАТ, равно 4 · 1 + 2 · 3 + 3 + 4 = 17.
Ответ: 17.