Решение задач на нахождение количества информации

Решение задач на нахождение количества информации

Цепи: закрепить навыки решения задач на нахождение количества информации; наработать навыки решения задач открытого типа.

Ход урока

I. Организационный момент

II. Актуализация знаний

-           С помощью какой формулы можно найти количество информации в различных сообщениях

•          Чем отличается алфавитный и содержательный подходы нахождения количества информации?

•          Какие параметры должны быть заданы в задаче при измерении информации с использованием содержательного подхода?

•          Какие параметры должны быть заданы при измерении информации с использованием алфавитного подхода?

III. Ход  урока

Рассмотрим задачу следующего типа.

•                     По дороге ехала легковая машина. Необходимо определить количество информации, которое получает наблюдатель, стоящий у пешеходного перехода.

•          Заданы ли необходимые параметры для решения задачи?

Нет. Оказывается, существуют задачи, где нет необходимых начальных (исходных) данных, которые позволили бы нам решить данную задачу. С такими задачами и приходится сталкиваться нам в жизни. И чтобы решить ее, необходимо самим задать нужные данные в зависимости от того, какой результат мы желаем получить. Такие задачи принято называть задачами открытого типа.

Для решения подобных задач мы должны сделать следующие допущения. Во-первых, определимся, каким способом мы будем решать заданную задачу. Во-вторых, какие исходные данные нам необходимы.

Пусть задача будет решена с помощью содержательного подхода. Тогда необходимо определиться, какое количество событий  может произойти. Если пешеход интересуется наличием транспорта на дороге для перехода улицы, тогда возможны два события: дорога свободна или нет. То есть N = 2, тогда I = 1 бит. Если любознательный пешеход интересуется, какой вид транспорта движется по дороге, например легковой, либо грузовой, либо мотоцикл, либо велосипед. Тогда N = 4 и соответственно I = 2 бит.

Решим данную задачу с использованием алфавитного подхода. Тогда в качестве допущения мы рассматриваем фразу «По дороге ехала легковая машина» как текст с использованием русского алфавита. Допускаем, что мощность алфавита N = 32, тогда I = 5 бит. Количество символов в фразе К = 31. Подставляем значения в формулу и получим:

I*K= 5 бит х 31 = 155 бит.

Рассмотренные задачи относятся к неформализованным или, другими словами, нешаблонным задачам. Типология нешаблонных задач определяется характером связей между подзадачами. Что это значит? Решение задач представляет собой процесс построения ассоциативных рядов. Последняя ассоциация ряда и решает задачу (отказ от решения тоже можно считать решением). Возможны две разновидности ассоциативных связей. Мы будем пользоваться словами: явная связь и латентная связь (latent - скрытый, неявный, невидимый).

Шаблонные задачи не имеют латентных связей, все связи имеют явный характер. Нешаблонные могут иметь одну или две латентные связи. При подборе в качестве задач репродуктивного уровня использовались простые задачи, которые сводятся к типовым задачам, позволяющим приобретать навыки использования этих средств. Задачи конструктивного типа сочетают типовые решения с определенной степенью творчества (типовые задачи в измененных ситуациях). И творческие задачи включают в себя неформализованные задачи (имеющие формулировки, близкие к реальным условиям жизни).

Человек от компьютера отличается тем, что обладает способностью усвоения новой интеллектуальной деятельности на базе имеющихся знаний. Ни один школьный предмет не формирует навыков решения «открытых» задач, то есть метапроцедурных, способных проецировать оптимальные методы решения на любые жизненные ситуации. Для этого необходимо развивать  дивергентное мышление. По определению Дж. Гилфорда, «дивергентное мышление - это мышление, идущее одновременно в разных направлениях, отступающее от логики». И, по словам М. Эриксона, *Именно дивергентное мышление способствует развитию творческих способностей в отличие от конвергентного мышления, которое овладевает людьми с возрастом, «делая их поведение более стереотипными».

Использование задач открытого типа позволяет развивать творческий потенциал. Решение подобных задач не столь очевидно и вызывает определенные сложности, так как  отсутствуют готовые (заданные) исходные данные.

При рассмотрении текста  часто возникает вопрос, необходимо ли подсчитывать пробел?

Для чего используется пробел? Для придания смысла всей фразе: нет пробела, нет смысла в наборе символов. Поэтому ответ на риторический вопрос не должен ограничиваться словом «да». И при использовании алфавитного подхода мы имеем дело с осмысленными фразами, когда даже при использовании технических средств для передачи информации не должен исчезнуть смысл передаваемого сообщения.

