Министерство образования и науки Российской Федерации Коми государственный педагогический институт

_{В.П. Одинец}

Зарисовки по истории компьютерных наук

Учебное пособие (в трех частях)

Часть I

Сыктывкар 2011

УДК 004:93

ББК 32.975 О42

Печатается по решению редакционно-издательского совета Коми государственного педагогического института

от 21.12. 2010 г.

Рецензенты:

Флегонтое А.В. - профессор, д-р физ.-мат. наук, зав. кафедрой

информационных систем и программного обеспечения РГПУ

им. А.И. Герцена (Санкт-Петербург), действительный член Академии Информатизации Образования

Фокин P.P. - профессор, д-р пед. наук, зав. кафедрой

информатики СПбГУСЭ (Санкт-Петербург),

действительный член Академии Информатизации Образования

Одинец, В.П.

042 Зарисовки по истории компьютерных наук : учебное пособие : в

3 ч. / В.П.Одинец. - Сыктывкар: Коми пединститут, 2011. - Ч. I. 200 с.

ISBN 978-5-87661-188-8

ISBN 978-5-87661-189-5 (Ч. 1)

Материал книги основан на лекциях, прочитанных автором в разные годы частью в Зеленогурском университете (Польша), частью в Сыктыв­карском государственном университете.

В трёх главах дан обзор истории вычислительной техники и архитек­туры компьютеров, истории развития теории алгоритмов, а также исто­рии систем искусственного интеллекта с древних времён до середины XX века.

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

УДК 004:93 ББК 32.975

ISBN 978-5-87661-188-8 © Одинец В.П., 2011

ISBN 978-5-87661-189-5 (Ч. 1) © Коми государственный педаго-

гический институт, 2011

Оглавление

Предисловие……………………………………………………………...4

Глава 1. История вычислительной техники и архитектуры компьютеров

§1.Доэлектронная эра истории компьютеров (до XVIII в.)…………...8 §2.Доэлектронная эра истории компьютеров (XVIII – XIX вв.)…….13 §3. Аналоговые компьютеры…………………………………………...23 §4. Почти первое поколение компьютеров…………………………....30 §5. История создания компьютеров в России (до 1948 г.)…………...44 §6.История создания компьютеров в России (1948 – 1954 гг.)……..54 Заключительные замечания по периодизации развития компьютерной техники……………………………………………..…..65

Глава II. История развития теории алгоритмов

Введение………………………………………………………………....68 §7.Вычислительная модель Поста……………………………………..70 §8.Вычислительная модель Тьюринга. Машина фон Неймана….…..80 §9. Вычислительные модели Маркова и Клини………………………89 §10.Проблемы разрешимости и перечислимости…………………...100 §11.X-я проблема Гильберта………………………………………..…111 §12. Элементы теории сложности. NP – проблема……………….…121

Глава III. История систем искусственного интеллекта

Введение………………………………………………………………..127 §13. Представление знаний в интеллектуальных системах…….…..129 §14. Экспертные системы…………………………………………..…145 Заключение (к главе III) ………………………………………………161

Библиографический список…………………………………………163 Именной указатель…………………………………………………...172 Предметный указатель……………………………………………....193

3

Предисловие

Прежде чем вести речь об истории компьютерных наук, следует определить, что входит в их перечень. По американской классификации «Computer Science» состоит из следующих разде­лов:

1. Вычислительная техника и архитектура компьютера.

2. Алгоритмы.

3. Искусственный интеллект.

4. Языки программирования.

5. Базы данных и информационно-поисковых систем.

6. Операционные системы и структуры данных.

7. Системы взаимодействия человека и компьютера.

8. Компьютерные сети (включая Internet).

9. Компьютерная графика.

Иногда в число компьютерных наук включают и программ­ное обеспечение.

Напомним, что целью обучения компьютерным наукам яв­ляется выявление и понимание отношения между компьютерны­ми системами и прикладными приложениями.

