- •Основы Теории Информации Гордеев э.Н.
- •Содержание
- •1Введение
- •1.1Предмет курса
- •1.2Основная цель курса
- •1.3Теория информации и смежные дисциплины
- •1.4Подходы к определению понятия информация.
- •2Алфавит. Слово. Язык. Информация.
- •3.1Задачи, алгоритмы
- •3.1.1Задача
- •3Информация и алгоритм.
- •3.2Алгоритм
- •3.2.1Нормальные алгорифмы Маркова (нам).
- •3.2.2Машины Тьюринга
- •4Кодирование информации. Количество информации. Сжатие информации.
- •4.1Кодирование информации.
- •4.1.1Примеры кодировок
- •4.1.2Свойства кодировок
- •4.2Наиболее распространенные способы кодирования и их свойства. Алгоритмы кодирования.
- •4.2.1Кодирование слов и поиск минимального кода
- •4.2.2Признаковое кодирование.
- •4.2.3Признаковое кодирование и проблема распознавания.
- •4.2.4Сериальное кодирование
- •4.2.5Алфавитное кодирование.
- •4.2.5.1Неравенство Крафта.
- •4.2.5.2Префиксные коды.
- •4.2.6Кодирование натурального ряда.
- •4.2.6.1Код Элайеса.
- •4.2.6.2Код Левенштейна
- •5Количество информации. Энтропия.
- •5.1.1Энтропия по Хартли.
- •5.1.2Энтропия по Шеннону.
- •5.1.2.1Математическая модель: алфавитное кодирование случайного источника.
- •5.1.2.2Энтропия по Шеннону
- •5.1.2.3Энтропия по Шеннону и энтропия по Хартли.
- •6Теорема Шеннона
- •7Свойства энтропии.
- •8Алгоритмы кодирования
- •8.1Алгоритм Шеннона (Фано)
- •8.2Алгоритм Хаффмана
- •8.3Блочное кодирование
- •8.4Алгоритм арифметического кодирования
- •8.5Код Элайеса
- •8.6Код Левенштейна
- •9Блочное кодирование и теорема Шеннона.
- •10Канал с шумом.
- •10.1Модели каналов.
- •10.2Передача информации по двоичному симметричному каналу с шумом
- •10.2.1Схема и принципы кодирования.
- •10.3Корректирующие способности кодов. Границы мощности.
- •10.4Теорема Шеннона для канала с шумом.
- •10.4.1Факты из теории вероятности.
- •10.4.2Схема кодирования и декодирования. Вспомогательные утверждения.
- •10.4.3Вероятностное доказательство теоремы.
- •10.4.4Комбинаторное доказательство теоремы.
- •10.5Линейные коды
- •10.5.1Пример. Код Хемминга.
- •10.5.2Замечание. Совершенные коды и теорема Шеннона.
- •10.5.3Бчх – коды
- •10.6Спектр кода. Эквидистантные коды
- •11Рекомендованная литература
1.4Подходы к определению понятия информация.
Определение алгоритма или информации дать пока не удалось, существуют лишь интуитивные понимания этих понятий.
Понятие «информации» является связующим звеном во всех научных дисциплинах, изучающих свойства коммуникации в окружающем мире. Получение человеком сведений об окружающем мире происходит путем восприятия и обработки информации. Проблемы создания и восприятия информации – сложнейшие вопросы, лежащие на стыке различных областей: философии, физиологии, информатики и др. С чем человек имеет дело: с самими объектами или только и информацией о них? Каким образом возникает информация? Как правильно получать, анализировать и передавать информацию? Можно ли сравнивать количество и качество информации и, если да, то в каком аспекте? Какие есть правила обращения с информацией и на чем они основаны или должны основываться? Как информация может быть представлена и что такое обработка информации? Как выделить и найти в информационном пространстве ту информацию, которая вас интересует?
Ответы на все эти и другие подобные вопросы хотя бы немного проясняются, если удается продвинуться в понимании самого базового понятия информации. Но анализ этого понятия связан с привлечением других понятий и частичной замены ими анализируемого. Подробное рассмотрение лежит за пределами нашего курса. Сделаем лишь короткое замечание.
Как только мы начинаем анализировать понятие информации, мы сразу попадаем в область, где наряду с неформализованными понятиями можно уже привлекать и некоторые слова, которые наряду с обиходным значением имеют и терминологическое. Приведенная ниже схема является иллюстрацией их взаимосвязи.
Рис. 2
Протокол – общепринятые правила, связанные с конкретным примером передачи, хранения и использования (зависит от постановки задачи и выбора системы).
Информация, как таковая, не сводится ни к одной из этих сущностей.
Приведенная ниже фраза не является определением понятия информация, но позволяет, на мой взгляд, хоть немного к этому понятию приблизиться.
Информация – это продукт деятельности субъекта (человека), предназначенный для другого субъекта (человека), представляющий собой инструкцию (часть инструкции) по преобразованию окружающего мира с минимальными затратами ресурса (энергии).
2Алфавит. Слово. Язык. Информация.
Так как наш курс математический, то мы будем опираться на недоказуемое утверждение (тезис), которое используется математиками при изучении информации.
Тезис. Любая информация может быть представлена словом в конечном алфавите.
Заметим при этом, что не любое слово в конечном алфавите является информацией.
Опр. Алфавит A – это конечный или бесконечный набор символов: A={a1,a2,…,an,…}.
Опр. Слово – это конечный упорядоченный набор символов алфавита.
Выделяется
специальное пустое слово
(слово, не содержащее символов).
Пусть
– множество всех слов в алфавите
.
Опр.
Язык L – это подмножество
.
(
).
Опр.
Конкатенация
слов
и
.
Информация (слово в конечном алфавите)- нематериальная сущность. При любых действиях с информацией необходимо различать собственно информацию (слово) и материальный носитель, с помощью которого производится действие с информацией: книга, дискета, электромагнитное поле и т.п.
Назовем информационным объектом материальный носитель с находящейся на нем информацией. Структура материального носителя может быть сложной. Например, он, как целое, может состоять из частей, с каждой из которых может быть связан свой собственный информационный объект. Или наоборот, из нескольких ИО может быть сформирован новый ИО, как целое из частей. Из этих новых ИО формируются еще более сложные системы ИО и т.д. Для таких «сложных» ИО обычно используется термин информационная система (ИС).
