Нормальна форма Бойса-Кодда

Запитання: Чи можна, не аналізуючи проблем, що можуть виникнути при роботі з відношенням, визначити, чи потребує це відношення нормалізації?

Відповідь: Якщо відношення знаходиться в нормальній формі Бойса-Кодда (НФБК), то воно майже напевно не потребує декомпозиції і може застосовуватися в РБД, інакше потрібна його нормалізація.

Відношення знаходиться в НФБК, якщо і тільки якщо кожний детермінант відношення є можливим ключем відношення.

Що стосується можливих ключів універсального відношення НАВАНТАЖЕННЯ, то їх два й обидва вони складові:

<Код_одержувача, Код_вантажу>;

<Код_одержувача, Найм_вантажу>.

4.3.2. Функціональні залежності

Детермінант. Нехай дані 2 атрибути: А та В, то говорять, що атрибут В функціонально залежить від атрибуту А, якщо для кожного значення атрибуту А існує рівно одне пов'язане з ним значення атрибуту В (у будь-які моменти часу). Або навпаки, атрибут А є детермінантом атрибуту В. А й В можуть бути складовими, тобто кожний з них може бути складений з декількох атрибутів.

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

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

Візьмемо два атрибути <Назва_одержувача> та <Код_одержувача>.

Переглянувши екземпляр відношення можна установити, що одному значенню атрибута <Код_одержувача> відповідає одне значення атрибута <Назва_одержувача>. Отже, можна припустити, що атрибут <Назва_одержувача> функціонально залежить від атрибута <Код_одержувача>.

Тепер перевіримо за змістом це припущення. А чи може одержувач з певним кодом мати іншу назву?

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

З іншого боку, чи може той самий одержувач мати кілька різних назв? Очевидно, що ні, якщо інше не обговорено окремо чи спеціально. Якщо такого застереження нема, то можна зробити остаточний висновок про те, що між атрибутами <Код_одержувача> і <Назва_одержувача> дійсно існує функціональна залежність, причому атрибут <Код_одержувача> є детермінантом атрибута <Назва_одержувача>.

Необхідно перевірити, чи є зворотна функціональна залежність між цими атрибутами.

У представленому екземплярі відношення зустрічається значення атрибута <Назва_одержувача>, якому відповідають два значення атрибута <Код_одержувача>. Два одержувачі 1010 і 1425 мають однакові назви. Отже, зворотна функціональна залежність між цими атрибутами відсутня. Атрибут <Назва_одержувача> не є детермінантом атрибута <Код_одержувача>.

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

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

Наприклад: атрибут <Маса_вантажу> функціонально не залежить від жодного атрибута відношення НАВАНТАЖЕННЯ. Пара атрибутів <Код_одержувача, Код_вантажу> є детермінантом для атрибута <Маса_вантажу>. Кожний з атрибутів пари є детермінантом: <Код_одержувача> для атрибутів <Назва_одержувача> і <Код_ЄСР>, <Код_вантажу> для атрибута <Найм_вантажу>.

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

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

Схема функціональних залежностей між атрибутами відношення НАВАНТАЖЕННЯ(Код_одержувача, Назва_одержувача, Код_ЄСР, Код_вантажу, Найменування_вантажу, Маса_вантажу) представлена на рисунку 7.

Висновок: не кожний детермінант є можливим ключем, а тільки 4-й та 5-й. Тому відношення НАВАНТАЖЕННЯ не знаходиться в НФБК, отже потрібна його декомпозиція.

На цьому закінчується другий етап проектування РБД.

Лекція 7

4.4. ER- метод нормалізації відношень

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

Існують й інші підходи до розв’язання цієї проблеми. Ми розглядатимемо лише один з них. Це так званий ER-методнормалізації відношень. Назва прийнята по перших буквах англійських слів: entity (E) – сутність і relationship (R) – зв'язок.

4.4.1. Поняття сутності та зв'язку

3-й етап проектування РБД є штучним в тому смислі, що він зовсім не піддається формалізації. Суть його полягає у виділенні з ненормалізованого відношення сутностей (як правило двох) і встановлення зв'язку між ними.

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

ПРИКЛАД: Проектується РБД для збереження інформації про викладачів факультету, які читають курси лекцій студентам.

