Презентация "Решение задания №1 из демоверсии ЕГЭ 2015" 11 класс

Подписи к слайдам:
Решение задания №1 из демоверсии ЕГЭ 2015 Для кодирования некоторой последовательности , состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 0; Б – 100; В – 1010; Г – 111; Д – 110. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать? Для кодирования некоторой последовательности , состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А – 0; Б – 100; В – 1010; Г – 111; Д – 110. Требуется сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно. Коды остальных букв меняться не должны. Каким из указанных способов это можно сделать?
      • для буквы В – 101
      • это невозможно
      • для буквы В – 010
      • для буквы Б – 10
      • Решение: Условие Фано: Любое кодовое слово не может быть началом другого кодового слова.
      • В – 101(соблюдается условие Фано)
      • В – 010, А – 0 (А является началом В)
      • Б – 10, В – 101(Б является началом В)

А-0 В-010

Б – 10 В – 101

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д и Е, используется неравномерный двоичный префиксный код. Даны кодовые слова для четырёх букв: А — 011, Б — 010, В — 001, Г — 000. Какие кодовые слова из приведённых ниже вариантов подходят для букв Д и Е? Если подходит более одного варианта, укажите тот, для которого сумма длин кодовых слов меньше. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д и Е, используется неравномерный двоичный префиксный код. Даны кодовые слова для четырёх букв: А — 011, Б — 010, В — 001, Г — 000. Какие кодовые слова из приведённых ниже вариантов подходят для букв Д и Е? Если подходит более одного варианта, укажите тот, для которого сумма длин кодовых слов меньше. 1) Д — 100, Е — 110 2) Д — 100, Е — 11 3) Д — 10, Е — 11 4) Д — 10, Е — 1 Решение: Проверим каждый вариант ответа, соблюдая условие Фано. 1) Первый вариант подходит. 2) Второй вариант ответа подходит 3) Третий вариант ответа подхо­дит 4) Четвёртый вариант ответа не подходит код буквы Е является началом кода буквы Д. Из подошедших нам вариантов ответа выбираем тот, у которого сумма длин кодовых слов меньше.

Е-1 Д-10

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А — 001, Б — 010, В— 000, Г — 011. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А — 001, Б — 010, В— 000, Г — 011. Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква Д. Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них. 1) 00 2) 01 3) 101 4) 0000 Решение: Для того, чтобы код можно было однозначно декодировать, необходимо, чтобы выполнялось условие Фано. 1) Д является началом А, В 2) удовлетворяет условию Фано 3) удовлетворяет усло­вию Фано 4) В является началом Д Выбирая из второго и третьего варианта, останавливаемся на втором, поскольку он короче.

Д-00 А-001 В-000

В-000 Д-0000

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А — 001, Б — 010, В— 000, Г — 011. Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Для букв А, Б, В и Г использовали такие кодовые слова: А — 001, Б — 010, В— 000, Г — 011. Укажите, каким кодовым словом из перечисленных ниже может быть закодирована буква Д. Код должен удовлетворять свойству однозначного декодирования. Если можно использовать более одного кодового слова, укажите кратчайшее из них. 1) 00 2) 01 3) 101 4) 0000 Решение: 1) Д является началом кода буквы В, поэтому этот вари­ант не подходит. 2) Д является началом кода буквы Б, Г, поэтому этот вариант не подходит. 3) Д=101: код буквы Д не является началом другого кода, следовательно, это правильный ответ. 4) В=000 является началом Д =0000.

Д-00 В-000

Д-01 Б-010 Г-011

Спасибо за внимание!