Самостоятельная работа

по теме «Условие Фано и кодирование информации»

для учащихся 10-11 классов,

планирующих сдавать ЕГЭ по информатике

Вариант 1

№ 1

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

№ 2

По каналу связи передаются сообщения, содержащие только пять букв: Ш, К, О, Л, А. Для передачи используется двоичный код, удовлетворяющий условию Фано. Для буквы О используется кодовое слово 0; для буквы А используется кодовое слово 10. Какова минимальная общая длина кодовых слов для всех пяти букв?

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

 № 3

Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: 

1. ААААА

2. ААААО

3. ААААУ

4. АААОА                                         Запишите слово, которое стоит на 210-м месте от начала списка.

№ 4

Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка:

      1. ААААА

2. ААААО

3. ААААУ

4. АААОА                                            Укажите номер первого слова, которое начинается с буквы У.

№ 5

Сколько слов длины 5, начинающихся с гласной буквы, можно составить из букв Е, Г, Э? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.

Вариант 2

№ 1

По каналу связи передаются сообщения, содержащие только четыре буквы: Р, Е, К, А; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв А, Р, Е используются такие кодовые слова: А: 111, Р: 0, Е: 100.  Укажите кратчайшее кодовое слово для буквы К. Если таких кодов несколько, укажите код с наименьшим числовым значением.  Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

№ 2

По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано; для букв A, Б, В используются такие кодовые слова: А — 1, Б – 010, В – 001.  Какова наименьшая возможная суммарная длина всех кодовых слов? Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.

№ 3

Все 5-буквенные слова, составленные из букв Л, Н, Р, Т, записаны в алфавитном порядке. Вот начало списка: 

1. ЛЛЛЛЛ

2. ЛЛЛЛН

3. ЛЛЛЛР

4. ЛЛЛЛТ

5. ЛЛЛНЛ               Запишите слово, которое стоит на 150-м месте от начала списка.

№ 4

Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: 

1. ААААА

2. ААААО

3. ААААУ

4. АААОА             Укажите номер первого слова, которое начинается с буквы О.

№ 5

Сколько слов длины 6, начинающихся с согласной буквы, можно составить из букв Г, О, Д? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.

Вариант 3

№ 1

По каналу связи передаются сообщения, содержащие только четыре буквы: П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: 0, П: 100.   Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

№ 2

По каналу связи передаются сообщения, содержащие только шесть букв: А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А – 00, B – 010, C – 1. Какова наименьшая возможная суммарная длина всех кодовых слов?  Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.

№ 3

Все 4-буквенные слова, составленные из букв Н, Р, Т, У, записаны в алфавитном порядке. Вот начало списка: 

1. НННН

2. НННР

3. НННТ

4. НННУ

5. ННРН                          Запишите слово, которое стоит на 215-м месте от начала списка.

№ 4

Все 5-буквенные слова, составленные из букв А, К, Р, У, записаны в алфавитном порядке. Вот начало списка: 

1. ААААА

2. ААААК

3. ААААР

4. ААААУ

5. АААКА                                  Укажите номер первого слова, которое начинается с буквы К.

№ 5

Сколько слов длины 5, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв З, И, М, А? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.

Вариант 4

№ 1

По каналу связи передаются сообщения, содержащие только пять букв: A, B, С, D, E. Для передачи используется двоичный код, допускающий однозначное декодирование. Для букв A, B, C используются такие кодовые слова:         A – 1, B – 010, C – 000.

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

№ 2

По каналу связи передаются сообщения, содержащие только шесть букв: А, B, C, D, E, F. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв A, B, C используются такие кодовые слова: А – 00, B – 010, C – 1. Какова наименьшая возможная суммарная длина всех кодовых слов?  Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.

№ 3

Все 5-буквенные слова, составленные из букв А, Н, П, записаны в алфавитном порядке.

Вот начало списка:

1. ААААА

2. ААААН

3. ААААП

4. АААНА

5. АААНН                     Запишите слово, которое стоит на 201-м месте от начала списка.

№ 4

Все 5-буквенные слова, составленные из букв А, О, У, записаны в алфавитном порядке. Вот начало списка: 

1. ААААА

2. ААААО

3. ААААУ

4. АААОА                            Укажите номер слова УАУАУ.

№ 5

Вася составляет 5-буквенные слова, в которых есть только буквы С, Л, О, Н, причём буква С используется в каждом слове ровно 1 раз. Каждая из других допустимых букв может встречаться в слове любое количество раз или не встречаться совсем. Словом считается любая допустимая последовательность букв, не обязательно осмысленная. Сколько существует таких слов, которые может написать Вася?

Ответы

Примечание

При составлении вариантов использовались задания с сайта Константина Полякова http://kpolyakov.spb.ru/school/ege.htm

Скачано с www.znanio.ru