Теорія інформації

[pic].

[pic].

[pic].

Учениця 10 А класу ГОУ РМЭ ЦО № 18.

Коробкова Анна.

р. Йошкар-Ола, 2004.

[pic].

1) Запровадження. Поняття энтропии.

2) Поняття информации.

3) Рішення деяких типових задач.

4) Заключение.

5) Список використаної литературы.

[pic].

Головним властивістю випадкових подій є повної впевненості у їх наступі, що дає відому невизначеність при виконанні пов’язаних із цими подіями дослідів. Проте зрозуміло, що ступінь цієї невизначеності у різних випадках буде абсолютно різною. Виникнення математичної теорії інформації можна було по тому, як було зазначено усвідомлено, що його інформації можна поставити числом.

Для практики дуже важливо вміти чисельно оцінювати ступінь невизначеності найрізноманітніших дослідів. Почнемо з розгляду дослідів, мають до равновероятных фіналів. Вочевидь, що ступінь невизначеності кожної такої досвіду визначається кількістю до: якщо к=1 результат досвіду взагалі перестав бути випадковим, то, при великому до пророкувати результат досвіду дуже й дуже складно. Отже, бажана чисельна ступінь невизначеності має бути функцією числа до, при до =1 звертатися до нуль і зростати за умов зростання числа к.

Тепер на дві незалежні досвіду Проте й У. Нехай досвід, А має до равновероятных фіналів, а досвід У — равновероятных фіналів. Вочевидь, що ступінь невизначеності подвійного досвіду АВ дорівнює сумі ступенів невизначеності дослідів Проте й У. Оскільки досвід АВ має ks равновероятных фіналів, дійшли наступному умові, якого має задовольняти наша функція f (k): f (ks)=f (k)+f (s). Це умова наштовхує на думку б сприйняти як міру невизначеності досвіду, що має равновероятных фіналів, число log k, оскільки логарифмічна функція — єдина, яка задовольнить всім переліченим вище умовам. Зауважимо, що вибір підстави системи логарифмів тут несуттєвий, оскільки з відомої формулы.

[pic]logbk = logba[pic]logak перехід від однієї системи логарифмів в іншу зводиться тільки в простому зміни одиниця виміру ступеня невизначеності. Зазвичай, використовуються логарифми при підставі 2. Така одиниця виміру називається двоичной одиницею чи битом.

Загальна невизначеність досвіду, що має фіналів, дорівнює сумі неопределённостей, внесених кожним результатом. Ця кількість називають ентропія досвіду А, його позначати через Н (А). Розглянемо деякі властивості ентропії. Насамперед, вона може приймати негативні значення: т.к. завжди 0? p (A)? 1, то log p (A) може бути позитивним, а — p (A) log p (A) — негативним (р (А) — можливість отримання результату На досвіді). Також зауважимо, що й р обмаль, те й твір — p (A) log p (A) теж буде невеликим, хоч і позитивним, тобто. при р[pic] твір — p log p необмежено убуває. Ентропія досвіду дорівнює нулю, коли один його фіналів мають ступінь ймовірності 1, інші ж — ступінь ймовірності 0. Найбільшу ентропію має досвід з равновероятными исходами.

[pic].

Нехай якесь вимір чи спостереження Б, попереднє досвіду Чи, можливо обмежити кількість можливих фіналів досвіду Проте й цим зменшити ступінь його невизначеності. А, щоб результат Б позначився на наступному досвіді А, потрібно, що його результат досягнуто не був відомий заздалегідь; тому Б можна як допоміжний, також має кілька допустимих фіналів. У цьому, якщо досвід, А залежить від досвіду Б, то здійснення Б не зменшує ентропії А; Якщо ж навпаки результат Б повністю визначає результат Бо ентропія, А зменшується до 0. Отже, разность.

I (A, Б)= H (A) — Hб (A) вказує, наскільки здійснення досвіду Б зменшує невизначеність А. Цю різницю називають кількістю інформації щодо досвіду А, що міститься в досвіді Б, чи, коротше, інформацією щодо А, котра міститься в Б. Отже, ми маємо можливість чисельного зміни информации.

Часто може статися, що, бажаючи дізнатися результат будь-якого досвіду А, ми можемо із метою по-різному вибирати досліди Б. І тут завжди рекомендується розпочинати з досвіду Б0, який містить найбільшу інформацію щодо Оскільки за іншого досвіді Б ми мабуть доможемося менше значного зменшення ступеня невизначеності А. А реально, звісно, може й наоборот.

Слід також помітити, хоча й не належить до тієї частини теорії, яка знадобиться нам вирішення завдань, що має яскраво виражений матеріальний характер — тобто може передаватися тільки з допомогою речовини чи энергии.

[pic].

. Нехай відомо, що житель деякого міста, А завжди кажуть правду, а жителі сусіднього міста Б завжди обманюють. Наглядач М. знає, що він перебуває у одному з цих міст, але з знає, якому саме. Шляхом опитування зустрічного їй потрібно визначити, що не місті він перебуває, чи якому місті живе його співрозмовник (жителі А можуть заходити в Б і навпаки), чи й інше разом. Питається, яке найменше число питань, що має поставити М. (всі запитання зустрічні відповідають лише так чи нет)?

