第1页 / 共624页
第2页 / 共624页
第3页 / 共624页
第4页 / 共624页
第5页 / 共624页
第6页 / 共624页
第7页 / 共624页
第8页 / 共624页
Computer Science: an Overview.pdf
Cover
Title Page
Copyright Page
Preface
Acknowledgments
Contents
Chapter 0 Introduction
0.1 The Role of Algorithms
0.2 The History of Computing
0.3 The Science of Algorithms
0.4 Abstraction
0.5 An Outline of Our Study
0.6 Social Repercussions
Chapter 1 Data Storage
1.1 Bits and Their Storage
Boolean Operations
Gates and Flip-Flops
Hexadecimal Notation
1.2 Main Memory
Memory Organization
Measuring Memory Capacity
1.3 Mass Storage
Magnetic Systems
Optical Systems
Flash Drives
File Storage and Retrieval
1.4 Representing Information as Bit Patterns
Representing Text
Representing Numeric Values
Representing Images
Representing Sound
1.5 The Binary System
Binary Notation
Binary Addition
Fractions in Binary
1.6 Storing Integers
Two’s Complement Notation
Excess Notation
1.7 Storing Fractions
Floating-Point Notation
Truncation Errors
1.8 Data Compression
Generic Data Compression Techniques
Compressing Images
Compressing Audio and Video
1.9 Communication Errors
Parity Bits
Error-Correcting Codes
Chapter 2 Data Manipulation
2.1 Computer Architecture
CPU Basics
The Stored-Program Concept
2.2 Machine Language
The Instruction Repertoire
An Illustrative Machine Language
2.3 Program Execution
An Example of Program Execution
Programs Versus Data
2.4 Arithmetic/Logic Instructions
Logic Operations
Rotation and Shift Operations
Arithmetic Operations
2.5 Communicating with Other Devices
The Role of Controllers
Direct Memory Access
Handshaking
Popular Communication Media
Communication Rates
2.6 Other Architectures
Pipelining
Multiprocessor Machines
Chapter 3 Operating Systems
3.1 The History of Operating Systems
3.2 Operating System Architecture
A Software Survey
Components of an Operating System
Getting It Started
3.3 Coordinating the Machine’s Activities
The Concept of a Process
Process Administration
3.4 Handling Competition Among Processes
Semaphores
Deadlock
3.5 Security
Attacks from the Outside
Attacks from Within
Chapter 4 Networking and the Internet
4.1 Network Fundamentals
Network Classifications
Protocols
Combining Networks
Methods of Process Communication
Distributed Systems
4.2 The Internet
Internet Architecture
Internet Addressing
Internet Applications
4.3 The World Wide Web
Web Implementation
HTML
XML
Client-Side and Server-Side Activities
4.4 Internet Protocols
The Layered Approach to Internet Software
The TCP/IP Protocol Suite
4.5 Security
Forms of Attack
Protection and Cures
Encryption
Legal Approaches to Network Security
Chapter 5 Algorithms
5.1 The Concept of an Algorithm
An Informal Review
The Formal Definition of an Algorithm
The Abstract Nature of Algorithms
5.2 Algorithm Representation
Primitives
Pseudocode
5.3 Algorithm Discovery
The Art of Problem Solving
Getting a Foot in the Door
5.4 Iterative Structures
The Sequential Search Algorithm
Loop Control
The Insertion Sort Algorithm
5.5 Recursive Structures
The Binary Search Algorithm
Recursive Control
5.6 Efficiency and Correctness
Algorithm Efficiency
Software Verification
Chapter 6 Programming Languages
6.1 Historical Perspective
Early Generations
Machine Independence and Beyond
Programming Paradigms
6.2 Traditional Programming Concepts
Variables and Data Types
Data Structure
Constants and Literals
Assignment Statements
Control Statements
Comments
6.3 Procedural Units
Procedures
Parameters
Functions
6.4 Language Implementation
The Translation Process
Software Development Packages
6.5 Object-Oriented Programming
Classes and Objects
Constructors
Additional Features
6.6 Programming Concurrent Activities
6.7 Declarative Programming
Logical Deduction
Prolog
Chapter 7 Software Engineering
7.1 The Software Engineering Discipline
7.2 The Software Life Cycle
The Cycle as a Whole
The Traditional Development Phase
7.3 Software Engineering Methodologies
7.4 Modularity
Modular Implementation
Coupling
Cohesion
Information Hiding
Components
7.5 Tools of the Trade
Some Old Friends
Unified Modeling Language
Design Patterns
7.6 Quality Assurance
The Scope of Quality Assurance
Software Testing
7.7 Documentation
7.8 The Human-Machine Interface
7.9 Software Ownership and Liability
Chapter 8 Data Abstractions
8.1 Basic Data Structures
Arrays
Lists, Stacks, and Queues
Trees
8.2 Related Concepts
Abstraction Again
Static Versus Dynamic Structures
Pointers
8.3 Implementing Data Structures
Storing Arrays
Storing Lists
Storing Stacks and Queues
Storing Binary Trees
Manipulating Data Structures
8.4 A Short Case Study
8.5 Customized Data Types
User-Defined Data Types
Abstract Data Types
8.6 Classes and Objects
8.7 Pointers in Machine Language
Chapter 9 Database Systems
9.1 Database Fundamentals
The Significance of Database Systems
The Role of Schemas
Database Management Systems
Database Models
9.2 The Relational Model
Issues of Relational Design
Relational Operations
SQL
9.3 Object-Oriented Databases
9.4 Maintaining Database Integrity
The Commit/Rollback Protocol
Locking
9.5 Traditional File Structures
Sequential Files
Indexed Files
Hash Files
9.6 Data Mining
9.7 Social Impact of Database Technology
Chapter 10 Computer Graphics
10.1 The Scope of Computer Graphics
10.2 Overview of 3D Graphics
10.3 Modeling
Modeling Individual Objects
Modeling Entire Scenes
10.4 Rendering
Light-Surface Interaction
Clipping, Scan Conversion, and Hidden-Surface Removal
Shading
Rendering-Pipeline Hardware
10.5 Dealing with Global Lighting
Ray Tracing
Radiosity
10.6 Animation
Animation Basics
Kinematics and Dynamics
The Animation Process
Chapter 11 Artificial Intelligence
11.1 Intelligence and Machines
Intelligent Agents
Research Methodologies
The Turing Test
11.2 Perception
Understanding Images
Language Processing
11.3 Reasoning
Production Systems
Search Trees
Heuristics
11.4 Additional Areas of Research
Representing and Manipulating Knowledge
Learning
Genetic Algorithms
11.5 Artificial Neural Networks
Basic Properties
Training Artificial Neural Networks
Associative Memory
11.6 Robotics
11.7 Considering the Consequences
Chapter 12 Theory of Computation
12.1 Functions and Their Computation
12.2 Turing Machines
Turing Machine Fundamentals
The Church-Turing Thesis
12.3 Universal Programming Languages
The Bare Bones Language
Programming in Bare Bones
The Universality of Bare Bones
12.4 A Noncomputable Function
The Halting Problem
The Unsolvability of the Halting Problem
12.5 Complexity of Problems
Measuring a Problem’s Complexity
Polynomial Versus Nonpolynomial Problems
NP Problems
12.6 Public-Key Cryptography
Modular Notation
RSA Public-Key Cryptography
Appendixes
A: ASCII
B: Circuits to Manipulate Two’s Complement Representations
C: A Simple Machine Language
D: High-Level Programming Languages
E: The Equivalence of Iterative and Recursive Structures
F: Answers to Questions & Exercises
Index
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
X
Y
Z
computer science
AN OVERVIEW
This page intentionally left blank
computer science
A N O V E R V I E W
11th Edition
J. Glenn Brookshear
with contributions from
David T. Smith
Indiana University of Pennsylvania
Dennis Brylow
Marquette University
Addison-Wesley
Boston Columbus Indianapolis New York San Francisco Upper Saddle River
Amsterdam Cape Town Dubai London Madrid Milan Munich Paris Montréal Toronto
Delhi Mexico City São Paulo Sydney Hong Kong Seoul Singapore Taipei Tokyo
Editorial Director: Marcia Horton
Editor-in-Chief: Michael Hirsch
Editorial Assistant: Stephanie Sellinger
Vice President of Marketing: Patrice Jones
Marketing Manager: Yezan Alayan
Marketing Coordinator: Kathryn Ferranti
Vice President, Production: Vince O’Brien
Managing Editor: Jeff Holcomb
Production Project Manager: Kayla
Smith-Tarbox
Senior Operations Supervisor: Lisa McDowell
Art Directors: Jayne Conte and Kristine
Carney
Cover Designer: Rachael Cronin
Cover Image: “Slot Canyon”
RF Media Editor: Dan Sandin and Wanda
© gettyimages® Inc.
Rockwell
Project Management: GEX Publishing Services
Composition and Illustration: GEX Publishing
Services
Printer/Binder: Edwards Brothers
Cover Printer: Lehigh-Phoenix
Color/Hagerstown
Credits
Figure 0.3: “An abacus ”. © Wayne Chandler. Figure 0.4: “The Mark I computer.” Courtesy of
IBM corporate archives. Unauthorized use is not permitted. Figure 10.1: “A photograph of a viral
world produced by using 3D graphics (from Toy Story by Walt Disney/Pixar Animation Studios) ©
Disney/Pixar. Figure 10.6: “A scene from Shrek 2 by Dreamworks SKG. © Dreamworks/
Picture Desk Inc./Kobal collection. Figure 11.19: “Results of using a neural network to classify
pixels in an image.” Inspired by www.actapress.com. Chapter 11, Robots Making History
feature: a. “A soccer robot kicks a ball during the RoboCup German Open 2010 on April 15, 2010
in Magdeburg, eastern Germany.” © Jens Schlueter/AFP/ Getty Images/ Newscom. b. “Tartan
Racing’s “Boss—winner of the Urban Challenge, a contest sponsored by DARPA to have vehicles
drive themselves an urban environment.” © DARPA. c. “One of NASA’s rovers—a robot geologist
exploring the surface of Mars.” Courtesy of NASA/JPL-Caltech.
Copyright © 2012, 2009, 2007, 2005, 2003 Pearson Education, Inc., publishing as Addison-
Wesley. All rights reserved. Manufactured in the United States of America. This publication is
protected by Copyright, and permission should be obtained from the publisher prior to any
prohibited reproduction, storage in a retrieval system, or transmission in any form or by any
means, electronic, mechanical, photocopying, recording, or likewise. To obtain permission(s)
to use material from this work, please submit a written request to Pearson Education, Inc.,
Permissions Department, 501 Boylston Street, Suite 900, Boston, Massachusetts 02116.
Many of the designations by manufacturers and sellers to distinguish their products are
claimed as trademarks. Where those designations appear in this book, and the publisher was
aware of a trademark claim, the designations have been printed in initial caps or all caps.
Library of Congress Catologing-in-Publication Data available upon request.
10 9 8 7 6 5 4 3 2 1—EB—14 13 12 11 10
ISBN 10: 0-13-256903-5
ISBN 13: 978-0-13-256903-3
preface
This book presents an introductory survey of computer science. It explores the
breadth of the subject while including enough depth to convey an honest appre-
ciation for the topics involved.
Audience
I wrote this text for students of computer science as well as students from
other disciplines. As for computer science students, most begin their studies
with the illusion that computer science is programming, Web browsing, and
Internet file sharing since that is essentially all they have seen. Yet computer
science is much more than this. In turn, beginning computer science stu-
dents need exposure to the breadth of the subject in which they are planning
to major. Providing this exposure is the theme of this book. It gives students
an overview of computer science—a foundation from which they can appreci-
ate the relevance and interrelationships of future courses in the field. This
survey approach is, in fact, the model used for introductory courses in the
natural sciences.
This broad background is also what students from other disciplines need if
they are to relate to the technical society in which they live. A computer science
course for this audience should provide a practical, realistic understanding of the
entire field rather than merely an introduction to using the Internet or training
in the use of some popular software packages. There is, of course, a proper place
for training, but this text is about educating.
Thus, while writing this text, maintaining accessibility for nontechnical stu-
dents was a major goal. The result is that previous editions have been used suc-
cessfully in courses for students over a wide range of disciplines and educational
levels, ranging from high school to graduate courses. This eleventh edition is
designed to continue that tradition.
New in the Eleventh Edition
The underlying theme during the development of this eleventh edition was to
update the text to include handheld mobile devices, in particular smartphones.
Thus, you will find that the text has been modified, and at times expanded, to
v
vi
Preface
present the relationship between the subject matter being discussed and smart-
phone technology. Specific topics include:
• Smartphone hardware
• The distinction between 3G and 4G networks
• Smartphone operating systems
• Smartphone software development
• The human/smartphone interface
These additions are most noticeable in Chapters 3 (Operating Systems) and
4 (Networking) but is also observable in Chapters 6 (Programming Languages),
and 7 (Software Engineering).
Other prominent changes to this edition include updates to the following
topics:
• Software ownership and liability: The material in Chapter 7 (Software
Engineering) pertaining to this topic has been rewritten and updated.
• Training artificial neural networks: This material, in Chapter 11 (Artificial
Intelligence), has been modernized.
Finally, you will find that the material throughout the text has been updated
to reflect the state of today’s technology. This is most prevalent in Chapter 0
(Introduction), Chapter 1 (Data Storage), and Chapter 2 (Data Manipulation).
Organization
This text follows a bottom-up arrangement of subjects that progresses from the
concrete to the abstract—an order that results in a sound pedagogical presentation
in which each topic leads to the next. It begins with the fundamentals of informa-
tion encoding, data storage, and computer architecture (Chapters 1 and 2); pro-
gresses to the study of operating systems (Chapter 3) and computer networks
(Chapter 4); investigates the topics of algorithms, programming languages, and
software development (Chapters 5 through 7); explores techniques for enhancing
the accessibility of information (Chapters 8 and 9); considers some major applica-
tions of computer technology via graphics (Chapter 10) and artificial intelligence
(Chapter 11); and closes with an introduction to the abstract theory of computa-
tion (Chapter 12).
Although the text follows this natural progression, the individual chapters
and sections are surprisingly independent and can usually be read as isolated
units or rearranged to form alternative sequences of study. Indeed, the book is
often used as a text for courses that cover the material in a variety of orders. One
of these alternatives begins with material from Chapters 5 and 6 (Algorithms and
Programming Languages) and returns to the earlier chapters as desired. In con-
trast, I know of one course that starts with the material on computability from
Chapter 12. In still other cases the text has been used in “senior capstone”
courses where it serves as merely a backbone from which to branch into projects
in different areas. Courses for less technically oriented audiences may want to
concentrate on Chapters 4 (Networking and the Internet), 9 (Database Systems),
10 (Computer Graphics), and 11 (Artificial Intelligence).
On the opening page of each chapter, I have used asterisks to mark some sec-
tions as optional. These are sections that cover topics of more specific interest or
To Instructors
vii
perhaps explore traditional topics in more depth. My intention is merely to pro-
vide suggestions for alternative paths though the text. There are, of course, other
shortcuts. In particular, if you are looking for a quick read, I suggest the follow-
ing sequence:
Section
1.1–1.4
2.1–2.3
3.1–3.3
4.1–4.3
5.1–5.4
6.1–6.4
7.1–7.2
8.1–8.3
9.1–9.2
10.1–10.2
11.1–11.3
12.1–12.2
Topic
Basics of data encoding and storage
Machine architecture and machine language
Operating systems
Networking and the Internet
Algorithms and algorithm design
Programming languages
Software engineering
Data abstractions
Database systems
Computer graphics
Artificial intelligence
Theory of computation
There are several themes woven throughout the text. One is that computer
science is dynamic. The text repeatedly presents topics in a historical perspec-
tive, discusses the current state of affairs, and indicates directions of research.
Another theme is the role of abstraction and the way in which abstract tools are
used to control complexity. This theme is introduced in Chapter 0 and then
echoed in the context of operating system architecture, networking, algorithm
development, programming language design, software engineering, data organi-
zation, and computer graphics.
To Instructors
There is more material in this text than can normally be covered in a single
semester so do not hesitate to skip topics that do not fit your course objectives or
to rearrange the order as you see fit. You will find that, although the text follows
a plot, the topics are covered in a largely independent manner that allows you to
pick and choose as you desire. The book is designed to be used as a course
resource—not as a course definition. I suggest encouraging students to read the
material not explicitly included in your course. I think we underrate students if
we assume that we have to explain everything in class. We should be helping
them learn to learn on their own.
I feel obliged to say a few words about the bottom-up, concrete-to-abstract
organization of the text. I think as academics we too often assume that students
will appreciate our perspective of a subject—often one that we have developed
over many years of working in a field. As teachers I think we do better by pre-
senting material from the student’s perspective. This is why the text starts with
data representation/storage, machine architecture, operating systems, and net-
working. These are topics to which students readily relate—they have most
likely heard terms such as JPEG and MP3; they have probably recorded data on
CDs and DVDs; they have purchased computer components; they have inter-
acted with an operating system; and they have used the Internet. By starting the
course with these topics, students discover answers to many of the “why” ques-
tions they have been carrying for years and learn to view the course as practical
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
