Примеры и задачи из архива ЕГЭ по теме " Алфавитный и вероятностный подходы "

Примеры и задачи из архива ЕГЭ по теме " Алфавитный и вероятностный подходы "

Документация +5
docx
информатика +1
7 кл—11 кл
08.02.2020
Рассмотрены темы школьного курса информатики, которые из-за повышенного внимания к программированию и алгоритмизации, преобладающего в экзаменационных вопросах, отходят на второй план: Алфавитный и вероятностный подходы.

150.000₽ призовой фонд • 11 почетных документов • Свидетельство публикации в СМИ

Опубликовать материал

Примеры и задачи из архива ЕГЭ алфавитный.docx

Примеры и задачи из архива ЕГЭ

ПРИМЕР 2.1

Сколько бит информации (I) нужно получить, чтобы отгадать загаданное число из 32 случайно расположенных чисел натурального ряда?

Решение

Для решения используем формулу (2.1): 2 log 32=I . Для наглядности представим эту формулу в следующем виде: 2 32 = I . Ответ: I = 5 бит.

 

ПРИМЕР 2.2

В составе поезда N = 16 вагонов. Среди них есть вагоны купейные и плацкартные. Сообщение о том, что ваш знакомый приезжает в купейном вагоне, несет I = 2 бита информации. Определить, сколько в поезде купейных вагонов?

Решение

Обозначим k — искомое число купейных вагонов. Вероятность того, что знакомый приезжает в купейном вагоне, равна р = k/N = k/16. Для решения используем формулу (2.2): 2log (1/ ) = Ip. Для нашего примера имеем: 2log (16 / ) = Ik . Величина I по условию задачи равна 2. Подставим значения: 22 16 / = k , откуда получаем k = 16/4 = 4, т. е. в поезде 4 купейных вагона.

Ответ: 4 вагона.

 

ПРИМЕР 2.3

Решим задачу, обратную задаче из примера 2.2. Будем вычислять количество информации (I) в зависимости от количества в поезде купейных вагонов (k).

Решение

Заполним табл. 2.2 функции 2 log= IN при N = 16 и k = 1, 2, 4, 8, 16. Рассматривая результаты решения, сделаем выводы. Чем меньше купейных вагонов в поезде, тем больше информации несет сообщение о том, что ваш знакомый приезжает в купейном вагоне. И чем больше купейных вагонов в поезде, тем меньше получаем количество информации. Когда все вагоны поезда купейные, количество получаемой информации равно нулю. Действительно, с учетом, что N = k и 021 = , имеем 22 log ( / ) log 1 0 = = = I N k .

Ответ: см. табл. 2.2.

 

ПРИМЕР 2.4

В мешке находятся 16 фруктов: 8 яблок, 4 груши, 2 лимона и 2 ананаса. Какое количество информации содержится в сообщениях о том, что из мешка случайным образом были последовательно взяты с возвратом яблоко ( 1 I ), груша ( 2 I ), лимон ( 3 I ) и ананас ( 4 I ).

Решение

Воспользуемся формулой (2.2) 2log (1/ ) = Ip. Определим вероятности утверждения "взять из мешка один фрукт": яблоко — 1 8/16 1/ 2 ==p , грушу — 24 /16 1/ 4 ==p , лимон — 3 2 /16 1/ 8 ==p , ананас — 4 2 /16 1/ 8 ==p . После подстановки в формулу получаем: 1 1 =I бит, 2 2 =I бита, 34 3 == II бита.

Ответ: 1 1 =I бит, 2 2 =I бита, 34 3 == II бита.

 

ПРИМЕР 2.5

 Документация некоторого учреждения размещена в 4-х комнатах. В каждой комнате находится 16 шкафов. Каждый шкаф имеет 8 полок. Определите количество информации, которое несет сообщение о том, что нужный документ находится в третьей комнате, в тринадцатом шкафу на пятой полке.

Решение

 Решим задачу двумя способами. Во втором случае будем использовать свойство аддитивности информации. Первый способ решения. Задача состоит в определении длины двоичного слова, однозначно кодирующего все количество полок с документами. Всего полок: S = 4×16×8 = 512. Длина двоичного кода (количество информации) равна

2 log 512 9 ==I бит. Столько бит информации содержит сообщение о месте нахождения нужного документа. Второй способ решения. Используем показанное выше свойство логарифмов (2.3). Раздельно определяем количество информации, полученной в сообщении о номере комнаты, номере шкафа в этой комнате и номере полки в этом шкафу. Вычисленные значения суммируем и получаем искомый результат:

2 2 2 log 4 log 16 log 8 2 4 3 9 = + + = + + =I бит.

В обоих случаях получен одинаковый ответ.

 

ПРИМЕР 2.6 

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

Решение

 Вероятность каждого из трех исходов равна 1/3. Для решения используем формулу Хартли в следующей записи: 2log (1/ 3) =−I . 

При вычислении количества информации используем формулу (2.6): 1ln3.ln 2 =−I (2.6)

Будем действовать так. Сначала получим значение натурального логарифма числа <2> (кнопка <ln>) и запишем его в память (кнопка <MS>). Затем вы- числим частное от деления <1> на <3> (кнопка </>) и получим значение натурального логарифма полученного частного (снова кнопка <ln>). Результат получим после деления логарифма частного (числителя формулы) на число из памяти — знаменатель формулы (кнопка <MR>). В результате получили ответ: I = 1,585 бит. По такой схеме можно легко и быстро вычислять точные значения количества информации.

Ответ: I = 1,585 бит.

 

ПРИМЕР 2.7