В РБД йдеться про два набори об'єктів: набір викладачів та набір курсів лекцій. Тобто маємо справу з двома сутностями: ВИКЛАДАЧ та КУРС.

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

Між двома сутностями ВИКЛАДАЧ та КУРС існує зв'язок ЧИТАЄ.

Зв'язок – це залежність (графічно – з'єднання) між двома і більше сутностями. В більшості випадків це є дієслово. Назви сутностей і зв’язку між ними прийнято писати великими буквами.

Зв’язок між двома сутностями називається бінарним. В процесі проектування РБД будемо розглядати тільки бінарні зв'язки, тому далі слово «бінарний» будемо опускати.

Кожний викладач має свій номер (№викладача), курс – також (№курс). №викладача та №курсу – це атрибути відповідних сутностей.

Атрибут – властивість сутності. (Не плутати з атрибутом відношення, це деяким чином різні поняття!) У принципі кожен атрибут може бути виділений в окрему сутність. Питання лише в тім, а чи варто це робити.

Для уявлення характеру зв’язку між сутностями складають діаграму ER-екземплярів

 

В1, В2,…, К1, К2,… – це екземпляри відповідних сутностей.

Лініями відповідності з’єднані екземпляри відповідних протилежних сутностей. Ними вказують які викладачі читають які курси.

Для того, щоб розподілити атрибути ненормалізованого відношення між сутностями складають діаграму ER-типу.

 

 

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

Обов’язково у списках атрибутів діаграми ER-типу повинні бути ключі відповідних сутностей.

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

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

Лекція 8

4.4.2. Тип зв'язку

Тип зв’язку можна визначити за діаграмою ER- екземплярів.

Поняття «тип зв’язку» має дві складові:

– ступінь зв’язку;

– клас належності зв’язаних сутностей.

Розглянемо ці поняття на прикладах з викладачами, що читають курси лекцій.

 

На 4-му етапі за допомогою діаграми ER-екземплярів проектувальник РБД визначає тип зв'язку, а за допомогою діаграми ER-типу розподіляє атрибути відношення між сутностями і вже потім визначає ключ кожної сутності.

Лекція 9

4.4.3. Побудова попередніх відношень

Наступний етап проектування РБД полягає в тому, щоб за допомогою одного з шести правил виводу (так званих правил Джексона) скласти набір попередніх відношень.

Вибір правила здійснюється на підставі встановленого типу зв'язку. Розглянемо як користуватися цими правилами на прикладах проектування РБД для деканату, в який повинні відбиватися відомості про закріплення викладачів за лекційними курсами.

4.4.3.1. Правило №1

Таблиця 10

Універсальне відношення 1:

№викладача	Прізвище	Кафедра	№курсу	Семестр
В1	Іванов	Станції	К2
В2	Петров	Станції	К1
В3	Сидорів	УЕР	К3

Правило №1. Якщо тип бінарного зв'язку 1:1, то потрібне лише одне відношення. Первинним ключем цього відношення може бути будь-який із ключів виділених сутностей.

Тобто універсальне відношення 1 не потребує нормалізації. Первинним ключем цього відношення може бути призначений атрибут №викладача (ключ сутності ВИКЛАДАЧ) або атрибут №курсу (ключ сутності КУРС).

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

Якщо при з’ясуванні детермінантів та можливих ключів універсального відношення 1 припустилися помилки, то все одно, відповідно до правила №1, в РБД залишиться одне відношення.

4.4.3.2. Правило №2

Таблиця 11

Універсальне відношення 2:

№викладача	Прізвище	Кафедра	№курсу	Семестр
В1	Іванов	Станції	К2
В2	Петров	Станції	К1
В3	Сидорів	УЕР	К4
-	-	-	К3

Правило №2. Якщо тип бінарного зв'язку 1:1 або 1:1, то достатньо двох відношень: по одному для кожної сутності, ключі яких використовуються в якості первинних у відповідних відношеннях. Додатково ключ необов'язкової сутності додається як атрибут у відношення, виділене для обов'язкової сутності.

Відповідно до вимог правила 2 складаємо два відношення спочатку в скороченому вигляді. Їх ще називають схемами відношень.

1) ВИКЛАДАЧ2(№викладача, Прізвище, Кафедра, №курсу);

2) КУРС2(№курсу, Семестр).

