Как нужно закодировать букву г чтобы длина кода была минимальной и допускалось однозначное разбиение
Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=1, Б=01, В=001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
Для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, требуется, чтобы никакой код не был началом другого (более длинного) кода.
Рассмотрим варианты для буквы Г, начиная с самого короткого.
3) Г=11: код буквы A является началом этого кода, поэтому этот вариант не подходит.
4) Код Г=101 не подходит по аналогичной причине.
2) Код Г=000 не совпадает с началом ни одного кода,следовательно это и есть правильный ответ.
Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=100, В=101. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
Для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, требуется, чтобы никакой код не был началом другого (более длинного) кода.
Рассмотрим варианты для буквы Г, начиная с самого короткого.
1) Г=1: код буквы Г является началом кода буквы В=101 и Б=100, поэтому этот вариант не подходит.
2) Код Г=11 не совпадает с началом ни одного кода,следовательно это и есть правильный ответ.
В вариантах 3) и 4) код буквы А=0 является началом кода буквы Г, поэтому они не подходят.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–10, Б–001, В–0001, Г–110, Д–111.
Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
2) для буквы В – 000
Мы видим, что выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова, поэтому однозначно можем раскодировать сообщение с начала.
Чтобы сократить код одной буквы, необходимо выполнение условия Фано в новом коде.
Вариант 3 не подходит, потому что 0 является началом кода 0001.
Вариант 4 не подходит, потому что код 1 является началом кода 111.
Вариант 2 подходит, так как не нарушает условия Фано.
Правильный ответ указан под номером 2.
Здравствуйте! Решая задачу по вашему принципу, я столкнулась с проблемой. Приведу пример:
По условию Фано подходят варианты А) и Б).
В вашем примере верный ответ — А. Если для буквы В выбрать код 101, то 1 будет являться началом кода для буквы В, нарушится условие Фано.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–011, Б–000, В–11, Г–001, Д–10. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
Мы видим, что выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова, поэтому однозначно можем раскодировать сообщение с начала.
Чтобы сократить код одной буквы, необходимо выполнение условия Фано в новом коде.
Вариант 3 не подходит, потому что 00 является началом кода 001.
Вариант 4 не подходит, потому что код 00 является началом кода 000.
Вариант 2 подходит, так как не нарушает условия Фано.
Правильный ответ указан под номером 2.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 00, Б – 01, В – 100, Г – 101, Д – 110. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
Мы видим, что выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова, поэтому однозначно можем раскодировать сообщение с начала.
Чтобы сократить код одной буквы, необходимо выполнение условия Фано в новом коде.
Вариант 3 не подходит, потому что 10 является началом кода 100.
Вариант 4 не подходит, потому что код 10 является началом кода 100 и 101.
Вариант 1 подходит, так как не нарушает условия Фано.
Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
41) Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=100, В=110. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы? У меня не один почему то не подходит ведь если подставлять каждая начинается с той же цифры объясните решение 1) 101 2) 10 3) 11 4) 01
У меня не один почему то не подходит ведь если подставлять каждая начинается с той же цифры объясните решение
Какое количество автобусов и машин нужно заказать, чтобы стоимость заказа была минимальной надо перевести группу из N человек. можно заказать автобус(вмещает 50 человек) и стоит A или.
Нужно зафиксировать букву флешки, чтобы она была и на других компьютерах Как зафиксировать определенную букву флешки, чтобы на других компьютерах при использовании флешки.
Разделить каждое слово из текста на буквы, затем закодировать каждую букву Здравствуйте! Учусь программировать на С++, хочу сделать одну программку. В чем суть: пользователь.
Спланировать перевозки, чтобы стоимость была минимальной В городе имеется 2 склада муки и 2 хлебозавода. Ежедневно с 1-го склада вывозится 50 т муки, а со.
Как нужно закодировать букву г чтобы длина кода была минимальной и допускалось однозначное разбиение
Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=1, Б=01, В=001. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
Для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, требуется, чтобы никакой код не был началом другого (более длинного) кода.
Рассмотрим варианты для буквы Г, начиная с самого короткого.
3) Г=11: код буквы A является началом этого кода, поэтому этот вариант не подходит.
4) Код Г=101 не подходит по аналогичной причине.
2) Код Г=000 не совпадает с началом ни одного кода,следовательно это и есть правильный ответ.
Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=100, В=101. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
Для того, чтобы сообщение, записанное с помощью неравномерного по длине кода, однозначно раскодировалось, требуется, чтобы никакой код не был началом другого (более длинного) кода.
Рассмотрим варианты для буквы Г, начиная с самого короткого.
1) Г=1: код буквы Г является началом кода буквы В=101 и Б=100, поэтому этот вариант не подходит.
2) Код Г=11 не совпадает с началом ни одного кода,следовательно это и есть правильный ответ.
В вариантах 3) и 4) код буквы А=0 является началом кода буквы Г, поэтому они не подходят.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–10, Б–001, В–0001, Г–110, Д–111.
Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
2) для буквы В – 000
Мы видим, что выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова, поэтому однозначно можем раскодировать сообщение с начала.
Чтобы сократить код одной буквы, необходимо выполнение условия Фано в новом коде.
Вариант 3 не подходит, потому что 0 является началом кода 0001.
Вариант 4 не подходит, потому что код 1 является началом кода 111.
Вариант 2 подходит, так как не нарушает условия Фано.
Правильный ответ указан под номером 2.
Здравствуйте! Решая задачу по вашему принципу, я столкнулась с проблемой. Приведу пример:
По условию Фано подходят варианты А) и Б).
В вашем примере верный ответ — А. Если для буквы В выбрать код 101, то 1 будет являться началом кода для буквы В, нарушится условие Фано.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А–011, Б–000, В–11, Г–001, Д–10. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
Мы видим, что выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова, поэтому однозначно можем раскодировать сообщение с начала.
Чтобы сократить код одной буквы, необходимо выполнение условия Фано в новом коде.
Вариант 3 не подходит, потому что 00 является началом кода 001.
Вариант 4 не подходит, потому что код 00 является началом кода 000.
Вариант 2 подходит, так как не нарушает условия Фано.
Правильный ответ указан под номером 2.
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 00, Б – 01, В – 100, Г – 101, Д – 110. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
Мы видим, что выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова, поэтому однозначно можем раскодировать сообщение с начала.
Чтобы сократить код одной буквы, необходимо выполнение условия Фано в новом коде.
Вариант 3 не подходит, потому что 10 является началом кода 100.
Вариант 4 не подходит, потому что код 10 является началом кода 100 и 101.
Вариант 1 подходит, так как не нарушает условия Фано.
Ответы на вступительные испытания по информатике 2
1) 0001 2) 000 (Верно) 3) 11
A10. Для какого из указанных значений X истинно высказывание
A11. В некоторой стране автомобильный номер состоит из 7 символов. В качестве символов используют 18 различных букв и десятичные цифры в любом порядке. Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байтов, при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством битов. Определите объем памяти, отводимый этой программой для записи 60 номеров.
1) 240 байт 2) 300 байт (Верно) 3) 360 байт
Бейсик
Паскаль
s = n
IF A(i) = z THEN s = s — 1
for i:=1 to n do begin
end
Си
Алгоритмический язык
s = n;
for (i = 1; i команда
выполняется, пока условие истинно, иначе происходит переход на следующую строку.
Сколько клеток лабиринта соответствуют требованию, что, выполнив предложенную программу, РОБОТ остановится в той же клетке, с которой он начал движение?
А14. Путешественник пришел в 9:00 на автостанцию населенного пункта КРАСНОЕ и обнаружил следующее расписание автобусов для всей районной сети маршрутов:
Пункт отправления
Пункт прибытия
Время отправления
Время прибытия
Серый бугор
Красное
9:50
11:10
Красное
Зеленые мхи
10:00
11:50
Чёрная горка
Серый бугор
10:15
12:00
Чёрная горка
Зеленые мхи
10:50
12:05
Зеленые мхи
Серый бугор
11:45
12:50
Красное
Чёрная горка
11:50
12:40
Чёрная горка
Красное
12:50
13:40
Красное
Серый бугор
13:00
14:20
Серый бугор
Чёрная горка
13:05
14:40
Зеленые мхи
Чёрная горка
13:15
14:30
Серый бугор
Зеленые мхи
13:45
14:50
Зеленые мхи
Красное
15:10
17:00
Определите самое раннее время, когда путешественник сможет оказаться в пункте СЕРЫЙ БУГОР согласно этому расписанию.
1) 11:10 2) 12:00 3) 14:20 (Верно)
А15. Ниже приведены фрагменты двух таблиц базы данных службы доставки магазина:
Покупатель
Улица
Дом
Квартира
Подьезд
Этаж
Лифт
Андреева Б.В.
Цветочная
12
68
1
12
есть
Борисова В.Г.
Полевая
4
21
2
4
есть
Васильев Д.Е.
Луговая
1
7
1
2
есть
Дмитриева Е.И.
Полевая
16
4
1
2
нет
Егоров И.К.
Луговая
5
79
3
3
есть
Захаров К.Л.
Цветочная
16
14
2
3
нет
№ заказа
Покупатель
Наименование товара
Кол-во
Общий вес, гр.
Цена
Сумма
1
Васильев Д.Е.
Мед липовый
1 банка
350
243
243
2
Дмитриева Е.И.
Сахар-песок
1 уп.
900
29
29
3
Егоров И.К.
Печенье клубничное
1 пач.
200
243
486
4
Егоров И.К.
Конфеты «Ассорти»
1 кор.
600
196
196
5
Андреева Б.В.
Халва
1 уп.
400
79
79
6
Борисова В.Г.
Печенье клубничное
4 пач.
800
42
168
Каков общий вес товаров, которые курьер должен доставить на ул. Луговая?
1) 550 грамм 2) 800 грамм 3) 1150 грамм (Верно)
А16. Лена забыла пароль для входа в Windows XP, но помнила алгоритм его получения из символов «A153B42FB4» в строке подсказки. Если последовательность символов «В4» заменить на «B52» и из получившейся строки удалить все нечетные числа, то полученная последовательность и будет паролем:
Как нужно закодировать букву г чтобы длина кода была минимальной и допускалось однозначное разбиение
Задания:
1) Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11 соответственно). Если таким способом закодировать последовательность символов ГБАВ и записать результат в шестнадцатеричной системе счисления, то получится: 1) 132 16 2) D2 16 3) 3102 16 4) 2D 16
Решение и ответ:
2) Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11 соответственно). Если таким способом закодировать последовательность символов ГБВА и записать результат шестнадцатеричным кодом, то получится:
1) 138 16 2) DBCA 16 3) D8 16 4) 3120 16
Решение и ответ:
По условию: А = 00 Б = 01 В = 10 Г = 11 Значит: ГБВА = 11011000 в двоичной системе. Переведем в шестнадцатеричную и получим D8 Ответ: 3
Решение и ответ:
4) Для кодирования букв А, Б, В, Г используются четырехразрядные последовательные двоичные числа от 1000 до 1011 соответственно. Если таким способом закодировать последовательность символов БГАВ и записать результат в восьмеричном коде, то получится: 1) 175423 2) 115612 3) 62577 4) 12376
Решение и ответ:
По условию: А = 1000 Б = 1001 В = 1010 Г = 1011 БГАВ = 1001101110001010, теперь слудует перевести данное число из двоичной в восьмеричную, и получить ответ. 1001101110001010 2 = 115612 8
Ответ: 2
Для кодирования букв А, В, С, D используются трехразрядные последовательные двоичные числа, начинающиеся с 1 (от 100 до 111 соответственно). Если таким способом закодировать последовательность символов CDAB и записать результат в шестнадцатеричном коде, то получится: 1) А52 16 2) 4С8 16 3) 15D 16 4) DE5 16
Решение и ответ:
По условию: Соответственно A = 100 B = 101 C = 110 D = 111 СDAB = 110111100101, переведем двоичное число в шестнадцатеричную: 110111100101 2 = DE5 16 Ответ: 4
6) Для кодирования букв К, L, М, N используются четырехразрядные последовательные двоичные числа от 1000 до 1011 соответственно. Если таким способом закодировать последовательность символов KMLN и записать результат в восьмеричном коде, то получится: 1) 84613 8 2) 105233 8 3) 12345 8 4) 776325 8
Решение и ответ:
По условию: соответственно K = 1000 L = 1001 M = 1010 N = 1011 KMLN = 1000101010011011, переведем в восьмеричное число:
1000101010011011 2 = 105233 8
Ответ: 2
7) Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв – из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
а b с d е 100 110 011 01 10 Определите, какой набор букв закодирован двоичной строкой 1000110110110, если известно, что все буквы в последовательности – разные: 1) cbade 2) acdeb 3) acbed 4) bacde
Решение и ответ:
Запишем двоичный код в виде битов: Методом перебора возможных вариантов, чтобы не повторялись буквы. Получается: 100 011 01 10 110 Следовательно: acdeb Ответ: 2
8) Для 6 букв латинского алфавита заданы их двоичные коды (для некоторых букв из двух бит, для некоторых – из трех). Эти коды представлены в таблице: А В С D Е F 00 100 10 011 11 101 Определите, какая последовательность из 6 букв закодирована двоичной строкой 011111000101100. 1) DEFBAC 2) ABDEFC 3) DECAFB 4) EFCABD
Решение и ответ:
Решим методом перебора, так как буквы в ответах не повторяются, значит и коды не должны повторяться:
9) Для кодирования букв А, В, С, D используются четырехразрядные последовательные двоичные числа, начинающиеся с 1 (от 1001 до 1100 соответственно). Если таким способом закодировать последовательность символов CADB и записать результат в шестнадцатеричном коде, то получится: 1) AF52 16 2) 4CB8 16 3) F15D 16 4) В9СА 16
10) Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код: А Б В Г 00 11 010 011 Если таким способом закодировать последовательность символов ВГАГБВ и записать результат в шестнадцатеричном коде, то получится: 1) CDADBC 16 2) A7C4 16 3) 412710 16 4) 4С7А 16
11) Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код: А Б В Г 00 11 010 011 Если таким способом закодировать последовательность символов ГАВБВГ и записать результат в шестнадцатеричном коде, то получится: 1) 62D3 16 2) 3D26 16 3) 31326 16 4) 62133 16
Ответ: 1
12) Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине
двоичный код: А Б В Г 00 11 010 011 Если таким способом закодировать последовательность символов ГБВАВГ и записать результат в шестнадцатеричном
13) Для кодирования сообщения, состоящего только из букв А, Б, В и Г, используется неравномерный по длине двоичный код: А Б В Г 00 11 010 011 Если таким способом закодировать последовательность символов ГАВБГВ и записать результат в шестнадцатеричном коде, то получится: 1) DACBDC 16 2) AD26 16 3) 621310 16 4) 62DA 16 Решение и ответ: соответственно..
14) Для кодирования сообщения, состоящего только из букв A, B, C, D и E, используется неравномерный по длине двоичный код: A B C D E 000 11 01 001 10 Какое (только одно!) из четырех полученных сообщений было передано без ошибок и может быть раскодировано: 1) 110000010011110 2) 110000011011110 3) 110001001001110 4) 110000001011110
Решение и ответ:
Возьмем первый код: 11 000 001 001 11 10 = BADDBE Второй код: 11 000 001 10 11 110 = с ошибкой в конце. Третий код: 11 000 10 01 001 110 = с ошибкой в конце. Четвертый код: 11 000 000 10 11 110 = с ошибкой в конце. Ответ: 1
15) Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г используется посимвольное
кодирование: А-00, Б-11, В-010, Г-011. Через канал связи передается сообщение: ВАГБГВ. Закодируйте сообщение
данным кодом. Полученную двоичную последовательность переведите в шестнадцатеричный вид. 1) AD34 2) 43DA 3) 101334 4) CADBCD Решение и ответ:
17) Для передачи по каналу связи сообщения, состоящего только из букв А, Б, В, Г, решили использовать неравномерный по длине код: A=0, Б=100, В=101. Как нужно закодировать букву Г, чтобы длина кода была минимальной и допускалось однозначное разбиение кодированного сообщения на буквы?
1) 1 2) 11 3) 01 4) 010
Аналогично заданию номер 16.
Ответ: 2
18) Черно-белое растровое изображение кодируется построчно, начиная с левого верхнего угла и заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0 – белый.
Для компактности результат записали в восьмеричной системе счисления. Выберите правильную запись кода. 1) 57414 2) 53414 3) 53412 4) 53012
Решение и ответ: После кодирования мы получаем данный код:
Ответ: 3
19) Для передачи по каналу связи сообщения, состоящего только из символов А, Б, В и Г используется посимвольное
кодирование: А-0, Б-11, В-100, Г-011. Через канал связи передается сообщение: ГБАВАВГ. Закодируйте сообщение
20) Для передачи данных по каналу связи используется 5-битовый код. Сообщение содержит только
буквы А, Б и В, которые кодируются следующими кодовыми словами:
A — 11010, Б — 00110, В — 10101.
При передаче возможны помехи. Однако некоторые ошибки можно попытаться исправить. Любые два из этих трёх кодовых слов отличаются друг от друга не менее чем в трёх позициях. Поэтому если при передаче слова произошла ошибка не более чем в одной позиции, то можно сделать обоснованное предположение о том, какая буква передавалась. (Говорят, что «код исправляет одну ошибку».) Например, если получено кодовое слово 10110, считается, что передавалась буква Б. (Отличие от кодового слова для Б — только в одной позиции, для остальных кодовых слов отличий больше.) Если принятое кодовое слово отличается от кодовых слов для букв А, Б, В более чем в одной позиции, то считается, что произошла ошибка(она обозначается‘x’).
Получено сообщение 00111 11110 11000 10111. Декодируйте это сообщение — выберите правильный вариант.
1) БААx 2) БААВ 3) xxxx 4) xAAx
Решение: 1) 00111 = Б, так как 1 ошибка в последней цифре. 2) 11110 = A, так как 1 ошибка в третьей цифре. 3) 11000 = А, так как 1 ошибка в четвертой цифре. 4) 10111 = В, так как 1 ошибка в четвертой цифре
00111 11110 11000 10111 = БААВ. Ответ: 2
Код является однозначно декодируемым тогда и только тогда, когда в построенном таким образом графе нет ориентированных циклов, включающих вершину Λ.
Таким образом, код (6) не обладает свойством однозначной декодируемости.
Проверим таким же способом код (5), который, как мы уже выяснили, не является ни префиксным, ни постфиксным. Множество последовательностей, которые совпадают с началом и концом кодовых слов, состоит из пустой строки и единицы: <Λ, 1>. Граф, построенный с помощью приведённого выше алгоритма, содержит два узла и одну петлю:
В этом графе нет цикла, содержащего вершину Λ, поэтому любое сообщение, записанное с помощью такого кода, декодируется однозначно. Выше мы показали это с помощью простых рассуждений.
Нужно отметить, что на практике применяются, главным образом, префиксные коды, поскольку они позволяют декодировать сообщение по мере его получения, не дожидаясь окончания приёма данных.
Ещё примеры
Заметим, что «обратное» условие Фано не выполняется: код буквы А (00) совпадает с окончанием кода буквы В (100), а код буквы Б (01) совпадает с окончанием кода буквы Г (101).
Теперь проверим, что получится, если сократить код буквы Д до 11 (вариант 1). Свойство однозначной декодируемости может быть потеряно только тогда, когда в результате такого сокращения нарушится условие Фано, то есть код буквы Д совпадёт с началом какого-то другого кодового слова. Видим, что этого не произошло — нет других кодовых слов, которые начинаются с 11, поэтому вариант 1 — это и есть верное решение.
Остается убедиться, что варианты 3 и 4 не подходят. Если мы сократим код буквы Г до 10 (вариант 3), условие Фано оказывается нарушенным, так как теперь код буквы Г (10) совпал с началом кода буквы В (100). Одновременно нарушено и «обратное» условие Фано: код буквы А (00) совпадает с окончанием кода буквы В (100). Но, как мы знаем, при этом код может всё-таки быть однозначно декодируемым.
Конечно, можно построить граф, как было сделано выше, и проверить, есть ли в нём циклы, включающие вершину Λ. В данном случае граф выглядит так:
Построение и анализ графа — дело достаточно трудоемкое и требующее аккуратности. Обычно в таких случаях значительно легче просто подобрать последовательность, которая может быть декодирована двумя разными способами.
Наконец, нужно убедиться, что вариант 4 не удовлетворяет условию. Если мы сократим код буквы Д до 10, условие Фано оказывается нарушенным, так как теперь код буквы Д (10) совпал с началом кода буквы В (100). Как и раньше, нарушено «обратное» условие Фано: код буквы А (00) совпадает с окончанием кода буквы В (100) и код буквы Б (01) совпадает с окончанием кода буквы Г (101).
Построим граф по методу Ал.А. Маркова:
Проверим вариант 1 — сократим код буквы Г до 00. При этом нарушилось условие Фано, которое обеспечивало однозначную декодируемость исходного варианта: теперь код буквы Г (00) совпадает с началом кода буквы Д (001). Но и обратное условие Фано тоже не выполняется для пары букв А-В. Поэтому можно предположить, что такой код не обладает свойством однозначной декодируемости. И действительно, легко находится цепочка 001011, которую можно раскодировать как ГБА (00 10 11) или ДВ (001 011).
Рассмотрим вариант 3 — сократим код буквы В до 01. При этом условие Фано выполняется, поскольку ни одно из кодовых слов не начинается с 01, то есть код является префиксным и однозначно раскодируется. Это и есть правильный ответ.
На всякий случай проверяем вариант 4 — сокращает код буквы Б до 1. При этом код перестает быть префиксным, и обратное условие Фано также не выполнено (код буквы Б совпадает с началом и концом кода буквы А). Сразу понятно, что последовательность 11 можно раскодировать как А или как ББ, поэтому этот вариант неверный.
Спланировать перевозки, чтобы стоимость была минимальной