IV. Закрепление изученного материала

•                     Человек бежит по улице. Какое количество информации получит прохожий, который идет по той же улице?

(Вариантов рассуждения может быть много. Может быть ситуация, когда оценивается вариант: человек идет шагом и человек бежит. Другой вариант: прохожему неинтересно, что кто- то бежит с ним рядом, тогда информация будет равна 0. Если человек бежит к автобусу, можно рассмотреть ситуацию: успеет или не успеет на автобус и т. д. В первом и третьем случаях количество событий равняется 2, соответственно информация равна 1 бит.)

•                     Вы пришли к другу в понедельник утром. Его нет дома. Какое количество информации вы получили?

(1-й вариант: вы ожидали, что друг вас может не дождаться. Количество информации равно 0. 2-й вариант: вероятность присутствия и отсутствия была одинакова, то есть количество возможных событий равна 2, соответственно количество информации равно 1 бит.)

·                    К вам ночью прибежала соседка вызвать по вашему телефону скорую помощь, а у вас не работает телефон. Какое количество информации получила соседка?

(1-й вариант: телефон работает и телефон не работает можно рассматривать как равновероятные события. Тогда количество информации равно 1 бит. 2-й вариант: исправность телефонных аппаратов событие не равновероятное, поэтому мы не можем использовать формулу для равновероятных событий.)

•                     Мальчик Петя принес в школу яблоко. Сколько бит информации может быть получено одноклассником на предложение: «Угости».

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

•                     Путник услышал, как в лесу раздался голос кукушки. Сколько бит информации он получит на свой вопрос: «Кукушка, кукушка, сколько мне жить?»

•                     В велокроссе участвуют 119 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объем сообщения, записанного устройством, после того как промежуточный финиш прошли 70 велосипедистов?   

1) 70 бит            2)  70 байт          3)  490 бит          4) 119 байт

Решение:

1)         велосипедистов было 119, у них 119 разных номеров, то есть, нам нужно закодировать 119 вариантов

2)         по таблице степеней двойки находим, что для этого нужно минимум 7 бит (при этом можно закодировать 128 вариантов, то есть, еще есть запас); итак, 7 бит на один отсчет

3)         когда 70 велосипедистов прошли промежуточный финиш, в память устройства записано 70 отсчетов

4)         поэтому в сообщении 70*7 = 490 бит информации  (ответ 3).

•                     Объем сообщения, содержащего 4096 символов, равен 1/512 части Мбайта. Какова мощность алфавита, с помощью которого записано это сообщение?

1) 8      2) 16    3) 4096           4) 16384

Большие числа. Что делать?

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

128 = 2⁷,         256 = 2⁸,         512 = 2⁹ ,        1024 = 2¹⁰,

2048 = 2¹¹,     4096 = 2¹² ,     8192 = 2¹³,     16384 = 2¹⁴,    65536 = 2¹⁶     и т.п.

Нужно помнить, что соотношение между единицами измерения количества информации также представляют собой степени двойки:

     1 байт = 8 бит = 2³ бит,

   1 Кбайт = 1024 байта = 2¹⁰ байта  = 2¹⁰ • 2³ бит = 2¹³ бит,

   1 Мбайт  = 1024 Кбайта = 2¹⁰ Кбайта = 2¹⁰ • 2¹⁰ байта = 2²⁰ байта = 2²⁰ • 2³ бит = 2²³ бит.

•                     В зоопарке 32 обезьяны живут в двух вольерах, А и Б. Одна из обезьян – альбинос (вся белая). Сообщение «Обезьяна-альбинос живет в вольере А» содержит 4 бита информации. Сколько обезьян живут в вольере Б?

1) 4      2) 16    3) 28    4) 30

Решение:

1)         информация в 4 бита соответствует выбору одного из 16 вариантов, …

2)         … поэтому в вольере А живет 1/16 часть всех обезьян (это самый важный момент!)

3)         всего обезьян – 32, поэтому в вольере А живет  32/16 = 2 обезьяны

4)         поэтому в вольере Б живут все оставшиеся 32 – 2 = 30 обезьян

5)         правильный ответ – 4.

