3.2Структурні міри інформації

3.2.1Загальна характеристика структурної метрики

При використанні структурних мір враховується лише дискретна будова даного інформаційного комплексу, тобто кількість інформаційних елементів тих, що містяться в ньому, зв'язків між ними або комбінацій з них.

Під інформаційними елементами розуміються неподільні частини (кванти) інформації в дискретних моделях реальних інформаційних комплексів, а також елементи алфавітів у числових системах.

У структурній теорії розрізняють геометричну, комбінаторну і адитивну міри інформації.

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

3.2.2Геометрична міра інформації

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

Інформаційна ємкість може бути представлена числом, що показує, яка кількість квантів міститься в повному масиві інформації.

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

Якщо інформація представлена повним комплексом XTN і дискретні відліки здійснюються по осях X, Т і N відповідно через інтервали , і , то безперервні координати розпадаються на елементи (кванти), кількість яких складає:

Тоді кількість інформації у повному комплексі XTN визначена геометричним методом у квантах дорівнює:

.

Може мати місце нерівномірна (по осях) і нестаціонарна (змінна у часі) дискретизація. Тоді кількість інформації визначається по більш складніших залежностям.

3.2.3Комбінаторна міра інформації

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

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

Комбінування можливе в комплексах з неоднаковими елементами, змінними зв'язками або різноманітними позиціями. Елементи неоднакові, якщо вони відрізняються один від одного будь-якою ознакою – розміром, формою, кольором і тому подібне

Однакові по всіх своїх ознаках елементи можуть стати неоднаковими, якщо врахувати їх положення, позицію. Тоді місце розташування елементів робить вплив на ціле (позиційні системи числення, формування образів). Прикладом прояву впливовості елементів може бути перенесення знаків в позиційній системі двійкових чисел: 11110 і 01111 або 00001 і 10000. У першому випадку міняє положення нуль, в другому випадку – одиниця. У першому випадку число міняється з 30 на 15, в другому – одиниця перетворюється на 16.

У комбінаториці розглядаються різні види з’єднання елементів деяких скінченних множин.

Двома основними правилами комбінаторики є:

Принцип суми. Якщо множина A містить m елементів, а множина B – n елементів, і ці множини не перетинаються, то містить m+n елементів.

Принцип добутку. Якщо множина A містить m елементів, а множина B – n елементів, то AB містить mn елементів, тобто пар.

Кількість елементів множини A визначається її потужністю – |A|.

Ці правила мають також вигляд:

Принцип суми. Якщо об'єкт A можна вибрати m способами, а об'єкт B – n іншими способами, то вибір "або A, або B" можна здійснити m+n способами.

Принцип добутку. Якщо об'єкт A можна вибрати m способами і після кожного такого вибору об'єкт B може бути вибраним n способами, то вибір "A і B" в указаному порядку можна здійснити mn способами.

Наведені правила очевидним чином узагальнюються на випадки довільних скінченних об'єднань множин, що попарно не перетинаються, та на скінченні декартові добутки.

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

Нагадаємо, що з точки зору математики послідовність довжини m елементів множини A – це функція, яка натуральним числам 1, 2, …, m ставить у відповідність елементи з A.

Розміщення з повтореннями по l елементів h-елементної множини A – це послідовність елементів множини A, що має довжину l.

(2.1)

Якщо |A|=h, то за правилом добутку множина всіх розміщень з повтореннями, тобто множина A^l=AA…A, містить h^l елементів. Зокрема, якщо |A|=2, то розміщень з повтореннями 2^l. Зауважимо, що ці розміщення можна взаємно однозначно поставити у відповідність послідовностям з 0 і 1 довжини l.

У багатьох комбінаторних задачах об'єкти, кількість яких треба обчислити, являють собою послідовності, у яких перший елемент належить множині A₁, другий – A₂, тощо. Але досить часто множина A₂ визначається лише після того, як зафіксовано перший член послідовності, A₃ – після того, як зафіксовано перші два і т.д. Обчислимо, наприклад, кількість 7-цифрових телефонних номерів, у яких немає двох однакових цифр поспіль. Якщо на першому місці в номері є, наприклад, 1, то на другому може бути будь-яка з 9 інших цифр. І так само на подальших сусідніх місцях. Таким чином, тут |A₁|=10, |A₂|=|A₃|=…=|A₇|=9, і загальна кількість номерів є 109⁶.

