Combinatorial Algorithms: Theory and Practice

Титульный лист ......Page 1
Выходные данные ......Page 2
Предисловие редактора перевода ......Page 3
Предисловие ......Page 4
1.1. Краткая аннотация ......Page 6
1.2. История ......Page 7
1.3. Модель системы передачи сигналов ......Page 8
1.4. Источник сообщений ......Page 9
1.5. Кодирование алфавита источника ......Page 10
1.6. Некоторые коды ......Page 12
1.7. Код ASCII ......Page 13
1.8. Некоторые другие коды ......Page 15
1.10. Служебные знаки ......Page 17
1.11. Краткое содержание книги ......Page 20
2.2. Простые проверки на четность ......Page 22
2.3. Коды с обнаружением ошибок ......Page 23
2.4. Независимые ошибки — белый шум ......Page 24
2.5. Повторная передача сообщения ......Page 25
2.6. Простые коды для обнаружения пакетов ошибок ......Page 26
2.7. Буквенно-цифровые коды — взвешенные коды ......Page 27
2.8. Обзор модулярной арифметики ......Page 29
2.9. Номера книг в системе ISBN ......Page 30
3.1. Необходимость в исправлении ошибок ......Page 31
3.2. Прямоугольные коды ......Page 32
3.3. Треугольные, кубические и $n$-мерные коды ......Page 33
3.4. Коды Хэмминга для исправления ошибок ......Page 35
3.5. Эквивалентные коды ......Page 38
3.6. Геометрический подход ......Page 39
3.7. Коды с исправлением одиночных ошибок и обнаружением двойных ошибок ......Page 41
3.9. Итоги ......Page 43
4.1. Введение ......Page 44
4.2. Однозначное декодирование ......Page 45
4.3. Мгновенные коды ......Page 46
4.4. Построение мгновенных кодов ......Page 47
4.5. Неравенство Крафта ......Page 48
4.6. Укороченные блочные коды ......Page 50
4.7. Неравенство Макмиллана ......Page 51
4.8. Коды Хаффмена ......Page 52
4.9. Частные случаи кодов Хаффмена ......Page 55
4.11. Коды Хаффмена с основанием $r$ ......Page 57
4.12. Шум в вероятностях кода Хаффмена ......Page 58
4.13. Использование кодов Хаффмена ......Page 60
4.14. Коды Хэмминга—Хаффмеиа ......Page 61
5.2. Что такое марковский процесс? ......Page 62
5.3. Эргодические марковские процессы ......Page 65
5.5. Расширения марковского процесса ......Page 67
5.6. Кодирование с предсказанием ......Page 68
5.7. Кодер для кодирования с предсказанием ......Page 69
5.9. Длины серий ......Page 70
5.10. Итоги рассмотрения кодирования с предсказанием ......Page 72
5.12. Обработка столкновений ......Page 73
5.14. Итоги рассмотрения перемешивания ......Page 74
5.15. Цель кода Грея ......Page 75
5.17. Декодирование кода Грея ......Page 76
5.18. Другие коды ......Page 77
6.2. Информация ......Page 78
6.3. Энтропия ......Page 80
6.4. Математические свойства энтропии ......Page 83
6.5. Энтропия и кодирование ......Page 85
6.6. Кодирование Шеннона—Фано ......Page 86
6.7. Насколько плохим является кодирование Шеннона—Фано? ......Page 87
6.8. Расширения кода ......Page 88
6.9. Примеры расширений ......Page 90
6.10. Энтропия марковского процесса ......Page 92
6.11. Пример марковского процесса ......Page 93
6.12. Смежная система ......Page 94
6.13. Итоги ......Page 96
7.2. Информационный канал ......Page 97
7.3. Соотношения в канале ......Page 98
7.4. Двоичный симметричный канал ......Page 99
7.5. Энтропия системы ......Page 101
7.6. Взаимная информация ......Page 103
7.7. Теорема Шеннона для семейств кодов ......Page 106
8.1. Определение пропускной способности канала ......Page 107
8.2. Канал, симетричный по входу ......Page 108
8.3. Равномерный вход ......Page 109
8.4. Коды с исправлением ошибок ......Page 110
8.5. Пропускная способность двоичного симметричного канала ......Page 111
8.6. Условная взаимная информация ......Page 113
9.1. Введение ......Page 114
9.2. Гамма-функция $\Gamma(n)$ ......Page 115
9.3. Приближение Стирлинга для $n!$ ......Page 116
9.4. Биномиальная оценка ......Page 119
9.5. Евклидово $n$-мерное пространство ......Page 121
9.6. Один парадокс ......Page 123
9.7. Неравенство Чебышева и дисперсия ......Page 124
9.8. Закон больших чисел ......Page 125
10.1. Введение ......Page 128
10.2. Решающие правила ......Page 129
10.3. Двоичный симметричный канал ......Page 131
10.4. Случайное кодирование ......Page 132
10.5. Средний случайный код ......Page 135
10.7. Оценка Фано ......Page 137
10.8. Обратная теорема Шеннона ......Page 139
11.1. Введение ......Page 140
11.2. Еще раз о кодах с проверкой на четность и с обнаружением ошибок ......Page 141
11.3. Еще раз о кодах Хэмминга ......Page 142
11.5. Многочлены или векторы? ......Page 144
11.6. Простые многочлены ......Page 146
11.8. Один частный случай ......Page 148
11.9. Регистры сдвига для кодирования ......Page 151
11.10. Декодирование кодов с исправлением одиночных ошибок ......Page 153
11.11. Код с исправлением двойных ошибок ......Page 154
11.12. Декодирование кодов с исправлением кратных ошибок ......Page 156
11.13. Итоги ......Page 157
А2. Интеграл Фурье ......Page 158
A3. Теорема отсчетов ......Page 159
А4. Ширина полосы и скорость изменения ......Page 160
А5. Амплитудная модуляция ......Page 161
А8. Ширина полосы с общей точки зрения ......Page 162
Приложение Б. Некоторые таблицы для вычисления энтропии ......Page 163
Список литературы ......Page 166
Дополнительный список литературы ......Page 167
Указатель ......Page 168
Оглавление ......Page 171