21ФИПИ 32DCC7№ 4Повышенная По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв…
- 1
Построим двоичное дерево кодов. Кодовые слова 00 и 01 полностью занимают ветви, начинающиеся с 0.
- 2
В ветви, начинающейся с 1, слова 1000 и 1001 занимают подветвь 100, а слова 110 и 111 — подветви 11. Единственная свободная ветвь — 101.
Ещё 2 шага — в полном решении
22ФИПИ 349C1D№ 4Повышенная Для кодирования некоторой последовательности, состоящей из букв $A$, $B$, $C$, $D$, $E$, $F$, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы $A$ использовали…
- 1
Кодовые слова $0$ и $10$ являются листьями дерева кодирования, поэтому продолжать их нельзя. Для букв $C$, $D$, $E$, $F$ остаётся ветвь, начинающаяся с $11$.
- 2
Четыре кодовых слова можно разместить на минимальной одинаковой глубине: $1100$, $1101$, $1110$, $1111$. Все они удовлетворяют условию Фано.$$|1100|=|1101|=|1110|=|1111|=4$$
Ещё 1 шаг — в полном решении
23ФИПИ 3528DB№ 4Повышенная По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Какое наименьшее количество…
- 1
Рассмотрим свободные ветви двоичного дерева. Кодовое слово 101 уже занято, поэтому в ветви 10 можно использовать слово 100 длины 3.
- 2
Ветвь 11 свободна полностью, поэтому для второй буквы можно взять кодовое слово 11 длины 2. Эти слова не являются началами друг друга и не нарушают условие Фано.$$l_1 + l_2 = 3 + 2 = 5$$
Ещё 1 шаг — в полном решении
24ФИПИ 364539№ 4Повышенная По каналу связи передаются шифрованные сообщения, содержащие только 10 букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв уже заданы кодовые…
- 1
Кодовое слово для буквы Т не должно начинаться с 00, 010, 011, 1000, 1001, 1010, 1011, 110 или 1110, поскольку тогда одно из существующих слов было бы началом нового.
- 2
Слова длины 1 и 2 невозможны: 0 и 1 являются началами существующих слов, а все варианты длины 2 заняты или имеют заданные продолжения.
Ещё 2 шага — в полном решении
25ФИПИ 38AA15№ 4Повышенная По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для девяти букв используются…
- 1
Слова $0$ и $1$ не подходят, поскольку являются началами нескольких заданных кодовых слов.
- 2
Слова длины 2 и 3 также не подходят: $00$, $01$, $10$ и $11$ либо уже заняты, либо являются началами существующих кодовых слов; их продолжения тоже нельзя использовать.
Ещё 2 шага — в полном решении
26ФИПИ 3A22BB№ 4Повышенная Для кодирования растрового рисунка, напечатанного с использованием шести красок, применили неравномерный двоичный код. Укажите кратчайшее кодовое слово для кодирования красного цвета, при котором…
- 1
Кодовое слово 0 уже используется, поэтому любое слово, начинающееся с 0, нарушит условие Фано.
- 2
Кодовое слово 10 уже используется, поэтому слова 100 и 101 не подходят: слово 10 было бы их началом.
Ещё 2 шага — в полном решении
27ФИПИ 3B9384№ 4Повышенная По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Какое наименьшее количество…
- 1
Размещаем известные кодовые слова в двоичном дереве: $10$, $011$, $110$ и $1110$. Ни одно новое слово не может иметь уже использованное слово своим началом и само не может быть началом другого слова.
- 2
Наиболее короткий набор из четырёх свободных листьев можно выбрать как $000$, $001$, $010$ и $1111$. Все эти слова удовлетворяют условию Фано.
Ещё 1 шаг — в полном решении
28ФИПИ 3D61E7№ 4Повышенная По каналу связи передаются сообщения, содержащие только четыре буквы: А, Б, В, Г; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв Б, В, Г используются такие кодовые…
- 1
Кодовое слово для буквы А не может начинаться с 0, поскольку 0 уже является кодовым словом для буквы Г.
- 2
Слова 10 и 11 также не подходят: 10 является началом кодового слова 101, а 11 — началом кодового слова 110.
Ещё 1 шаг — в полном решении
29ФИПИ 3e32BA№ 4Повышенная По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв…
- 1
По условию Фано ни одно кодовое слово не может быть началом другого. Кодовые слова 10 и 11 занимают обе ветви после первого знака 1.
- 2
Кодовые слова 010 и 011 занимают обе ветви после префикса 01. Поэтому четыре оставшихся кодовых слова должны располагаться в поддереве с префиксом 00.
Ещё 2 шага — в полном решении
30ФИПИ 40E3DC№ 4Повышенная Для кодирования последовательности из букв К, Л, М, Н, П, Р используют неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М, Н соответственно использованы кодовые слова 000…
- 1
Кодовое слово длины 1 не подходит: 0 является началом слов 000, 001 и 010, а 1 является началом слова 11.
- 2
Проверим слова длины 2. Слова 00 и 01 являются началами уже заданных кодовых слов, а слово 11 совпадает с уже использованным кодовым словом.
Ещё 2 шага — в полном решении
31ФИПИ 41C3F7№ 4Повышенная По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв…
- 1
Проверим двузначные кодовые слова. Код 00 уже занят, 01 является началом кодов 010 и 011, 10 является началом кодов 1000 и 1001, а 11 является началом кода 111.
- 2
На следующем уровне свободными являются ветви 101 и 110. Они не являются началами известных кодов и не являются началами друг друга, поэтому их можно назначить буквам Ж и З.
Ещё 1 шаг — в полном решении
32ФИПИ 42D598№ 4Повышенная По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для девяти букв используются…
- 1
Проверим кодовые слова длины 1. Коды 0 и 1 недопустимы, поскольку являются началами уже заданных кодовых слов.
- 2
Проверим коды длины 2: 00 уже занято, 01 является началом кодов 010 и 011, 10 является началом кодов 1000, 1001 и 1011, 11 является началом кодов 1101 и 111.
Ещё 2 шага — в полном решении
33ФИПИ 460D7D№ 4Повышенная Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали…
- 1
Кодовые слова 000 и 001 занимают две ветви, начинающиеся с 00, а слова 10 и 11 — обе ветви, начинающиеся с 1.
- 2
Единственная свободная ветвь минимальной длины — 01. Однако если присвоить 01 букве Д, то любое кодовое слово для Е, начинающееся с 01, будет иметь 01 своим началом, что нарушит условие Фано.
Ещё 1 шаг — в полном решении
34ФИПИ 501859№ 4Повышенная По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются…
- 1
Проверим кодовые слова малой длины. Код длины 1 невозможен, так как $0$ и $1$ являются началами существующих слов.
- 2
Коды длины 2 также невозможны: $00$ уже занято, а $01$, $10$ и $11$ являются началами существующих кодовых слов.
Ещё 2 шага — в полном решении
35ФИПИ 504F2E№ 4Повышенная Для кодирования растрового рисунка, напечатанного с использованием шести красок, применили неравномерный двоичный код. Для кодирования цветов используются кодовые слова. Укажите кратчайшее кодовое…
- 1
Код синего цвета не может начинаться с $0$, так как код $0$ уже является кодовым словом белого цвета.
- 2
Код $1$ невозможен, поскольку он был бы началом кодов $10$, $1110$, $11110$ и $11111$.
Ещё 2 шага — в полном решении
36ФИПИ 52C6F3№ 4Повышенная По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У. Для передачи используется неравномерный двоичный код. Для девяти букв используются…
- 1
Проверим кодовые слова небольшой длины. Код длины 1 невозможен, так как 0 и 1 являются началами уже имеющихся кодов.
- 2
Все кодовые слова длины 2 и 3 также конфликтуют с существующими кодами: 00, 01, 10 и 11 уже являются началами кодовых слов, а их продолжения заняты.
Ещё 1 шаг — в полном решении
37ФИПИ 543CA7№ 4Повышенная Для кодирования некоторой последовательности, состоящей из букв A, B, C, D, E, F, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы A использовали кодовое слово…
- 1
Кодовые слова 00 и 01 уже использованы для букв A и B. Оставшиеся кодовые слова должны удовлетворять условию Фано и не пересекаться с ними по началу.
- 2
Распределяя оставшиеся ветви двоичного дерева наиболее экономно, можно получить для букв C, D, E, F длины 2, 3, 3 и 4 соответственно.$$l_C + l_D + l_E + l_F = 2 + 3 + 3 + 4$$
Ещё 1 шаг — в полном решении
38ФИПИ 54C568№ 4Повышенная По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для девяти букв используются…
- 1
Однозначно декодируемый код по условию Фано не допускает, чтобы одно кодовое слово было началом другого.
- 2
Слова, начинающиеся с 0, уже занимают ветви 00, 010 и 011. Слова, начинающиеся с 1, занимают ветви 1000, 1001, 1010, 110, 1110 и 1111.
Ещё 2 шага — в полном решении
39ФИПИ 566A47№ 4Повышенная По каналу связи передаются шифрованные сообщения, содержащие только десять букв: A, B, C, D, E, F, S, X, Y, Z; для передачи используется неравномерный двоичный код. Для кодирования букв используются…
- 1
Проверим кодовые слова длины 1. Слова 0 и 1 являются началами уже имеющихся кодов, поэтому они не подходят.
- 2
Для длины 2 все варианты также исключаются: 00 уже используется, 01 является началом кодов 010 и 011, 10 — началом кодов 1000, 1001 и 1010, а 11 — началом кодов 1100, 1101 и 111.
Ещё 2 шага — в полном решении
40ФИПИ 5A9Ae0№ 4Повышенная По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв…
- 1
Известные кодовые слова занимают ветви 01 и 11, а также две ветви 000 и 001 внутри ветви 00.
- 2
Единственная свободная крупная ветвь — 10. Чтобы разместить в ней четыре кодовых слова и сохранить условие Фано, её нужно разделить до четырёх листьев: 1000, 1001, 1010 и 1011.
Ещё 1 шаг — в полном решении