Теория информации лабы Бурькова. Теория информации
 Скачать 0.93 Mb.
|
|
3 Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «Оренбургский государственный университет» Кафедра вычислительной техники и защиты информации Е.В. Бурькова ТЕОРИЯ ИНФОРМАЦИИ Методические указания Рекомендовано к изданию редакционно-издательским советом федерального государственного бюджетного образовательного учреждения высшего образования «Оренбургский государственный университет» для обучающихся по образовательной программе высшего образования по направлению подготовки 10.03.01 Информационная безопасность Оренбург 2018 2 УДК 004.7 ББК 32.811 Б 91 Рецензент – кандидат технических наук, доцент Ю.И. Синицын Бурькова Е.В. Б 91 Теория информации: методические указания / Е.В. Бурькова; Оренбургский гос. ун-т. – Оренбург: ОГУ, 2018. – 50 с. В методических указаниях представлены теоретические сведения по ос- новам теории информации. Методические указания содержат задачи для проведения практических работ по курсу «Теория информации», а также вопросы для самопроверки. Методические указания предназначены для обучающихся по образова- тельной программе высшего образования по направлению подготовки 10.03.01 Информационная безопасность. УДК 004.7 ББК 32.811 © Бурькова Е.В., 2018 © ОГУ, 2018 3 Содержание Введение ........................................................................................................................... 4 Основные определения теории информации ............................................................... 5 1 Лабораторная работа № 1. Теоремы теории вероятности в теории информации . 7 1.1 Цель работы ............................................................................................................ 7 1.2 Теоретические сведения ........................................................................................ 7 1.3 Задание ................................................................................................................... 10 1.4 Контрольные вопросы .......................................................................................... 12 2 Лабораторная работа № 2. Количественная оценка информации ......................... 13 2.1 Цель работы .......................................................................................................... 13 2.2 Теоретические сведения ...................................................................................... 13 2.3 Задание ................................................................................................................... 16 2.4 Контрольные вопросы .......................................................................................... 18 3 Лабораторная работа № 3. Условная энтропия и энтропия объединения ....... 19 3.1 Цель работы .......................................................................................................... 19 3.2 Теоретические сведения ...................................................................................... 19 3.3 Задание ................................................................................................................... 23 3.4 Контрольные вопросы .......................................................................................... 25 4 Лабораторная работа № 4. Вычисление информационных потерь при передаче сообщений по каналам связи с шумами ..................................................... 26 4.2 Теоретические сведения ...................................................................................... 26 4.3 Задание ................................................................................................................... 30 4.4 Контрольные вопросы .......................................................................................... 31 5 Лабораторная работа № 5. Информационные характеристики каналов связи .... 32 5.1 Цель работы .......................................................................................................... 32 5.2 Теоретические сведения ...................................................................................... 32 5.3 Задание ................................................................................................................... 35 5.4 Контрольные вопросы .......................................................................................... 37 6 Лабораторная работа № 6. Избыточность и оптимальное кодирование информации.................................................................................................................... 38 6.1 Цель работы .......................................................................................................... 38 6.2 Теоретические сведения ...................................................................................... 38 6.3 Задание ................................................................................................................... 44 6.4 Контрольные вопросы .......................................................................................... 45 7 Лабораторная работа № 7. Эффективное кодирование. Метод Хаффмана .... 46 7.1 Цель работы .......................................................................................................... 46 7.2 Теоретические сведения ...................................................................................... 46 7.3 Задание ................................................................................................................... 48 7.4 Контрольные вопросы .......................................................................................... 49 Список использованных источников .......................................................................... 50 4 Введение Теория информации является одним из важных курсов для подготовки бакалавров, бедующая профессиональная деятельность которых связана с процессами обработки и защиты информации. Теория информации связана с изучением систем обработки и передачи информации, измерением количества информации, кодированием. Теория информации решает такие теоретические вопросы как, количественная оценка информации; анализ информационных характеристик источников сообщений и каналов связи и выявление возможности кодирования и декодирования сообщений, обеспечивающих максимально допустимую скорость передачи сообщений по каналу связи с помехами и без помех. Принципы теории информации используются в различных областях науки и связано это с тем, что в основе своей эта теория математическая. Основные ее понятия: энтропия, количество информации, пропускная способность канала связи определяются только через вероятности событий, которым может быть определено самое различное физическое наполнение. Подход к исследованиям в других областях науки с позиций использования основных идей теории информации получил название теоретико-информационного подхода. Этот подход позволяет решать задачи в области исследования каналов передачи информации, определения оптимальных способов кодирования и декодирования, максимальной скорости передачи и пропускной способности каналов, а также другие важные задачи в области систем связи. Данные методические указания предназначены для проведения практических работ по курсу «Теория информации» для студентов направления подготовки 10.03.01 Информационная безопасность. Методические указания содержат теоретические сведения, задания и вопросы для самопроверки. Вопросы и задачи, рассматриваемые в данных методических указаниях, являются важными для формирования профессиональных компетенций будущего специалиста в сфере информационной безопасности. 5 Основные определения теории информации Информация - это характеристика внутренней организованности матери- альной системы по множеству состояний, которые она может принимать. Инфор- мация объективно существует независимо от нашего сознания, но выявляется при взаимодействии с конкретным объектом. Информационные системы - это класс технических систем, предназначен- ных для хранения, передачи и преобразования информации. Под информационным процессом понимают совокупность последова- тельных действий со сведениями, направленных на получение определенного ре- зультата. Основные информационные процессы: восприятие, преобразование, обработка, хранение, передача, отображение. Восприятие информации (ввод) – это отображение данных на каком-либо носителе или в каких-либо качественных сторонах объекта. На этапе восприятия информации производится извлечение и анализ информации о каком-либо объек- те (процессе), в результате чего формируется образ объекта, проводится его иден- тификация и оценка. Преобразование информации – изменение формы и вида сведений. Передача информации – перенос сведений из одной точки пространства в другую. При этом всегда стремятся минимизировать время передачи. Обработка информации – любые действия со сведениями, выполняемые по детерминированному алгоритму, которые приводят к изменению их вида, а также содержательности, ценности, полезности. Хранение информации – перенос сведений от одного момента времени до другого. При этом стремятся минимизировать объем носителя или пространства, в котором сведения хранятся. Отображение (вывод) информации – представление сведений на каком- либо носителе или в какой-либо качественной стороне объекта в целях воспри- ятия их. 6 Сообщение – это совокупность символов или первичных сигналов, содер- жащих информацию. Дискретные сообщения – это сообщения, которые формируются в ре- зультате последовательной выдачи источником сообщений отдельных элементов - знаков. Множество различных знаков называют алфавитом источника сообще- ния, а число знаков - объемом алфавита. Непрерывные сообщения не разделены на элементы. Они описываются непрерывнымифункциями времени, принимающими непрерывное множество значений. Сигнал - это физический процесс, отображающий (несущий) сообщение. Кодированием называют преобразование сообщения в сигнал, удобный для передачи по данному каналу связи. Декодирование - операция восстановления сообщения по принятому сиг- налу. Помехами называют любые воздействия, как внешние, так и внутренние, вызывающие отклонение принятых сигналов от переданных сигналов. Верностью передачи называют меру соответствия принятого сообщения посланному сообщению. Канал связи – это совокупность средств, предназначенных для передачи сообщений. Количество информации – это основная характеристика сообщения, свя- занная со степенью его неопределенности. В качестве меры неопределенности выбора состояния источника с равновероятными состояниями принимают лога- рифм числа состояний. Бит – единица измерения количества информации, это количество инфор- мации, которым характеризуется один двоичный элемент при равновероятных со- стояниях 0 и 1. Энтропия - количество информации, приходящееся на один элемент сооб- щения (знак, букву). 7 1 Лабораторная работа № 1. Теоремы теории вероятности в теории информации 1.1 Цель работы Освоение основных понятий теории вероятности и применение их в решении задач теории информации. 1.2 Теоретические сведения Под событием понимают любой факт, который может произойти в резуль- тате какого-либо опыта или эксперимента. Под опытом понимается осуществле- ние определённого комплекса условий. События называются совместными, если наступление одного из них не исключает наступления другого. В противном слу- чае события называются несовместными. Событие называется достоверным, ес- ли оно обязательно произойдет в условиях данного опыта. Событие называется невозможным, если оно не может произойти в условиях данного опыта. Событие называется возможным, или случайным, если в результате опыта оно может появиться, но может и не появиться. События называются равновозможными, если по условиям испытания ни одно из этих событий не является объективно бо- лее возможным, чем другие. Важным понятием является полная группа событий. Несколько событий в данном опыте образуют полную группу, если в результате опыта обязательно появится хотя бы одно из них. Вероятностью события А называется число, равное отношению числа ис- ходов m, благоприятствующих появлению события, к числу всех равновозмож- ных исходов n: Вероятность события характеризуется следующими свойствами: 8 1) 1 ) ( 0 A P ; 2) Р(А) = 0 означает, что А – событие невозможное; 3) Р(В) = 1 означает, что В – событие достоверное. Теорема сложения вероятностей. Если два события несовместны, то ве- роятность наступления каждого из них равна сумме их вероятностей Следствие 1. Для полной группы событий сумма их вероятностей равна 1. Следствие 2. Сумма вероятностей двух противоположных событий Условной вероятностью события В называется вероятность наступления события В при условии, что событие А уже наступило. Обозначается P(B/A) или P A (В). Теорема умножения вероятностей. Вероятность совместного наступления событий А и В, равна произведению вероятности одного из них на условную ве- роятность другого Следствие. Вероятность произведения двух независимых событий равна произведению их вероятностей Теорема сложения вероятностей для случая, когда события совместны. Вероятность наступления хотя бы одного из двух совместных событий равна сумме вероятностей этих событий, минус вероятность их совместного появления, Объединение теорем сложения и умножения выражается в формуле полной вероятности 9 Теорема. Вероятность события А, которое может произойти при осуществ- лении одного из несовместных событий B1, B2, B3, ..., Bn, образующих полную группу, определяется формулой: События B 1 , B 2 , B 3 ,..., B n называются гипотезами. В случае, если событие А, появляющееся совместно с каким-либо из несо- вместных событий B 1 , B 2 , B 3 , ..., B n , образующих полную группу, произошло и требуется произвести оценку вероятностей событий B 1 , B 2 , B 3 ,..., B n , применяется формула Байеса: Пример. По каналу связи с помехами передается одно из двух сообщений: 1) 11111 с вероятностью равной 0,7; 2) 00000 с вероятностью равной 0,3. Вероятность правильного приема каждого из символов 0 и 1 равна 0,6. Сим- волы искажаются помехами независимо друг от друга. На выходе канала получа- ют кодовое сообщение 10110. Определить вероятности передачи первого и второго сообщений. Решение. Пусть событие А состоит в приеме сообщения 10110. Это событие может произойти в совокупности с событием В1 - передавалось сообщение 11111 и со- бытием В2 - передавалось сообщение 00000. При этом Р(В1) = 0,7, Р(В2) = 0,3. Условная вероятность приема сообщения 10110 при условии, что передава- лась команда 11111 равна 10 P(A/В1)=P(1/1)∙P(0/1)∙P(1/1)∙P(1/1)∙P(0/1), где P(1/1)=0,6, P(0/1)=1- P(1/1)=0,4 P(A/В1)=0,6∙0,4∙0,6∙0,6∙0,4=0,035. Условная вероятность приема сообщения 10110 при условии, что передава- лась команда 00000 равна По формуле полной вероятности Р(А)=Р(В1)Р(А/В1)+ Р(В2 )Р(А/В2) = 0,7∙0,035+0,3∙0,023 = 0,0314 По формуле Байеса Ответ. Сравнивая вероятности, можно сделать вывод о том, что более веро- ятна передача сообщения 11111. 1.3 Задание Задача 1. В урне 3 белых и 3 черных шара. Из урны дважды вынимают по одному шару, не возвращая их обратно. Найти вероятность появления белого ша- ра при втором испытании, если при первом испытании был извлечен черный шар. Задача 2. В магазин поступила новая продукция с трех предприятий. Про- центный состав этой продукции: 20 % - продукция первого предприятия, 30 % - продукция второго, 50 % - продукция третьего. Продукции высшего сорта, посту- 11 пившего от первого предприятия 10 %, от второго предприятия – 5 %, от третье- го – 20 %. Найти вероятность того, что случайно купленная продукция будет высшего сорта. Задача 3. На любой из позиций двоичного кода может быть с равной веро- ятностью переданы «0» и «1». Помехи преобразуют «1» в «0» с вероятностью 0,02 и «0» в «1» с вероятностью 0,04. Найти вероятность того, что был передан «0», если принят «0». Задача 4. По линии связи посылаются сигналы «1» и «0» с вероятностями Р1 = 0,6 и Р0 = 0,4. Если посылается сигнал «1», то с вероятностью r11 = 0,9 при- нимается сигнал «1», с вероятностью r10 = 0,1 принимается сигнал «0». Если по- сылается сигнал «0», то с вероятностями r01 = 0,3 принимается сигнал «1», r00 = 0,7 принимается сигнал «0». Какова условная вероятность того, что посылается сигнал «1» при условии, что принимается сигнал «1»? Задача 5. Вероятность искажения отдельного бита Р=0,02, длина кодовой комбинации n=8. Найти вероятность безошибочной передачи всей комбинации, вероятность ошибки передачи, а также вероятности передачи с одной, двумя и тремя ошибками. Задача 6. По линии связи посылаются сигналы «1» и «0» с вероятностями Р1 = 0,6 и Р0 = 0,4. Если посылается сигнал «1», то с вероятностью r11 = 0,9 при- нимается сигнал «1», с вероятностью r10 = 0,1 принимается сигнал «0». Если по- сылается сигнал «0», то с вероятностями r01 = 0,3 принимается сигнал «1», r00 = 0,7 принимается сигнал «0». Какова вероятность того, что принимается сигнал 1? Задача 7. По линии связи посылаются сигналы «1» и «0» с вероятностями Р1 = 0,6 и Р0 = 0,4. Если посылается сигнал «1», то с вероятностью r11 = 0,9 при- нимается сигнал «1», с вероятностью r10 = 0,1 принимается сигнал «0». Если по- сылается сигнал «0», то с вероятностями r01 = 0,3 принимается сигнал «1», r00 = 0,7 принимается сигнал «0». Какова вероятность того, что принимается сигнал 0? 12 |