Конспект урока "Подготовка к ЕГЭ по информатике. Задание 4. Условие Фано"

Условие Фано. Задание 4

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

Обратное условие Фано означает, что никакое кодовое слово не является окончанием другого кодового слова.

Способ решения 4 задания -- дерево Фано

Пример задания

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

Алгоритм решения

1.Построим дерево Фано и обозначим на нём занятые коды:

2. Заметим, что по условию Фано ветки занятых кодов обрываются, и мы не имеем право использовать коды ниже для кодирования новых букв (создавать новые ответвления), так как это будет противоречить условию Фано.

3. Остается один незанятый код - 01, создавать от него новые ответвления нет смысла: во-первых, потому что это единственная незакодированная буква (иначе пришлось бы создавать новые ответвления, чтобы выполнялось условие Фано), во-вторых, по условию просят кратчайшее возможное кодовое слово: 01 -- кратчайший вариант из возможных, поэтому он и будет ответом на задачу.

Ответ: 01

Задания в классе (простые):

Задание 1. Ваня кодирует символы в алфавите. Все коды должны удовлетворять условию однозначного декодирования (ни одно слово не может быть началом другого слова). В алфавите представлены следующие символы: A, B, C, D. Кодовые слова A, B, C равны 00, 010, 111, соответственно. Определите наименьшее (по длине и по значению) кодовое слово для буквы D.

Решение

1. По условию Фано буква D не может начинаться с “00” и кодироваться как “00”, так как “00” – это кодирование буквы “А”.

2. Также буква D не может кодироваться как “01” и “11”, так как код для буквы В начинается с “01”, код для С начинается с “11”.

3. Тогда для кодирования буквы D остаются варианты: “10”, “011”, “110” и последующие ветки, следующие за этими кодами.

4. По условию просят “наименьшее (по длине и по значению) кодовое слово”, следовательно, для кодирования буквы D возьмем код 10.

Ответ: 10

Задание 2. Ваня кодирует символы в алфавите. Все коды должны удовлетворять условию однозначного декодирования (ни одно слово не может быть началом другого слова). В алфавите представлены следующие символы: К, Л, М, Н. Кодовые слова К, Л, М равны 0, 10, 110, соответственно. Определите наименьшее (по длине и по значению) кодовое слово для буквы Н.

Решение

1. По условию Фано буква Н не может начинаться с “0” и кодироваться как “0”, так как “0” – это кодирование буквы “К”.

 2. Также буква Н не может кодироваться как “10” и “11”, так как код для буквы Л – “10”, код для М начинается с “11”.

3. Тогда для кодирования буквы Н остаются варианты: “111” и последующие ветки, следующие за этим кодом.

 4. По условию просят “наименьшее (по длине и по значению) кодовое слово”, следовательно, для кодирования буквы Н возьмем код 111.

Ответ: 111

Задание 3. Ваня кодирует символы в алфавите. Все коды должны удовлетворять условию однозначного декодирования (ни одно слово не может быть началом другого слова). В алфавите представлены следующие символы: А, Б, В, Г, Д, Е, Ё, Ж, З, И. Некоторые кодовые слова известны и представлены в таблице:

Определите наименьшее (по длине и по значению) кодовое слово для буквы Ж.

Решение

1. Заметим, что код для буквы “Ж” не может начинаться с нуля, так как все коды, начинающиеся с нуля уже заняты, следовательно, рассматриваем только коды, начинающиеся с единицы.

2. Таким образом, построив дерево Фано для кодов, начинающихся с единицы, получим, что для буквы “Ж” остались коды: “1001”, “100010” и последующие ветки, следующие за этими кодами.

3. По условию просят “наименьшее (по длине и по значению) кодовое слово”, следовательно, для кодирования буквы Ж возьмем код 1001.

Ответ: 1001

Задания в классе (сложнее):

Задание 1.

Игорь кодирует символы в алфавите. Все коды должны удовлетворять условию однозначного декодирования (ни одно слово не может быть началом другого слова). В алфавите представлены следующие символы: А, Б, В, Г. Для буквы А используется код 1, для буквы Б – 000. Определите минимальную сумму длин всех кодов для букв, находящихся в алфавите.

Решение

1. Обозначим длины уже существующих кодов: для буквы А длина кода равна 1, для буквы Б – 3.

2. Построим дерево Фано и определим коды для оставшихся букв: они не могут начинаться с “1”, так как буква “А” кодируется как “1”

3. Тогда для кодирования букв В и Г остаются варианты: “01”, “001” и последующие ветки, следующие за этими кодами.

4. Так как по условию просят “минимальную сумму длин всех кодов для букв, находящихся в алфавите”, логично будет взять для буквы В код “001” (длина 3), для буквы Г код “01” (длина 2) – это обеспечит минимальность суммы длин всех кодов. Таким образом, сумма равна 1 + 3 + 3 + 2 = 9.

Ответ: 9

Задание2. Игорь кодирует символы в алфавите. Все коды должны удовлетворять условию однозначного декодирования (ни одно слово не может быть началом другого слова). В алфавите представлены следующие символы: C, К, О, Р. Для буквы С код равен 10, для буквы К – 001. Определите наименьшую возможную сумму длин букв О и Р.

Решение

Сначала определим оставшиеся кодовые слова. С – 10 (длина 2) – по условию. К – 001 (длина 3) – по условию. О – 01 или 11 (длина 2) Р – 01 или 11 (длина 2) Получается, что сумма кодов О и Р равна 2 + 2 = 4.

Ответ: 4

Задание3. Игорь кодирует символы в алфавите. Все коды должны удовлетворять условию однозначного декодирования (ни одно слово не может быть началом другого слова). В алфавите представлены следующие символы: A, B, C, D, E. Для буквы A код равен 10, для буквы B – 11. Определите наименьшую возможную сумму длин всех кодов букв.

Решение

Сначала определим оставшиеся кодовые слова. A – 10 (длина 2) – по условию. B – 11 (длина 2) – по условию. C – вариант 1: 00 или 011 или 010 (длина 2 или 3), вариант 2: 000 или 001 или 01 (длина 2 или 3). D – вариант 1: 00 или 011 или 010 (длина 2 или 3), вариант 2: 000 или 001 или 01 (длина 2 или 3). E – вариант 1: 00 или 011 или 010 (длина 2 или 3), вариант 2: 000 или 001 или 01 (длина 2 или 3). Соответсвенно, если выбрать для С кодовое слово 00 из первого варианта, тогда D и Е будут кодироваться словами длины 3. В данных вариантах длина будет всегда одинакова. Получаем: 2 + 2 + 2 + 3 + 3 = 12.

Ответ : 12