Введение в компьютерные науки, 6-е издание

Дж. Гленн Брукшир

 

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

Предисловие

Данная книга представляет собой введение в область компьютерных наук. В ней сочетается необходимая широта обзора предмета с достаточно глубоким проникновением в сущность излагаемого материала. Я писал эту книгу для двух категорий читателей.

Для будущих специалистов по компьютерным наукам и вычислительной технике

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

Для студентов других дисциплин

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

Структура книги

Материал книги упорядочен в соответствии с восходящим подходом, предусматривающим переход от конкретного к абстрактному. Именно такой способ изложения обеспечивает ясную и доступную подачу материала, когда одна тема плавно переходит в другую. Часть I включает обсуждение вопросов, связанных с аппаратным обеспечением. Она начинается с объяснений, как информация представляется и записывается в машинах и как выбранные способы представления влияют на свойства этих машин (глава 1). Затем описывае тся, как машины обрабатывают данные с помощью программ на машинных языках (глава 2).

В части II обсуждаются вопросы, связанные с программным обеспечением, как функционирование машины координируется операционной системой и как это координирование может быть распространено на всю компьютерную сеть, а также на межсетевые взаимодействия (глава 3). На этой стадии обучения студенты получают информацию, необходимую для понимания принципов построения и функционирования типичной компьютерной системы. По сути, главы 1√3 могут использоваться как основа для краткого курса лекций " Что должен знать каждый грамотный пользователь компьютера".

В последующих главах этой части рассматриваются вопросы разработки программного обеспечения, включая разработку и анализ алгоритмов (глава 4), применение языков программирования и используемые ими парадигмы (глава 5), а также проектирование программного обеспечения (глава 6).

В части III детально рассматриваются темы, затронутые в предыдущей части, и обсуждается взаимосвязь между алгоритмами и построением структур хранения данных. В частности, здесь дано введение в теорию структур данных (глава 7), приводятся элементарные сведения о методах файлового хранения информации (глава 8) и представлен общий обзор систем баз данных (глава 9).

Курс достигает своей кульминации в части IV, включающей рассмотрение наиболее впечатляющих достижений в области вычислительной техники. Эта часть начинается с главы об искусственном интеллекте, в которой обсуждаются технологии создания вычислительных машин, способных к восприятию и проведению рассуждений (глава 10). Заканчивается данная часть рассмотрением ограничений, присущих алгоритмическим системам, и тех пределов, которые эти ограничения устанавливают в отношении возможностей вычислите льных машин (глава 11).

Кроме того, существует ряд тем, которые красной нитью проходят через всю книгу. Первая - это то, что компьютерные науки являются весьма динамичной областью знания. Все рассматриваемые темы подаются в исторической перспективе, обсуждается достигнутый на данный момент уровень развития и указываются основные направления текущих исследований. Вторая тема состоит в пояснении значения абстрактных методов и способов применения различных абстрактных инструментов для управления уровнем сложности. Фактически даж е само построение книги отвечает раскрытию этой темы за счет представления материала в порядке прогрессирующей абстракции - аппаратное оборудование предоставляет абстрактные инструменты, используемые системным программным обеспечением, а системное программное обеспечение, в свою очередь, предоставляет абстрактные инструменты, используемые прикладным программным обеспечением.

Студенту

Впервые я познакомился с областью компьютерных наук во время службы в военно-морских силах США, в конце 60-х √ начале 70-х годов. (Я сознаю, что это признание старит меня в глазах читателя, однако и с вами это тоже когда-нибудь произойдет.) Большую часть всего срока службы я занимался тем, что содержал в исправности системное программное обеспечение компьютеров военно-морского флота, установленных в Лондоне. По окончании службы я вернулся к учебе и в 1975 году закончил аспирантуру . С тех пор я преподаю компьютерные науки и математику.

