Пройти тестирование по 10 заданиям
Пройти тестирование по всем заданиям
Вернуться к каталогу заданий
Версия для печати и копирования в MS Word
1
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 011, Г — 100. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
2
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 00, Г — 101. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МАГИЯ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
3
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 011, И — 10. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ГРАММ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
4
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, Г, И, М, Р, Я. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 010, Б — 00, Г — 101. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ГРАММ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
5
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, И, К, Л, О, С. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 001, И — 01, С — 10. Какое наименьшее количество двоичных знаков потребуется для кодирования слова КОЛОБОК?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Пройти тестирование по этим заданиям
Старый каталог
Каталог заданий по типам по темам
?
1. Анализ информационных моделей
49
2. Построение таблиц истинности логических выражений
60
3. Поиск информации в реляционных базах данных
23
4. Кодирование и декодирование информации
70
5. Анализ и построение алгоритмов для исполнителей
81
6. Определение результатов работы простейших алгоритмов
31
7. Кодирование и декодирование информации. Передача информации
64
8. Перебор слов и системы счисления
144
10. Поиск символов в текстовом редакторе
36
11. Вычисление количества информации
121
12. Выполнение алгоритмов для исполнителей
76
13. Поиск путей в графе
177
14. Кодирование чисел. Системы счисления
96
15. Преобразование логических выражений
100
16. Рекурсивные алгоритмы
87
17. Обработки числовой последовательности
36
19. Выигрышная стратегия. Задание 1
110
20. Выигрышная стратегия. Задание 2
110
21. Выигрышная стратегия. Задание 3
110
22. Многопроцессорные системы
36
23. Оператор присваивания и ветвления. Перебор вариантов, построение дерева
84
24. Обработка символьных строк
37
25. Обработка целочисленной информации
36
26. Обработка целочисленной информации
35
Дополнительные задания для подготовки
Задания Д1. Анализ информационных моделей
106
Задания Д1. Кодирование и операции над числами в разных системах счисления
90
Задания Д2. Кодирование цвета
4
Задания Д2. Построение таблиц истинности логических выражений
26
Задания Д3. Анализ информационных моделей
30
Задания Д3. Базы данных. Файловая система
159
Задания Д4. Базы данных. Файловая система
2
Задания Д4. Кодирование и декодирование информации
54
Задания Д5. Анализ и построение алгоритмов для исполнителей
106
Задания Д5. Разные задачи
1
Задания Д6. Анализ программ
184
Задания Д6. Символьные строки
9
Задания Д7. Анализ диаграмм и электронных таблиц
171
Задания Д7. Базы данных. Файловая система
91
Задания Д7. Кодирование и декодирование информации. Передача информации
127
Задания Д8. Кодирование и декодирование информации
54
Задания Д8. Перебор слов и системы счисления
54
Задания Д9. Анализ и построение алгоритмов для исполнителей
85
Задания Д10. Анализ диаграмм и электронных таблиц
76
Задания Д11. Вычисление количества информации
69
Задания Д11. Кодирование и декодирование информации. Передача информации
77
Задания Д12. Выполнение алгоритмов для исполнителей
103
Задания Д12. Организация компьютерных сетей. Адресация
155
Задания Д12. Построение таблиц истинности логических выражений
91
Задания Д13. Выполнение алгоритмов для исполнителей
30
Задания Д14. Запросы для поисковых систем с использованием логических выражений
49
Задания Д14. Кодирование чисел. Системы счисления
51
Задания Д15. Преобразование логических выражений
44
Задания Д16. Обработка массивов и матриц
44
Задания Д16. Рекурсивные алгоритмы
81
Задания Д17. Анализ программы с циклами и условными операторами
1
Задания Д17. Запросы для поисковых систем с использованием логических выражений
118
Задания Д18. Оператор присваивания и ветвления
32
Задания Д19 C4. Обработка символьных строк
60
Задания Д19. Обработка массивов и матриц
93
Задания Д21. Анализ программ с циклами и подпрограммами
72
Задания Д22. Анализ программы с циклами и условными операторами
109
Задания Д23. Логические уравнения
116
Задания Д23. Оператор присваивания и ветвления. Перебор вариантов, построение дерева
9
Задания Д24 C1. Исправление ошибок в программе
153
Задания Д25 C2. Алгоритмы обработки массивов
185
Задания Д26 C3. Выигрышная стратегия
152
Задания Д27 C4. Программирование
122
За это задание ты можешь получить 1 балл. На решение дается около 3 минут. Уровень сложности: базовый.
Средний процент выполнения: 84.4%
Ответом к заданию 4 по информатике может быть цифра (число) или слово.
Разбор сложных заданий в тг-канале
Задачи для практики
Задача 1
По каналу связи передаются сообщения, каждое из которых содержит 15 букв А, 10 букв Б, 7 букв В и 5 букв Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью.При выборе кода учитывались два требования: а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование); б) общая длина закодированного сообщения должна быть как можно меньше.
Определите, чему равна длина кодового сообщения для кода, удовлетворяющего перечисленным условиям.
Решение
Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. В данной задаче требуется получить минимальную длину закодированного сообщения, поэтому кодовые слова следует подбирать так, чтобы самая часто встречающаяся буква кодировалась самым коротким кодовым словом. Исходя из этого, можно построить код следующего вида: А – 00, Б – 01, В – 10, Г – 11. Этот код удовлетворяет условию Фано, и длина всего сообщения, закодированного этим кодом, будет равна 15$·$2+10$·$2+7$·$2+5$·$2=74. Для проверки имеет смысл составить ещё один код, удовлетворяющий условию Фано, который мог бы быть оптимальным для некоторых сообщений. Например, рассмотрим такой код: А – 0, Б – 10, В – 110, Г – 111. Тогда длина закодированного сообщения будет 15$·$1+10$·$2+7$·$3+5$·$3=71. Следовательно, такой вариант нас устраивает, данный код является более выгодным, и длина сообщения, закодированного этими кодовыми словами, рана 71.
Ответ: 71
Задача 2
По каналу связи передаются сообщения, каждое из которых содержит 15 букв А, 14 букв Б, 12 букв В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью.При выборе кода учитывались два требования: а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование); б) общая длина закодированного сообщения должна быть как можно меньше.
Определите, чему равна длина кодового сообщения для кода, удовлетворяющего перечисленным условиям.
Решение
Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. В данной задаче требуется получить минимальную длину закодированного сообщения, поэтому кодовые слова следует подбирать так, чтобы самая часто встречающаяся буква кодировалась самым коротким кодовым словом. Исходя из этого, можно построить код следующего вида: А – 00, Б – 01, В – 10, Г – 11. Этот код удовлетворяет условию Фано, и длина всего сообщения, закодированного этим кодом, будет равна 15$·$2+14$·$2+12$·$2+4$·$2=90. Для проверки имеет смысл составить ещё один код, удовлетворяющий условию Фано, который мог бы быть оптимальным для некоторых сообщений. Например, рассмотрим такой код: А – 0, Б – 10, В – 110, Г – 111. Тогда длина закодированного сообщения будет 15$·$1+14$·$2+12$·$3+4$·$3=91. Следовательно, такой вариант нас не устраивает, первый код является более выгодным, и длина сообщения, закодированного этими кодовыми словами, рана 90.
Ответ: 90
Задача 3
По каналу связи передаются сообщения, каждое из которых содержит 20 букв Е, 18 букв И, 16 букв К и 10 букв П (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования: а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование); б) общая длина закодированного сообщения должна быть как можно меньше.
Определите, чему равна длина кодового сообщения для кода, удовлетворяющего перечисленным условиям.
Решение
Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. В данной задаче требуется получить минимальную длину закодированного сообщения, поэтому кодовые слова следует подбирать так, чтобы самая часто встречающаяся буква кодировалась самым коротким кодовым словом. Исходя из этого, можно построить код следующего вида: Е – 00, И – 01, К – 10, П – 11. Этот код удовлетворяет условию Фано, и длина всего сообщения, закодированного этим кодом, будет равна 20$·$2+18$·$2+16$·$2+10$·$2=128. Для проверки имеет смысл составить ещё один код, удовлетворяющий условию Фано, который мог бы быть оптимальным для некоторых сообщений. Например, рассмотрим такой код: Е – 0, И – 10, К – 110, П – 111. Тогда длина закодированного сообщения будет 20$·$1+18$·$2+16$·$3+10$·$3=134. Следовательно, такой вариант нас не устраивает, первый код является более выгодным, и длина сообщения, закодированного этими кодовыми словами, рана 128.
Ответ: 128
Задача 4
По каналу связи передаются сообщения, каждое из которых содержит 18 букв Е, 10 букв И, 8 букв К и 6 букв П (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью.При выборе кода учитывались два требования: а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование); б) общая длина закодированного сообщения должна быть как можно меньше.
Определите, чему равна длина кодового сообщения для кода, удовлетворяющего перечисленным условиям.
Решение
Для решения данной задачи рассмотрим дерево, у которого из корня и любой вершины выходят по две ветви. Сопоставим каждой левой ветви 0, а каждой правой — 1. Тогда, проходя от вершины к каждому из листьев (узлов, из которых не выходят ветви) и выписывая последовательность нулей и единиц, соответствующих обходу дерева, получим набор кодовых слов, образующих префиксный код (код, в котором ни одно кодовое слово не является началом другого). Префиксный код является однозначно декодируемым.
По условию задачи в сообщении используются только 4 различные буквы. Следовательно, для построения кодовых слов возможно использование одного из двух деревьев. При использовании других кодовых деревьев длины кодовых слов будут или совпадать с длинами кодовых слов дерева (в этом случае общая длина кодового сообщения так же будет совпадать), или будут больше, и, следовательно, не будут удовлетворять условию наименьшей длины кодового сообщения.
На основе дерева получим кодовые слова 00, 01, 10 и 11. Все слова имеют длину 2. Учитывая количество вхождений каждой из букв в сообщение, получим, что в этом случае длина закодированного сообщения равна 2 · (18 + 10 + 8 + 6) = 84.
На основе дерева получим кодовые слова 0, 01, 110 и 111.
Чтобы общая длина кодового сообщения была наименьшей, следует назначить букве, встречающейся наибольшее число раз, кодовое слово наименьшей длины. Например, Е — 0, И — 01, К — 110 и П — 111.
В этом коде длины кодовых слов для букв Е, И, К и П равны 1, 2, 3 и 3 соответственно. Учитывая количество вхождений каждой из букв в сообщение, получим, что в этом длина закодированного сообщения равна 1 · 18 + 2 · 10 + 3 · 8 + 3 · 6 = 80.
Следовательно, наименьшая длина кодового сообщения, для кода удовлетворяющего условиям задачи, равна 80.
Ответ: 80
Задача 5
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, в котором ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование). Известно, что для двух букв были использованы кодовые слова 10 и 110. Определите наименьшую возможную суммарную длину всех шести кодовых слов.
Решение
Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. Известны кодовые слова 10 и 110, следовательно, для других кодовых слов мы можем использовать только коды, начинающиеся с 0 или 111. Взять в качестве кодового слова 0 нельзя, т.к. в таком случае невозможно будет найти другие кодовые слова, удовлетворяющие условию Фано для оставшихся сообщений. Таким образом, можем использовать 00, 010, 011, 111. Суммарная длина всех кодовых слов – 16.
Ответ: 16
Задача 6
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, решили использовать неравномерный двоичный код, в котором ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование). Известно, что для двух букв были использованы кодовые слова 10 и 111.
Определите наименьшую возможную суммарную длину всех пяти кодовых слов.
Решение
Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. Известны кодовые слова 10 и 111, следовательно, для других кодовых слов мы можем использовать только коды, начинающиеся с 0 или 110. Взять в качестве кодового слова 0 нельзя, т.к. в таком случае невозможно будет найти другие кодовые слова, удовлетворяющие условию Фано для оставшихся сообщений. Таким образом, можем использовать 00, 01, 110. Суммарная длина всех кодовых слов – 12.
Ответ: 12
Задача 7
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, решили использовать неравномерный двоичный код, в котором ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование). Известно, что для двух букв были использованы кодовые слова 1 и 010.
Определите наименьшую возможную суммарную длину всех пяти кодовых слов.
Решение
Для решения данной задачи рассмотрим дерево, у которого из корня и любой вершины выходят по две ветви. Сопоставим каждой левой ветви 0, а каждой правой — 1. Тогда, проходя от вершины к каждому из листьев (узлов, из которых не выходят ветви) и выписывая последовательность нулей и единиц, соответствующих обходу дерева, получим набор кодовых слов, образующих префиксный код (код, в котором ни одно кодовое слово не является началом другого).
Согласно условию задачи, искомый код должен содержать кодовые слова 1 и 010. Значит, узлы, соответствующие эти кодовым словам, должны быть листьями. На основе этих данных построим дерево.
Однако построенное дерево соответствует коду, содержащему только 4 кодовых слова. По условию задачи требуется пять кодовых слов. Для этого следует продолжить построение дерева для одного из узлов: 00 или 011.
Продолжив построение из узла 00, мы получим кодовые слова 000, 001, 010, 011, 1. Суммарная длина всех кодовых слов равна 3 + 3 + 3 + 3 + 1 = 13.
Продолжив построение из узла 0110, мы получим кодовые слова 00, 010, 0011, 0111, 1. Суммарная длина всех кодовых слов равна 2 + 3 + 4 + 4 + 1 = 14.
Следовательно, наименьшая возможная длина всех кодовых слов равна 13.
Ответ: 13
Задача 8
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А − 01, Б − 11, В − 001, Г − 0001, Д − 0000.
Определите букву, для которой можно сократить длину кодового слова так, чтобы код по-прежнему можно было однозначно декодировать. Коды остальных букв меняться не должны. В ответе укажите букву и её сокращенное кодовое слово без пробелов и запятых. Например, А0.
Решение
Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. В данной задаче нужно просмотреть кодовые слова для каждой из букв и проверить будет ли выполняться условие Фано, если мы каким-нибудь образом сократим данное кодовое слово. Например, рассмотрим букву А – 01. Если заменить её код на 1, то он будет являться началом кода буквы Б. Если заменить код на 0, то он будет являться началом кодов букв В, Г и Д. Таким образом, при любом сокращении кода буквы А условие Фано нарушается. Проверив подобным образом все буквы, приходим к выводу, что можно сократить букву Б, закодировав её словом 1. В таком случае нарушения условия Фано не произойдёт.
Ответ: б1
Задача 9
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код:А − 01, Б − 10, В − 110, Г − 001, Д − 000.
Определите букву, для которой можно сократить длину кодового слова так, чтобы код по-прежнему можно было однозначно декодировать. Коды остальных букв меняться не должны.
В ответе укажите букву и её сокращенное кодовое слово без пробелов и запятых. Например, А0.
Решение
Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. В данной задаче нужно просмотреть кодовые слова для каждой из букв и проверить будет ли выполняться условие Фано, если мы каким-нибудь образом сократим данное кодовое слово. Например, рассмотрим букву А – 01. Если заменить её код на 1, то он будет являться началом кодов букв Б и В. Если заменить код на 0, то он будет являться началом кодов букв Г и Д. Таким образом, при любом сокращении кода буквы А условие Фано нарушается. Проверив подобным образом все буквы, приходим к выводу, что можно сократить букву В, закодировав её словом 11. В таком случае нарушения условия Фано не произойдёт.
Ответ: в11
Задача 10
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А − 01, Б − 11, В − 001, Г − 101, Д − 100.
Определите букву, для которой можно сократить длину кодового слова так, чтобы код по-прежнему можно было однозначно декодировать. Коды остальных букв меняться не должны. В ответе укажите букву и её сокращенное кодовое слово без пробелов и запятых. Например, А0.
Решение
Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. В данной задаче нужно просмотреть кодовые слова для каждой из букв и проверить будет ли выполняться условие Фано, если мы каким-нибудь образом сократим данное кодовое слово. Например, рассмотрим букву А – 01. Если заменить её код на 1, то он будет являться началом кодов букв Б, Г и Д. Если заменить код на 0, то он будет являться началом кода буквы В. Таким образом, при любом сокращении кода буквы А условие Фано нарушается. Проверив подобным образом все буквы, приходим к выводу, что можно сократить букву В, закодировав её словом 00. В таком случае нарушения условия Фано не произойдёт.
Ответ: в00
Задача 11
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А − 00, Б − 01, В − 110, Г − 101, Д − 111.
Определите букву, для которой можно сократить длину кодового слова так, чтобы код по-прежнему можно было однозначно декодировать. Коды остальных букв меняться не должны. В ответе укажите букву и её сокращенное кодовое слово без пробелов и запятых. Например, А0.
Решение
Для решения данной задачи построим дерево, у которого из корня и любой вершины выходят по две ветви. Сопоставим каждой левой ветви 0, а каждой правой — 1. Тогда, проходя от вершины к каждому из листьев (узлов, из которых не выходят ветви) и выписывая последовательность нулей и единиц, соответствующих обходу дерева, получим набор кодовых слов, образующих префиксный код (код, в котором ни одно кодовое слово не является началом другого). Префиксный код является однозначно декодируемым. На рисунке представлено дерево, соответствующее заданному коду.
При сокращении кодового слова в дереве нужно заменить один из полученных листьев узлом более высокого уровня. Такая возможность есть только для кодового слова буквы Г. Вместо листа 100 можно взять узел более высокого уровня 10.
В этом случае полученный код: А — 00, Б — 01, В — 110, Г — 10, Д — 111 — будет префиксным и однозначно декодируемым.
Ответ: г10
Задача 12
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В и Г используются следующие кодовые слова: А − 10, Б − 11, В − 000, Г − 001. Укажите, каким кодовым словом может быть закодирована буква Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Решение
Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. Известны кодовые слова 10, 11, 000, 001, следовательно, для других кодовых слов мы можем использовать только коды, начинающиеся с 01. Слово 01 можно использовать в качестве кодового, т.к. условие Фано для него выполняется. Это кодовое слово является минимальным, т.к. любой код меньший длины в данном случае не будет удовлетворять условию Фано.
Ответ: 01
Задача 13
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В и Г используются следующие кодовые слова: А − 00, Б − 011, В − 010, Г − 10. Укажите, каким кодовым словом может быть закодирована буква Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Решение
Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. Известны кодовые слова 00, 011, 010, 10, следовательно, для других кодовых слов мы можем использовать только коды, начинающиеся с 11. Слово 11 можно использовать в качестве кодового, т.к. условие Фано для него выполняется. Это кодовое слово является минимальным, т.к. любой код меньший длины в данном случае не будет удовлетворять условию Фано.
Ответ: 11
Задача 14
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, допускающий однозначное декодирование. Для букв А, Б, В и Г используются следующие кодовые слова: А − 000, Б − 001, В − 010, Г − 011. Укажите, каким кодовым словом может быть закодирована буква Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Решение
Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. Известны кодовые слова 000, 001, 010, 011, следовательно, для других кодовых слов мы можем использовать только коды, начинающиеся с 1. Слово 1 можно использовать в качестве кодового, т.к. условие Фано для него выполняется.
Ответ: 1
Задача 15
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Известно, что для двух букв были использованы кодовые слова 00 и 10. Определите наименьшую возможную суммарную длину всех кодовых слов.
Задача 16
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 1, для буквы Б — кодовое слово 01. Какова наименьшая возможная сумма длин всех шести кодовых слов?
Примечание: Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки кодированных сообщений.
Задача 17
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 100, для буквы Б — кодовое слово 01. Укажите наименьшую сумму длин кодовых слов для букв В, Г, Д и Е, при котором код будет допускать однозначное декодирование.
Примечание: Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки кодированных сообщений.