Реферат: Теория информации
/>/>/>Ученица 10 А класса ГОУ РМЭ ЦО № 18
Коробкова Анна
г. Йошкар-Ола, 2004
/>
1) Введение. Понятиеэнтропии.
2) Понятие информации.
3) Решение некоторыхтиповых задач.
4) Заключение
5) Список использованнойлитературы.
/>
Главнымсвойством случайных событий является отсутствие полной уверенности в ихнаступлении, создающее известную неопределённость при выполнении связанных сэтими событиями опытов. Однако совершенно ясно, что степень этойнеопределённости в различных случаях будет совершенно разной. Возникновениематематической теории информации стало возможным после того, как былоосознанно, что количество информации можно задать числом.
Дляпрактики очень важно уметь численно оценивать степень неопределённости самыхразнообразных опытов. Начнём с рассмотрения опытов, имеющих к равновероятныхисходов. Очевидно, что степень неопределённости каждого такого опытаопределяется числом к: если при к=1 исход опыта вообще не является случайным,то при большом к предсказать исход опыта очень и очень сложно. Таким образом,искомая численная степень неопределённости должна являться функцией числа к,при к =1 обращаться в нуль и возрастать при возрастании числа к.
Теперьрассмотрим два независимых опыта А и В. Пусть опыт А имеет к равновероятныхисходов, а опыт В – равновероятных исходов. Очевидно, что степеньнеопределённости двойного опыта АВ равна сумме степеней неопределённости опытовА и В. А так как опыт АВ имеет ks равновероятных исходов, приходим кследующему условию, которому должна удовлетворять наша функция f(k):
f(ks)=f(k)+f(s).
Это условиенаталкивает на мысль принять за меру неопределённости опыта, имеющего кравновероятных исходов, число log k, так каклогарифмическая функция – единственная, удовлетворяющая всем вышеперечисленнымусловиям. Заметим, что выбор основания системы логарифмов здесь несуществен,так как в силу известной формулы
/>logbk= logba/>logak
переход от однойсистемы логарифмов к другой сводится лишь к простому изменению единицыизмерения степени неопределённости. Как правило, используются логарифмы приосновании 2. Такая единица измерения называется двоичной единицей или битом.
Общаянеопределённость опыта, имеющего к исходов, равна сумме неопределённостей,вносимых каждым исходом. Это число называют энтропией опыта А, будем егообозначать через Н(А). Рассмотрим некоторые свойства энтропии. Прежде всего,она не может принимать отрицательные значения: т.к. всегда
0 ≤ p(A) ≤ 1, то log p(A) не может бытьположительным, а – p(A) log p(A) – отрицательным(р(А) – вероятность получения исхода А в опыте). Также заметим, что если рочень мало, то и произведение – p(A) log p(A) тоже будет весьмамалым, хотя и положительным, т.е. при р/> произведение– p log p неограниченноубывает. Энтропия опыта равна нулю, когда один из его исходов имеют степеньвероятности 1, а остальные – степень вероятности 0. Наибольшую энтропию имеетопыт с равновероятными исходами.
/>
Пустькакое-либо измерение или наблюдение Б, предшествующее опыту А, может ограничитьколичество возможных исходов опыта А и тем самым уменьшить степень егонеопределённости. Для того, чтобы результат Б сказался на последующем опыте А,нужно, чтобы его результат не был известен заранее; поэтому Б можнорассматривать как вспомогательный, также имеющий несколько допустимых исходов. При этом, если опыт А не зависит от опыта Б, то осуществление Б не уменьшаетэнтропии А; если же наоборот результат Б полностью предопределяет исход А, тоэнтропия А уменьшается до 0.
Таким образом,разность
I(A, Б)= H(A) – Hб(A)
указывает, насколькоосуществление опыта Б уменьшает неопределённость А. Эту разность называютколичеством информации относительно опыта А, содержащемся в опыте Б, или,короче, информацией о А, содержащейся в Б. Таким образом, мы получаемвозможность численного изменения информации.
Частоможет случиться, что, желая узнать исход какого-либо опыта А, мы можем с этойцелью по-разному выбирать опыты Б. В этом случае всегда рекомендуется начинатьс того опыта Б0, который содержит наибольшую информацию относительноА, так как при другом опыте Б мывероятно добьемся менее значительногоуменьшения степени неопределённости А. Реально же, конечно, может получиться инаоборот.
Такженеобходимо заметить, хотя это и не относится к той части теории, котораяпригодится нам для решения задач, что информация имеет ярко выраженный материальныйхарактер — то есть она может передаваться только с помощью вещества илиэнергии.
/>
/> Пусть известно, чтожитель некоторого города А всегда говорят правду, а жители соседнего города Бвсегда обманывают. Наблюдатель Н. знает, что он находится в одном из этих двухгородов, но не знает, в каком именно. Путём опроса встречного ему требуетсяопределить, в каком городе он находится, или в каком городе живёт егособеседник (жители А могут заходить в Б и наоборот), или то и другое вместе. Спрашивается,каково наименьшее число вопросов, которые должен задать Н. (на все вопросывстречные отвечают лишь да или нет)?
/>
Пусть Н. надоопределить, в каком городе он находится. Здесь опыт А может иметь 2равновероятных исхода. Энтропия Н(А) опыта А равна одному биту. Далее, опыт Б всоставе одного вопроса, также может иметь два исхода, поэтому энтропия Н(Б)самое большее равна одному биту. Следовательно, можно надеяться, что при удачнопоставленном вопросе Б будет иметь место равенство
I(Б, А) = Н(А)
Для этого тольконеобходимо, чтобы оба ответа на вопрос Б были равновероятны, и исход Бполностью определял результат А. Всем этим условиям удовлетворяет вопрос«Живёте ли вы в этом городе?» (положительный ответ может быть дан только вгороде А, а отрицательный – в Б).
Ещё проще узнать, в каком городе живёт егособеседник – для этого достаточно задать какой-нибудь вопрос, ответ на которыйН. знает заранее (например, равно ли дважды два четырём?).
Если же Н. должен узнать ответы на оба вопроса,ему предстоит определить исход сложного опыта А1А2. В этом случае он нуждаетсяв информации, большей 1 бита. Таким образом, оценки количества информации даютнам строгое доказательство того, что за один вопрос выяснить, где находится Н.и откуда родом отвечающий. Для этого нужно как минимум 2 вопроса.
/> Сколько вопросов надозадать, чтобы отгадать задуманное число, не превосходящее 10, если спрашиваемыйотвечает на вопросы лишь «да» и «нет»?
/>
Опыт А, состоящий ввыяснении задуманного числа, может иметь 10 различных исходов. До ответа напервый вопрос все эти исходы можно считать равновероятными, так что энтропияН(А) опыта А равна log10/> 3,32 бита. Рассмотримсложный опыт Бк = б1б2б3…бк,заключающийся в том, что спрашивающий задаёт к вопросов. Для того чтобы исходопыта Бк полностью определял исход А, необходимо, чтобы имело месторавенство I (Бк, А) =Н (А). Отсюда:
log 10 = Н (А) = I (Бк, А)/> Н (Бк)/> к
тоесть
к/> log 10/> 3,32
или,так как к — целое число,
к/> 4.
Теперь рассмотрим,какие вопросы выгоднее всего задавать. Во-первых, нужно, чтобы энтропия былавозможно большей (то есть действительно равнялась одному биту), а значит обаварианта ответа должны быть равновероятны. Далее нужно, чтобы информация I(б1, А)относительно А, заключённая в б1, равнялась энтропии Н (б1)опыта б1, а не была бы меньше этой величины. Для этого надо, чтобыответ на первый вопрос не содержал «посторонней» информации, то есть чтобыусловная энтропия На (б1)равнялась нулю. Эти условия достаточно ясно указывают на то, как нужнопоставить первый вопрос. Разобьём множество всех возможных значений нашейпеременной (то есть множество целых положительных чисел от 1 до 10) на две равныепо численности группы (так как исходы опыта б1 должны бытьравновероятны) и спросим, относится ли задуманное число к одной или другой изних (например, больше ли оно пяти). Далее нужно разбивать оставшееся множествочисел на две возможно близкие по численности части, и тогда мы определимзадуманное число с помощью четырёх вопросов. Нужно сказать, что с помощью техже четырёх вопросов мы угадаем не только одно из 10 задуманных чисел, но дажеодно из 16, так как после того как уже выяснено, что число имеет одно из Хзначений, где Х нечётно, невозможно добиться строгой равновероятности исходовпоследующего опыта, следовательно, энтропия этого опыта будет меньше 1. Этоозначает, что наш опыт не особенно выгоден с точки зрения полученнойинформации, то есть что с помощью того же числа вопросов можно найти загаданноечисло, имеющее не одно из 10, а одно из 24 = 16 возможных значений.
Вообще, наименьшее число k вопросов,позволяющее найти заданное число Х, имеющее одно из n допустимых значений,определяется неравенствами
k – 1< log n ≤ k или 2k — 1 < n ≤ 2k. />
Также можно заметить, что независимо отзначения n
k ≥ log n;
при этом k = log n только в том случае,когда число n является целойстепенью числа 2.
/> Имеется 25 монетодного достоинства; 24 из них имеют одинаковый вес, а одна – фальшивая –несколько легче остальных. Спрашивается, сколькими взвешиваниями на чашечныхвесах без гирь можно обнаружить эту фальшивую монету.
/>
Опыт А, результаткоторого требуется определить, имеет в этом случае 25 возможных исходов,значит, так как эти исходы равновероятны, Н(Б) = log 25. Опыт б1,состоящий в одном взвешивании, может иметь 3 исхода (либо перевесит леваячашка, либо правая, либо веса останутся в равновесии); поэтому Н (б1)= log 3 и информация I(б1, А),получаемая при проведении такого опыта, не превосходит log 3. Рассмотрим теперьсложный опыт Бк = б1б2…бк,заключающийся в kпоследовательных взвешиваниях; он даёт информацию, не превосходящую k log 3. Если опыт Бкпозволяет полностью определить исход опыта А, то должно выполняться
Н (Бк)≥ I (Бк, А)≥ Н (А) или k log 3 ≥ log 25.
Отсюда заключаем, что 3к ≥25, то есть
K ≥ log3 25 = />
Или, так как k – целое число, k ≥ 3.
Нетрудно показать,что с помощью трёх взвешиваний всегда можно определить фальшивую монету.Предположим, что на каждую чашку весов нами положено по n монет, не положенына весы будут 25 — 2nмонет. Так как вероятность того, что фальшивая монета окажется в данной группеиз n монет, равна />, то три исхода опыта б1будут иметь наиболее близкие вероятности, если n = 8 и 25 — 2n = 9. При любомисходе опыта при втором взвешивании (опыт б2) на обе чашки весовследует положить по 3 монеты из определившейся после предыдущего опыта группы,а третьим взвешиванием мы из группы из трёх монет найдём фальшивую, положив поодной монете на обе чашки весов.
/> Имеется 12 монетодного достоинства; 11 из них имеют одинаковый вес, а одна – фальшивая –отличается по весу от остальных (причём неизвестно, легче она или тяжелеенастоящих). Каково наименьшее число взвешиваний на чашечных весах без гирь,которое позволяет обнаружить фальшивую монету и выяснить, легче она, чемостальные монеты, или тяжелее?
/>
Здесь рассматриваетсяопыт А, имеющий 24 возможных равновероятных исхода. Энтропия Н (А) опыта Аравна log 24. Таким образом,нам нужно получить log24 единиц информации. Так как, произведя сложный опыт Ак = а1а2…ак,состоящий в k взвешиваниях, мы можемполучить информацию, не большую, чем k log 3 = log 3, а 33 =27, то с первого взгляда кажется ясным, что трёх взвешиваний будет достаточно.
Пусть при первомвзвешивании мы положили на обе чашки по n монет. Если чашкивесов при этом остались в равновесии, то фальшивой является одна из 12−2n отложенных монет,что отвечает 2(12−2n) исходам рассматриваемого опыта А (из общегочисла 24 исходов). Если перевесила правая чашка, то либо фальшивой и болеетяжёлой является одна из n «правых» монет, либо фальшивой и болеелёгкой является одна из n «левых» монет − эти случаи отвечают 2n исходам А, точно также, случаю, когда перевесила левая чашка, отвечают 2n исходов А. Такимобразом, три исхода первого взвешивания имеют вероятности
/>, /> и />.
Отсюда сразу следует,что наибольшую энтропию опыт будет иметь при n = 4, три исходакоторого равновероятны. Далее рассмотрим отдельно 2 случая.
1). При первом взвешивании чашки весовостались в равновесии. В таком случае фальшивой является одна из четырёхотложенных монет. Нам надо при помощи двух взвешиваний определить, какая именноиз них является фальшивой, и выяснить, легче она или тяжелее остальных; так каку нас осталось 2∙4 = 8 возможных исходов опыта А, а 2 log 3 = log 9 > log 8, то можно ожидать,что это возможно. Если, однако, положить на каждую чашку весов по одной монете,и они останутся в равновесии, то следующим опытом нам надо будет определитьисход опыта, имеющего 4 возможных исхода, что невозможно. То же самоеполучится, если положить на каждую чашку по две монеты. Однако рано говорить,что трёх взвешиваний недостаточно для выполнения задачи – ведь у нас ещёостались заведомо настоящие монеты после завершения первого опыта. Обозначимчерез аm,n<sup/>опыт, состоящий втом, что на правую чашку весов кладутся m из нашихподозрительных монет, а на левую n ≤ m из этих монет и ещё m−n заведомо настоящихмонет. Через р(Р), р(П) и р(Л) мы обозначим соответственно вероятности того,что при опыте аm,n<sup/>чашки весов останутсяв равновесии и что перетянет правая или левая чашка весов. Так как, очевидно, m + n ≤ 4, то всеопыты аm,n<sup/>легко перечислить:отвечающие им значения вероятностей р(Р), р(П) и р(Л) собраны в таблице, вкоторой также указана энтропия в битах Н(аm,n) опыта аm,n<sup/>(равная − р(Р) log р(Р) − р(П) log р(П) − р(Л) log р(Л)).
m
n
р(Р)
р(П)
р(Л)
Н(аm,n)
1 1 0,5 0,25 0,25 1,50 1 0,75 0,125 0,125 1,06 2 2 0,5 0,5 1,00 2 1 0,25 0,375 0,375 1,56 2 0,5 0,25 0,25 1,50 3 1 0,5 0,5 1,00 3 0,25 0,375 0,375 1,56 4 0,5 0,5 1,00
Из этой таблицывидно, что наибольшую энтропию имеют опыты а2,1 и а3,0;поэтому для получения наибольшей информации следует воспользоваться ими.Нетрудно видеть, что в обоих случаях мы можем затем третьим взвешиванием полностьюопределить исход А.
2). При первом взвешивании одна из двухчашек весов (например, правая) перетянула. В таком случае, либо одна изчетырёх «правых» монет является фальшивой и более тяжёлой, либо одна из четырёх«левых» − фальшивой и более лёгкой. При втором взвешивании мы можем направую чашку весов положить n1 «правых» монет и n2 «левых», а на левуючашку − m1 «правых» монет, m2 «левых» и (n1 + n2) − (m1 + m2) заведомо настоящихиз числа не участвовавших в первом взвешивании. Здесь тоже можно составитьтаблицу энтропий опытов а<sup/>n1,n2;m1,m2, однако, так какчисло всевозможных вариантов тут слишком велико, то некоторые из нихцелесообразно исключить с самого начала.
Заметим, что после двух взвешиваний у насдолжно остаться не более трёх возможных исходов опыта А. Отсюда следует, чточисло сомнительных монет, не участвующих во втором взвешивании, не должнопревосходить 3.
Перечислим теперь всеслучаи, удовлетворяющие этим условиям.
n1
n2
m1
m2
р(Р)
р(П)
р(Л)
Н(а<sup/>n1,n2;m1,m2)
2 1 2 1 0,25 0,375 0,375 1,56 2 1 2 0,375 0,25 0,375 1,56 2 1 1 1 0,375 0,375 0,25 1,56 1 2 1 2 0,25 0,375 0,375 1,56 1 2 2 0,375 0,375 0,25 1,56 1 2 1 1 0,375 0,25 0,375 1,56 3 1 1 0,375 0,375 0,25 1,56 1 3 1 0,375 0,25 0,375 1,56 2 2 1 1 0,25 0,375 0,375 1,56 2 2 1 0,375 0,25 0,375 1,56 2 2 1 0,375 0,375 0,25 1,56 3 2 1 0,25 0,375 0,375 1,56 2 3 1 0,25 0,375 0,375 1,56Таким образом, мывидим, что здесь имеется уже не два, как в предыдущем случае, а целых 13вариантов второго опыта. Энтропия каждого из них достаточна, чтобы иметьвозможность полностью определить исход А с помощью ещё одного, третьёго,взвешивания.
Значит, действительнотрёх взвешиваний достаточно, чтобы ответить на поставленный в задаче вопрос.
/>
Я думаю, излишнеговорить о том, что теория информации имеет огромное значение для развитиясовременной науки и техники. Она получила широкое применение в физике,микроэлектронике, а также во всех отраслях техники, где необходимо решатьпроблемы хранения, получения и передачи информации.
Список использованной литературы.
1) А. Реньи. «Запискистудента теории информации».
2) А.М. Яглом, И.М.Яглом. «Вероятность и информация».