Введение в Алгебраическую теорию информации - Гоппа В.Д.
Скачать (прямая ссылка):
Армстронг.
Многозначные зависимости были введены Р. Фейджином. Наиболее полное
изложение теории реляционных баз данных содержится в книге Д. Мейера [13]
и К. Делобеля и М. Адиба [22].
Для математического описания реляционных баз данных обычно используется
язык математической логики, причем создается своя "реляционная алгебра".
В то же время речь идет в этой теории об устранении избыточности, так что
напрашивалось обращение к теории информации. Традиционная вероятностная
теория информации оказывалась при этом далекой от запросов информатики.
Иначе обстоит дело с алгебраической теорией информации. В рамках этой
теории основные понятия теории реляционных баз данных получают
естественное и простое объяснение. Функциональная зависимость оказывается
эквивалентной обращению в нуль условной информации (энтропии).
Многозначные зависимости получают прозрачное истолкование в терминах
условной независимости слов.
106
Связь между словами и графами прослеживается во многих работах по теории
графов, например в книге К. Бержа [2 ]. При описании задач поиска и
сортировки мы следуем изложению Д. Кнута [10].
Задача построения эйлеровых контуров с использованием остовного дерева
была решена Н. де Брейном и др. [18]. При изложении этих результатов в
гл. 4 использовались идеи П. Ка-стелейна и Д. Фоата. При изложении
основных алгоритмов на графах мы следуем книге В. Липского [11].
Гл. 5 книги, в которой изучается память слова с помощью циклического
сдвига, основана на статье [8 ].
Мы включили в эту книгу также основные сведения о том, как хранится и
обрабатывается в живых организмах генетическая информация с помощью слов,
"буквами" которых являются сложные полимерные молекулы. При этом мы
следуем изложению Ф. Айалы и Дж. Кайгера [1 ] и книге С.Г. Инге-Вечто-
мова [9 ].
СОДЕРЖАНИЕ
Предисловие .............. ........................................
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-информация слова .............................................