Зауважимо, що атрибут №курсу, як ключ необов'язкової сутності КУРС, доданий у відношення ВИКЛАДАЧ2.

А тепер подамо отримані відношення разом із даними у вигляді таблиць.

Таблиця 12 Таблиця 13

Відношення ВИКЛАДАЧ2: Відношення КУРС2:

№викладача	Прізвище	Кафедра	№курсу		№курсу	Семестр
В1	Іванов	Станції	К2		К2
В2	Петров	Станції	К1		К1
В3	Сидорів	УЕР	К3		К3
					К4

4.4.3.3. Правило №3

Таблиця 14

Універсальне відношення 3:

№викладача	Прізвище	Кафедра	№курсу	Семестр
В1	Іванов	Станції	К2
В2	Петров	Станції	-	-
В3	Сидорів	УЕР	К1
В4	Шевченко	АТЗ	К3
-	-	-	К4

Правило №3. Якщо тип бінарного зв'язку 1:1, то достатньо трьох відношень: по одному для кожної сутності, ключі яких використовуються в якості первинних у відповідних відношеннях, і ще одне відношення для зв'язку. Відношення зв'язку повинне мати серед своїх атрибутів ключ від кожної сутності.

Відповідно до вимог правила 3 складаємо спочатку три схеми відношень.

1) ВИКЛАДАЧ3(№викладача, Прізвище, Кафедра);

2) КУРС3(№курсу, Семестр);

3) ВИКЛАДАЧ3–КУРС3(№викладача, №курсу).

Зауважимо, що у відношенні зв'язку ВИКЛАДАЧ3–КУРС3 цілком можливо призначити первинним ключем атрибут №курсу.

А тепер подамо отримані відношення разом із даними у вигляді таблиць.

Таблиця 15 Таблиця 16 Таблиця 17

Відношення ВИКЛАДАЧ3: Відношення КУРС3: Відношення ВИКЛАДАЧ3–КУРС3:

№викладача	Прізвище	Кафедра		№курсу	Семестр		№викладача	№курсу
В1	Іванов	Станції		К2			В1	К2
В2	Петров	Станції		К1			В3	К1
В3	Сидорів	УЕР		К3			В4	К3
В4	Шевченко	АТЗ		К4

4.4.3.4. Правило №4

Таблиця 18

Універсальне відношення 4:

№викладача	Прізвище	Кафедра	№курсу	Семестр
В3	Сидорів	УЕР	К1
В1	Іванов	Станції	К2
В2	Петров	Станції	К3
В5	Муха	Станції	К4
В5	Муха	Станції	К5
В7	Семенов	Екон	К6
В4	Шевченко	АТЗ	-	-
В6	Савенко	Екон	-	-

Правило №4. Якщо тип бінарного зв'язку n : 1, n : 1, 1 : n або 1 : n то достатньо двох відношень: по одному для кожної сутності, ключі яких використовуються в якості первинних у відповідних відношеннях. Додатково ключ однозв'язкової сутності додається як атрибут у відношення, відведене для багатозв'язкової сутності.

Відповідно до вимог правила 4 складаємо спочатку дві схеми відношень.

1) ВИКЛАДАЧ4(№викладача, Прізвище, Кафедра);

2) КУРС4(№курсу, Семестр, №викладача).

Зауважимо, що атрибут №викладача, як ключ однозв’язкової сутності ВИКЛАДАЧ, доданий у відношення КУРС4.

А тепер подамо отримані відношення разом із даними у вигляді таблиць.

Таблиця 19 Таблиця 20

Відношення ВИКЛАДАЧ4: Відношення КУРС4:

№викладача	Прізвище	Кафедра		№курсу	Семестр	№викладача
В3	Сидорів	УЕР		К1		В3
В1	Іванов	Станції		К2		В1
В2	Петров	Станції		К3		В2
В5	Муха	Станції		К4		В5
В7	Семенов	Екон		К5		В5
В6	Савенко	Екон		К6		В7

4.4.3.5. Правило №5

Таблиця 21

Універсальне відношення 5:

№викладача	Прізвище	Кафедра	№курсу	Семестр
В3	Сидорів	УЕР	К1
В2	Петров	Станції	К2
В2	Петров	Станції	К3
В5	Муха	Станції	К4
-	-	-	К5
В5	Муха	Станції	К6
В5	Муха	Станції	К7
В1	Іванов	Станції	-	-
В4	Шевченко	АТЗ	-	-
В6	Савенко	УЕР	-	-

