Файл: Лабораторная работа 1 Защита документов ms office Цель изучить методы защиты документов ms office, правила создания сложных паролей.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 08.11.2023
Просмотров: 934
Скачиваний: 25
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
приносимое сообщением о таком событии, равно нулю. Информация появится лишь тогда, когда источник будет иметь по крайней мере более одного возможного состояния.
Рассмотрим источник, выдающий последовательность независимых дискретных сообщений {
λ
i
}, каждое из которых случайным образом выбирают из алфавита сообщения
A (
λ
i
) =
λ
1
,
λ
2
,
λ
3
, ...
λ
K
, где K - размер алфавита источника. Такой источник будем называть источником без памяти с конечным дискретным алфавитом. Сообщения, вырабатываемые таким источником, называются простыми сообщениями.
В каждом элементарном сообщении
λ
i
для его получателя содержится некоторая информация. Определим количественную меру этой информации и выясним, от чего она зависит.
До того, как связь состоялась, у получателя всегда имеется большая или меньшая неопределенность относительно того, какое сообщение
λ
i
из числа возможных будет передано.
Совершенно очевидно, что степень этой неопределенности, или неожиданности передачи
λ
i
, зависит от вероятности передачи того или иного сообщения. Например, есливероятность передачи какого-либо сообщения
λ
i
очень высока, то еще до передачи мы почти наверняка знаем, какое сообщение будет передано, и его прием не принесет нам почти никакой новой информации.
Таким образом, очевидно, что количество информации, содержащейся в элементарном сообщении
λ
i
, является некоторой функцией от вероятности передачи этого сообщения Р(
λ
i
):
J (
λ
i
) =
ϕ
{P (
λ
i
)}. (1.31)
Определим вид этой функции
ϕ
. Для этого потребуем, чтобы мера количества информации J(
λ
i
) удовлетворяла двум интуитивным свойствам:
1.
Если выбор сообщения
λ
i
заранее предопределен
(Р(
λ
i
) =
1 неопределенности нет), то количество информации в этом сообщении равно нулю: J (
λ
i
)
=
ϕ
{1} = 0.
2.
Если источник последовательно выбирает сообщения
λ
i
и
λ
j
и вероятность такого выбора Р(
λ
i
,
λ
j
) есть совместная вероятность событий
λ
i
и
λ
j
, то количество
информации в этих двух элементарных сообщениях будет равно сумме количеств информации
в каждом из них.
Вероятность совместного выпадения событий
λ
i
и
λ
j
Р(
λ
i
,
λ
j
), как известно, определяется по формуле полной вероятности
Р (
λ
i
,
λ
j
) = Р(
λ
i
)
⋅
Р(
λ
j
/
λ
i
) = P
⋅
Q. (1.32)
Тогда, в соответствии с требованием (2), должно выполняться
условие
ϕ
{ P
⋅
Q } =
ϕ
(P) +
ϕ
(Q). (1.33)
Нетрудно догадаться, что функцией, удовлетворяющей этим двум предъявляемым к ней условиям, является функция вида
Рассмотрим источник, выдающий последовательность независимых дискретных сообщений {
λ
i
}, каждое из которых случайным образом выбирают из алфавита сообщения
A (
λ
i
) =
λ
1
,
λ
2
,
λ
3
, ...
λ
K
, где K - размер алфавита источника. Такой источник будем называть источником без памяти с конечным дискретным алфавитом. Сообщения, вырабатываемые таким источником, называются простыми сообщениями.
В каждом элементарном сообщении
λ
i
для его получателя содержится некоторая информация. Определим количественную меру этой информации и выясним, от чего она зависит.
До того, как связь состоялась, у получателя всегда имеется большая или меньшая неопределенность относительно того, какое сообщение
λ
i
из числа возможных будет передано.
Совершенно очевидно, что степень этой неопределенности, или неожиданности передачи
λ
i
, зависит от вероятности передачи того или иного сообщения. Например, есливероятность передачи какого-либо сообщения
λ
i
очень высока, то еще до передачи мы почти наверняка знаем, какое сообщение будет передано, и его прием не принесет нам почти никакой новой информации.
Таким образом, очевидно, что количество информации, содержащейся в элементарном сообщении
λ
i
, является некоторой функцией от вероятности передачи этого сообщения Р(
λ
i
):
J (
λ
i
) =
ϕ
{P (
λ
i
)}. (1.31)
Определим вид этой функции
ϕ
. Для этого потребуем, чтобы мера количества информации J(
λ
i
) удовлетворяла двум интуитивным свойствам:
1.
Если выбор сообщения
λ
i
заранее предопределен
(Р(
λ
i
) =
1 неопределенности нет), то количество информации в этом сообщении равно нулю: J (
λ
i
)
=
ϕ
{1} = 0.
2.
Если источник последовательно выбирает сообщения
λ
i
и
λ
j
и вероятность такого выбора Р(
λ
i
,
λ
j
) есть совместная вероятность событий
λ
i
и
λ
j
, то количество
информации в этих двух элементарных сообщениях будет равно сумме количеств информации
в каждом из них.
Вероятность совместного выпадения событий
λ
i
и
λ
j
Р(
λ
i
,
λ
j
), как известно, определяется по формуле полной вероятности
Р (
λ
i
,
λ
j
) = Р(
λ
i
)
⋅
Р(
λ
j
/
λ
i
) = P
⋅
Q. (1.32)
Тогда, в соответствии с требованием (2), должно выполняться
условие
ϕ
{ P
⋅
Q } =
ϕ
(P) +
ϕ
(Q). (1.33)
Нетрудно догадаться, что функцией, удовлетворяющей этим двум предъявляемым к ней условиям, является функция вида
J (
λ
i
) = a log P(
λ
i
), (1.34) при этом как коэффициент a, так и основание логарифма могут быть выбраны произвольно.
Однако для удобства (чтобы количественная мера информации была положительной) принимают a = - 1. Основание логарифма обычно выбирают равным двум, и тогда
J (
λ
i
) = - log
2
P(
λ
i
). (1.35)
Определенная таким образом единица измерения информации называется двоичной
единицей, или битом информации. Например, если какое-либо из элементарных сообщений
λ
i
может быть выбрано из алфавита и передано с вероятностью P(
λ
i
) =
1/8, то говорят, что в нем содержится log
2
(1/8) = 3 бита информации.
Иногда в качестве основания логарифма выбирают e, тогда информация измеряется в натуральных единицах, или натах.
Количество информации, содержащееся в одном элементарном сообщении
λ
i
, еще никак не характеризует источник. Одни элементарные сообщения могут нести много информации, но передаваться очень редко, другие - передаваться чаще, но нести меньше информации.
Поэтому источник может быть охарактеризован средним количеством информации,
приходящимся на одно элементарное сообщение, носящим название “энтропия источника” и определяемым следующим образом:
K
H(
λ
) = −
∑
P(
λ
i
)⋅ log P(
λ
i
), i = 1, K. (1.36)
i=
1
Энтропия, как количественная мера информативности источника, обладает следующими свойствами:
1.
Энтропия есть величина вещественная, ограниченная и неотрицательная. Эти ее свойства вытекают из вида выражения для Н(
λ
), а также с учетом того, что 0 < P(
λ
i
) < 1.
2.
Энтропия детерминированных сообщений равна нулю, то есть Н(
λ
) = 0, если хотя бы одно из сообщений имеет вероятность, равную единице.
3. Энтропия максимальна, если сообщения
λ
i
равновероятны, то
есть
P(
λ
1
) = P(
λ
2
) = ....... P(
λ
k
) = 1/K , и тогда
K
H(
λ
) = −
1
K
∑
log
1
K
= log K . (1.37)
i=
1
Как видно из последнего выражения, в случае равновероятных сообщений энтропия растет с увеличением объема алфавита источника (ростом числа сообщений). При неравновероятных элементарных сообщениях
λ
i
энтропия, соответственно, уменьшается.
4. Энтропия двоичного источника (K = 2) может изменяться от нуля до единицы.
Действительно, энтропия системы из двух сообщений
λ
1
и
λ
2
H(
λ
)=−P(
λ
1
)
*
log P(
λ
1
)− P(
λ
2
)
*
log P(
λ
2
)=
(1.38)
=−P(
λ
1
)
*
log P(
λ
1
)−{
1− P(
λ
1
)}
*
log{
1− P(
λ
1
)}.
Из последнего выражения видно, что энтропия равна нулю при P(
λ
1
) = 0; P(
λ
2
)=
1, или P(
λ
1
) =
1; P(
λ
2
) =
0; при этом максимум энтропии будет иметь место, когда P(
λ
1
)=P(
λ
2
)=1/2 и ее максимальное значение будет равно 1 бит.
Лабораторная работа №11 Методы сжатия.
Алгоритм Хаффмена
Цель: ознакомиться с общими принципами сжатия информации с использованием метода
Хаффмена
Исследование экономичных схем поиска привело к появлению метода сжатия информации, который был назван методом Хаффмена. Фактически Дэвид Хаффмен (1925-
1999) просто нашел метод решения задачи для сокращения объемов передаваемой и хранимой информации, и построенные на его основе программы оказались настолько эффективны, что вызвали целый поток конкурентных исследований в этой области.
Первоначально речь шла о сжатии текстовой информации, но затем внимание стало обращаться к экономному хранению других типов данных: изображений, музыки, кинофильмов.
Алгоритм Хаффмена
Суть алгоритма Хаффмена сводится к следующему:
✓
буквы алфавита сообщений выписываются в основной столбец таблицы в порядке убывания вероятностей;
✓
две последние буквы объединяются в одну вспомогательную букву, которой приписывается суммарная вероятность;
✓
вероятности букв, не участвовавших в объединении, и полученная суммарная вероятность снова располагаются в порядке убывания вероятностей, а две последние объединяются до тех пор, пока не получают единственную вспомогательную букву с вероятностью единица;
✓
далее для построения кода используется бинарное дерево, в корне которого располагается буква с вероятностью единица, при ветвлении ветви с большей вероятностью присваивается код единица, а с меньшей — код ноль (возможно левой — единица, а правой — ноль).
Пример 1. Рассмотрим условный алфавит из восьми букв, каждой из которых приписана соответствующая вероятность ее появления в сообщении
(табл. 1).
Таблица 1
Кодовое дерево представлено на рисунке 1.
Рис. 1. Кодовое (бинарное) дерево для примера 1.
Выполнить практическое задание:
Задача 1. Даны символы a, b, c, d с частотами f a
= 0,5; f b
= 0,25; f c
= 0,125; f d
= 0,125. Построить эффективный код методом Хаффмена.
Задача 2. Построить код Хаффмена для алфавита, состоящего из пяти символов a, b, c, d, e с частотами (вероятностями появления в тексте) a – 0,37; b – 0,22; c – 0,16; d – 0,14; e – 0,11
Задача 4. Подсчитать частоты символов во фразе и по этим частотам построить код Хаффмена:
1.
на_дворе_трава_на_траве_дрова_не_руби_дрова_на траве_двора;
2.
aaabbaaabbababababaaaaabbbaaaabbbaaabbbbaaabbbdadadadadadddddaaa;
3.
мороз_и_солнце_день_чудесный_еще_ты_дремлешь_друг_прелестный
(А. Пушкин);
4.
если_жизнь_тебя_обманет_не_печалься_не_сердись_в_день_уныния_с мирись_день_веселья_верь_настанет (А. Пушкин);
5.
имеем_не_храним_потеряем_плачем;
6.
в_горнице_моей_светло_это_от_ночной_звезды_матушка_возьмет_вед ро_молча_принесет_воды (Н. Рубцов);
7.
выше_гор_могут_быть_только_горы_на_которых_еще_не_бывал (В. Высоцкий);
8.
белеет_парус_одинокий_в_тумане_моря_голубом_что_ищет_он_в_стр ане_далекой_что_кинул_он_в_краю_родном (М. Лермонтов);
9.
в_глубокой_теснине_Дарьяла_где_роется_Терек_во_мгле_старинная башня стояла_чернея на черной скале (М. Лермонтов);
10.
не_презирай_совета_ничьего_но_прежде_рассмотри_его (И.А. Крылов);
11.
образование_это_то_что_остается_когда_все_выученное_забыто;
12.
математику_уже_за_то_любить_следует_что_она_ум_в_порядок_прив одит (М.В. Ломо- носов);
13.
математика_это_язык_на_котором_написана_книга_природы (Галилео Галилей)
14.
деньги_дороги_жизнь_человеческая_ещё_дороже_а_время_дороже_все го
(А.В.
Суворов);
15.
легко в учении_тяжело_в_походе_тяжело_в_учении_легко_в_походе (А.В. Суворов).
1 2 3 4 5 6 7 8 9
Контрольные вопросы:
1.
Поясните алгоритм построения кода для сообщения с заданными вероятностями букв по алгоритму Хаффмена
2.
Поясните алгоритм построения кода для произвольного сообщения по алгоритму
Хаффмена
Лабораторная работа №12 Корректирующие коды. Коды Хэмминга
Цель: ознакомиться с общими принципами построения и использования корректирующих кодов для контроля целостности информации, распространяемой по телекоммуникационным каналам, изучить метод кодирования по Хэммингу
Кодом называется система условных знаков (символов) для передачи, обработки и
хранения (запоминания) различной информации.
Предметом исследования теории кодирования являются отображения конечных или счетных множеств объектов произвольной природы в множества последовательностей из цифр 0, 1,…r-1, где r – некоторое целое положительное число (в частности, r = 2). Такие отображения называются кодированиями.
Большинство задач теории кодирования укладывается в следующую схему:
Для заданного множества объектов рассматривается класс кодирований, обладающих определенными свойствами. Требуется построить кодирование из рассматриваемого класса, оптимальное в некотором заранее заданном смысле. Обычно критерий оптимальности кодирования так или иначе связан с минимизацией длин кодов, в то время как требуемые свойства кодирований могут быть весьма разнообразными. Среди таких свойств:
✓
существование однозначного обратного отображения
(декодирования),
✓
возможность исправления при декодировании ошибок различного типа,
✓
возможность простой реализации (простота алгоритма) кодирования и декодирования и т.п.
Способы контроля правильности передачи данных. Код с проверкой на четность
Контроль целостности информации при передаче от источника к приемнику может осуществляться с использованием корректирующих кодов.
Простейший корректирующий код – код с проверкой на четность, который образуется добавлением к группе информационных разрядов одного избыточного, значение которого выбирается таким образом, чтобы сумма единиц в кодовой комбинации, т.е. вес кодовой комбинации, была всегда четна.
Пример 1. Рассмотрим код с проверкой на четность, образованный добавлением контрольного разряда к простому двоичному коду:
Информационные разряды Контрольный разряд
0 000 0
1 001 1
2 010 1
3 011 0
4 100 1
5 101 0
6 110 0
7 111 1
Такой код обнаруживает все одиночные ошибки и групповые ошибки нечетной кратности, так как четность количества единиц в этом случае будет также нарушаться.
Следует отметить, что при кодировании целесообразно число единиц в кодовой комбинации делать нечетным и осуществлять контроль на нечетность. В этом случае любая комбинация, в том числе и изображающая ноль, будет иметь хотя бы одну единицу, что дает возможность отличить полное отсутствие информации от передачи нуля.
Рассмотрим некоторые виды преобразований двоичных слов, называемых ошибками.
Одиночной ошибкой вида 0→1 (1→0) в слове X называют результат замены одного из символов 0 (соответственно 1) символом 1 (соответственно 0). Одиночные ошибки этого вида называют также
замещениями символов, или аддитивными ошибками.
Одиночной ошибкой вида 0→∧ (1→∧) в слове X называют результат удаления одного
из символов 0 (соответственно 1); при этом длина слова уменьшается на единицу. Одиночные ошибки этого вида называются
выпадениями символов.
Одиночной ошибкой вида ∧→0 (∧→1) называют результат вставки символовперед некоторым символом слова или после его последнего символа; при этом длина слова увеличивается на единицу.
Одиночной ошибкой вида +2
i
(-2
i
)
в слове X ∈ В
n
, где 0 ≤ i < n, называют преобразование слова X в слово Y ∈ В
n
, числовое значение которого на 2
i больше
(соответственно меньше) числового значения слова X. Одиночные ошибки вида +2
i и
-
2
i
называются арифметическими ошибками.
Для иллюстрации в таблице 1 приведены слова, полученные из слова 0001101 (двоичная запись числа 13) в результате ошибок рассматриваемых видов.
Таблица 1