Работы по теории информации и кибернетики (1963)

  

К. Шеннон. Работы по теории информации и кибернетики. М. 1963 г.

Книга представляет собой сборник статей выдающегося математика и инженера, члена Национальной академии наук США, Клода Эльвуда Шеннона. Многие из включенных в сборник работ, опубликованных проф. Шенноном в различных журналах в 1938—1962 годах, положили начало новым областям исследований в области общей теории связи, теории автоматов, электротехники, теории информации и лингвистики, таким, как теория анализа и синтеза релейных устройств, теория вероятностных схем, теория передачи информации и т. д.

Статьи расположены в сборнике по тематическому принципу: в первой части помещены работы по теории управляющих систем, во второй — по теории информации, в третьей — все остальные. В конце книги приводится библиография работ по теории информации.

Книга представляет интерес для широкого круга математиков и специалистов, работающих в области автоматического управления, теории связи, радиотехники, теории надежности и в смежных областях, так или иначе связанных с использованием результатов теории информации. Она будет полезна также студентам старших курсов университетов и технических вузов, инженерам и научным работникам различных специальностей, занимающимся вопросами, связанными с математическими аспектами кибернетики.



Оглавление

ПРЕДИСЛОВИЕ
СИМВОЛИЧЕСКИЙ АНАЛИЗ РЕЛЕЙНЫХ И ПЕРЕКЛЮЧАТЕЛЬНЫХ СХЕМ
2. Параллельно-последовательные двухполюсные схемы. Основные определения и постулаты
3. Многополюсные и не параллельно-последовательные схемы
Преобразование треугольника в звезду и звезды в ячейку
Функция сопротивления не параллельно-последовательной схемы
Системы уравнений
Реле и переключатели специальных типов
4. Синтез схем
Двойственные схемы
Синтез схем, реализующих симметрические функции
Составление уравнений по рабочим характеристикам
5. Примеры
ЧИСЛО ДВУХПОЛЮСНЫХ ПАРАЛЛЕЛЬНО-ПОСЛЕДОВАТЕЛЬНЫХ СЕТЕЙ
1. Получение производящей функции
2. Численный подсчет
3. Асимптотическое поведение
4. Параллельно-последовательная реализация переключательных функций
СИНТЕЗ ДВУХПОЛЮСНЫХ ПЕРЕКЛЮЧАТЕЛЬНЫХ СХЕМ
2. Основная теорема синтеза
3. Синтез схем для произвольных функций.
Часть II. РАСПРЕДЕЛЕНИЕ НАГРУЗКИ МЕЖДУ РЕЛЕ
5. Разделительное дерево
6. Другие задачи распределения
7. Функция «мю»
Часть III. СПЕЦИАЛЬНЫЕ ФУНКЦИИ
9. Частично симметрические функции
ПРИМЕЧАНИЯ РЕДАКТОРА
ТРЕБОВАНИЯ, ПРЕДЪЯВЛЯЕМЫЕ К ОБЪЕМУ ПАМЯТИ ТЕЛЕФОННОГО КОММУТАТОРА
2. Память, требуемая для S произвольных вызовов от N абонентов
3. Условие раздельной памяти
4. Связь с теорией информации
НАДЕЖНЫЕ СХЕМЫ ИЗ НЕНАДЕЖНЫХ РЕЛЕ
Идеализированные реле
Общий метод повышения надежности
Свойства функции h(p)
Комбинация двух схем
Оценки функции h'(p)
Схемы заданной длины и ширины
Оценки числа контактов в случае, когда реле уже достаточно надежны
Сравнение с элементами фон Неймана
Реле с неопределенным временем срабатывания
Синтез надежных схем в целом
Приложение. Верхние оценки для вероятностей ошибок в случае гамакообразных l-w-схем
ИСПОЛЬЗОВАНИЕ МАШИНЫ ДЛЯ ПРОЕКТИРОВАНИЯ ПЕРЕКЛЮЧАТЕЛЬНЫХ СХЕМ
ВЫЧИСЛИТЕЛЬНЫЕ УСТРОЙСТВА И АВТОМАТЫ
Машины Тьюринга
Логические машины
«Играющие машины»
Обучаемые машины
Самовоспроизводящиеся машины
Обращение к читателю
МАШИНА ДЛЯ ИГРЫ В ШАХМАТЫ
СОСТАВЛЕНИЕ ПРОГРАММ ДЛЯ ИГРЫ В ШАХМАТЫ НА ВЫЧИСЛИТЕЛЬНОЙ МАШИНЕ
3. Приближенная оценочная функция
4. Стратегия, основанная на оценочной функции
5. Составление программы для универсальной вычислительной машины для реализации стратегии типа А
6. Улучшение стратегии
7. Изменения в игре и в стиле
8. Другой тип стратегии
ПРИЛОЖЕНИЕ. ОЦЕНОЧНАЯ ФУНКЦИЯ ДЛЯ ШАХМАТ
ИГРАЮЩИЕ МАШИНЫ
СООБЩЕНИЕ О МАШИНЕ, РЕШАЮЩЕЙ ЛАБИРИНТНУЮ ЗАДАЧУ
ВКЛАД ФОН НЕЙМАНА В ТЕОРИЮ АВТОМАТОВ
МАТЕМАТИЧЕСКАЯ ТЕОРИЯ СВЯЗИ
1. ДИСКРЕТНЫЕ СИСТЕМЫ БЕЗ ШУМОВ
2. Дискретный источник сообщений
3. Последовательные приближения к английскому языку
4. Графическое представление марковского процесса
5. Эргодические и смешанные источники
6. Выбор, неопределенность и энтропия
7. Энтропия источника сообщений
8. Представление операций кодирования и декодирования
9. Основная теорема для канала без шума
10. Рассмотрение полученных результатов и примеры
11. Примеры
II. ДИСКРЕТНЫЙ КАНАЛ С ШУМОМ
12. Надежность и пропускная способность канала
13. Основная теорема для дискретного канала с шумом
14. Рассмотрение полученных результатов
15. Пример дискретного канала и его пропускной способности
16. Пропускная способность канала в некоторых частных случаях
17. Пример эффективного кодирования
III. ИНФОРМАЦИЯ ДЛЯ НЕПРЕРЫВНЫХ ВЕЛИЧИН
19. Ансамбли функций с ограниченной полосой частот
20. Энтропия непрерывного распределения
21. Энтропия ансамбля функций
22. Потеря энтропии в линейных фильтрах
23. Энтропия суммы двух ансамблей
IV. НЕПРЕРЫВНЫЙ КАНАЛ
24. Пропускная способность непрерывного канала
25. Пропускная способность канала при ограничении средней мощности
26. Пропускная способность канала при ограничении пиковой мощности
V. СКОРОСТЬ СОЗДАНИЯ СООБЩЕНИЙ ДЛЯ НЕПРЕРЫВНОГО ИСТОЧНИКА
28. Скорость создания сообщений источником при данной точности воспроизведения
29. Вычисление скорости создания сообщений
Приложение 1. РОСТ ЧИСЛА БЛОКОВ СИМВОЛОВ ПРИ УСЛОВИЯХ, ОПИСЫВАЕМЫХ КОНЕЧНЫМ ЧИСЛОМ СОСТОЯНИЙ
Приложение 2. ВЫВОД РАВЕНСТВА …
Приложение 3. ТЕОРЕМА ОБ ЭРГОДИЧЕСКИХ ИСТОЧНИКАХ
Приложение 4. МАКСИМИЗАЦИЯ СКОРОСТИ ДЛЯ СИСТЕМЫ ОГРАНИЧЕНИЯ
Приложение 5
Приложение 6
Приложение 7
ТЕОРИЯ СВЯЗИ В СЕКРЕТНЫХ СИСТЕМАХ
Часть I. МАТЕМАТИЧЕСКАЯ СТРУКТУРА СЕКРЕТНЫХ СИСТЕМ
3. Способы изображения систем
4. Примеры секретных систем
5. Оценка секретных систем
6. Алгебра секретных систем
7. Чистые и смешанные шифры
8. Подобные системы
Часть II. ТЕОРЕТИЧЕСКАЯ СЕКРЕТНОСТЬ
10. Совершенная секретность
11. Ненадежность
12. Свойства ненадежности
13. Ненадежность простой подстановки для языка с двухбуквенным алфавитом
14. Характеристика ненадежности для «случайного» шифра
15. Применение к стандартным шифрам
16. Правильность решения криптограммы
17. Идеальные секретные системы
18. Примеры идеальных секретных систем
19. Дополнительные замечания о ненадежности и избыточности
20. Распределение ненадежности
Часть III. ПРАКТИЧЕСКАЯ СЕКРЕТНОСТЬ
22. Общие замечания о решении криптограмм
23. Статистические методы
24. Метод вероятных слов
25. Перемешивание
26. Шифры типа …
27. Несовместимость требований к хорошим системам
ПРИЛОЖЕНИЕ. Доказательство теоремы 3
СОВРЕМЕННЫЕ ДОСТИЖЕНИЯ ТЕОРИИ СВЯЗИ
Измерение информаций
Кодирование информации
Пропускная способность канала
Идеальные и практические системы
ПРИНЦИПЫ КОДОВО-ИМПУЛЬСНОЙ МОДУЛЯЦИИ
2. Условия передачи для КИМ
3. Действие системы КИМ
4. Сравнение КИМ и ЧМ
5. Заключение
Приложение I
Приложение II
СВЯЗЬ ПРИ НАЛИЧИИ ШУМА
2. Теорема отсчетов
3. Геометрическое представление сигналов
4. Геометрическое представление сообщений
5. Геометрическое представление передатчика и приемника
6. Отображение пространства
7. Пропускная способность канала при наличии белого теплового шума
8. Обсуждение
9. Произвольный гауссовский шум
10. Пропускная способность канала при произвольном типе шума
11. Дискретные источники информации
12. Непрерывные источники информации
НЕКОТОРЫЕ ЗАДАЧИ ТЕОРИИ ИНФОРМАЦИИ
ПРОПУСКНАЯ СПОСОБНОСТЬ КАНАЛА С ШУМОМ ПРИ НУЛЕВОЙ ОШИБКЕ
Пропускная способность канала при нулевой ошибке
Пропускная способность для суммы и произведения каналов
Каналы с обратной связью
ГЕОМЕТРИЧЕСКИЙ ПОДХОД К ТЕОРИИ ПРОПУСКНОЙ СПОСОБНОСТИ. КАНАЛОВ СВЯЗИ
КАНАЛЫ С ДОПОЛНИТЕЛЬНОЙ ИНФОРМАЦИЕЙ НА ПЕРЕДАТЧИКЕ
Дискретный канал без памяти с дополнительной информацией о состоянии
Приложение
НЕКОТОРЫЕ РЕЗУЛЬТАТЫ ТЕОРИИ КОДИРОВАНИЯ ДЛЯ КАНАЛОВ С ШУМАМИ
Оценка вероятности ошибки в терминах производящей функции моментов
Пропускная способность канала с конечным числом состояний, состояние которого вычислимо на обоих концах
Пропускная способность канала с конечным числом состояний в случае, когда состояние вычислимо на передающем конце и не вычислимо на приемном конце
ЗАМЕЧАНИЯ О ЧАСТИЧНОМ УПОРЯДОЧИВАНИИ КАНАЛОВ СВЯЗИ
Дальнейшее обобщение и некоторые предположения
ВЕРОЯТНОСТЬ ОШИБКИ ДЛЯ ОПТИМАЛЬНЫХ кодов В ГАУССОВСКОМ КАНАЛЕ
2. Сводка результатов
3. Нижняя граница, основанная на соображениях «сферической упаковки»
4. Верхняя граница, определяемая методом случайного кодирования
5. Формулы для скорости передачи R как функции угла конуса
6. Асимптотические формулы для …
7. Асимптотическое выражение для верхней границы при случайном кодировании
8. Жесткая верхняя граница
9. Жесткая нижняя граница
10. Поведение границ вблизи пропускной способности канала
11. Верхняя граница, полученная методом исчерпывания
12. Нижняя граница для гауссовского канала, получаемая исходя из минимального расстояния
13. Границы ошибок и другие условия, накладываемые на точки
14. Кривые для асимптотических границ
ТЕОРЕМЫ КОДИРОВАНИЯ ДЛЯ ДИСКРЕТНОГО ИСТОЧНИКА ПРИ ЗАДАННОМ КРИТЕРИИ ТОЧНОСТИ
Мера искажения отдельной буквы
Несколько простых примеров
Скорость при заданном искажении R(d)
Выпуклость вниз кривой R(d)
Нахождение R(d) в некоторых простых случаях
Скорость передачи для произведения источников с мерой, являющейся суммой мер искажения
Нижняя граница для искажения при заданной пропускной способности канала
Теоремы кодирования при заданной мере искажения отдельной буквы
Двойственность источника и канала
Численные расчеты для некоторых простых каналов
Обобщение на случаи непрерывных алфавитов
Разностная мера искажения
Определение меры локального искажения
Функции Rn(d) и R(d) для меры локального искажения и эргодического источника
Прямая теорема кодирования для меры локального искажения
Обратная теорема кодирования
Канал с памятью
ДВУСТОРОННИЕ КАНАЛЫ СВЯЗИ
4. Средние взаимные скорости передачи информации
5. Распределение информации
6. Случайное кодирование для двусторонних каналов
7. Вероятность ошибки для ансамбля кодов
8. Выпуклая оболочка G как внутренняя граница области пропускной способности
9. Внешняя граница для области пропускной способности
10. Выпуклость вниз как функций от …
11. Приложения свойства выпуклости. Каналы с симметричной структурой
12. Характер области, выделяемой внешней границей
13. Пример, в котором внутренняя и внешняя границы различны
14. Достижимость внешней границы при зависимых источниках
15. Общий метод нахождения области пропускной способности двустороннего канала
16. Двусторонние каналы с памятью
17. Обобщение на каналы с Т концами
БАНДВАГОН
ПРЕДСКАЗАНИЕ И ЭНТРОПИЯ ПЕЧАТНОГО АНГЛИЙСКОГО ТЕКСТА
2. Вычисление энтропии по статистике английского языка
3. Предсказание английского текста
4. Идеальное N-граммное предсказывание
5. Граница для энтропии на основании частот предсказания
6. Результаты эксперимента для английского языка
УПРОЩЕННЫЙ ВЫВОД ЛИНЕЙНОЙ ТЕОРИИ СГЛАЖИВАНИЯ И ПРЕДСКАЗАНИЯ ПО МЕТОДУ НАИМЕНЬШИХ КВАДРАТОВ
3. Свойства линейных фильтров
4. Основное выражение для среднеквадратичной ошибки
5. Чистая проблема сглаживания
6. Проблема чистого предсказания
7. Предсказание при наличии шума
8. Обобщения
9. Обсуждение основных предположений
МАТЕМАТИЧЕСКАЯ ТЕОРИЯ ДИФФЕРЕНЦИАЛЬНОГО АНАЛИЗАТОРА
Основное условие разрешимости
Реализация функций
Системы уравнений
Аппроксимация множителей с помощью передаточных чисел
Автоматическое управление скоростью работы устройства
О МАКСИМАЛЬНОМ ПОТОКЕ ЧЕРЕЗ СЕТЬ
ТЕОРЕМА О РАСКРАСКЕ РЕБЕР ГРАФА
УНИВЕРСАЛЬНАЯ МАШИНА ТЬЮРИНГА С ДВУМЯ ВНУТРЕННИМИ СОСТОЯНИЯМИ
Невозможность создания универсальной машины Тьюринга с одним состоянием
Моделирование машины Тьюринга с помощью только двух символов на ленте
ВЫЧИСЛИМОСТЬ НА ВЕРОЯТНОСТНЫХ МАШИНАХ
Приложение
БИБЛИОГРАФИЯ РАБОТ ПО ШЕННОНОВСКОЙ ТЕОРИИ ОПТИМАЛЬНОГО КОДИРОВАНИЯ ИНФОРМАЦИИ
email@scask.ru