Кількість інформації згідно Р. Хартлі

Объединенная вероятностная схема

Імовірнісна схема

Вступ

Література.

Час – 2 год.

Навчальні питання

Лекція 3. Кількість інформації та ентропія

Задачі

Контрольні питання

Висновки

1. Які існують типи шифрів підстановки?

2. Які існують типи шифрів перестановки?

3. Наведіть приклад шифру Цезаря і його криптоаналіз.

4. Наведіть приклад шифру простої заміни.

5. Як можна здійснити криптоаналіз шифру простої заміни?

6. Наведіть приклад шифру Віженера.

7. У чому суть методу підрахунку числа збігів криптоаналізу шифру Віженера?

8. У чому суть методу Казіски криптоаналізу шифру Віженера?

9. Наведіть приклад шифру Вернама.

10. Наведіть приклад шифру Плейфера.

11. Наведіть приклад шифру перестановки.

Задача 1. Следующая криптограмма о президенте Кеннеди (Kennedy) получена с помощью простой замены. Определите открытый текст.

Задача 2. Дешифруйте следующий шифртекст, полученный при использований шифра Плэйфэра с ключом (как в разд. 2.3.2).

Задача 3. Зашифруйте следующий текст, с помощью шифра Виженера с ключом .

Задача 4. Рассмотрим криптограмму, полученную с помощью шифра Цезаря. Напишите программу в пакете "Mathematica" для поиска всех подстрок длины 5 в шифртексте, которые могли бы быть получены из слова . Проверьте эту программу на тексте из табл. 2.1. (См. также входную строку в примере 2.2).

1.... Імовірнісна схема. 1

2.... Кількість інформації згідно Р. Хартлі 3

3.... Кількість інформації за К. Шеноном.. 5

4.... Аксіоми Хінчина і Фадєєва. 7

1. Духин, Александр Александрович. Теория информации: Учебное пособие / А.А.Духин. - М.: Гелиос АРВ, 2007.

2. Стариченко Б. Е. Теоретические основы информатики: Учебное пособие для вузов. - 2-е изд. перераб. и доп. - М.: Горячая линия - Телеком, 2003.

3. Дмитриев В.И. Прикладная теория информации. Учебник для студентов ВУЗов по специальности «Автоматизированные системы обработки информации и управления». – М.: Высшая школа, 1989 – 320 с.

Исходным понятием в теории информации является понятие вероятностной схемы. Пусть - вероятностное пространство[1], где

W ‑ произвольное множество, элементы которого называются элементарными событиями, исходами или точками;

M – некоторая зафиксированная система подмножеств M Ì W ‑ случайных событий, удовлетворяющая свойствам σ(сигма)-алгебры:

· Пустое множество Æ должно быть событием, то есть принадлежать M. Это событие, которое существует в любом вероятностном пространстве, называется невозможным, поскольку оно никогда не происходит.

· Все множество W также должно быть событием: W Î M. Это событие называется достоверным, так как происходит при любой реализации случайного опыта.

· Совокупность событий M должна образовывать алгебру, то есть быть замкнутой относительно основных теоретико-множественных операций, выполняемых над конечным числом событий. Если A Î M и B Î M, тогда должно быть AÈB ÎM, AÇB ÎM, `A=W ‑AÎM. Операции над событиями имеют очевидный содержательный смысл.

· В дополнение к указанным свойствам, система M должна быть замкнута относительно операций над событиями, выполняемых в счетном числе (свойство s-алгебры). Если , тогда должно быть и .

Р ‑ это числовая функция, которая определена на M и ставит в соответствие каждому событию B Î M число P(B), которое называется вероятностью события B. Эта функция должна быть конечной сигма-аддитивной мерой, равной 1 на всем пространстве, то есть обладать свойствами:

§ 0≤P(B)≤1 для любого B Î M;

§ P(Æ) = 0, P(W)= 1;

§ Если A Î M и B Î M — события, причем AÇB =Æ, тогда P(AÈB)=P(A)+P(B) (свойство аддитивности).

§ Если , причем если B_iÇB_j=Æ для любых i¹j, тогда должно быть (свойство сигма-аддитивности).

Пусть ‑ полная группа попарно несовместимых исходов события A.

Определение 1.1. Параназывается вероятностной схемой события .

Говорят, что вероятностная схема А дискретна, если число событий не более чем счётно. В этом случае будем записывать в виде:

(1)

где а_k - исход вероятностной схемы, p_k - вероятность исхода,

, .

Если число исходов {а_k} более чем счётно, то вероятностная схема А называется непрерывной. Тогда её задают, описывая множество возможных исходов и указывая с помощью плотности распределения вероятностей p(x) вероятностное распределение на исходах.

Пусть существует вероятностная схема события A

, , ,

и вероятностная схема события B

, , ,

тогда можно задать объединенную вероятностную схему некоторого события С, которое будет имеет вид:

,

дополнительно заметим, что

Важной характеристикой схемы является энтропия ‑ средняя мера неравновероятности исходов схемы. Энтропия и близкое понятие количество информации по-разному определялись рядом авторов. Приведём некоторые из этих определений.

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

Согласно Р. Хартли[2] количество информации, содержащееся в сообщении, должно удовлетворять двум требованиям:

a) Пусть сообщение Т₁ записанное в алфавите A₁, |A₁|=m₁ имеет длину n₁, а сообщение Т₂, записанное в алфавите А₂, |A₂|=m₂, имеет длину n₂. Тогда если выполнено , то сообщения Т₁ и Т₂ несут одинаковое количество информации.

b) Количество информации, содержащееся в сообщении, пропорционально его длине.

Пусть алфавит источника сообщений состоит из знаков, каждый из которых может служить элементом сообщения. Количество возможных сообщений длины равно числу перестановок с неограниченными повторениями:

Если для получателя все сообщений от источника являются равновероятными, то получение конкретного сообщения равносильно для него случайному выбору одного из сообщений с вероятностью .

Чем больше (или меньше вероятность сообщения), тем большая степень неопределенности характеризует этот выбор и тем более информативным можно считать сообщение.

Очевидно, что количество информации, содержащейся в элементарном сообщении , является некоторой функцией от вероятности передачи этого сообщения :