[pic].

Нехай М. треба визначити, що не місті він перебуває. Тут досвід, А може мати 2 равновероятных результату. Ентропія Н (А) досвіду, А дорівнює одному битку. Далі, досвід Б у складі запитання, також два результату, тому ентропія Н (Б) найбільше дорівнює одному битку. Отже, можна сподіватися, що з вдало поставленому питанні Б матиме місце равенство.

I (Б, А) = Н (А).

І тому лише необхідна, щоб обидва відповіді питання Б були равновероятны, й вирішили результат Б повністю визначав результат А. Все це умовам задовольняє питання «Живете ви у цьому місті?» (позитивний відповідь може бути даний лише у місті А, а негативний — в Б). Ще простіше дізнатися, що не місті живе його співрозмовник — при цьому досить буде задати питання, у відповідь який М. знає заздалегідь (наприклад, одно чи двічі два чотирьох?). Якщо ж М. потрібно розказати відповіді обидва запитання, він має визначити результат складного досвіду А1А2. І тут він вимагає інформації, більшої 1 біта. Отже, оцінки кількості інформації дають нам суворе доказ те, що за питання з’ясувати, де знаходиться М. і звідки родом відповідальний. Треба лише принаймні 2 вопроса.

. Скільки питань треба поставити, щоб відгадати задумане число, не перевершували 10, якщо спрашиваемый відповідає стосовно питань лише «так» и.

«нет»?

[pic].

Досвід А, котра перебувала з’ясуванні задуманого числа, може мати 10 різних фіналів. До відповіді перше запитання всі ці результати вважатимуться равновероятными, отже ентропія Н (А) досвіду, А дорівнює log 10[pic] 3,32 біта. Розглянемо складний досвід Бк = б1б2б3… бк, що полягає у цьому, що запитувач задає до питань. Щоб результат досвіду Бк повністю визначав результат А, необхідно, щоб можна говорити про рівність I (Бк, А) = М (А). Звідси: log 10 = М (А) = I (Бк, А)[pic] М (Бк)[pic] до тобто к[pic] log 10[pic] 3,32 чи, бо дійшли — ціла кількість, к[pic] 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. [pic] Можна помітити, що незалежно від значення n k? log n; у своїй k = log n в тому разі, коли кількість n є цілої ступенем числа 2.

. Є 25 монет одного гідності; 24 їх мають однакову вагу, тоді як — фальшива — кілька легше інших. Питається, скількома взвешиваниями на чашечных терезах без гир можна знайти цю фальшиву монету.

[pic].

Досвід А, результат якого вимагають визначити, має у цьому випадку 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 = [pic] Або, оскільки k — ціла кількість, k? 3.

Неважко показати, що з допомогою трьох зважувань можна визначити фальшиву монету. Припустимо, що у кожну чашку терезів нами належить по n монет, не покладено на ваги будуть 25 — 2N монет. Оскільки можливість, що фальшива монета опиниться у цій групі з n монет, дорівнює [pic], то три результату досвіду б1 матимуть найближчі ймовірності, якщо n = 8 і 25 — 2N = 9. При будь-якому результаті досвіду другий — коли зважуванні (досвід б2) на обидві чашки терезів слід покласти по 3 монети з визначеної після попереднього досвіду групи, а третім зважуванням ми із групи із трьох монет знайдемо фальшиву, поклавши за однією монеті на обидві чашки весов.

. Є 12 монет одного гідності; 11 їх всі мають однакову вагу, тоді як — фальшива — відрізняється на вагу від інших (причому невідомо, легше вона чи важче справжніх). Яке найменше число зважувань на чашечных терезах без гир, що дозволяє знайти фальшиву монетку і вирушили з’ясувати, легше вона, ніж інші монети, чи тяжелее?

[pic].

Тут розглядається досвід А, має 24 можливих равновероятных результату. Ентропія М (А) досвіду, А дорівнює log 24. Отже, ми мусимо отримати log 24 одиниць інформації. Оскільки, провівши складний досвід Ак = а1а2… ак, котра перебувала k взвешиваниях, ми маємо очікувати інформацію, невелику, ніж k log 3 = log 3, а 33 = 27, те з першого погляду здається ясним, що трьох зважувань буде достаточно.

Нехай з першого зважуванні ми поклали на обидві чашки по n монет. Якщо чашки терезів у своїй залишилися у рівновазі, то фальшивої є одне з 12−2n відкладених монет, який відповідає 2(12−2n) исходам аналізованого досвіду, А (від кількості 24 фіналів). Якщо переважила права чашка, то або фальшивої горілки й більш важкій є одне з n «правих» монет, або фальшивої і більше легкої є одне з n «лівих» монет — ці випадки відповідають 2N исходам А, точно як і, випадку, коли переважила ліва чашка, відповідають 2N фіналів А. Отже, три результату першого зважування мають вероятности.

[pic], [pic] і [pic].

