Содержательный подход к измерению информации отталкивается от определения информации как содержания сообщения, получаемого человеком. Сущность содержательного подхода заключается в следующем: сообщение, информирующее об исходе какого-то события, снимает неопределенность знания человека об этом событии.
Чем больше первоначальная неопределенность знания, тем больше информации несет сообщение, снимающее эту неопределенность.
Ситуация 1. В ваш класс назначен новый учитель информатики; на вопрос «Это мужчина или женщина?» вам ответили: «Мужчина».
Ситуация 2. На чемпионате страны по футболу играли команды «Динамо» и «Зенит». Из спортивных новостей по радио вы узнаете, что игра закончилась победой «Зенита».
Ситуация 3. На выборах мэра города было представлено четыре кандидата. После подведения итогов голосования вы узнали, что избран Н. Н. Никитин.
Вопрос: в какой из трех ситуаций полученное сообщение несет больше информации?
Неопределенность знания — это количество возможных вариантов ответа на интересовавший вас вопрос. Еще можно сказать: возможных исходов события. Здесь событие — например, выборы мэра; исход — выбор, например, Н. Н. Никитина.
В первой ситуации 2 варианта ответа: мужчина, женщина; во второй ситуации 3 варианта: выиграл «Зенит», ничья, выиграло «Динамо»; в третьей ситуации — 4 варианта: 4 кандидата на пост мэра.
Согласно данному выше определению, наибольшее количество информации несет сообщение в третьей ситуации, поскольку неопределенность знания об исходе события в этом случае была наибольшей.
В 40-х годах XX века проблема измерения информации была решена американским ученым Клодом Шенноном — основателем теории информации. Согласно Шеннону, информация — это снятая неопределенность знания человека об исходе какого-то события.
В теории информации единица измерения информации определяется следующим образом.
Сообщение, уменьшающее неопределенность знания об исходе некоторого события в два раза, несет 1 бит информации.
Согласно этому определению, сообщение в первой из описанных ситуаций несет 1 бит информации, поскольку из двух возможных вариантов ответа был выбран один.
Следовательно, количество информации, полученное во второй и в третьей ситуациях, больше, чем один бит. Но как измерить это количество?
Рассмотрим еще один пример.
Ученик написал контрольную по информатике и спрашивает учителя о полученной оценке. Оценка может оказаться любой: от 2 до 5. На что учитель отвечает: «Угадай оценку за два вопроса, ответом на которые может быть только «да» или «нет»». Подумав, ученик задал первый вопрос: «Оценка выше тройки?». «Да», — ответил учитель. Второй вопрос: «Это пятерка?». «Нет», — ответил учитель. Ученик понял, что он получил четверку. Какая бы ни была оценка, таким способом она будет угадана!
Первоначально неопределенность знания (количество возможных оценок) была равна четырем. С ответом на каждый вопрос неопределенность знания уменьшалась в 2 раза и, следовательно, согласно данному выше определению, передавался 1 бит информации.
Узнав оценку (одну из четырех возможных), ученик получил 2 бита информации.
Рассмотрим еще один частный пример, а затем выведем общее правило.
Вы едете на электропоезде, в котором 8 вагонов, а на вокзале вас встречает товарищ. Товарищ позвонил вам по мобильному телефону и спросил, в каком вагоне вы едете. Вы предлагаете угадать номер вагона, задав наименьшее количество вопросов, ответами на которые могут быть только слова «да» или «нет».
Немного подумав, товарищ стал спрашивать:
Схематически поиск номера вагона выглядит так:
Каждый ответ уменьшал неопределенность знания в два раза. Всего было задано три вопроса. Значит, в сумме набрано 3 бита информации. То есть сообщение о том, что вы едете в пятом вагоне, несет 3 бита информации.
Способ решения проблемы, примененный в примерах с оценками и вагонами, называется методом половинного деления: ответ на каждый вопрос уменьшает неопределенность знания, имеющуюся перед ответом на этот вопрос, наполовину. Каждый такой ответ несет 1 бит информации.
Заметим, что решение подобных проблем методом половинного деления наиболее рационально. Таким способом всегда можно угадать, например, любой из восьми вариантов за 3 вопроса. Если бы поиск производился последовательным перебором: «Ты едешь в первом вагоне?» «Нет», «Во втором вагоне?» «Нет» и т. д., то про пятый вагон вы смогли бы узнать после пяти вопросов, а про восьмой — после восьми.
Тема:Неопределенность знания и количество информации
образовательная: сформировать представлений об информации, как мере уменьшения неопределенности знания, формировать практические навыки по определению количества информации.
развивающая: развивать умения и навыки решения информационных задач, развить познавательный интерес, информационную культуру, расширять словарный запас по теме « Количество информации как мера уменьшения неопределенности знания »
воспитательная: формировать интерес к предмету, воспитывать настойчивость в преодолении трудностей в учебной работе, воспитать стремление к саморазвитию
Тип урока: изучение нового материала
Форма урока: синтетическая .
Место урока в учебной теме: первичный
Методы и методические приемы:
Материалы и оборудование: презентация, раздаточный материал, проектор, ноутбук
сведения об окружающем мире и протекающих в нем процессах, воспринимаемые человеком или специальными устройствами
Итак, мы с вами ведем речь об информации и способах измерения информации. Тема нашего урока: «Неопределенность знания и количество информации»
III. Изучение нового материала
Человек всегда стремиться к количественному измерению различных величин. Получая ту или иную информацию, мы понимаем, что не всегда ее бывает достаточно для того, чтобы решить какие-либо проблемы. И как оценить информационный объем книги или статьи?
Содержательный подход позволяет оценить количество информации с точки зрения уменьшения неопределенности наших знаний об объекте.
Рассмотрим, как можно измерить количество информации на примере подбрасывания монеты. Будем считать, то наша монета идеальная: не зависает в воздухе, не падает на ребро и не пропадает момент бросания. Сколько возможных положений может занять монета после подбрасывания?
Ответ учащихся: Два положения: «орел» или «решка».
Неопределенность знания о результате некоторого события — это число возможных результатов события.
Как происходит уменьшение неопределенности знаний
Рассмотрим пример. На книжном стеллаже 8 полок. Сколько информации содержит сообщение о том, где находится книга?
Рассмотрим более сложную задачу. В классе 8 учеников. Учитель хочет узнать, кто дежурный и для этого предлагает детям ответить на предложенные вопросы.
Дежурный сидит на последних двух партах?
Ответ учащихся: Нет.
Дежурный сидит на правом ряду?
Дежурный сидит на первой парте?
Ответ учащихся: Нет
Давайте посмотрим на полученную таблицу. Какова начальная неопределенность?
Какое общее количество информации мы получили?
Ответ учащихся: 3 бита.
Посмотрите на эти числа: 8, 2 и 3. Как они связаны между собой?
Ответ учащихся: 8 равно 2 в кубе.
Следующие соотношения единиц измерения количества информации следует запомнить:
Давайте теперь, используя формулу Хартли, рассчитаем количество информации в различных случаях. Использовать раздаточный материал.
Задача2. В рулетке общее количество лунок равно 128. Какое количество информации мы получим в зрительном сообщении об остановке шарика в одной из лунок.
Задача 3. При угадывании целого числа в диапазоне от 1 до N было получено 9 бит информации. Чему равно N?
Задача4. Загадано слово из 10 букв. Вы просите открыть пятую букву. Вам ее открыли. Сколько информации вы получили?
Эти задачи мы решали коллективно. А теперь я предлагаю вам самостоятельно решить следующую задачу.
В колоде 32 карты. Определите количество информации, содержащейся в сообщениях.
Проверка решения задачи
V. Проверка уровня усвоения материала. Самостоятельная работа.
Информатика. Случайность и неопределенность. Определение — что такое комбинаторика
Случайность и неопределенность
Комбинаторика — это раздел математики, изучающий сочетания, перестановки, размещения и перечисления элементов множества.
Что такое неопределенность?
Неопределенность — это недостаток или отсутствие информации о чем-либо.
Случайность — это категория для обозначения связей между такими явлениями реального мира, которые в одних условиях могут осуществиться, а в других — нет. Случайность события заключается в том, что реализация того или иного исхода имеет некоторую степень неопределенности.
Случайность проявляется практически во всех областях деятельности человека.
Событие — это явление, произошедшее в результате действий. События обычно обозначаются большими латинскими буквами: А, В, С и т. д.
Случайное событие — это событие, которое может как произойти, так и не произойти.
Суммой событий Ай В называется событие С, которое состоит в появлении события А или события В или обоих событий сразу:
Произведением событий А и В называется событие С, которое состоит в совместном появлении событий А и В (их совмещении):
Вероятность события — это мера объективной возможности появления события.
Событие А называется независимым от события В, если вероятность события А не зависит от того, наступило событие В или нет. Иначе событие А называется зависимым от события В.
Несовместными называются события, которые не могут наступить одновременно: наступление одного исключает появление другого.
Псевдослучайность — это категория, которой в информатике обозначается имитация случайных явлений.
Псевдослучайные числа — это числа, которые используются в программировании для имитации случайных чисел.
Генератор псевдослучайных чисел — это алгоритм, создающий последовательность чисел, элементы которой почти независимы друг от друга и подчиняются определённому распределению.
Генератор псевдослучайных последовательностей — это алгоритм построения последовательности псевдослучайных чисел, обусловленной неким внешним источником случайных значений (например, помехами). Зная i-e число в последовательности, по формулам можно определить её (г + 1)-й элемент.
Примеры. 1. Определить вероятность появления грани игрального кубика с числом 6.
В этом случае количество общих исходов равно 6, поскольку в игральном кубике 6 граней. Однако благоприятный исход только один, так как у кубика только одна грань с цифрой 6, поэтому
Пример 2. Сгенерировать список чисел от 1 до N, расположенный в случайном порядке.
Присваиваем элементам списка нулевые значения.
Помещаем элемент в последовательность.
Если позиция элемента содержит «О», можно помещать элемент.
Если позиция не «О», то генерируется случайный номер для элемента.
Присваиваем элементам списка нулевые значения.
Помещаем элемент в последовательность.
Если позиция элемента содержит «0», можно помещать элемент.
Если позиция не «0», то проверяем все последующие, пока не найдём «0».
Присваиваем элементам списка нулевые значения.
Помещаем элемент в последовательность.
Если позиция элемента содержит «0», можно помещать элемент.
Если позиция не «0», то генерируется случайный номер для элемента. Сгенерированное случайное число указывает, сколько пустых ячеек следует пропустить, прежде чем заносить в список новое число.
Генератор псевдослучайных последовательностей используется при написании криптографических алгоритмов и алгоритмов шифрования.
Содержательный подход к измерению информации отталкивается от определения информации как содержания сообщения, получаемого человеком. Сущность содержательного подхода заключается в следующем: сообщение, информирующее о каком-то событии, снимает неопределенность знаний человека об этом событии.
Чем больше первоначальная неопределенность знаний, тем больше информации несет сообщение, снимающее эту неопределенность.
Ситуация 1. В ваш класс назначен новый учитель информатики; на вопрос: «Это мужчина или женщина», вам ответили: «Мужчина».
Ситуация 2. На чемпионате страны по футболу играли команды Динамо и Зенит. Из спортивных новостей по радио вы узнаете, что игра закончилась победой Зенита.
Ситуация 3. На выборах мера города было четыре кандидата. После подведения итогов голосования вы узнали, что избран Никитин Н.Н.
Вопрос: в какой из трех ситуаций полученное сообщение несет больше информации?
Неопределенность знаний – это количество возможных вариантов ответа на интересовавший вас вопрос. В первой ситуации – 2 варианта: мужчина, женщина; во второй ситуации 3 варианта: выиграли, ничья, проиграли; в третьей ситуации – 4 варианта: 4 кандидата на пост мера.
Согласно данному выше определению, наибольшее количество информации несет сообщение в третьей ситуации, поскольку неопределенность знаний о результате события (выборов мера) в этом случае была наибольшей.
В 40-х годах ХХ века, проблема измерения информации была решена американским ученым Клодом Шенноном – основателем теории информации. Согласно К.Шеннону, информация – это снятая неопределенность в знаниях человека о результате какого-то события.
В теории информации единица измерения информации определяется следующим образом.
Сообщение, уменьшающее неопределенность знаний о результате некоторого события в два раза, несет 1 бит информации
Согласно этому определению, сообщение в первой из описанных ситуаций несет 1 бит информации, поскольку из двух возможных вариантов ответа был выбран один.
Следовательно, количество информации, полученное во второй и в третьей ситуациях, больше, чем один бит. Но как их измерить?
Рассмотрим другой пример выбора одного из четырех вариантов, более удобный для измерения количества информации.
Первоначально неопределенность знаний (число вариантов полученной оценки) была равна четырем. С ответом на каждый вопрос неопределенность уменьшалась в 2 раза и, следовательно, согласно данному выше определению одного бита, передавался 1 бит информации.
Первоначальные варианты : Варианты, оставшиеся после 1-го вопроса: (1 бит) Вариант, оставшийся после 2-го вопроса: (+1 бит)
Узнав оценку (одну из четырех возможных) ученик получил 2 бита информации.
Рассмотрим еще один частный пример, а затем выведем общее правило.
Вы едете на электропоезде, в котором 8 вагонов, а на вокзале вас встречает товарищ. Товарищ позвонил вам по мобильному телефону и спросил, в каком вагоне вы едете. Вы предлагаете угадать номер вагона, задав наименьшее количество вопросов, ответами на которые могут быть слова «да» или «нет».
Немного подумав, товарищ стал спрашивать:
— Номер вагона больше четырех?
— Номер вагона больше шести?
— Ну теперь все ясно! Ты едешь в пятом вагоне!
Схематически поиск номера вагона выглядит так:
Первоначальное число вариантов: После 1-го вопроса (1 бит): После 2-го вопроса (+1 бит): После 3-го вопроса (+1 бит):
Каждый ответ уменьшал неопределенность в два раза. Всего было задано три вопроса. Значит в сумме набрано 3 бита информации. И если бы сразу было сказано, что вы едете в пятом вагоне, то этим сообщением было бы передано те же 3 бита информации.
Способ поиска решения проблемы, примененный в примерах с оценками и вагонами, называется методом половинного деления: ответ на каждый вопрос уменьшает неопределенность знаний наполовину. При этом каждый такой ответ несет 1 бит информации.
«Главная формула» информатики
Сформулируем одно очень важное условие, относящееся к рассмотренным примерам. Во всех ситуациях предполагается, что все возможные варианты событий равновероятны. Равновероятно, что учитель может быть мужчиной или женщиной; равновероятен любой исход футбольного матча, равновероятен выбор одного из четырех кандидатов в меры города. То же относится и к примерам с оценками и вагонами.
Тогда полученные нами результаты описываются следующими формулировками:
— сообщение об одном из двух равновероятных результатов некоторого события несет 1 бит информации;
— сообщение об одном из четырех равновероятных результатов некоторого события несет 2 бита информации;
— сообщение об одном из восьми равновероятных результатов некоторого события несет 3 бит информации.
Обозначим буквой N количество возможных результатов события, или, как мы это еще называли, — неопределенность знаний. Буквой i будем обозначать количество информации в сообщении об одном из N результатов.
Нетрудно заметить, что связь между этими величинами выражается следующей формулой:
2 i = N.
Пусть в поезде не 8, а 16 вагонов. Чтобы ответить на вопрос, сколько информации содержится в сообщении о номере искомого вагона, нужно решить уравнение:
Количество информации (i), содержащееся в сообщении об одном из N равновероятных результатов некоторого событий, определяется из решения показательного уравнения: 2 i = N
Пример 1. В кинозале 16 рядов, в каждом ряду 32 места. Сколько информации несет сообщение о том, что вам купили билет на 12-й ряд, 10-е место?
Решение задачи: в кинозале всего 16×32=512 мест. Сообщение о купленном билете однозначно определяет выбор одного из этих мест. Из уравнения 2 i = 512=2 9получаем: i=9 бит.
Но эту же задачу можно решать иначе. Сообщение о номере ряда несет 4 бита информации, т.к. 2 4 =16. Сообщение о номере места несет 5 бит информации, т.к. 2 5 =32. В целом сообщение про ряд и место несет: 4+5=9 бит информации.
Данный пример иллюстрирует выполнение закона аддитивности информации (правило сложения): количество информации в сообщении одновременно о нескольких результатах независимых друг от друга событий равно сумме количеств информации о каждом событии отдельно.
Информация играет для нас важную роль потому, что наше знание всегда неполно, в нём есть неопределенность. Эта неопределённость мешает нам решать свои задачи, принимать правильные решения. Полученная информация уменьшает («снимает») неопределённость, полностью или частично. Поэтому количество полученной информации можно оценить по величине уменьшения неопределенности:
где ННАЧ — начальная неопределённость, а НКОН — конечная (после получения сообщения).
Если неопределённость полностью снимается, то НКОН = 0.
Чтобы оценить информацию с этой точки зрения, нужно как-то вычислить неопределённость, выразить её числом. Эту задачу решил в 1948 г. американский математик Клод Шеннон.
Пусть неопределённость состоит в том, что мы можем получить одно из N возможных сообщений, причём известно, что вероятность получения сообщения с номером i равна рi.
Неопределённость знания об источнике данных вычисляется по формуле Шеннона
Величина Н часто называется информационной энтропией. С точки зрения математики это среднее количество информации, которую мы получаем при полном снятии неопределённости (когда выбран один из возможных вариантов).
Когда неопределённость наибольшая? Зададим вопрос «Идёт ли сейчас снег?» зимой и летом. Летом неопределённость очень маленькая, так как, скорее всего, снега нет, ситуация ясна. Зимой же неопределённость велика, потому что снег может идти или не идти примерно с равной вероятностью.
Перейдём к числам. Будем считать, что вероятность снега зимой равна P1 = 0,5. Чему равна вероятность р2 того, что снега нет? «Здравый смысл» подсказывает, что р2 = 0,5 (остальные 50%). Математики говорят, что два события, «Снег идёт» и «Снега нет», составляют полную систему. Это значит, что обязательно случится какое-нибудь одно из этих событий, и при этом другое точно не произойдёт. Слово «обязательно» означает, что вероятность этих двух событий в сумме равна 1.
Сумма вероятностей всех событий, составляющих полную систему, равна 1.
Для «зимнего» случая количество информации при получении сообщений «Снег идёт» и «Снега нет» одинаковое, потому что их вероятности одинаковые:
Неопределённость, вычисленная по формуле Шеннона, также равна 1 биту:
а неопределённость (среднее количество информации) равна
Мы получили то, что ожидали: зимой неопределённость в ответе на вопрос «Идёт ли сейчас снег?» значительно больше, чем летом. Можно предположить (и это действительно так), что неопределённость наибольшая в том случае, когда вероятности всех событий равны.
Летом эта неопределённость очень близка к нулю, поэтому можно предположить (и это также верно), что она стремится к нулю, если вероятность одного из двух событий стремится к нулю.
Неопределённость наибольшая для случая, когда все события равновероятны.
При этом вероятность каждого из N событий равна р = 1/N, поэтому по формуле Шеннона
Отсюда следует, что:
При равновероятных событиях неопределённость совпадает с количеством информации, вычисленной по формуле Хартли.
Неопределенность знания — это количество возможных вариантов ответа на интересовавший вас вопрос. Еще можно сказать: возможных исходов события. Здесь событие — например, выборы мэра; исход — выбор, например, Н. Н. Никитина.
Сообщение, уменьшающее неопределенность знания об исходе некоторого события в два раза, несет 1 бит информации.
«Главная формула» информатики
В 40-х годах ХХ века, проблема измерения информации была решена американским ученым Клодом Шенноном – основателем теории информации. Согласно К.Шеннону, информация – это снятая неопределенность в знаниях человека о результате какого-то события.