Эта книга возникла на основе докладов и лекций, прочитан­ных в Зеленогурском университете (Польша) в разные годы (2003–2010), и курса лекций, прочитанного в Сыктывкарском го­сударственном университете в 2010/11 учебном году, а также ма­териалов к учебному пособию по теории алгоритмов, изданному (совместно с М.В. Поспеловым) в 2006 г.

Снятие грифа секретности со многих материалов по созда­нию компьютеров в 30–50-е годы XX века (в Германии, США,

4

Великобритании и СССР) существенно обогатило наше видение истории компьютерных наук.

Не углубляясь в чисто технические детали (хотя и признавая их важность), основное внимание в книге сосредоточено на исто­рии появления идей и методов. При этом даются необходимые пояснения по разным разделам математики и информатики (пре­жде всего по теории чисел и математической логике).

Наша книга не претендует на полноту охвата заявленных трёх тем: в первой главе, названной «История вычислительной техники и архитектура компьютеров», нет речи об истории орга­низации компьютерных систем (процессорах, основной памяти, вспомогательной памяти, системах ввода-вывода), нет речи и об истории цифрового логического уровня (вентилях и булевой ал­гебре, основных цифровых логических схемах, примерах цен­тральных процессоров и шин), об истории уровней микроархи­тектуры, уровней архитектуры набора команд, их типах, истории уровней операционной системы, параллельных компьютерных архитектурах. Это правда, но не вся правда, так как рассказывая, например, о К. Шенноне или В.И. Шестакове, Дж. фон Неймане или И.С. Бруке, А. Тьюринге или С.А. Лебедеве, мы касаемся многого из перечисленного выше.

Во второй главе, посвящённой истории теории алгоритмов, нет речи ни о случайных алгоритмах, ни об алгоритмах с ораку­лом, ни о главных нумерациях, ни конкретных алгоритмов, на­пример, сортировки, жадных алгоритмов, алгоритма Краскала, алгоритма Флойда-Уоршелла, алгоритма Дейкстры.

Впрочем, об истории этих алгоритмов можно прочитать и в учебниках по теории алгоритмов, в частности, в книгах Дональда

5

Кнута (Donald Ervin Knuth: 1938) [134–137], или в учебниках по дискретной математике, например, в [139] И.В. Романовского.

Наконец, в главе по истории систем искусственного интел­лекта (ИИ) нами не затрагиваются модели и методы решения за­дач ИИ, планирование задач ИИ, особенности систем ИИ в робо­тотехнике, включая вопросы систем машинного зрения, голосо­вых систем, дактильных систем, проблем машинного перевода и др. Эти материалы, бесспорно, интересны и могут стать предме­том обсуждения на семинарах по истории ИИ.

Поскольку данное пособие охватывает только I часть исто­рии компьютерных наук (а предполагается издание ещё двух час­тей), то ко многим творцам этих наук будем неоднократно воз­вращаться.

Заметим также, что изучение компьютерных наук (в отличие от пользования компьютером) предполагает знание математиче­ской логики, теории графов, дискретной математики, теории чи­сел, математического анализа, элементов высшей геометрии и ал­гебры. Хотя настоящая книга не может служить заменой учебни­ков, тем не менее, считаем полезным давать в части параграфов задачи для самостоятельной работы по тематике данного пара­графа.

В конце книги даётся список основной литературы. (Допол­нительная литература представлена в подстрочных примечани­ях.) Разумеется, в век Интернета каждый читатель может попол­нить данный текст новыми материалами. Автор будет только рад этому.

В конце книги даны именной и предметный указатели. Для удобства читателей именной указатель снабжён датами жизни.

6

Обо всех замечаниях и предложениях можно сообщить ав­тору по e-mail: [e-mail].

В заключение автор хотел бы выразить свою признатель­ность рецензентам – профессорам А.В. Флегонтову и Р.Р. Фокину за ценные замечания, учтённые автором; М.Н. Истоминой за творческий набор первой версии книги. Автор хотел бы также поблагодарить доцента М.В. Поспелова, прочитавшего первую версию книги и способствовавшего её улучшению.