•                В некоторой стране автомобильный номер длиной 7 символов составляется из заглавных букв (всего используется 26 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 20 автомобильных номеров.

1) 20 байт         2) 105 байт     3) 120 байт     4) 140 байт

Решение:

1)         всего используется 26 букв + 10 цифр = 36 символов

2)         для кодирования 36 вариантов необходимо использовать 6 бит, так как   пяти бит не хватит (они позволяют кодировать только 32 варианта), а шести уже достаточно

3)         таким образом, на каждый символ нужно 6 бит (минимально возможное количество бит)

4)         полный номер содержит 7 символов, каждый по 6 бит, поэтому на номер требуется  бита

5)         по условию каждый номер кодируется целым числом байт (в каждом байте – 8 бит), поэтому требуется 6 байт на номер ( ), пяти байтов не хватает, а шесть – минимально возможное количество

6)         на 20 номеров нужно выделить  байт

7)         правильный ответ – 3.

•                Каждая ячейка памяти компьютера, работающего в троичной системе счисления, может принимать три различных значения (-1, 0, 1). Для хранения некоторой величины отвели 4 ячейки памяти. Сколько различных значений может принимать эта величина?

Решение:

1)         непривычность этой задачи состоит в том, что используется троичная система

2)         фактически мы имеем дело с языком, алфавит которого содержит M=3 различных символа

3)         поэтому количество всех возможных «слов» длиной N  равно Q=3^N

4)         для  N=4  получаем  Q=3⁴ 

5)         таким образом, правильный ответ – 81.

•                     В школьной базе данных хранятся записи, содержащие информацию об учениках:

<Фамилия> – 16 символов: русские буквы (первая прописная, остальные строчные),

<Имя> – 12 символов: русские буквы (первая прописная, остальные строчные),

<Отчество> – 16 символов: русские буквы (первая прописная, остальные строчные),

<Год рождения> – числа от 1992 до 2003.

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

1) 28    2) 29    3) 46    4) 56

Решение:

1)         очевидно, что нужно определить минимально возможные размеры в битах для каждого из четырех полей и сложить их;

2)         важно! известно, что первые буквы имени, отчества и фамилии – всегда заглавные, поэтому можно хранить их в виде строчных и делать заглавными только при выводе на экран (но нас это уже не волнует)

3)         таким образом, для символьных полей достаточно использовать алфавит из 32 символов (русские строчные буквы, «е» и «ё» совпадают, пробелы не нужны)

4)         для кодирования каждого символа 32-символьного алфавита нужно 5 бит (32 = 25), поэтому для хранения имени, отчества и фамилии нужно (16 + 12 + 16)•5=220 бит 

5)         для года рождения есть 12 вариантов, поэтому для него нужно отвести 4 бита

(24 = 16 ≥ 12)

6)         таким образом, всего требуется 224 бита или 28 байт 7)            правильный ответ – 1.

V. Задачи для  самостоятельной работы

1. Сколько битов информации содержится в 16 байтах?

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

3. Определить информативность сообщения «А + В = С», если для описания математических формул необходимо воспользоваться 64-символьным алфавитом.

4. Сколько битов информации содержится в 32 байтах?

5. Для приготовления салата необходимо воспользоваться 8 ингредиентами. Повар решил сэкономить продукты и воспользовался только 4. Сколько бит информации содержится в сообщении, что салат состоит из 4 составляющих?

6. Для представления числовых данных используют 16-ричный алфавит, включающий знаки математических действий. Сколько битов информации содержит выражение 64 * 5 = 320?

Решение:

1. 16 байт х 8 = 128 бит.

2. N = 16, 2^I = 16, отсюда I = 4 бит. Использование одного цвета в сообщении несет в себе 4 бит. Но художник использовал 2 цвета, тогда I₂ = 4 * 2 = 8 бит.

3. Дано: N = 64; К = 5. Найти: I_k - ?

2^I = 64; I = 6 бит. Тогда I_k = 5 х 6 = 30 бит.

4. 32 байт х 8 = 256 бит.

5. N = 8, 2^I = 8, отсюда I = 3 бит. Использование одного ингредиента в сообщении несет в себе 3 бит. Всего использовано 4 ингредиента, тогда I_k= 4 х 3 = 12 бит.

6. Дано: N = 16; К = 8. Найти: I_k-?

2^I = 16; I = 4 бит. Тогда I_k= 4 х 8 = 32 бит.

Домашнее задание: подготовиться к самостоятельной работе.