Многое изменилось за эти годы в компьютерных науках, однако многое осталось и неизменным. В частности, компьютерным наукам всегда была и по-прежнему присуща некоторая притягательная сила. В этой области знаний постоянно происходит множество увлекательных событий. Развитие и повсеместное распространение Internet, прогресс в области искусственного интеллекта, уникальные возможности сбора и распространения информации в неслыханных размерах - это только некоторые из аспектов, способных воздействовать на ва шу жизнь. Вы живете в замечательном, изменяющемся мире, и вам предоставляется реальная возможность стать участником происходящих событий. Воспользуйтесь же ею! Чем больше вы узнаете, тем лучше будете подготовлены. Эта книга позволит вам заложить основу, но это отнюдь не предел. Прочтите ее, а потом совершенствуйтесь дальше и дальше. Одно из наиболее достойных качеств, которое вы можете развить в себе, - это умение учиться самостоятельно.

Преподавателю

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

Я уже указывал, что книга построена по восходящему принципу, от конкретного к абстрактному, однако позвольте мне остановиться на этом подробнее. Как ученые мы слишком часто полагаем, что студенты непременно оценят наш подход к предмету, который вырабатывался нами на протяжении многих лет работы в этой области. Однако как преподаватели мы поступим лучше, если будем подавать материал, ориентируясь на точку зрения студента. Именно поэтому книга начинается с освещения темы представления и хранения данных, которая выбрана мною в качестве отправной точки для изложения последующего материала. Современные студенты уже знакомы с магнитными дисками, модемами, компакт-дисками, и я обнаружил, что они проявляют интерес к тому, как эти устройства работают. Я часто наблюдал, как они находят ответы на многие свои "почему?", после чего начинают воспринимать этот курс скорее как практический, нежели как теоретический. После такого начала книга естественно подходит к раскрытию вопросов о программном обеспечении, которое контролирует эти устройства. Далее рассматривается, как можно разработать собственное программное обеспечение. Затем обсуждение переходит к таким абстрактным вопросам, как разработка алгоритмов, способ представления функций, а также сложность, что и является основным содержанием большинства традиционных вводных компьютерных курсов.

Всем нам известно, что студенты познают гораздо больше того, чему мы их обучаем, и те знания, которые они получают окольным путем, зачастую воспринимаются лучше, чем те, которые подаются им непосредственно. Эта особенность становится особенно важной, когда приходит время "учить" решать задачи. Студенты не учатся решать проблемы как отдельную дисциплину путем изучения методологий по решению задач. Они учатся справляться с проблемами, решая их. Поэтому по всему тексту книги я включил многочисленные задан ия. Я настоятельно рекомендую вам использовать их и подробно пояснять методы их решения.

Еще одна тема, которую я отнес к этой же категории, - это профессионализм, этика и социальная ответственность. Я не считаю, что подобный материал может быть представлен как отдельный предмет. Напротив, он должен выходить на поверхность там, где это уместно, и именно такой подход выбран в данной книге. В частности, в разделы 0.5, 3.7, 6.1, 10.1 и 10.7 включены такие темы, как безопасность, конфиденциальность, ответственность, социальные аспекты, обсуждаемые в контексте работы в сети, использование баз данных, разработка программного обеспечения и применение искусственного интеллекта. Кроме того, каждая глава включает ряд вопросов (раздел "Общественные и социальные вопросы"), побуждающих студентов к размышлениям об отношении представленного в книге материала к жизни того общества, частью которого они являются.

Педагогические аспекты

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

Более того, каждая глава (за исключением вступительной) заканчивается двумя группами задач. Первая включает подборку задач под заголовком "Упражнения", разработанных для использования в качестве "домашнего задания", поскольку они относятся к содержанию всей главы и в тексте прямо не рассматриваются. Вторая группа содержит вопросы под заголовком "Общественные и социальные вопросы", которые предназначены для обдумывания и обсуждения. Многие из этих вопросов могут быть использованы в качестве небольших за даний на проведение исследований, результаты которых должны быть представлены в виде письменных или устных отчетов.

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

Web-узел

