 |
Теория информации и смежные дисциплины
|
|
|
|
Основы Теории Информации
Гордеев Э.Н.
Москва
-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
Протокол – общепринятые правила, связанные с конкретным примером передачи, хранения и использования (зависит от постановки задачи и выбора системы).
Информация, как таковая, не сводится ни к одной из этих сущностей.
Приведенная ниже фраза не является определением понятия информация, но позволяет, на мой взгляд, хоть немного к этому понятию приблизиться.
Информация – это продукт деятельности субъекта (человека), предназначенный для другого субъекта (человека), представляющий собой инструкцию (часть инструкции) по преобразованию окружающего мира с минимальными затратами ресурса (энергии).
|
|
|
