Практична Мета роботи: вивчення властивостей ентропії як кількісної міри інформації Теоретичні відомості Дискретне джерело інформації – це таке джерело, яке може виробити (згенерувати) за скінчений відрізок часу тільки скінчену множину повідомлень. Алфавіт – множина },,,,{ 321 MxxxxX = символів, які м ожуть з’явитися на виході дискрет ного джерела; M – потужність, тобто кількість різноманітних символів алфавіту. Для опису джерел, які не ма ють пам’яті, достатньо мати значення безумовних імовірностей p(xi) виникнення символів xi , i = 1, 2, 3,…, M на його виході. Більшість реальних джерел інформації є джерелами з пам’ят -тю. Розподіл ймовірностей виникнення чергового символу на виход і дискретного джерела з пам’яттю залежить від того, які симво ли були попередніми. Таке джерело інформації називають марковським, оскільки процес появи символів на його виході адекватний ланцюгам Маркова. Кількість інформації – одне із основних понять теорі ї інфо рмації, яка розглядає технічні аспекти інформаційних проблем, тобто вона дає відповіді на запитання такого типу: якою повинна бути ємність запам’ятовуючого пристрою для запису даних про стан деякої системи, якими повинні бу ти характеристики каналу зв’язку для передачі певного повідомлення тощо. Кількісна оцінка інформації пов’язана з поняттям ентропії. Ентропія є мірою невизначеності, непрогнозованості ситуації. Зменше ння ентропії, що відбулось завдяки деякому повідомленню, точно збігається з кількістю інформації, яка міститься в цьому повідомленні. Для дискретного немарковського ( без пам’яті ) джерела інфо рмації ентропія H визначається за таким виразом: ? = − ∑ ?(??) log2 ?(??) ? ?=1 Зазначимо, що Н не зал ежить в ід того, якими є випадкові події або величини ( якщо хі – випадкова величина ), а визначається тільки значеннями ймовірностей. Це означає, що ентропія є характеристикою розподілу ймовірностей. Розглянемо сукупність двох дискретних немарковських джерел інформації з алфавітами },,,,{ 321 MxxxxX = та },,,,{ 321 NyyyyY = , ентропії яких позначимо відповідно як H(X) та H(Y). Якщо джерела статистично залежні, то обчислюють їх середню ( повну) умовну ентропію: ?(? ?⁄ ) = ∑ ?(??) ∙ ?(? ??⁄ ) = − ∑ ∑ ?(??, ??) ∙ log2 ?(??/??) ? ?=1 ? ?=1 ? ?=1 де )/()(),( ikiki xypxpyxp = – ймовірність сумісної появи символів xi та yk на виходах відповідно першого та другого джерела; ?(? ??⁄ ) – часткова умовна ентропія Ця ентропія характеризує в середньому невизначеність символів на виході другого джерела, якщо є можливість спостерігати за появою символів на виході першого джерела. Аналогічно визначається частинна )/( kyXH та середня ( повна ) )/( YXH умовні ентропії для першого джерела. Якщо дискретні джерела статистично незалежні, то ?(?? ??⁄ ) = ?(??), ?(??, ??) = ?(??) ∙ ?(??) ?(? ?⁄ ) = ?(? ??⁄ ) = ?(?) ?(? ?⁄ ) = ?(? ??⁄ ) = ?(?) Середня умовна ентропія )/( XYH не може перевищувати безумовну ентропію )(YH ; частинна умовна ентропія )/( ixYH може бути більша, ніж )(YH . Для двох визначених вище дискретних джерел можна розрах увати сумісну ентропію H(X,Y) сукупності символів xi та yk або ентропію об'єднання ансамблів X та Y : ?(?, ?) = − ∑ ∑ ?(??, ??) ∙ log2 ?(??, ??) ? ?=1 ? ?=1 Для обчислення H(X,Y) слід мати набір або матрицю ймовірностей ?(??, ??) сумісної появи xi та yk             ),(),(),( ),(),(),( ),(),(),( 21 22221 11211 NMNN M M yxpyxpyxp yxpyxpyxp yxpyxpyxp     . Сума елементів k-го рядка цієї матриці дорівнює безумовній імові рності )( kyp появи символу yk на виході другого джерела, а сума елементів i-го стовпця – безумовній ймовірності )( ixp появи симв олу xi на виході першого джерела: ;),()( 1  = = M i kik yxpyp .),()( 1  = = N k kii yxpxp Маючи безумовні ймовірності )( ixp та )( kyp появи символів xi та yk на виході кожного з джерел, а також ймовірності ),( ki yxp сумісної їх появи, можна обчислити умовні ймовірності )/( ki yxp та )/( ik xyp , кор истуючись виразом: а далі знайти умовні ентропії H(Y/X) H(X/Y). Кількість інформації визначається за формулою: I(X,Y) = H(X) + H(Y) - H(X,Y) = H(X) - H(X/Y) = I(Y,X) Практичні завдання Завдання 1 Обчислити ентропію дискретного джерела інформації: Х = {х1, х2, х3, х4, х5, х6, х7, х8, х9, х10}, заданого розподілом р(хі). Значення р(хі) взяти з табл.1. варіант вибрати згідно з порядковим номером у списку. Таблиця 1 Значення ймовірностей появи символів Завдання 2 1. Два статистично незалежних джерела А та В визначаються матрицею ймовірностей p(ai,bj) (див. таблицю 2 згідно варіанту). Визначити часткову та загальну умовну ентропію, ентропію об'єднання, безумовну ентропію цих джерел, а також кількість інформації, що припадає на пару повідомлень ai,bi. 2. Провести аналіз та оцінку одержаних результатів. Таблиця 2 Матриця ймовірностей p(ai,bj) № вар. p(ai,bj) № вар. p(ai,bj) № вар. p(ai,bj) 1) 0,1 0,25 0,1 0,14 0,16 0,1 0,1 0,04 0,01 2) 0,1 0,24 0,1 0,14 0,17 0,1 0,1 0,04 0,01 3) 0,1 0,24 0,1 0,14 0,17 0,1 0,1 0,04 0,01 4) 0,2 0,2 0,04 0,14 0,17 0,1 0,1 0,04 0,01 5) 0,2 0,01 0,04 0,14 0,4 0,1 0,1 0 0,01 6) 0,2 0,01 0,04 0,14 0,3 0,1 0,1 0,1 0,01 7) 0,01 0,01 0,04 0,15 0,4 0,18 0,1 0,1 0,01 8) 0,01 0,01 0,04 0,1 0,45 0,18 0,1 0,1 0,01 9) 0,01 0,02 0,04 0,1 0,44 0,18 0,1 0,1 0,01 10) 0,01 0,02 0,04 0,1 0,33 0,19 0,11 0,1 0,1 11) 0,01 0,15 0,04 0,1 0,23 0,19 0,08 0,1 0,1 12) 0,01 0,15 0,24 0,1 0,03 0,19 0,08 0,1 0,1 13) 0,01 0,08 0,24 0,1 0,03 0,19 0,15 0,1 0,1 14) 0,01 0,08 0,24 0,1 0,04 0,18 0,15 0,1 0,1 15) 0,01 0,08 0,23 0,1 0,05 0,18 0,15 0,1 0,1 16) 0,02 0,07 0,23 0,1 0,05 0,18 0,15 0,1 0,1 17) 0,02 0,07 0 0,29 0,05 0,18 0,15 0 0,24 18) 0,02 0,07 0,1 0,29 0,05 0,08 0,15 0 0,24 19) 0,02 0,07 0,14 0,15 0,15 0,08 0,15 0 0,24 20) 0,02 0,03 0,14 0,15 0,15 0,12 0,15 0 0,24 21) 0 0,03 0,14 0,15 0 0,12 0,15 0,41 0 22) 0,17 0,03 0 0,15 0 0,12 0 0,41 0,12 23) 0,12 0 0,1 0,15 0,03 0,12 0,05 0,31 0,12 24) 0,17 0 0,1 0,15 0,03 0,12 0 0,31 0,12 25) 0,12 0 0,07 0,15 0,06 0,12 0,05 0,31 0,12 26) 0,12 0,05 0,07 0,15 0,01 0,12 0,05 0,31 0,12 27) 0 0,21 0 0,23 0 0,25 0 0,31 0 Завдання 3. Джерела А та В мають розподіли PA = {0,1; 0,1; 0,15; 0,125; 0,125; 0,1; 0,15; 0,15}, PB = {0,5; 0,3; 0,1; 0,025; 0,025; 0,02; 0,15; 0,15}. Ентропія якого джерела більша? Завдання 4. При передачі банківської інформації реченнями по 14 рядків на кожні 100 речень цифра 6 зустрічається 80 разів, а цифра 9 – 60 разів. Числа 69 і 96 зустрічаються 16 разів. Визначити умовну ентропію появи в реченні цифри 9, якщо в ньому є цифра 6, та умовну ентропію цифри 6, якщо в реченні з’явилася цифра 9. Контрольні питання: 1. Що таке ентропія та назвіть її властивості? 2. Які існують види ентропії? 3. Доведіть, що ентропія максимальна у випадку рівноймовірних повідомлень. Практична робота № 2 Тема: ЕКСПЕРИМЕНТАЛЬНЕ ВИЗНАЧЕННЯ ЕНТРОПІЇ ПОВІДОМЛЕННЯ Мета роботи: вивчення властивостей ентропії як кількісної міри інформації. Завдання 1 Обчислити ентропію дискретного джерела інформації: Х={х1,х2,х3,х4,х5,х6,х7,х8,х9,х10}, заданого розподілом р(хі). Значення р(хі) взяти з табл. 2.1. варіант вибрати згідно з порядковим номером у списку. Завдання 2 3. Два статистично незалежних джер ела А та В визначаються матрицею ймовірностей p(ai,bj) (див. таблицю 2.2 згідно варіанту). Визначити часткову та загальну умовну ентропію, ентропію об'єднання, безумовну ентропію цих джерел, а також кількість інформації, що припадає на пару повідомлень ai,bi. 4. Провести аналіз та оцінку одержаних результатів. Завдання 3. Джерела А та В мають розподіли PA = {0,1; 0,1; 0,15; 0,125; 0,125; 0,1; 0,15; 0,15}, PB = {0,5; 0,3; 0,1; 0,025; 0,025; 0,02; 0,15; 0,15}. Ентропія якого джерела більша? Завдання 4. При передачі банківської інформації реченнями по 14 рядків на кожні 100 речень цифра 6 зустрічається 80 разів, а цифра 9 – 60 разів. Числа 69 і 96 зустрічаються 16 разів. Визначити умовну ентропію появи в реченні цифри 9, якщо в ньому є цифра 6, та умовну ен тропію цифри 6, якщо в реченні з’явилася цифра 9. Таблиця 2.2 – Матриця ймовірностей p(ai,bj) № вар. p(ai,bj) № вар. p(ai,bj) № вар. p(ai,bj) 1) 0,1 0,25 0,1 0,14 0,16 0,1 0,1 0,04 0,01 2) 0,1 0,24 0,1 0,14 0,17 0,1 0,1 0,04 0,01 3) 0,1 0,24 0,1 0,14 0,17 0,1 0,1 0,04 0,01 4) 0,2 0,2 0,04 0,14 0,17 0,1 0,1 0,04 0,01 5) 0,2 0,01 0,04 0,14 0,4 0,1 0,1 0 0,01 6) 0,2 0,01 0,04 0,14 0,3 0,1 0,1 0,1 0,01 7) 0,01 0,01 0,04 0,15 0,4 0,18 0,1 0,1 0,01 8) 0,01 0,01 0,04 0,1 0,45 0,18 0,1 0,1 0,01 9) 0,01 0,02 0,04 0,1 0,44 0,18 0,1 0,1 0,01 10) 0,01 0,02 0,04 0,1 0,33 0,19 0,11 0,1 0,1 11) 0,01 0,15 0,04 0,1 0,23 0,19 0,08 0,1 0,1 12) 0,01 0,15 0,24 0,1 0,03 0,19 0,08 0,1 0,1 13) 0,01 0,08 0,24 0,1 0,03 0,19 0,15 0,1 0,1 14) 0,01 0,08 0,24 0,1 0,04 0,18 0,15 0,1 0,1 15) 0,01 0,08 0,23 0,1 0,05 0,18 0,15 0,1 0,1 16) 0,02 0,07 0,23 0,1 0,05 0,18 0,15 0,1 0,1 17) 0,02 0,07 0 0,29 0,05 0,18 0,15 0 0,24 18) 0,02 0,07 0,1 0,29 0,05 0,08 0,15 0 0,24 19) 0,02 0,07 0,14 0,15 0,15 0,08 0,15 0 0,24 20) 0,02 0,03 0,14 0,15 0,15 0,12 0,15 0 0,24 21) 0 0,03 0,14 0,15 0 0,12 0,15 0,41 0 22) 0,17 0,03 0 0,15 0 0,12 0 0,41 0,12 23) 0,12 0 0,1 0,15 0,03 0,12 0,05 0,31 0,12 24) 0,17 0 0,1 0,15 0,03 0,12 0 0,31 0,12 25) 0,12 0 0,07 0,15 0,06 0,12 0,05 0,31 0,12 26) 0,12 0,05 0,07 0,15 0,01 0,12 0,05 0,31 0,12 27) 0 0,21 0 0,23 0 0,25 0 0,31 0 Контрольні питання: 1. Що таке ентропія, види ентропії та назвіть їх властивості? 2. Доведіть, що ентропія максимальна у випадку рівноймовірних повідомлень.