Идеи, определившие облик информатики

Идеи,  
определившие  
облик информатики 
Под редакцией Гарри Р. Льюиса 

Ideas  
That Created  
the Future
Classic Papers of Computer Science
Edited by Harry R. Lewis
The MIT Press
Cambridge, Massachusetts
London, England

Идеи,  
определившие  
облик информатики
Классические статьи  
по компьютерным наукам 
Под редакцией Гарри Р. Льюиса
Москва, 2023

УДК	 004.04
ББК 32.372
И29
И29 	 Идеи, определившие облик информатики / под ред. Гарри Р. Льюиса; пер. 
с англ. А. А. Слинкина. – М.: ДМК Пресс, 2023. – 616 с.: ил. 
ISBN 978-5-93700-208-2
В книге собрано 46 классических статей по информатике, которые прочертили 
карту развития этой науки. Охвачены все аспекты компьютерных наук; особое внимание уделяется периоду с 1936 по 1980 год, но рассматриваются и важные ранние 
работы. Знакомя читателей с работами мыслителей от Аристотеля и Лейбница до 
Алана Тьюринга и Норберта Винера, книга документирует открытия и изобретения, приведшие к созданию современных цифровых технологий. Каждую статью 
сопровождает краткий очерк, где представлен исторический и интеллектуальный 
контекст, за авторством Гарри Льюиса, редактора издания. 
Книга будет полезна всем, кто интересуется информатикой и истоками этого 
увлекательного мира.
УДК  004.04
ББК  32.372
The MIT Press Cambridge, Massachusetts London, England. 
The rights to the Russian-language edition obtained through Igor Korzhenevskiy of Alexander 
Korzhenevski Agency (Moscow).
Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения 
владельцев авторских прав.
ISBN 978-0-26204-530-8 (англ.) 	
©  2021 Harry R. Lewis
ISBN 978-5-93700-208-2 (рус.) 	
©  Перевод, оформление, издание,  
ДМК Пресс, 2023

Посвящается  
тем экстравагантным и скептически  
настроенным учителям, которые показали мне новые места:  
Филу Бриджесу, Джиму Магуайру, Вэну Эллиоту,  
Десмонду О’Грейди, Шейле Грейбах, Тому Читэму,  
Айвену Сазэрленду и Бэрту Дребену

Я могу предсказать твое будущее. Нет ничего проще. …  
Но кто может знать твое прошлое? … Что оно значило?  
Что оно пыталось сказать тебе?
– Торнтон Уайльдер «The Skin of Our Teeth»

Содержание
От издательства.....................................................................................................11
Предисловие............................................................................................................12
Введение: корни и рост информатики.......................................................15
1 
Первая аналитика (~350 год до н. э.)..................................................25
Аристотель
2 
Истинный метод (1677)...........................................................................30
Готфрид Вильгельм Лейбниц
3 
Набросок Аналитической машины (1843)......................................35
Л. Ф. Менабреа с замечаниями переводчика, Ады Августы, 
графини Лавлейс
4 
Исследование законов мышления, на которых  
основаны математические теории  логики  
и вероятностей (1854)...............................................................................54
Джордж Буль
5 
Математические проблемы (1900).....................................................74
Давид Гильберт
6 
О вычислимых числах с приложением к проблеме 
разрешения (1936)......................................................................................81
Алан Мэтисон Тьюринг
7 
Предлагаемая автоматическая вычислительная  
машина (1937)..............................................................................................94
Говард Хатауэй Эйкен
8 
Символический анализ релейных и переключательных  
схем.................................................................................................................106
Клод Шеннон