Правило №5. Якщо тип бінарного зв'язку 1 : n або 1 : n, n : 1, n : 1, то достатньо трьох відношень: по одному для кожної сутності, ключі яких використовуються в якості первинних у відповідних відношеннях, і ще одне відношення для зв'язку. Відношення зв'язку повинне мати серед своїх атрибутів ключ від кожної сутності.

Відповідно до вимог правила 5 складаємо спочатку три схеми відношень.

1) ВИКЛАДАЧ5(№викладача, Прізвище, Кафедра);

2) КУРС5(№курсу, Семестр);

3) ВИКЛАДАЧ5–КУРС5(№викладача, №курсу).

Зауважимо, що у відношенні зв'язку ВИКЛАДАЧ5–КУРС5 в якості первинного ключа використовується атрибут №курсу. А взагалі, завжди коли для виводу попередніх відношень використовується правило №5, у відношенні зв'язку первинним ключем призначається ключ багатозв'язкової сутності.

А тепер подамо отримані відношення разом із даними у вигляді таблиць.

Таблиця 22 Таблиця 23 Таблиця 24

Відношення ВИКЛАДАЧ5: Відношення КУРС5: Відношення ВИКЛАДАЧ5–КУРС5:

№викладача	Прізвище	Кафедра		№курсу	Семестр		№викладача	№курсу
В3	Сидорів	УЕР		К1			В3	К1
В2	Петров	Станції		К2			В2	К2
В5	Муха	Станції		К3			В2	К3
В1	Іванов	Станції		К4			В5	К4
В4	Шевченко	АТЗ		К5			В5	К6
В6	Савенко	УЕР		К6			В5	К7
				К7

4.4.3.6. Правило №6

Таблиця 25

Універсальне відношення 6:

№викладача	Прізвище	Кафедра	№курсу	Семестр
В3	Сидорів	УЕР	К1
В2	Петров	Станції	К2
В2	Петров	Станції	К3
В5	Муха	Станції	К4
-	-	-	К5
В5	Муха	Станції	К6
В5	Муха	Станції	К7
В1	Іванов	Станції	К4
В4	Шевченко	АТЗ	-	-
В6	Савенко	УЕР	-	-

Правило №6. Якщо тип бінарного зв'язку m : n , m : n, m : n , або m : n, то достатньо трьох відношень: по одному для кожної сутності, ключі яких використовуються в якості первинних у відповідних відношеннях, і ще одне відношення для зв'язку. Відношення зв'язку повинне мати серед своїх атрибутів ключ від кожної сутності.

Відповідно до вимог правила 6 складаємо спочатку три схеми відношень.

1) ВИКЛАДАЧ6(№викладача, Прізвище, Кафедра);

2) КУРС6(№курсу, Семестр);

3) ВИКЛАДАЧ6–КУРС6(№викладача, №курсу).

Зауважимо, що у відношенні зв'язку ВИКЛАДАЧ6–КУРС6 в якості первинного ключа використовується пара атрибутів №викладача і №курсу. А взагалі завжди, коли для виводу попередніх відношень використовується правило №6, у відношенні зв'язку первинним ключем призначається пара атрибутів, складена з ключів обох сутностей.

А тепер подамо отримані відношення разом із даними у вигляді таблиць.

Таблиця 26 Таблиця 27 Таблиця 28

Відношення ВИКЛАДАЧ6: Відношення КУРС6: Відношення ВИКЛАДАЧ6–КУРС6:

№викладача	Прізвище	Кафедра		№курсу	Семестр		№викладача	№курсу
В3	Сидорів	УЕР		К1			В3	К1
В2	Петров	Станції		К2			В2	К2
В5	Муха	Станції		К3			В2	К3
В1	Іванов	Станції		К4			В5	К4
В4	Шевченко	АТЗ		К5			В5	К6
В6	Савенко	УЕР		К6			В5	К7
				К7			В1	К4

Зверніть увагу, що кількість кортежів у відношеннях, відведених під сутності, дорівнює кількості екземплярів відповідної сутності, поданих на діаграмі ER-екземплярів. Кількість кортежів у відношеннях зв'язку дорівнює кількості ліній відповідності на діаграмі ER-екземплярів.