Звідси відразу слід, що найбільшу ентропію досвід матиме при n = 4, три результату якого равновероятны. Далі розглянемо окремо 2 случая.

1). За першого зважуванні чашки терезів залишилися у рівновазі. У цьому разі фальшивої є одне з чотирьох відкладених монет. Мусимо при допомоги двох зважувань визначити, яке саме з них фальшивої, і з’ясувати, легше вона чи важче інших; тому що в нас залишилося 2?4 = 8 можливих фіналів досвіду А, а 2 log 3 = log 9 > log 8, можна очікувати, що може бути. Якщо, проте, покласти кожну чашку терезів за однією монеті, і вона залишиться в рівновазі, то наступним досвідом потрібно влаштувати результат досвіду, має 4 можливих результату, що організувати неможливо. Це ж вийде, якщо покласти кожну чашку по дві монети. Проте рано говорити, що трьох зважувань замало виконання завдання — в нас ще залишилися явно справжні монети після завершення першої спроби. Означимо через аm, n досвід, котра перебувала тому, що у праву чашку терезів кладуться m з підозрілих монет, але в ліву n? m з цих монет і ще m-n явно справжніх монет. Через р (Р), р (П) і р (Л) ми позначимо відповідно ймовірності те, що при досвіді аm, n чашки терезів залишаться у рівновазі І що перетягне права чи ліва чашка терезів. Оскільки, очевидно, m + n? 4, усі досліди аm, n легко перерахувати: відповідальні їм значення ймовірностей р (Р), р (П) і р (Л) зібрані в таблиці, у якій також зазначена ентропія в бітах Н (аm, n) досвіду аm, n (рівна — р (Р) log р (Р) — р (П) log р (П) — р (Л) log р (Л)).

|m |n |р (Р) |р (П) |р (Л) |Н (аm, n) | |1 |1 |0,5 |0,25 |0,25 |1,50 | |1 |0 |0,75 |0,125 |0,125 |1,06 | |2 |2 |0 |0,5 |0,5 |1,00 | |2 |1 |0,25 |0,375 |0,375 |1,56 | |2 |0 |0,5 |0,25 |0,25 |1,50 | |3 |1 |0 |0,5 |0,5 |1,00 | |3 |0 |0,25 |0,375 |0,375 |1,56 | |4 |0 |0 |0,5 |0,5 |1,00 |.

З цієї таблиці видно, що найбільшу ентропію мають досліди а2,1 і а3,0; для отримання найбільшої інформації слід скористатися ними. Неважко бачити, що у обох випадках ми можемо потім третім зважуванням повністю визначити результат А.

2). За першого зважуванні одне з двох чашок терезів (наприклад, права) перетягла. У разі, або одне з чотирьох «правих» монет є фальшивої горілки й більш важкій, або одне з чотирьох «лівих» — фальшивої горілки й більш легкої. При другому зважуванні ми можемо праву чашку терезів покласти n1 «правих» монет і n2 «лівих», але в ліву чашку — m1 «правих» монет, m2 «лівих» і (n1 + n2) — (m1 + m2) явно справжніх у складі не брали участь у першому зважуванні. Тут також можна скласти таблицю энтропий дослідів, а n1, n2;m1,m2, проте, оскільки кількість різноманітних варіантів тут дуже велика, то окремі доцільно виключити з початку. Зауважимо, що відбулося після двох зважувань ми має бути трохи більше трьох можливих фіналів досвіду А. Звідси випливає, що кількість сумнівних монет, не що беруть участь у другому зважуванні, на повинен перевершувати 3.

Перерахуємо що тепер випадки, задовольняють цим условиям.

|n1 |n2 |m1 |m2 |р (Р) |р (П) |р (Л) |Н (а | | | | | | | | |n1,n2;m1,m2) | |2 |1 |2 |1 |0,25 |0,375 |0,375 |1,56 | |2 |1 |2 |0 |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 |0 |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 |0,375 |0,375 |0,25 |1,56 | |1 |3 |0 |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 |0,375 |0,25 |0,375 |1,56 | |2 |2 |0 |1 |0,375 |0,375 |0,25 |1,56 | |3 |2 |1 |0 |0,25 |0,375 |0,375 |1,56 | |2 |3 |0 |1 |0,25 |0,375 |0,375 |1,56 |.

Отже, бачимо, що тут є не два, як і попередньому разі, а цілих 13 варіантів другого досвіду. Ентропія кожного з них достатня, щоб матимуть можливість повністю визначити результат, А допомогою ще одного, третьёго, взвешивания.

Отже, справді трьох зважувань досить, аби цей проведений завданню вопрос.

[pic].

Гадаю, зайве говорити, що теорія інформації має величезну значення у розвиток сучасної науку й техніки. Він отримав широке використання у фізиці, мікроелектроніці, і навіть в усіх галузях техніки, де потрібно вирішувати проблеми зберігання, отримання й передачі информации.

Список використаної литературы.

1) А. Реньи. «Записки студента теорії информации».

2) А. М. Яглом, І.М. Яглом. «Можливість і информация». pic][pic][pic].