реши и нарисуй дерево

Краткий ответ

Буква Л получает код 1101 (числовое значение 13). Свободное место в дереве только одно, поэтому вариантов больше нет.

Дерево

корень
├─ 0
│  ├─ 0 → А (00)
│  └─ 1
│     ├─ 0 → В (010)
│     └─ 1 → Е (011)
└─ 1
   ├─ 0
   │  ├─ 0
   │  │  ├─ 0 → К (1000)
   │  │  └─ 1 → М (1001)
   │  └─ 1
   │     ├─ 0 → Д (1010)
   │     └─ 1 → И (1011)
   └─ 1
      ├─ 0
      │  ├─ 0 → Г (1100)
      │  └─ 1 → Л (1101)  ← единственное свободное место
      └─ 1 → Б (111)

Как это получается

1. Что означает условие Фано. Ни одно кодовое слово не должно быть началом другого. В дереве это значит: буквы сидят только в листьях, а узел, у которого есть потомки, занимать нельзя — иначе его код стал бы префиксом чужого.

2. Разбираем известные коды.

• Ветка \(0\): \(00\) — это А (лист), значит \(01\) — внутренний узел; его дети \(010\) = В и \(011\) = Е. Ветка \(0\) заполнена полностью.
• Ветка \(1\):
  • \(10 \to 100 \to 1000\) = К, \(1001\) = М; \(101 \to 1010\) = Д, \(1011\) = И — заполнено;
  • \(11 \to 110 \to 1100\) = Г, а вот \(1101\) свободно; \(111\) = Б.

3. Ищем свободный узел. Выписываем все узлы, которые нельзя брать: они либо уже кодовые слова, либо префиксы чужих слов. Это \(0, 00, 01, 010, 011, 1, 10, 100, 1001, 101, 1010, 1011, 11, 110, 1100, 111\). Единственный незанятый лист — \(1101\). Его и получает Л: \(1101\).

Короткий код взять нельзя, например \(110\) — он является началом слова \(1100\) (Г), а \(111\) уже занято буквой Б.

Проверка

Неравенство Крафта для десяти полученных кодов:

\[ 2^{-2}+3\cdot 2^{-3}+6\cdot 2^{-4}=\tfrac14+\tfrac38+\tfrac38=1 \]

Сумма равна единице — код полный, «лишних» листьев нет, значит выбор единственный. Дополнительно: \(1101\) не является префиксом ни одного слова и ни одно слово не является его префиксом — условие Фано выполнено.

Ответ: 1101.