Комбінаторне визначення кількості інформації з ХАРТЛИ
Білет №1
1. Теорія інформації: предмет, завдання, основні напрями і інформаційні характеристики.
2. Маршрутизація з урахуванням стану зв’язків, алгоритм Дейкстри.
Відповіді:
1) Теорія інформації займається вивченням кількісних закономірностей, пов'язаних з одержанням, обробкою, збереженням, передачею інформації і служить математичним апаратом опису процесів управління.
Через те, що передачі інформації властиві риси випадковості, теорія інформації є розділом теорії імовірностей.
До числа основних задач теорії інформації відносяться:
- пошук способів представлення інформації, зручних для передачі (кодування інформації);
- оцінка кількості інформації;
- визначення пропускної здатності каналу зв'язку для передачі інформації від джерела до приймача;
- забезпечення своєчасного і безпомилкового прийому інформації й інші.
Математичний опис закономірностей процесу передачі інформації складає зміст основних понять теорії інформації.
Таким чином, предметом теорії інформації є кількісні закономірності процесів одержання, перетворення (обробки), збереження і передачі інформації.
У рамках загальної теорії інформації варто виділити три основних напрямки, а саме структурний, статистичний і семантичний.
Структурна теорія інформації враховує тільки дискретну побудову розглянутої системи, кількість інформаційних елементів, що містяться, зв'язків між ними і можливими комбінаціями з цих елементів. Ця теорія застосовується для оцінки інформаційних можливостей систем поза залежністю від умов їхнього застосування (тобто без обліку статистики). Наприклад, оцінюються інформаційні можливості каналів зв'язку, пристроїв, що запам'ятовують і реєструють і т.д.
|
|
|
Статистична теорія інформації дозволяє оцінювати інформаційні можливості систем з урахуванням їхніх статистичних характеристик, тобто з урахуванням конкретного застосування розглянутих систем. У рамках цього напрямку істотно те, що цілком ігнорується зміст, цінність повідомлень.
Семантична теорія інформації враховує значеннєвий зміст інформації, що визначає її доцільність, істотність, корисність, цінність. Змістовність інформації оцінюється за ступенем істинності або хибності подій, за ефектом, що робить інформація на результат управління і т.д.
У теорії інформації під інформацією розуміють сукупність відомостей про будь-які події, процеси, явища і т.п., розглянуті в аспекті їхньої передачі в просторі і в часі.
Інформацію передають у виді повідомлень. Повідомленням називають інформацію, виражену у визначеній формі і призначену для передачі від джерела до адресата. Прикладами повідомлень служать тексти телеграм, мова, музика, телевізійне зображення, дані на виході комп'ютера, команди в системі автоматичного управління об'єктами і т.п.
|
|
|
Повідомлення передають за допомогою сигналів, що є носіями інформації. Основним видом сигналів є електричні сигнали. Останнім часом все більше поширення одержують оптичні сигнали, наприклад, у волоконно-оптичних лініях передачі інформації.
У теорії інформації вивчають властивості процесів, що мають місце при передачі інформації на відстань за допомогою сигналів. При цьому важливе значення мають поняття якості і швидкості передачі інформації.
Якість передачі інформації тим вище, чим меншим є перекручування інформації на прийомній стороні. Зі збільшенням швидкості передачі інформації потрібно вживати спеціальних заходів, що перешкоджають втратам інформації і зниженню якості передачі інформації.
2) Маршрутизація з урахуванням стану зв'язків. На початку функціонування мережі кожен вузол формує групу пакетів стану ліній LSA (Link State Advertisements). LSA-пакет містить ідентифікатори власного і сусіднього вузлів, а також вартість зв'язків між ними. На наступному кроці пакети стану ліній розсилаються широкомовно всім іншим вузлам мережі. Вузли, що одержали LSA-пакети від усіх маршрутизаторів мережі, паралельно один з одним створюють топологічну базу даних, утримуючі всі LSA-повідомлення. На основі отриманої інформації вузли розраховують шляхи з мінімальними вартостями. При цьому маршрутизатор розраховує топологію найкоротших шляхів у виді SPF-дерева, поміщаючи себе в корінь. Усякий раз, коли LSA-пакет викликає зміну в базі дані стани каналів, алгоритм обліку станів ліній перераховує шляхи й обновляє таблицю маршрутизації.
|
|
|
Алгоритм SPF гарантує правильне функціонування мережі при порушеннях зв'язку або виході з ладу окремих маршрутизаторів і виключає можливість дворазової передачі пакета по тому самому шляху. До алгоритмів, що використовують знання про топологію всієї мережі і враховуючої вартості зв'язків між усіма її вузлами, відноситься алгоритм Дейкстри (Dijkstra's algorithm) (Эдсгер Вайб Дейкстра). За допомогою цього алгоритму знаходяться найкоротші маршрути від даного вузла-джерела до всіх інших вузлів мережі.
На основі алгоритму Дейкстри найкоротші шляхи від заданого вузла-джерела до всіх інших вузлів мережі визначаються ітераційно (покроково) в процесі перебору маршрутів у порядку збільшення числа їхніх сегментів. Побудова шляхів відбувається поетапно. На 
-м кроці знаходяться шляхів з мінімальною вартістю до вузлів.
|
|
|
Для формального визначення алгоритму введемо наступні позначення:
– безліч вузлів мережі (вузлів комутації, оснащених маршрутизаторами);
– вузол-джерело;
– безліч вузлів, оброблених алгоритмом;
– «вартість шляху» від вузла 
до вузла 
, що при початковій ініціалізації встановлюється 
, 
, якщо ці вузли не є суміжними (сусідами) і 
, якщо вузли і – «сусіди»;
– вартість шляху від вузла до вузла 
.
Алгоритм містить 3 етапи.
Етап 1. Ініціалізація.
Для усіх вузлів 
і несуміжних із установлюємо 
, а 
. Безлічі привласнюємо значення 
, що означає – у безліч досліджених вузлів включене тільки вихідне вузол-джерело.
Визначаємо допоміжну множину 
вузлів 
, суміжних з (вузлів-сусідів). Для вузлів 
вартість шляхів приймаємо рівною 
.
Призначаємо поточним вузлом 
вузол-джерело 
.
Етап 2. Відшукання вузла, найближчого до вузла і не вхідного в безліч .
Здійснюється пошук наступного вузла графа мережі, що не входить у безліч і не має шлях з мінімальною вартістю від вузла-джерела до цього вузла. Знайдений вузол включається в безліч . Виконуються наступні операції:
- 
, для всіх , суміжних з вузлом . Обновимо значення поточного вузла 
.
Якщо «відстані» 
однакові для декількох вузлів , то 
, для якого мінімальна «вартість шляху» 
. У випадку рівності «шляхів» між визначеними вузлами-сусідями для вибору маршруту можуть бути використані іншиі критерії, наприклад, мінімальний IP - адрес;
- 
;
- перевірка умови 
, якщо «ТАК», те алгоритм закінчений (усі вузли графа відпрацьовані), якщо «НІ», те виконується наступний етап.
Етап 3. Відшукання шляху до вузла k з мінімальною вартістю.
Визначаємо допоміжну множину вузлів ( 
), суміжних з (вузлів-сусідів).
Відшукання такого шляху здійснюється відповідно до виразу:
для усіх вузлів і суміжних (сусідів) з вузлом .
Якщо множина 
порожня, то алогрітм вважається завершеним. Максимальне число кроків алгоритму рівне 
.
Етапи 2, 3 циклічно повторяться доти, поки не будуть визначені оптимальні (найкоротші) шляхи від вузла-джерела до усіх вершин мережі, тобто поки безліч не збіжиться з безліччю , що перевіряється на 2-му етапі.
На кожній ітерації до безлічі додається новий вузол , а значення 
на цей момент часу являє собою мінімальну вартість шляху від вузла-джерела до вузла . Шлях з найменшою вартістю повинний проходити тільки через вузли, що уже входять у безліч . Варто помітити, що на першій ітерації вузол повинний бути зв'язаний із джерелом прямо. Другий, що додається в безліч вузол, повинний бути зв'язаний прямо або з вузлом-джерелом, або з вузлом, уже доданим до безлічі . На наступних кроках значення шляхів з найменшою вартістю обновляється тільки для вузлів, ще не включених у безліч .
Основною гідністю алгоритму Дейкстри є його збіжність – число кроків алгоритму не перевищує 
. Недоліком є те, що у ряді достатніх окремих випадків визначені алгоритмом «найкоротші відстані» між деякими вузлами мережі не будуть такими.
Білет №2
1. Кількість інформації: визначення, властивості і основні співвідношення.
2. Алгоритми і протоколи маршрутизації в комп’ютерних мережах.
Відповіді
1) Тобто в загальному випадку мірою кількості інформації повинна служити величина, що вимірює зміну імовірності події під впливом повідомлення.
Разом з тим, доцільно пред'явити ще деякі вимоги до визначення кількості інформації. Варто врахувати, що (для дискретної системи) інформація передається звичайно не одним символом, а їх послідовністю. Розумно вимагати, щоб у випадку незалежних символів (повідомлень) загальна кількість отриманої інформації дорівнювало сумі кількостей інформації в окремих символах або повідомленнях. Ще більш загальна розумна вимога полягає в тім, щоб кількість інформації лінійно наростало з ростом числа символом (повідомлень) навіть і при наявності статистичної залежності між ними.
Задоволення цим вимогам призводить до наступного визначення кількості інформації, що не є єдино можливим і єдино застосовуваним, однак відповідає нашим інтуїтивним уявленням.
Кількість інформації в повідомленні про деяку подію, апріорна (до прийому повідомлення) імовірність якого 
, а апостеріорна (після прийому повідомлення) імовірність якого 
, визначимо як
, (1)
логарифм відносини відповідних імовірностей. Покажемо, що така міра зручна у світлі представлених вище вимог.
Розглянемо для простоти спочатку випадок, у якому відсутні шуми, тобто приймач приймає повідомлення безпомилково (узагалі говорячи в лініях зв'язку шуми (причина помилок) є завжди). У цьому випадку 
(імовірність події після прийому безпомилкового повідомлення про нього) і кількість інформації дорівнює
. (2)
Запитується, яку прийняти основу в логарифмі. Взагалі говорячи, це байдуже. Від цього міняється тільки масштаб. Можна, наприклад, прийняти основу 10 ( 
), тоді ми одержимо десяткову одиницю кількості інформації (дит). Для аналітичних розрахунків зручно застосувати натуральний логарифм ( 
), і відповідно з'являється натуральна одиниця кількості інформації (нат). Найчастіше (це зручно з погляду особливостей цифрової техніки) застосовують двійкові логарифми і відповідно двійкові одиниці інформації (біти). Біт — це кількість інформації ( 
біт) (десь і далі будемо позначати 
), що утримується в повідомленні про настання одного з двох рівноймовірних подій ( 
).
Співвідношення для визначення кількості інформації були отримані нами інтуїтивно. Обґрунтуємо справедливість (2).
У класичній теорії інформації відомо принаймні два визначення кількості інформації. Обидва визначення дуже близькі між собою, принципове розходження між ними з'являється лише при спробі ввести значеннєвий зміст інформації. Перше визначення (по ХАРТЛИ) використовує комбінаторний підхід, друге (по ШЕННОНУ) поширює на передачу й обробку інформації ймовірну точку зору.
Комбінаторне визначення кількості інформації з ХАРТЛИ
Нехай потужність деякого алфавіту A дорівнює m, тобто алфавіт складається з m дискретних символів, а кожне повідомлення включає n символів. У прийнятих позначеннях загальна кількість дискретних повідомлень, що може бути передано, дорівнює
. (3)
Приклад 1. Знайти загальну кількість дискретних повідомлень якщо повідомлення формується з двох символів ( 
), що належать алфавітові з трьох букв ( 
) А, В, С.
Відповідно до формули (3) число можливих повідомлень буде дорівнює 
, а саме АА, ВА, СА; АВ, ВВ, СВ; АС, ВС, СС.
Міра кількості інформації повинна задовольняти наступним вимогам:
- кількість інформації повинна дорівнювати нулю, якщо в системі можливий лише один результат;
- кількість інформації повинна мати властивість адитивності, тобто кількість інформації в повідомленні повинна бути пропорційна його довжині.
В цих умовах неважко бачити, що вираження (3) незручно брати як міру кількості інформації, тому що, по-перше, якщо вся безліч або ансамбль можливих повідомлень складається з одного повідомлення ( 
), то інформація в ньому повинна бути відсутня, по-друге, якщо є два незалежних джерела повідомлень, кожне з яких має у своєму ансамблі 
і 
повідомлень, то загальне число можливих повідомлень від цих двох джерел 
, тобто є добутком, тоді як кількості інформації повинні складатися, і загальна кількість повинна бути прямо пропорційною числу символів у повідомленні. Тому за кількість інформації 
узятий логарифм числа можливих повідомлень
. (4)
Дата добавления: 2023-01-08; просмотров: 20; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!