К.Шеннон РАБОТЫ ПО ТЕОРИИ ИНФОРМАЦИИ И КИБЕРНЕТИКЕ ИЗДАТЕЛЬСТВО ИНОСТРАННОЙ ЛИТЕРАТУРЫ, Москва 1963 Книга представляет собой сборник статей выдающегося математика и инженера, члена Национальной

академии наук США, Клода Эльвуда Шеннона.

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

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

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

СОДЕРЖАНИЕ Предисловие ТЕОРИЯ УПРАВЛЯЮЩИХ СИСТЕМ Символический анализ релейных и переключательных схем Число двухполюсных параллельно-последовательных сетей Синтез двухполюсных переключательных схем Требования, предъявляемые к объему памяти телефонного коммутатора Надежные схемы из ненадежных реле Использование машины для проектирования переключательных схем Вычислительные устройства и автоматы Машина для игры в шахматы Составление программ для игры в шахматы на вычислительной машине Играющие машины Сообщение о машине, решающей лабиринтную задачу Вклад фон Неймана в теорию автоматов ТЕОРИЯ ИНФОРМАЦИИ Математическая теория связи Теория связи в секретных системах Современные достижения теории связи Принципы кодово-импульсной модуляции Связь при наличии шума Некоторые задачи теории информации Пропускная способность канала с шумом при нулевой ошибке Геометрический подход к теории пропускной способности каналов связи Каналы с дополнительной информацией на передатчике Некоторые результаты теории кодирования для каналов с шумами Замечания о частичном упорядочении каналов связи Вероятность ошибки для оптимальных кодов в гауссовском канале Теоремы кодирования для дискретного источника при заданном критерии точности Двусторонние каналы связи РАЗНОЕ Бандвагон Предсказание и энтропия печатного английского текста Упрощенный вывод линейной теории сглаживания и предсказания по методу наименьших квадратов Математическая теория дифференциального анализатора О максимальном потоке через сеть Теорема о раскраске ребер графа Универсальная машина Тьюринга с двумя внутренними состояниями Вычислимость на вероятностных машинах Библиография Именной указатель Предметный указатель ИМЕННОЙ УКАЗАТЕЛЬ Аккерман (Ackermann W.) 13 Вернам (Vernam G. S.) Александров А. Д. 488 Винер (Wiener N.) 180, 215, 293, 294, Александров П. С. 488 309, 322, 403, Батлер (Butler S.) 162, 179 Виньерон (Vigneron H.) Беннет (Bennet W.) 413, 437, 588 Виттстон (Whittstone) Беркли (Berkeley E. С.) 59, 179 Вуджер (Woodger J.) Беркс (Burks A.) 233 Габор (Gabor D.) 403, Беттел (Battel) 193 Галлагер (Gallager R. G.) Бигелоу (Bigelou) 226, 224, 231 Гейне (Gaines H. F.) Биркгоф (Birkhoff G.) 59, 293 Гельфонд А. О. Блекуэлл (Blackwell D.) 650, 685 Герьери (Guerrieri J.) Боде (Bode H. W.) 322, 463, 687 Гилберт (Gilbert E. N.) 104, Больцман (Boltzmann L.) 261, 403 Гилиге (Giliege M.) Брейман (Breiman L.) 658 Гильберт (Hilbert D.) 13, 56, Брозин (Brosin) 230 Гобсон (Hobson E. W.) Буль (Bool G.) 13, 59 Голдстейн (Goldstine H.) Буш (Bush V.) 709 Голей (Goley M. J. F.) Бэббидж (Babbage Ch.) 162, 163 Гольден (Holden) Васильев Ю. Л. 102 Греа (Grea R.) Ватанабе (Watanabe S.) 750 Гупта (Gupta) 51, 53, Велч (Welch В. L.) 550, 551, 572 Гуревич (Hurewicz W.) 293, Давенпорт (Davenport W. В.) 291 Мак-Каллок (McCulloch W.) 148, 163, Данциг (Danzig G.) 730 179, Девид (David H.) 558, 571 Мак-Карти (McCarthy J.) Девис (Davis M.) 781 Мак-Кинси (McKinsey J. С. С.) Де Гроот (De Groot A. D.) 186, 196, Мак-Коллум (McCollum D. M.) 167, 209, 215 Де-Леу (De Leeuw К.) 751 Мак-Лейн (MacLane S.) Дерр (Derr) 196 Мак-Магон (Mac Mahon P.) 46, Джерард (Gerard)225, 231 Мак-Миллан (McMillan B.) 322, Джонсон (Johnson N.) 550, 551, 572 Мецар (Meszar J.) Дибольд (Diebold J.) 179 Мид (Mead) Добрушин Р. Л. 281, 319, 330, 543, Монтгомери (Montgomerie G.) 587, 598 Моргенштерн (Morgenstern O.) 194, Дуб (Doob J. L.) 293, 343, 781 215, Дьюи (Dewey G.) 253, 671 Myp (Moore E. F.) 114, 154, 169, Игонне (Higonnet R.) 102 Mypora (Muroga S.) 288, Кантор (Cantor G.) 445 Мурский В. Л. Кардо (Cardot С.) 102 Мюирхед (Muirhead) Кейстер (Keister W.) 219 Найквист (Nyquist H.) 243, 403, 434, Кельвин (Kelvin) 709 Кемпелен (Kempelen von W.) 182, Накасима (Nakasima A.) 9, 193, 217 Нейман фон (Naumann von J.) 114, Кендалл (Kendall M. G.) 251 176-178, 180, 194, 215, 231, Кёниг (Konig D.) 735 233Ч239, 293, Клини (Kleene S. C.) 165, 179, 782 Новиков П. С. Колмогоров А. Н. 332, 343, 587, 687 Оливер (Oliver B.) 322, 414, Кондон (Condon) 196 Оруэлл (Orowell G.) Котельников В. А. 295, 435 Оттингер (Oettinger A. E.) 173, Котурат (Couturat L.) 13, 59 Петерсен (Petersen J.) Крамер (Cramer H.) 638 Пиз (Pease W.) Кричевский Р. Е. 58 Пинскер М. С. Крускал (Kruskal W.) 558, 571 Пирс (Pierce J. R.) 322, Крылов А. Н. 709 Питтс (Pitts W.) 59, 148, 179, Кудрявцев Л. Д. 735 Пиш (Piesch H.) Купман (Koopman) 293 Поваров Г. Н. 102, Курант (Courant R.) 56 Пойа (Полна) (Polya G.) Кэли (Cayley A.) 46 Пост (Post E. L.) Кэннон (Cannon W. B.) 175 Пратт (Pratt F.) 253, 366, 382, Ландаль (Landahl H. D.) 179 Раис (Rice S. O.) 542, Литльвуд (Littlewood J. E.) 682 Райт (Wright E. M.) 50, 195, Лупанов О. Б. 102, 104 Райффа (Raiffa H.) Льюс (Luce R. D.) 341 Риордан (Riordan J.) 46, 82, Любич Ю. И. 322 Poccep (Rosser J.) Рут (Root W. L.) Самуэль А. Л. (Samuel A. L.) 220 Форд (Ford L.) Сарымсаков Г. А. 256 Фостер (Foster R. M.) 46, Севидж (Savage L. J.) 223, 225, 226, Франк (Frank) 226, 228 231 Фреше (Frechet M.) Силверман (Silverman R.) 538 Смит Фробениус (Frobenius G.) 525, (Smith J. B.) 167, 179, 251 Халмош (Halmos P. R.) Стрэчн (Strachey C. S.) 170, 171, 180, Хантингтон (Huntington E. V.) 220, 309 Харди (Hardy G. N.) 50, 195, 215, Сулливан (Sullivan H.) 309, 403 Харкевич A. A. Таллер (Tuller W. G.) 309, 403 Харкнес (Harkness) Тихомиров В. 332 Хартли (Hartley R. V. L.) 243, 244, Тойбер (Teuber) 226, 230 403, 413, Толмен (Tolman R. С.) 261 Хартри (Hartree D.) Томасян (Thomasian A.) 658 Хаусхолдер (Householder A. S.) Торрес-и-Квеведо (Torres у Quevedo Хегельбергер (Hagelbarger D. W.) L.) 182, 191, 218 174, 221, 651, Тоуни (Tawney) 196 Хилл (Hill L. S.) Трахтенброт Б. А. 165 Хинчин А. Я. 261, Троттер (Trotter H.) 771 Холбрук (Holbrook B. D.) Туркетт (Turquette A.) 13 Хопф (Hopf E.) 293, 398, Тьюринг (Turing A. M.) 165, 166, 180, Хопф (Hopf H.) 236, 238, 740, 741, 782 Хоэл (Hoel P. G.) Уайтхед (Whitehead A.) 13 Хэмминг (Hamming R.) Уивер (Weaver E.) 243 Ципф (Zipf C. V.) Уиттекер (Whittaker J.) 437 Чандрасекар (Chandrasekhar S.) Уолман (Wallman H.) 445 Чернев (Chernev) Фаддеев В. К. 261 Чернов (Chernoff H.) 517, 531, Фаин (Fine R.) 209, 215 Черч (Church A.) Файнстейн(Реш51еш A.) 281, 531, Шапиро (Shapiro N.) 729 Шестаков В. И. Фалкерсон (Fulkerson D.) 730 Эйлер (Euler L.) Фано (Fano R. M.) 272 Элайес (Elias P.) 487, 531, 543, Фелдман (Feldman С. В.) 413 Эшби (Ashby W. R.) 175, 176, Феллер (Feller W.) 256, 257, 781 Яблонский С. В. 13, Фёрстер (Foerster von) 228, 230 Яглом А. М. Финк (Fink D. G.) 413 Яглом И. М. ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ Алгебра Буля 13, 59 Анализатор контактных схем Ч Ч интерпретация 60 Ч Ч Ч особенности Ч Ч класс функций 92, 128 Ансамбль функций Ч Ч логическая интерпретация 13 Ч Чс ограниченной длительностью Ч Ч особые правила 61 Ч Ч функция кворума 128 Ч Ч Ч Ч полосой частот Ч секретных систем 350 Ч Ч скорость числа измерений Ч Ч стационарный 292 Искажения мера 589, 612, 614. Ч Ч эргодический 293 Ч Ч схем Асимптотическая надежность 577 Источник информации 245, Асимптотическое распределение 705 Ч Ч дискретный 249, Бит 244 Ч Ч Ч с конечным числом Вероятность ошибки 467, 514, 548 состояний Ч Ч оптимальная 542, 551 Ч Ч непрерывный Ч Ч Ч границы 565, 566, 571, 574, Ч Ч произведение 577 Ч Ч скорость создания сообщений Ч Ч средняя для множества кодов 318, 320, 511 Ч Ч смешанный Ч Ч Ч Ч ансамбля пар кодов 632 Ч Ч с независимыми буквами Выходные последовательности Ч Ч эргодический 257, случайного устройства 772 Исчисление высказываний Вычислительные устройства и Канал 246, автоматы 162 Ч гауссовский Групповая инвариантность 93 Ч двоичный двусторонний Ч Ч для двух переменных 98 умножающий Ч Ч Ч трех переменных 98 Ч Ч симметричный 543, Ч Ч специальный случай 94 Ч Ч стирающий Декодирование 500 Ч двусторонний 622, Ч по минимуму расстояния и Ч Ч с памятью максимуму правдоподобия 541 Ч Ч Ч симметричной структурой Декодирующая система 465 Ч Ч оптимальная 541 Канал дискретный без памяти 465, Дискретный преобразователь 268 Дискретный преобразователь Ч Ч Ч шума вырожденный 268 Ч Ч Ч с шумом Дифференциальный анализатор 709 Ч непрерывный Ч Ч автоматическое управление Ч произведение 466, работой 726 Ч с дополнительной информацией Ч Ч идеализированный 711 Ч Ч передаточные числа 725 Ч Ч конечным числом состояний Избыточность кода 267 522, Ч английского языка 267 Ч Ч обратной связью Инвариантно устройство (оператор) Ч Ч памятью 294 Ч Ч Г концами Информация взаимная 630 Ч сумма 564, Ч мера 245 Ч частичное упорядочивание Ч- скорость передачи 277, 305, 595 Ч чистый Ч средние взаимные скорости Канала надежность передачи 628 Квантование Искажение 275 Код блоковый для дискретного Ч полное 589 канала без памяти Ч Ч Ч двустороннего канала 627 Ч кодово-импульсная 403, 414, 425, Ч Ч Ч канала с дополнительной информацией 499 Ч фазово-импульсная 403, Ч входная скорость 465 Ч частотная 403, Ч райсовский 573 Ненадежность Ч случайный 470 Ч ключа 368, Ч Хегельбергера 651 Ч и избыточность Кодирование 604, 630, 631 Ч распределение Кодовое слово 509 Криптограмма Ч свойства 335, 389 Ч случайного шифра Логика символическая 13 Ч сообщения 368, Ч Ч система аксиом 14 Отклонение вероятности Матрица смежности 469 Отношение сигнал/шум Машина Тьюринга 165, 740 Отображение, понижающее Ч Ч метод построения 741 смежность Ч Ч моделирование 747 Переключатели селекторные Ч Ч понятие A-вычислимости 166 Ч шаговые Ч Ч проблема работы 742 Помехоустойчивость Ч Ч с двумя состояниями 741 Пороговая мощность Ч Ч Ч одним состоянием 744 Пороговой эффект Ч Ч универсальная 166 Предсказание английского языка Ч Ч Ч свойства 166 Ч идеальное n-граммное 677, Машины вероятностные 751 Ч линейное 689, 701, Ч Ч классы 752 Ч минимально-квадратичное Ч вырабатывающие свои принципы Ч лобратное игры 220 Ч по методу Винера Ч Колмогорова Ч вычислительной и мозга сравнение 237 Ч при наличии шума Ч для игры в полностью Предсказания средне-квадратичная проанализированные игры 218 ошибка Ч Ч Ч полный анализ которой Пропускная способность, неизвестен 219 геометрический подход Ч Ч нахождения пути в лабиринте Ч Ч дискретного канала без памяти 172 с дополнительной информацией Машины играющие 168, 216 488, Ч Ч группы 168 Ч Ч Ч Ч Ч шума Ч Ч типы 218 Ч Ч Ч Ч с шумом Ч логические 162 Ч Ч канала с конечным числом Ч обучаемые 171 состояний 522, Ч Ч гомеостат 175 Ч Ч Ч Ч шумом при нулевой Ч стохастические 765 ошибке 464, 466, 467, Модуляция амплитудная 420 Ч Ч Ч Ч памятью Ч Ч однополосная 442 Ч Ч непрерывного канала Пропускная способность Ч поведение непрерывного канала при Ч подсчет по Гупта ограничении средней мощности Ч Ч Ч Дарбу 308 ЧЧ Ч Эйлеру Ч Ч Ч Ч Ч Ч пиковой мощности Ч получение производящей функции 309 Ч Ч при наличии белого шума 446 Ч правило соответствия Ч Ч Ч произвольном типе шума Ч приведенные 455 Ч расширенные Пропускной способности область Ч ребра 628, 654, 659 Ч сечение Процесс марковский 255, 342 Сети существенно-параллельные Рабочее число 33 Ч существенно-последовательные Реле идеализированные 116 Ч эквивалентность соединений Ч нижняя оценка числа контактов Сопротивления способы соединения 142 Ч распределение нагрузок 66, 83 Ч схем способы определения Ч с неопределенным временем Ч функция 11, 21, срабатывания 146 Сумматор Ч типы неисправностей 116 Схем общая теория Сглаживание 687, 703 Ч переключательных анализ Ч линейное 689 Ч Ч синтез Секретные системы 333 Ч Ч теория Ч Ч идеальные 338, 382 Ч сопротивление Ч Ч идемпотентные 353 Схема гамакообразная 138, 144, Ч Ч подобные 337, 359 Ч универсальная Ч Ч совершенно 361, 363 Схемы вероятность замыкания Ч Ч чистые 336 Ч Ч размыкания Ч Ч эндоморфные 352 Ч верхние границы вероятности Ч Ч Ч лалгебраические системы ошибок 353 Ч двоичное сопротивление Система связи 245, 433 Ч двойственные Ч Ч геометрическое представление Ч двухполюсные 10, 437, 439, 441, 442 Ч длина Ч Ч дискретная 246 Ч заданной длины и ширины Ч Ч идеальная 451 Ч метод каскадов Ч Ч непрерывная 246 Ч Ч нахождения Ч Ч смешанная 246 Ч Ч повышения надежности Ч декодирования 509, 627 Ч Ч построения Ч рабочих чисел 33 Ч мостиковые Сети аппроксимация числа 57 Ч направленного действия Ч асимптотическое поведение 54 Ч нахождение двойственной Ч максимальный поток через 729 Ч не параллельно-последовательные Ч параллельно-последовательные 46 Ч Ч Ч Ч методы построения 21 Ч синтеза основная Ч Ч Ч Ч многополюсные 19 Теория автоматов Ч параллельно-последовательные 17 Ч Ч вклад фон Неймана Ч параллельные 11 Ч Ч Ч Ч Ч мультитрюк Ч переключательные 9, 154 Ч Ч проблемы эволюции Ч преобразования 19 Точность передачи Ч проектирование двухполюсных Точности критерий 316, 155 Фильтр линейный Ч Ч на анализаторе 155 Ч с минимальной фазовой Ч разделительное дерево 89 характеристикой 693, Ч разделительные 67 Функции несимметрические Ч реализующей функцию синтез 32 Ч произвольной реализация Ч релейные 9 Ч частично-симметрические, Ч Ч синтез 47 Ч h (p) свойства Ч Ч с постоянным напряжением Ч (n) оценка Ч с блокировкой Функций ансамбль Ч селекторные Ч метод реализации Ч символический анализ Функций реализация Ч синтез надежных Ч Ч симметрических 35, Ч Ч переключательных Функциональная разделимость Ч символический анализ Функциональных соотношений типы Ч сложение сопротивлений Ч с постоянным током Функция переключательная Схемы типы Ч порождающая Ч Ч соединений Ч производящая 46, Ч умножение сопротивлений Ч Ч получение Ч управления Ч сопротивления схемы Ч Ч свойства Ч (n) Ч формирование функций Ч Ч поведение нескольких переменных Ч (n) Ч функция h(p) Шифр Бофора 345, Ч ширина Ч Вернама 346, Ч эквивалентной данной, методы Ч Виженера 345, 346, 360, нахождения Ч дробный Теорема де Моргана Ч Плэйфер Ч для канала без шума, основная Ч простой подстановки Ч Ч дискретного канала с шумом, Ч случайный основная Ч чистый 354, Ч о раскраске ребер графа Ч Цезаря 345, 358, 360, Ч Ч схемах и функциях 26Ч Шум белый 292, 304, 408, 409, 448, Ч Ч способах соединения сопротивлений 12, Ч Ч мощность Ч Ч эргодических источниках Ч Гауссовский, см. шум белый Ч отсчетов (Котельникова) Ч Ч произвольный 454 Ч ансамбля функций 300, Ч квантования 415, 423 Ч непрерывного распределения Ч тепловой, см. шум белый Ч относительная Энтропийная мощность 301, 303, 456 Ч условная 263, Энтропия 261 Эффективный процесс Ч английского языка    Книги, научные публикации