5. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано

5. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано.
Для буквы А использовали кодовое слово 0; для буквы Б – кодовое слово 10. Какова наименьшая возможная сумма длин всех шести кодовых слов?

Примечание.
Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Ответ: 19 ___________________________.

 

Решение:
1) Кодируем:
     А   0
     Б   10
     В   110
     Г   1110
     Д   1111
     Е   10000
 итого:19  Ответ: 19
     


1. Еще одна задача 

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А–111, Б–110, В–100, Г–0.

Укажите, каким из приведенных ниже кодовых слов может быть закодирована буква Д. Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них.

1) 00; 2) 001; 3) 10; 4) 101

Решение. Набор кодовых слов для букв А, Б, В, Г является префиксным (ни одно из них не является началом другого). Посмотрим, нет ли среди предложенных вариантов такого, после добавления которого код останется префиксным. Однако, в отличие от задачи из демо-варианта, здесь по условию более одного варианта может приводить к тому, что получится код, допускающий однозначное декодирование. Поэтому нужно перебирать варианты от более коротких к более длинных и, если вариант не приводит к префиксному коду, убеждаться, что этот вариант действительно дает код, не допускающий однозначного декодирования.

1) Код для Д: 00 – не допускает однозначного декодирования (00 допускает две расшифровки: ГГ и Д).

2) Код для Д: 10 – не допускает однозначного декодирования (100 допускает две расшифровки: В и ДГ).

3) Код для Д: 001 – не допускает однозначного декодирования (00100 допускает две расшифровки: ГГВ и ДГГ).

4) Код для Д: 101 – вместе с кодами для А, Б, В, Г образует префиксный код.

Правильный ответ: 4


Еще одна Задача 2.

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код: А–1, Б–000, В–001, Г–011. Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования.

1) 00 2) 01 3) 11 4) 010

Решение. Набор кодовых слов для букв А, Б, В, Г является префиксным (ни одно из них не является началом другого). Посмотрим, нет ли среди предложенных вариантов такого, после добавления которого код останется префиксным.

1) 00 – не подходит (является началом кодового слова 000 для буквы Б);

2) 01 – не подходит (является началом кодового слова 011 для буквы Г);

3) 11– не подходит (является продолжением(!) кодового слова 1 для буквы А);

4) 010 – подходит! (не является ничьим началом и никто не является его началом).

Ответ: 4.

Замечание 1. Условие Фано является достаточным условием того, что код допускает однозначное декодирование, но не является необходимым. То есть код может допускать однозначное декодирование, но не удовлетворять условию Фано. Простейший пример таких кодов – т.н. постфиксные коды. Это такие коды, в которых никакое кодовое слово не является концом другого кодового слова. Для этих кодов расшифровка производится так же, как и для префиксных кодов, но двигаясь справа налево.

Замечание 2. В рассмотренной задаче А достаточно найти один вариант, удовлетворяющий требованиям задачи. НЕ ТРЕБУЕТСЯ доказывать, что при остальных вариантах код не будет допускать однозначного декодирования. Однако, в данном случае это сделать несложно. А именно:

1) Код Д: 00. Тогда 000000 допускает две расшифровки: ББ и ДДД.

2) Код Д: 01. Тогда 011 допускает две расшифровки: Г и ДА.

2) Код Д: 11. Тогда 11 допускает две расшифровки: АА и Д.


НаименованиеВремяСтоимость 
1

Дистанционный репетитор по информатике по Skype

      1 час от 600 руб.


Запись


Со студентами провожу занятия по высшей математике, математическому анализу, теории вероятности и математической статистике,  линейной алгебре. Индивидуальные занятия в Москве в офисе на м.Китай-город.

Подготовку к ЕГЭ школьников по математике, физике и информатике,  
 занятия со студентами по высшей математике, физике.

Демоверсия ЕГЭ 2017 по математике. Профильный уровень.

Демоверсия ЕГЭ 2017 по физике.

Демоверсия ЕГЭ 2017 по информатике

Вот основные темы по высшей математике: пределы, последовательности, производные, интегрирование, дифференцирование, линейная алгебра, аналитическая геометрия, теория вероятности.

Решение задач:

Пределы

Производные

Бесконечно малые величины

Интегралы

На главную страницу: запись на занятие с репетитором по математике, физике и информатике

Профессиональный репетитор по математике, информатике и физике:

 

Александр Анатольевич Борцов 


КАК ВЫБРАТЬ:
связаться с Александром Анатольевичем
с помощью WhatsApp (лучше) или Telegram
+7-926-859-12-55 

C самого начала своего продвижения по службе, когда еще учился в аспирантуре, я мечтал собрать вместе  мои основные интересы научной деятельности в области Квантовой физики и лазеров: Математику, Информатику, Физику и Обучение.

Компетентный математик и физик для студентов и школьников, кандидат физико математических наук, доктор технических наук по специальности радиофизика. Образование: Физический факультет МГУ им.М.В.Ломоносова с отличием, Специальность -Физика. Преподавал в  МЭИ, педагогический стаж более 15 лет. Является автором  монографии на английском языке "Laser Opto-Electronic Oscillator", 2020, изд. Springer. Автор более 60 ти научных публикаций в зарубежных и отечественных научных журналах по темам Квантовая Электроника, Квантовая радиофизика, Лазеры, Наноэлектроника, Лазерный оптоэлектронный генератор и др.. Хорошо   подготовит без посредников контрольной работе по математике и физике в 11 класс с помощью современных технологий по улучшению памяти. Помощь в оформлении докладов.

 Обучал основам Python, MathLab, Data Science и Machine Learning. 

Более 320 учащихся  поступили «на бюджет» в университеты и  ВУЗы Москвы: ВШЭ, МАИ, МЭИ и МГТУ и т.д.Опыт репетитора по математике для аспирантов более 20 лет.Занятия ведутся дистанционно по Skype и Zoom|и очно в Москве м. Китай-город]. Есть большой опыт подготовки к экзаменам по физике и математике по англоязычным программам университетов (SAT,GMAT). По методикам и учебникам университетов готовил к экзаменам по математике и физике  студентов из Канады, Германии, Испании и  Нидерланды. Говорю по английски, владею английским, преподаю на английском математику и физику..
Занятия ведутся И очно в Москве м. Китай-город и по Skype и Zoom

Запись на занятия

Ваше сообщение отправлено