Данная книга дополняется материалом, собранным на специальном Web-узле, предназначенном для ее информационной поддержки. Его адрес http://www.awlonline.com/brookshear. На этом узле представлен материал как для студентов, так и преподавателей, включая вспомогательное программное обеспечение, руководства к лабораторным работам по разнообразным языкам программирования, ссылки на дополнительные темы по интересам, а также на материалы , разработанные другими читателями этой книги.

Замечания к шестому изданию

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

Тема сжатия данных была перенесена из главы 2 в новый раздел 1.8. Этот раздел также содержит сведения о программе LZ77 и методах представления изображений, включая обсуждение форматов GIF и JPEG. Материал по анализу алгоритмов, который раньше рассматривался в главе 11, был расширен и перемещен в главу 4 "Алгоритмы". Глава 4 стала более доступной для понимания после удаления обсуждения методов быстрой сортировки. В главу 5 "Языки программирования" был добавлен раздел 5 .5, посвященный объектно-ориентированному программированию. Часть этого материала входила раньше в главу 7. Большая часть главы 6 "Технология разработки программного обеспечения" была полностью переписана. Теперь она включает введение в шаблоны проектирования и новый раздел по тестированию. В главе 7 "Структуры данных" появился новый раздел 7.7, содержащий сведения об использовании косвенной адресации на уровне машинных языков. Глава 8 "Файловые структуры" была полностью пе реписана в целях лучшего восприятия материала (за счет удаления излишних примеров по конкретным языкам программирования). Раздел 9.4 по объектно-ориентированным базам данных был переписан, и появился новый раздел 9.6, посвященный социальным аспектам использования технологии баз данных. В главу 10 "Искусственный интеллект" включены два новых раздела - 10.5 "Генетические алгоритмы" и 10.7 "Осмысливание последствий". Кроме того, прежние разделы 10.3, 10.4 и 10.5 были у прощены и объединены. В главу 11 "Теория вычислений" был добавлен раздел 11.6 "Криптография с использованием открытых ключей".

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

СОДЕРЖАНИЕ