Приклад 2.1.

При A={a, b, c} розміщення з повтореннями по два елементи – це пари (a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c).

Розміщення без повторень. Розміщення по l елементів h-елементної множини A, де lh – це послідовність елементів множини A, що має довжину l і попарно різні члени. За принципом добутку, можлива кількість таких послідовностей дорівнює

Q=h(h-1)…(h-l+1),

або використовуючи прийняті позначення

. (2.2)

Приклад 2.2.

При A={a, b, c} розміщення по два елементи – це пари (a,b), (a,c), (b,a), (b,c), (c,a), (c,b).

Приклад 2.3.

Розподіл h різних кульок по одній на кожний з l різних ящиків, lh. Ящики можна пронумерувати від 1 до l, кульки – від 1 до h. Тоді кожному розподілу взаємно однозначно відповідає послідовність довжини l попарно різних номерів від 1 до h. Неважко підрахувати кількість послідовностей. На першому місці може стояти будь-який із номерів 1, …, h. На другому – незалежно від того, який саме був на першому, будь-який із h-1, що залишилися. І так далі. Тоді можлива кількість таких послідовностей дорівнює

Q=h(h-1)…(h-l+1).

Перестановка без повторень. Перестановка h елементів множини A– це розміщення по h елементів, тобто послідовність елементів множини A, що має довжину h і попарно різні члени.

Очевидно, що кількість перестановок h елементів дорівнює кількості розміщень по m при , тобто:

. (2.3).

Приклад 2.4.

При A={a, b, c} усі перестановки – це трійки (a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a).

Комбінація без повторень. Комбінація по m елементів h-елементної множини – це її m-елементна підмножина.

З кожної m-елементної комбінації елементів h-елементної множини можна утворити m! перестановок елементів цієї підмножини. Їх можна розглядати як розміщення по m елементів. Таким чином, кожні m! розміщень із тим самим складом, але різним порядком елементів відповідають одній комбінації. Звідси очевидно, що кількість комбінацій є:

. (2.4)

Приклад 2.5.

При A={a, b, c} усі комбінації по два елементи – це підмножини {a,b}, {a,c}, {b,c}.

Приклад 2.6.

Розподіл h різних кульок по одній на кожний з m однакових ящиків, mh. Оскільки ящики однакові, то розподіл взаємно однозначно визначається підмножиною з m кульок, що розкладаються,тобто:

.

Перестановки з повтореннями. Перестановка з повтореннями по l елементів множини A={a₁, a₂, …, a_h} складу (k₁, k₂, …, k_h) – це послідовність довжини l=k₁+k₂+…+k_h, в якій елементи a₁, a₂, …, a_h повторюються відповідно k₁, k₂, …, k_h разів.

Кількість перестановок з повтореннями з елементів множини A={a₁, a₂, …, a_h} складу (k₁, k₂, …, k_h) позначається P(k₁, k₂, …, k_h) і дорівнює:

. (2.5)

Приклад 2.7.

При A={a, b, c} перестановками з повтореннями складу (1, 0, 2) є послідовності (a,c,c), (c,a,c), (c,c,a), складу (1, 1, 1) – (a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a).

Приклад 2.8.

Нехай l різних кульок розкладаються по h різних ящиках так, що в першому ящику k₁ кульок, у другому – k₂ кульок, …, у h-му – k_h кульок, причому l=k₁+k₂+…+k_h. Пронумеруємо кульки від 1 до l, ящики – від 1 до h. Задамо розподілення кульок як функцію, яка ставить у відповідність номеру кульки номер ящика, куди вона потрапила. Отже, маємо послідовність довжини l=k₁+k₂+…+k_h, в якій номери 1, 2, …, h повторюються k₁, k₂, …, k_h разів відповідно. Очевидно, що така функція відповідає розкладу кульок взаємно однозначно. Таким чином, розклад подається як перестановка з повтореннями складу (k₁, k₂, …, k_h).