Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Теория информации и смежные дисциплины




Основы Теории Информации

 

 

Гордеев Э.Н.

 

Москва

-2011-


Содержание

1 Введение. 4

1.1 Предмет курса. 4

1.2 Основная цель курса. 4

1.3 Теория информации и смежные дисциплины.. 4

1.4 Подходы к определению понятия информация. 5

2 Алфавит. Слово. Язык. Информация. 7

3 Информация и алгоритм. 8

3.1 Задачи, алгоритмы.. 8

3.1.1 Задача. 8

3.2 Алгоритм.. 13

3.2.1 Нормальные алгорифмы Маркова (НАМ). 17

3.2.2 Машины Тьюринга. 20

4 Кодирование информации. Количество информации. Сжатие информации. 24

4.1 Кодирование информации. 25

4.1.1 Примеры кодировок. 26

4.1.2 Свойства кодировок. 27

4.2 Наиболее распространенные способы кодирования и их свойства. Алгоритмы кодирования. 28

4.2.1 Кодирование слов и поиск минимального кода. 29

4.2.2 Признаковое кодирование. 29

4.2.3 Признаковое кодирование и проблема распознавания. 30

4.2.4 Сериальное кодирование. 33

4.2.5 Алфавитное кодирование. 35

4.2.6 Кодирование натурального ряда. 38

5 Количество информации. Энтропия. 40

5.1.1 Энтропия по Хартли. 40

5.1.2 Энтропия по Шеннону. 40

6 Теорема Шеннона. 43

7 Свойства энтропии. 46

8 Алгоритмы кодирования. 48

8.1 Алгоритм Шеннона (Фано) 48

8.2 Алгоритм Хаффмана. 49

8.3 Блочное кодирование. 50

8.4 Алгоритм арифметического кодирования. 52

8.5 Код Элайеса. 53

8.6 Код Левенштейна. 55

9 Блочное кодирование и теорема Шеннона. 55

10 Канал с шумом. 56

10.1 Модели каналов. 57

10.2 Передача информации по двоичному симметричному каналу с шумом.. 58

10.2.1 Схема и принципы кодирования. 58

10.3 Корректирующие способности кодов. Границы мощности. 61

10.4 Теорема Шеннона для канала с шумом. 64

10.4.1 Факты из теории вероятности. 64

10.4.2 Схема кодирования и декодирования. Вспомогательные утверждения. 65

10.4.3 Вероятностное доказательство теоремы. 67

10.4.4 Комбинаторное доказательство теоремы. 68

10.5 Линейные коды.. 70

10.5.1 Пример. Код Хемминга. 73

10.5.2 Замечание. Совершенные коды и теорема Шеннона. 75

10.5.3 БЧХ – коды.. 75

10.6 Спектр кода. Эквидистантные коды.. 78

11 Рекомендованная литература. 80

 


Введение

Предмет курса

Математические модели и методы, используемые при передачи, приеме и храниении информации. Классические результаты Теории информации и результаты последних десятилетий, которые могут быть отнесены к теории информации.

Основная цель курса

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

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

 

Теория информации и смежные дисциплины

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

Информация – нематериальная сущность, не имеющая физических атрибутов.

Информатика, Кибернетика и Теория информации – различные науки, а значит должны отличаться либо объектами, либо методологией.

Кибернетика – наука о:

Получении информации;

Хранении информации;

Передачи информации;

Преобразовании информации;

Использовании информации.

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

В конце 70-х начале 80-х годов появилось понятие «информатика» (англ. “ Computer Science ”). Это тоже наука о получении, хранении и использовании информации, но ее проблематика связана с появлением и развитием компьютеризации. По сути, и в кибернетике и в информатике ставятся одинаковые задачи.

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

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

Грубую схему дает нижеприведенный рисунок.

 

Теория информации:  

Рис. 1

 

1.4 Подходы к определению понятия информация.

Определение алгоритма или информации дать пока не удалось, существуют лишь интуитивные понимания этих понятий.

Понятие «информации» является связующим звеном во всех научных дисциплинах, изучающих свойства коммуникации в окружающем мире. Получение человеком сведений об окружающем мире происходит путем восприятия и обработки информации. Проблемы создания и восприятия информации – сложнейшие вопросы, лежащие на стыке различных областей: философии, физиологии, информатики и др. С чем человек имеет дело: с самими объектами или только и информацией о них? Каким образом возникает информация? Как правильно получать, анализировать и передавать информацию? Можно ли сравнивать количество и качество информации и, если да, то в каком аспекте? Какие есть правила обращения с информацией и на чем они основаны или должны основываться? Как информация может быть представлена и что такое обработка информации? Как выделить и найти в информационном пространстве ту информацию, которая вас интересует?

Ответы на все эти и другие подобные вопросы хотя бы немного проясняются, если удается продвинуться в понимании самого базового понятия информации. Но анализ этого понятия связан с привлечением других понятий и частичной замены ими анализируемого. Подробное рассмотрение лежит за пределами нашего курса. Сделаем лишь короткое замечание.

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

Рис. 2

Протокол – общепринятые правила, связанные с конкретным примером передачи, хранения и использования (зависит от постановки задачи и выбора системы).

Информация, как таковая, не сводится ни к одной из этих сущностей.

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

Информация – это продукт деятельности субъекта (человека), предназначенный для другого субъекта (человека), представляющий собой инструкцию (часть инструкции) по преобразованию окружающего мира с минимальными затратами ресурса (энергии).

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...