Введение в Алгебраическую теорию информации - Гоппа В.Д.
Введение в Алгебраическую теорию информации
Автор: Гоппа В.Д.Издательство: М.: Наука
Год издания: 1995
Страницы: 112
Читать: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
Скачать:
В.Д.Гоппа
ВВЕДЕНИЕ В АЛГЕБРАИЧЕСКУЮ ТЕОРИЮ ИНФОРМАЦИИ
М.: Наука. Физматлит, 1995.-112 с.
Развивается алгебраический подход к теории информации. Теория
информации трактуется как абстрактная теория слов со своими
специфическими задачами, связанными с хранением слов в памяти компьютера,
обработкой слов и их передачей по каналам связи. На множестве слов
канонически присутствует алгебраическая структура, связанная с действием
симметрической группы на словах. Эта структура используется для
определения информации слова с различными приложениями к информатике.
Книга предназначена для широкого круга читателей.
СОДЕРЖАНИЕ
Предисловие 4
1. Информация слов и теоремы кодирования 5
1.1. Информация по Хартли 5
1.2. Отношение эквивалентности 5
1.3. Неравномерное кодирование слов 6
1.4. Действие группы на множестве 7
1.5. 0-информация слова 7
1.6. Условная 0-информация 9
1.7. Вычисление условной информации 11
1.8. Группировка наблюдений (квантование) 14
1.9. Нахождение числа орбит 15
1.10. Сжатие по Фитингофу 18
1.11. Независимость 21
1.12. Канал с шумом 22
1.13. Асимптотическое поведение информации. Энтропия 29
1.14. Прямое произведение слов 31
2. Распознавание образов 33
2.1. Постановка задачи распознавания. Информационная матрица 33
2.2. Вычисление информативности признака 35
2.3. Кластерный анализ в пространстве признаков 37
2.4. Формирование сложных признаков 40
2.5. Переход в новое пространство признаков. Метрика Хэмминга 42
2.6. Распознавание 43
3. Реляционные базы данных 45
3.1. Отношения 45
3.2. Функциональные зависимости 47
3.3. Декомпозиция на основе функциональных зависимостей 49
3.4. Декомпозиция и условная независимость 51
3.5. Многозначная зависимость 54
4. Слова и графы 57
4.1. Граф алгебраического канала 57
4.2. Поиск пути 58
4.3. Основное дерево графа 60
4.4. Ордерево. Иерархические структуры 61
4.5. Бинарный поиск 64
4.6. Быстрая сортировка 65
4.7. Дерево поиска 67
4.8. Кратчайший маршрут (алгоритм Дикстры) 69
4.9. Максимальный маршрут. Сетевая модель комплекса операций 72
4.10. Эйлеров граф 75
4.11. Максимальный поток в сети 79
5. Память в словах 83
5.1. 1 -информация слова 83
5.2. 1-сжатие по Фитингофу 85
5.3. да-информация слова 86
5.4. Информационная характеристика слова 88
5.5. Генетическая информация 90
5.6. Генетический код 95
5.7. Хромосомная база данных 100
Исторический очерк 104
Список литературы 108
ПРЕДИСЛОВИЕ
В книге развивается алгебраический подход к теории информации. Теория
информации трактуется как абстрактная теория слов со своими
специфическими задачами, связанными с хранением слов в памяти компьютера,
обработкой слов и их передачей по каналам связи. На множестве слов
канонически присутствует алгебраическая структура, связанная с действием
симметрической группы на словах. Эта структура используется для
определения информации слова с различными приложениями к информатике.
Книга состоит из пяти глав и исторического очерка.
В первой главе вводятся основные понятия теории информации и доказываются
теоремы кодирования. Во второй главе веденные понятия применяются для
распознавания образов. Приводятся алгоритмы вычисления информативности
признака и кластерного анализа в пространстве признаков. Третья глава
посвящена реляционным базам данных. Основное внимание уделяется синтезу
баз данных на основе декомпозиции. В четвертой главе анализируется связь
между словами и графами. Рассматриваются основные алгоритмы на графах,
которые находят применение при сжатии информации, распознавании образов и
синтезе баз данных. В последней главе изучается память слов и основные
процессы, связанные с хранением и преобразованием генетической информации
(молекулярная биология с точки зрения информатики).
Книга написана на основе курса лекций, прочитанных автором в 1986-1990
г.г. на Специальном факультете информатики в науках о Земле Московского
геологоразведочного института. Автор благодарен декану факультета А.А.
Виноградову за любезное приглашение прочитать этот курс лекций и
слушателям, чьи замечания автор учел при написании книги.
Лекции сопровождались лабораторными занятиями в компьютерном классе,
которые проводил Е.Н. Городничев. Многие результаты, включенные в книгу,
появились в процессе нашей совместной работы, так что его можно считать
полноправным соавтором книги.
Чрезвычайно полезными оказались беседы с О.Н. Ковалевой
о проблемах, связанных с реляционными базами данных. Консультантом по
генетике явился мой сын В.В. Гоппа, окончивший биофак МГУ. Всем этим
лицам выражаю глубокую благодарность.
1. ИНФОРМАЦИЯ СЛОВ И ТЕОРЕМЫ КОДИРОВАНИЯ
1.1. Информация по Хартли
Пусть Q-конечное множество, IQI-его мощность. Информация элемента со G Q
определяется по Хартли [17] следующим образом:
Эта величина равна с точностью до округления числу двоичных символов
необходимых для записи элемента со (индивидуализации элемента множества).
1.2. Отношение эквивалентности
Пусть теперь на множестве Q задано отношение эквивалентности , т.е.