Содержание
9 
Логическое исчисление идей, относящихся к нервной 
активности..................................................................................................115
Уоррен Мак-Каллок и Уолтер Питтс
10 
Первая редакция отчета о EDVAC (1945)........................................127
Джон фон Нейман
11 
Как мы можем мыслить (1945)..........................................................148
Ванневар Буш
12 
Математическая теория связи (1948)..............................................165
Клод Шеннон
13 
Коды с обнаружением и исправлением ошибок (1950)..........182
Р. У. Хэмминг
14 
Вычислительные машины и разум..................................................196
Алан Мэтисон Тьюринг
15 
Наилучший метод конструирования автоматической 
вычислительной машины (1951)......................................................221
Морис Уилкс
16 
Обучение компьютера (1952)..............................................................226
Грейс Мюррей Хоппер
17 
О кратчайшем остовном поддереве графа и о задаче 
коммивояжера (1956).............................................................................239
Джозеф Б. Крускал мл.
18 
Перцептрон: вероятностная модель хранения 
и организации информации (1958).................................................244
Фрэнк Розенблатт
19 
Некоторые этические и технические последствия 
автоматизации (1960)............................................................................254
Норберт Винер
20 
Симбиоз человека и машины (1960)...............................................264
Дж. К. Р. Ликлайдер
21 
Рекурсивные функции символических выражений 
и их вычисление машиной (1960)....................................................279
Джон Маккарти
22 
Усиление человеческого интеллекта: концептуальная 
модель (1962)..............................................................................................291
Дуглас К. Энгельбарт

Содержание
23 
Экспериментальная система с разделением времени  
(1962)..............................................................................................................305
Фернандо Корбато, Марджори Мервин Даггетт, Роберт К. Дейли
24 
Sketchpad (1963).........................................................................................322
Айвен Э. Сазерленд
25 
Упаковка большего числа компонентов  
на интегральной схеме (1965)............................................................333
Гордон Мур
26 
Решение задачи параллельного управления  
программой (1965)...................................................................................341
Эдсгер Дейкстра
27 
Элиза – компьютерная программа для изучения 
взаимодействия между человеком  и машиной  
на естественном языке (1966)............................................................346
Джозеф Вейценбаум
28 
Структура системы мультипрограмми-рования THE  
(1968)..............................................................................................................355
Эдсгер Дейкстра
29 
О вреде оператора go to (1968)...........................................................367
Эдсгер Дейкстра
30 
Метод исключения Гаусса не оптимален (1969)........................371
Фолькер Штрассен
31 
Аксиоматическая основа компьютерного 
программирования (1969)....................................................................375
Ч. Э. Р. Хоар
32 
Реляционная модель данных для больших совместно 
используемых банков данных (1970)..............................................387
Эдгар Ф. Кодд
33 
Управление разработкой больших компьютерных  
систем (1970)...............................................................................................404
Уинстон У. Ройс
34 
Сложность процедур вывода теорем (1971).................................418
Стивен А. Кук
35 
Статистическая интерпретация специфичности  
термина и ее применение к поиску  (1972)...................................426
Карен Спарк Джонс

Содержание
36 
Сводимость комбинаторных проблем (1972)..............................437
Ричард Карп
37 
Система с разделением времени Unix (1974)..............................446
Деннис Ритчи и Кеннет Томпсон
38 
Протокол взаимодействия сетей с коммутацией  
пакетов (1974)............................................................................................466
Винтон Серф и Роберт Кан
39 
Программирование с абстрактными типами данных  
(1974)..............................................................................................................483
Барбара Лисков и Стивен Зиллес
40 
Мифический человеко-месяц (1956)...............................................497
Фредерик Ф. Брукс
41 
Ethernet: распределенная коммутация пакетов  
для локальных вычислительных сетей  (1976)............................507
Роберт Меткалф и Дэвид Р. Роджерс
43 
Новые направления в криптографии (1976)...............................525
Уитфилд Диффи и Мартин Хеллман
43 
Большой омикрон, большая омега и большая тета (1976)....549
Дональд Э. Кнут
44 
Социальные процессы и доказательства теорем 
и правильности программ (1976).....................................................556
Ричард ДеМилло, Ричард Липтон и Алан Перлис
45 
Метод получения цифровых подписей  
и криптосистемы с открытым ключом (1978)............................576
Рональд Ривест, Ади Шамир и Лен Адлеман
46 
Как разделить секрет (1979)................................................................591
Ади Шамир
Литература.............................................................................................................595
Предметный указатель.....................................................................................610