Глава нулевая. Введение 21
0.1. Знакомство с алгоритмами   22
0.2. Происхождение вычислительных машин 26
0.3. Эволюция компьютерных наук 30
0.4. Роль абстракции    32
0.5. Этические, социальные и правовые аспекты   33
Социальные и общественные вопросы   34
Рекомендуемая литература    36
АРХИТЕКТУРА МАШИН   37
Глава первая. Хранение данных   39
1.1. Хранение битов 40
1.2. Основная память    48
1.3. Массовая память    51
1.4. Представление информации в виде комбинации
двоичных  разрядов  59
1.5. Двоичная система счисления 68
1.6. Представление целых чисел  71
1.7. Представление дробных значений 79
1.8. Сжатие данных  85
1.9. Ошибки при передаче информации 91
Упражнения  97
Общественные и социальные вопросы   106
Рекомендуемая литература    107
Дополнительная литература   108
Глава вторая. Обработка данных  109
2.1. Центральный процессор  110
2.2. Концепция хранимой программы   115
2.3. Выполнение программы   119
2.4. Арифметические и логические команды    127
2.5. Взаимодействие с другими устройствами  132
2.6. Другие типы архитектуры компьютеров    137
Упражнения  142
Социальные и общественные вопросы   151
Рекомендуемая литература    153
Дополнительная литература   153
ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ 155
Глава третья. Операционные системы и сети   157
3.1. Эволюция операционных систем   158
3.2. Архитектура операционных систем    163
3.3. Координация действий машины    171
3.4. Организация конкуренции между процессами   176
3.5. Сети   182
3.6. Сетевые протоколы  190
3.7. Безопасность   200
Упражнения  204
Общественные и социальные вопросы   209
Рекомендуемая литература    211
Дополнительная литература   211
Глава четвертая. Алгоритмы  213
4.1. Понятие алгоритма  214
4.2. Представление алгоритма    217
4.3. Создание алгоритма 225
4.4. Итерационные структуры 232
4.5. Рекурсивные структуры  243
4.6. Эффективность и правильность   254
Упражнения  266
Общественные и социальные вопросы   274
Рекомендуемая литература    276
Глава пятая. Языки программирования 277
5.1. Исторический обзор 278
5.2. Концепции традиционного программирования   288
5.3. Процедуры и функции    300
5.4. Реализация языка   307
5.5. Объектно-ориентированное программирование  318
5.6. Программирование параллельных процессов    322
5.7. Декларативное программирование 325
Упражнения  331
Общественные и социальные вопросы   337
Рекомендуемая литература    339
Дополнительная литература   339
Глава шестая. Технология разработки
программного  обеспечения   341
6.1. Предмет технологии разработки программного
обеспечения 342
6.2. Жизненный цикл программного обеспечения    345
6.3. Модульность    351
6.4. Методы проектирования  358
6.5. Тестирование   366
6.6. Документирование   368
6.7. Право собственности и ответственность за
создаваемое программное обеспечение   370
Упражнения  373
Общественные и социальные вопросы   376
Рекомендуемая литература    377
Дополнительная литература   378
ОРГАНИЗАЦИЯ ДАННЫХ   379
Глава седьмая. Структуры данных 381
7.1. Массивы    382
7.2. Списки 385
7.3. Стеки  393
7.4. Очереди    398
7.5. Древовидные структуры  402
7.6. Специализированные типы данных 414
7.7. Указатели в машинном языке 421
Упражнения  422
Общественные и социальные вопросы   431
Рекомендуемая литература    432
Дополнительная литература   432
Глава восьмая. Файловые структуры   433
8.1. Роль операционной системы  434
8.2. Последовательные файлы 436
8.3. Текстовые файлы    442
8.4. Индексация 446
8.5. Хеширование    450
Упражнения  457
Общественные и социальные вопросы   461
Рекомендуемая литература    462
Глава девятая. Структуры баз данных 463
9.1. Общие понятия  464
9.2. Многоуровневый подход к реализации
баз данных  467
9.3. Реляционная модель 470
9.4. Объектно-ориентированные базы данных   485
9.5. Обеспечение целостности баз данных 488
9.6. Влияние технологий баз данных на общество  493
Упражнения  496
Общественные и социальные вопросы   502
Рекомендуемая литература    503
Дополнительная литература   504
ПОТЕНЦИАЛ АЛГОРИТМИЧЕСКИХ МАШИН 505
Глава десятая. Искусственный интеллект  507
10.1. Машины и интеллект    508
10.2. Распознавание изображений 512
10.3. Способность к рассуждению 515
10.4. Искусственные нейронные сети  528
10.5. Генетические алгоритмы    537
10.6. Приложения теории искусственного интеллекта   542
10.7. Осмысливание последствий  551
Упражнения  554
Общественные и социальные вопросы   560
Рекомендуемая литература    562
Дополнительная литература   562
Глава одиннадцатая. Теория вычислений   563
11.1. Простейший язык программирования  564
11.2. Машины Тьюринга   570
11.3. Вычислимые функции    575
11.4. Невычислимые функции  579
11.5. Сложность задач   586
11.6. Криптография с использованием открытых ключей 596
Упражнения  606
Общественные и социальные вопросы   610
Рекомендуемая литература    612
Дополнительная литература   612
ПРИЛОЖЕНИЯ  613
Приложение A. Код ASCII 615
Приложение Б. Электронные схемы обработки чисел
в двоичном дополнительном коде  617
Приложение В. Пример типичного машинного языка  621
Архитектура машины  621
Машинный язык   621
Приложение Г. Примеры программ  625
Язык Ada    625
Язык C  626
Язык C++    627
Язык FORTRAN    629
Язык JAVA   629
Язык PASCAL 630
Приложение Д. Эквивалентность итеративных
и рекурсивных структур  633
Приложение Е. Ответы на вопросы для самопроверки    635
Часть I 635
Часть II    644
Часть III   657
Часть IV    669
Предметный указатель     679