При отгадывании одного задуманного числа из восьми случайно расположенных чисел натурального ряда воспользуемся той же методикой, что и в примере 1.1, но делить числа будем на две неравные части. В процессе отгадывания задаются вопросы, например: "В первой части находится задуманное число?" На эти вопросы получаем ответы "Да" или "Нет", которые снимают неопределенность и несут соответствующее количество информации. Разделим все восемь чисел на две группы — 5 чисел и 3 числа. Вероятности нахождения задуманного числа в группах различны. Чем больше чисел в группе, тем больше эта вероятность. Для первой группы она равна 1 5/8 =p . Для второй — 2 3/8 =p . Можно ожидать, что и количество информации, содержащейся в ответе на вопрос "В какой группе находится загаданное число?", будет различным для первой и второй групп. Можно также предположить, что чем меньше вероятность нахождения числа в группе, тем большее количество информации содержится в сообщении, что число находится в этой группе. Определим количество информации. Вычисления можно выполнять с помощью калькулятора или воспользоваться табл. 2.3. Сообщение о нахождении числа в первой группе содержит 12 log 5/ 8 0,678 = − =I бита. Сообщение о нахождении числа во второй группе содержит 22 log 3/ 8 1,415 = − =I бита. Предположения подтвердились. Пусть получен первый ответ — число находится во второй группе. В этой группе три числа (рис. 2.1). Разделим ее на две группы — два числа и одно число. Вычислим количество информации, содержащейся в ожидаемых сообщениях  о нахождении числа в группах: 32 log 2 / 3 0,585 = − =I бита и  42 log 1/ 3 1,585 = − =I бита. Если на второй вопрос получен ответ о нахождении числа во второй группе (в ней одно число), то число отгадано за две попытки. Для определения общего количества информации, которое было получено при отгадывании числа, используем свойство аддитивности информации (2.3): 241,415 1,585 3 = + = + = I I I = 3 бита.

 Если же на второй вопрос получен ответ о нахождении числа в первой группе (см. рис. 2.1, в ней два числа), то требуется задавать еще один вопрос и получать ответ, который будет содержать 52 log 1/ 2 1 = − =I бит информации. Третий вопрос приводит к отгадке числа. Снова, используя свойство аддитивности, получаем:

2 3 5 2 2 2 log (3/ 8) log (2 / 3) log (1/ 2) 1,415 0,585 1 3 = + + = + + = + + = I I I I бита. Это объясняется тем, что события, состоящие в отгадывании с первой попытки любого из восьми чисел, имеют одинаковую вероятность, равную 1/8.

 

ПРИМЕР 2.8

В колоде 36 карт. Из них 12 карт с "портретами" валетов, дам и королей. Какое количество информации содержит сообщение о том, что из колоды была взята  с возвратом карта с портретом ( 1 I ), туз ( 2 I ), любая карта от шестерки до десятки ( 3 I ), туз пик ( 4 I )?

Решение Все четыре события имеют разную вероятность выполнения. Эти вероятности соответственно равны: 1 12 / 36 1/ 3 ==p , 2 4 / 36 1/ 9 ==p , 3 20 / 36 5/ 9 ==p , 4 1/36 =p . Для вычисления количеств информации используем формулу

22 log (1/ ) log . = = − I p p

 Вычисления дают следующие результаты:

12 log 12 / 36 1,585 = − =I , 22 log 4 / 36 3,17 = − =I ,

32 log 20 / 36 0,848 = − =I , 42 log 1/ 36 5,17 = − =I .

Последний результат показывает, что для кодирования всех 36 карт требуется 5,17 бита или шестибитовое двоичное слово ( 52 32 = — мало, т. к. 32 < 36,

6 2 64 = , 64 > 36 — достаточно).

Ответ:

 1 1,585 =I бита, 2 3,17 =I бита, 3 0,848 =I бита, 4 5,17 =I бита.

 

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

ПРИМЕР 2.17 (из архива ЕГЭ)

Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для других — из трех). Эти коды представлены в таблице:

a b c d e

000 110 01 001 10

Определите, какой набор букв закодирован двоичной строкой 1100000100110:

1) baade; 2) badde; 3) bacde; 4) bacdb.

Решение

В задаче задано кодирование символов префиксным кодом (по алгоритму Хаффмана). Заданная двоичная строка расшифровывается однозначно. Приступать к декодированию следует с начала строки, сравнивая заданные двоичные коды букв со значениями битов двоичной строки.

110 • 000 • 01 • 001 • 10 — bacde

Ответ: 3) bacde.

 

ЗАДАНИЕ 2.2 (из архива ЕГЭ)

Для 5 букв русского алфавита заданы их двоичные коды (для некоторых букв —из двух бит, для некоторых — из трех). Эти коды представлены в таблице:

В К А Р Д

000 11 01 001 10

Из четырех полученных сообщений в этой кодировке только одно прошло без

ошибки и может быть корректно декодировано. Найдите его:

1) 110100000100110011;

2) 111010000010010011;

3) 110100001001100111;

4) 110110000100110010.

 

ЗАДАНИЕ 2.3 (из архива ЕГЭ)

Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых букв — из двух бит, для других — из трех). Эти коды представлены в таблице:

a b c d e

000 01 100 10 011

Определите, какой набор букв закодирован двоичной строкой 0110100011000:

1) ebcea; 2) bddea; 3) bdcea; 4) ebaea.

Найдите решение.

 

ЗАДАНИЕ 2.4 (из архива ЕГЭ)

В ящике находятся 32 теннисных мяча, среди которых есть мяч желтого цвета.

Наудачу вынимается один мяч. Сообщение "извлечен мяч НЕ желтого цвета"

несет 4 бита информации. Сколько в ящике мячей желтого цвета?


 

скачать по прямой ссылке
Друзья! Добро пожаловать на обновленный сайт «Знанио»!

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

Что-то не получается или не работает? Мы всегда на связи ;)