4.5. Перевірка отриманих відношень.

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

Коли всі атрибути розподілені між відношеннями (наразі ці відношення після розподілу всіх атрибутів називаються пробними), їх необхідно перевірити, чи знаходяться вони в НФБК. Для цього необхідно дослідити функціональні залежності між атрибутами кожного пробного відношення. Якщо якесь пробне відношення не знаходиться в НФБК, то з цим відношенням потрібно виконати ще один цикл нормалізації, і так доти, поки не приведемо всі відношення до НФБК.

Щоб уникнути проблем, що можуть виникнути при роботі з застосуванням БД, до РБД включаються лише ті відношення, що знаходяться в НФБК.

На цьому закінчується проектування РБД і починається розробка застосування БД.

Етапи розробки застосувань РБД і роботи з ними на ЕОМ докладно розглядається на лабораторних заняттях.

Лекція 10

5. ОСНОВНІ ПОНЯТТЯ ТЕОРІЇ ІНФОРМАЦІЇ

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

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

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

Звідси випливає дві задачі теорії інформації:

1. пошук економних методів кодування інформації;

2. визначення кількості та потужності пристроїв, що запам'ятовують та зберігають інформацію (обсягу пам'яті ЕОМ, пропускної спроможності каналів зв'язку).

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

Повідомлення – це сукупність відомостей про стан деякої системи.

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

Повідомлення має сенс тільки в тому випадку, коли стан системи наперед невідомий та ще й випадковий.

Такий системі Х апріорі (тобто до одержання повідомлення про її стан) властивий деякий ступінь невизначеності. Як його (цей ступінь невизначеності) вимірити чи обчислити?

Розглянемо три приклади:

1-й приклад. Система ВАГОН має два можливі стани:

– 1-й стан: вагон завантажений;

– 2-й стан: вагон порожній.

2-й приклад. Система ВАГОН має 5 можливих станів:

– 1-й стан: вагон критий;

– 2-й стан: піввагон вагон порожній;

– 3-й стан: платформа вагон Критий;

– 4-й стан: цистерна піввагон вагон порожній;

– 5-й стан: хопер вагон.

Для кожного прикладу стани системи ВАГОН рівноймовірні. Ступінь невизначеності системи ВАГОН в другому прикладі більше за перший приклад. Таким чином, чим більше можливих станів має система, тим більший ступінь невизначеності системи, але невизначеність системи залежить не тільки від кількості можливих станів системи.

3-й приклад. Система ВАГОН має два можливі стани:

– 1-й стан: вагон справний, ймовірність перебування системи ВАГОН в 1-му стані Р₁= 0,95;

– 2-й стан: вагон несправний, ймовірність перебування системи ВАГОН в 1-му стані Р₂= 0,05.

Ступінь невизначеності системи ВАГОН в третьому прикладі менше за перший приклад.

Система ВАГОН в третьому прикладі має малий ступінь невизначеності тому що майже напевно вагон виявиться справним. У прикладі із навантаженим чи порожнім вагоном, де ймовірність перебування системи ВАГОН в одному зі станів Р₂=Р₁=0,5, ступінь невизначеності системи значно більший.

Висновок: ступінь невизначеності системи залежить від кількості її можливих станів, а також від ймовірностей цих станів.

В загальному вигляді систему Х з кінцевою множиною станів можна подати як статистичний ряд спостережень випадкових подій, де можливі стани системи – це події.

Таблиця 29

	X	X1...	X2	....	Xn
	P	Р1,..	Р2.	....	Рn

де X₁, X₂... .... .X_n – стани системи Х,

n – кількість можливих станів системи Х,

Р₁, Р₂... .... Р_n – ймовірність перебування системи Х в і-му стані.

Сума ймовірностей можливих станів системи дорівнює одиниці, тобто стани системи складають повну групу подій.

5.1. Одиниці виміру ступеню невизначеності системи

Мірою апріорної (до одержання повідомлення) невизначеності системи Х в теорії інформації є ентропія.

, (Чому потрібний знак мінус, тому що логарифм чисел менших за одиницю величина від’ємна, ≤ )

де – лічильник можливих станів системи;

– загальна кількість можливих станів системи;

– ймовірність перебування системи в і-му стані;

– будь-яке ціле число більше за одиницю. Від нього залежить розмірність ентропії. Тобто вибір величини відповідає вибору одиниць виміру ентропії: – десяткові, – двійкові.

Оскільки всі ð, тому ентропія невід’ємна величина.

На практиці зручно прийняти , тому що це добре співвідноситься з двійковою системою подання інформації в ЕОМ .

За одиницю виміру ентропії прийнятий ступінь невизначеності системи, що має два рівноймовірні стани, й називається ця одиниця біт (bit: binary digit – двійкова цифра).

біт

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

Ентропія системи, яка має рівноймовірних станів, дорівнює логарифму числа можливих станів системи.

,

бо ймовірність і-го стану системи .

Наприклад, ентропія системи , що має рівноймовірних станів:

біт байт.

5.2. Властивості ентропії

1. Ентропія системи, стан якої відомий, дорівнює нулю.

,

бо границя невизначеності .

Якщо стан системи відомий, це означає, що ймовірність одного зі станів системи дорівнює одиниці, решти – нулю.

2. Ентропія системи з кінцевою множиною можливих станів досягає максимуму, якщо всі стани системи рівноймовірні.

.

Приклад 1. Розрахуємо ентропію інвентарного № вагона. Інвентарний № вагона складається з -ми цифр; число можливих станів системи – , тому що -у цифру не можна вважати випадковою.

біт.

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

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

Система може перебувати в одному з трьох станів:

– на вантажний район за добу не прибуло жодного піввагона, :

;

– на вантажний район за добу прибув один піввагон, :

;

– на вантажний район за добу прибуло два піввагона, :

.

Таблиця 30

Стан системи
Кількість піввагонів
Ймовірність

 

біт.

Лекція 11

5.3. Ентропія та інформація

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

,

де – отримана інформація про стан системи, яку можна оцінити за допомогою ентропії.

.

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

Повна інформація про стан системи дорівнює ентропії цієї системи. А формула для її розрахунку має дещо інший вигляд:

.

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

Інформацію від окремого повідомлення про перебування системи в і-му стані називають частковою інформацією.

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

,

де – випадковий стан системи.

Саме тому повну інформацію називають ще середньою інформацією про стан системи.

Коли всі стани системи рівноймовірні часткова інформація дорівнює повній.

.

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

Висновок: найбільша часткова інформація міститься в повідомленні про найменш ймовірний стан системи.

Наприклад:

нехай , тоді біт,

але якщо , тоді біт.

Розрахуємо часткову інформацію про прибуття на вантажний район одного, двох піввагонів чи не прибуття жодного:

, біт,

, біт,

, біт.

5.4. Ентропія як міра кількості інформації

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

При цьому абстрагуються від змісту цієї інформації.

Приклад.

Нехай система має 4 стани з ймовірностями ; ; . Для передачі повідомлення про стан системи можна скористатися двобітовими кодами:

~; ~; ~; ~.

Щоб передати повідомлень треба мати канал зв’язку потужністю біт за секунду (бод).

Розрахуємо ентропію системи:

Тобто повна інформація про стан системи :

біта.

Як бачимо, для з'ясування стану системи достатньо в повідомленні передавати в середньому всього біта інформації, а не біта, як ми припускали.

Часткова інформація від кожного повідомлення про стан системи S є різною.

Кількість інформації в кожному окремому повідомленні про те, чи знаходиться система S в і-му стані дорівнює:

- в -му стані біт,

- в -му стані біта,

_- в -му чи -му стані біта.

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

У відповідності до отриманих даних про часткову інформацію від окремих повідомлень складемо коди для їхньої передачі інакше:

~(1 біт); ~(2 біта); ~(3 біта); ~(3 біта).

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

*До речі, розділяти повідомлення між собою не треба, можна відрізнити одне повідомлення від іншого й без роздільників.

Алгоритм розпізнавання змісту повідомлення: якщо перший символ , то це (і кінець), інакше, якщо другий символ , це (і кінець), інакше, якщо третій символ , це (і кінець), інакше це .

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

Відшукаємо математичне сподівання кількості біт інформації для передачі окремого повідомлення префіксним кодом:

біта.

де – кількість біт в окремому повідомленні про стан системи .

Відповідно для передачі повідомлень префіксним кодом треба мати канал зв’язку потужністю біт за секунду (бод), а не , як при використанні рівномірного коду.

Рівність повної інформації та ентропії системи є ознакою оптимального кодування повідомлень про її стан.

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

Якщо б всі стани системи були б рівноймовірні, то користуватися цим кодом було б недоречно. Доведемо це.

Розрахуємо ентропію системи з чотирма рівноймовірними станами:

біта,

а повна інформація про стан цієї системи, якщо скористатися префіксним кодом:

біт.

В цьому випадку треба скористатися рівномірним кодом з однаковим числом знаків в кожному повідомленні:

біта.

Для кодування повідомлень про стан системи треба скористатися рівномірним кодом. Рівність ентропії системи та повної інформації про її стан є ознакою оптимального кодування повідомлень.

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

Саме так розробляють оптимальні коди повідомлень, а також розраховують потужність каналів зв’язку та запам’ятовуючих пристроїв.

Лекція 12

5.5. Кодування дискретних повідомлень

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

Інформація безпосередньо від джерела користувачеві передається за допомогою повідомлень. Впорядкована послідовність кодових символів (сигналів) називається повідомленням.

Коли повідомлення потрібно передавати по каналах зв'язку, кожний символ (сигнал) повідомлення подається у вигляді ряду інших кодових символів (приклад – абетка Морзе, де кожна буква або цифра повідомлення подається у вигляді різних комбінацій двох символів: точка і тире).

5.5.1. Запис повідомлення за допомогою кодів

Дискретне повідомлення складається з кінцевого числа символів, кожний символ повідомлення можна пронумерувати, тоді текст повідомлення можна подати як послідовність чисел – номерів символів у списку.

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

,

де – загальна кількість різних символів , які можуть зустрічатися в повідомленні.

Наприклад: розглянемо повідомлення, у якому можуть зустрічатися 80 символів:

.

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

Алфавіт – це множина символів , за допомогою яких кодуються елементи повідомлення.

,

де – загальна кількість символів (цифр) алфавіту .

Загальна кількістькодових символівалфавітуназивається основою коду.

Алфавіти відмінні загальною кількістю символів, які мають використовуватися при кодуванні повідомлення.

Наприклад:

– двійковий алфавіт: , ,

– вісімковий алфавіт: , ,

– десятковий алфавіт: , ,

– шістнадцятковий алфавіт: , .

З символів алфавіту можна складати кодові слова або кодові комбінації:

,

де – довжина кодового слова К.

Зверніть увагу на незвичайну індексацію кодових символів: символи кодового слова нумерують справа наліво, починаючи з нуля й називають розрядами.

Приклад:

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

, , , .

, , , .

У кодовому слові біт (розрядів), в алфавіті – символів (цифр).

Скільки різних слів довжиною можна записати за допомогою алфавіту з основою коду ?

раз

де – загальна кількість кодових слів .

Приклад: скільки різних –розрядних кодових слів можна записати за допомогою двійкового алфавіту?

, , слів

де – основа коду,

– довжина кодового слова.

За допомогою алфавіту можна скласти –бітових кодових слів.

Для кодування повідомлень довжиною символів, треба щоб загальна кількість кодових слів N₀ була б не менше за кількість кодових слів, які використовуються для кодування всіх можливих символів повідомлення N.

Тобто потрібно щоб завжди виконувалася умова:

≤.

Приклад:

Для кодування повідомлень потрібно кожному елементу повідомлення поставити в однозначну відповідність деяке кодове слово:

,

тобто

~, .

Загальний список кодових слів називається кодом. В списку може бути не більше кодових слів.

Перетворювання повідомлень з однієї форми в іншу за допомогою коду називається кодуванням повідомлення.

Таким чином кодове слово можна розглядати як -розрядне число в системі числення з основою :

.

Наприклад: можна розглядати як -розрядне двійкове число.

Ця обставина дозволяє легко перетворювати коди, переводячи відповідні числа з однієї системи числення в іншу.

При фізичному опрацюванні даних на ЕОМ використовується двійкове кодування чисел (фізично – немає імпульсу, – є). З цими імпульсами оперують ЕОМ.

Лекція 13

5.5.2. Способи перетворювання кодів

Перетворення цілих чисел з однієї системи числення з основою

Развернуть

Открыть в широком формате