计算机科学概论 英文版 第5版PDF电子书下载

1 Laying the Groundwork 2

Chapter 1 The Big Picture 3

1.1 Computing Systems 4

Layers of a Computing System 4

Abstraction 6

1.2 The History of Computing 8

A Brief History of Computing Hardware 8

A Brief History of Computing Software 17

Predictions 23

1.3 Computing as a Tool and a Discipline 24

Summary 27

Ethical Issues:The Tenth Strand 27

Key Terms 28

Exercises 28

Thought Questions 31

2 The Information Layer 32

Chapter 2 Binary Values and Number Systems 33

2.1 Numbers and Computing 34

2.2 Positional Notation 34

Binary,Octal,and Hexadecimal 36

Arithmetic in Other Bases 39

Power-of-2 Number Systems 40

Converting from Base 10 to Other Bases 42

Binary Values and Computers 43

Summary 45

Ethical Issues:Knowledge Units for the Tenth Strand 46

Key Terms 46

Exercises 47

Thought Questions 51

Chapter 3 Data Representation 53

3.1 Data and Computers 54

Analog and Digital Data 55

Binary Representations 57

3.2 Representing Numeric Data 59

Representing Negative Values 59

Representing Real Numbers 63

3.3 Representing Text 66

The ASCII Character Set 67

The Unicode Character Set 67

Text Compression 69

3.4 Representing Audio Data 73

Audio Formats 75

The MP3 Audio Format 76

3.5 Representing Images and Graphics 76

Representing Color 76

Digitized Images and Graphics 78

Vector Representation of Graphics 79

3.6 Representing Video 80

Video Codecs 80

Summary 82

Ethical Issues:Codes of Ethics 82

Key Terms 84

Exercises 84

Thought Questions 89

3 The Hardware Layer 90

Chapter 4 Gates and Circuits 91

4.1 Computers and Electricity 92

4.2 Gates 94

NOT Gate 94

AND Gate 95

OR Gate 96

XOR Gate 96

NAND and NOR Gates 97

Review of Gate Processing 98

Gates with More Inputs 98

4.3 Constructing Gates 99

Transistors 99

4.4 Circuits 101

Combinational Circuits 102

Adders 105

Multiplexers 107

4.5 Circuits as Memory 108

4.6 Integrated Circuits 109

4.7 CPU Chips 110

Summary 110

Ethical Issues:Has a Professional Code of Ethics Been Violated? 111

Key Terms 111

Exercises 112

Thought Questions 117

Chapter 5 Computing Components 119

5.1 Individual Computer Components 120

5.2 Stored-Program Concept 125

von Neumann Architecture 125

The Fetch-Execute Cycle 130

RAM and ROM 132

Secondary Storage Devices 133

Touch Screens 137

5.3 Embedded Systems 139

5.4 Parallel Architectures 140

Parallel Computing 140

Classes of Parallel Hardware 142

Summary 143

Ethical Issues:The Digital Divide 144

Key Terms 144

Exercises 145

Thought Questions 148

4 The Programming Layer 150

Chapter 6 Low-Level Programming Languages and Pseudocode 151

6.1 Computer Operations 152

6.2 Machine Language 152

Pep/8:A Virtual Computer 153

6.3 A Program Example 160

Hand Simulation 161

Pep/8 Simulator 163

6.4 Assembly Language 165

Pep/8 Assembly Language 166

Assembler Directives 167

Assembly-Language Version of Program Hello 167

A New Program 168

A Program with Branching 170

A Program with a Loop 173

6.5 Expressing Algorithms 175

Pseudocode Functionality 175

Following a Pseudocode Algorithm 179

Writing a Pseudocode Algorithm 181

Translating a Pseudocode Algorithm 184

6.6 Testing 186

Summary 187

Ethical Issues:Copyrighting and Software Piracy 188

Key Terms 188

Exercises 189

Thought Questions 193

Chapter 7 Problem Solving and Algorithms 195

7.1 How to Solve Problems 196

Ask Questions 196

Look for Familiar Things 197

Divide and Conquer 198

Algorithms 198

Computer Problem-Solving Process 200

Summary of Methodology 202

Testing the Algorithm 202

7.2 Algorithms with Simple Variables 203

An Algorithm with Selection 203

Algorithms with Repetition 204

7.3 Composite Variables 210

Arrays 210

Records 211

7.4 Searching Algorithms 212

Sequential Search 212

Sequential Search in a Sorted Array 213

Binary Search 215

7.5 Sorting 218

Selection Sort 218

Bubble Sort 221

Insertion Sort 222

7.6 Recursive Algorithms 223

Subprogram Statements 224

Recursive Factorial 225

Recursive Binary Search 226

Quicksort 227

7.7 Important Threads 232

Information Hiding 232

Abstraction 233

Naming Things 234

Testing 235

Summary 235

Ethical Issues:Open-Source Software 236

Key Terms 237

Exercises 237

Thought Questions 243

Chapter 8 Abstract Data Types and Subprograms 245

8.1 What Is an Abstract Data Type? 246

8.2 Stacks 246

8.3 Queues 247

8.4 Lists 248

8.5 Trees 251

Binary Trees 251

Binary Search Trees 254

Other Operations 259

8.6 Graphs 260

Creating a Graph 262

Graph Algorithms 263

8.7 Subprograms 268

Parameter Passing 269

Value and Reference Parameters 271

Summary 274

Ethical Issues:Workplace Monitoring 275

Key Terms 276

Exercises 276

Thought Questions 283

Chapter 9 Object-Oriented Design and High-Level Programming Languages 285

9.1 Object-Oriented Methodology 286

Object Orientation 286

Design Methodology 287

Example 290

9.2 Translation Process 295

Compilers 295

Interpreters 295

9.3 Programming Language Paradigms 298

Imperative Paradigm 298

Declarative Paradigm 299

9.4 Functionality in High-Level Languages 301

Boolean Expressions 301

Data Typing 303

Input/Output Structures 308

Control Structures 310

9.5 Functionality of Object-Oriented Languages 317

Encapsulation 317

Classes 318

Inheritance 320

Polymorphism 321

9.6 Comparison of Procedural and Object-Oriented Designs 322

Summary 324

Ethical Issues:Hoaxes and Scams 325

Key Terms 326

Exercises 326

Thought Questions 331

5 The Operating Systems Layer 332

Chapter 10 Operating Systems 333

10.1 Roles of an Operating System 334

Memory,Process,and CPU Management 336

Batch Processing 337

Timesharing 338

Other OS Factors 339

10.2 Memory Management 340

Single Contiguous Memory Management 341

Partition Memory Management 343

Paged Memory Management 345

10.3 Process Management 347

The Process States 347

The Process Control Block 349

10.4 CPU Scheduling 349

First Come,First Served 350

Shortest Job Next 351

Round Robin 351

Summary 353

Ethical Issues:Medical Privacy:HIPAA 354

Key Terms 355

Exercises 355

Thought Questions 361

Chapter 11 File Systems and Directories 363

11.1 File Systems 364

Text and Binary Files 364

File Types 365

File Operations 367

File Access 368

File Protection 369

11.2 Directories 370

Directory Trees 371

Path Names 372

11.3 Disk Scheduling 375

First-Come,First-Served Disk Scheduling 377

Shortest-Seek-Time-First Disk Scheduling 377

SCAN Disk Scheduling 378

Summary 379

Ethical Issues:Privacy:Opt-In or Opt-Out? 379

Key Terms 380

Exercises 380

Thought Questions 385

6 The Applications Layer 386

Chapter 12 Information Systems 387

12.1 Managing Information 388

12.2 Spreadsheets 389

Spreadsheet Formulas 391

Circular References 394

Spreadsheet Analysis 397

12.3 Database Management Systems 398

The Relational Model 398

Relationships 401

Structured Query Language 402

Database Design 404

12.4 E-Commerce 405

Summary 406

Ethical Issues:Politics and the Internet:The Candidate's View 408

Key Terms 408

Exercises 409

Thought Questions 413

Chapter 13 Artificial Intelligence 415

13.1 Thinking Machines 416

The Turing Test 417

Aspects of AI 419

13.2 Knowledge Representation 419

Semantic Networks 420

Search Trees 422

13.3 Expert Systems 424

13.4 Neural Networks 427

Biological Neural Networks 427

Artificial Neural Networks 429

13.5 Natural Language Processing 430

Voice Synthesis 431

Voice Recognition 432

Natural Language Comprehension 433

13.6 Robotics 435

The Sense-Plan-Act Paradigm 435

Subsumption Architecture 438

Physical Components 439

Summary 439

Ethical Issues:Politics and the Internet:The Public's View 440

Key Terms 441

Exercises 441

Thought Questions 445

Chapter 14 Simulation,Graphics,Gaming,and Other Applications 447

14.1 What Is Simulation? 448

Complex Systems 448

Models 449

Constructing Models 449

14.2 Specific Models 451

Queuing Systems 451

Meteorological Models 454

Computational Biology 460

Other Models 460

Computing Power Necessary 461

14.3 Computer Graphics 461

How Light Works 464

Object Shape Matters 465

Simulating Light 466

Modeling Complex Objects 468

Getting Things to Move 474

14.4 Gaming 475

History of Gaming 476

Creating the Virtual World 477

Game Design and Development 478

Game Programming 479

Summary 480

Ethical Issues:Gaming as an Addiction 481

Key Terms 482

Exercises 482

Thought Questions 485

7 The Communications Layer 486

Chapter 15 Networks 487

15.1 Networking 488

Types of Networks 489

Internet Connections 491

Packet Switching 494

15.2 Open Systems and Protocols 495

Open Systems 495

Network Protocols 496

TCP/IP 496

High-Level Protocols 497

MIME Types 498

Firewalls 498

15.3 Network Addresses 500

Domain Name System 501

15.4 Cloud Computing 503

Summary 504

Ethical Issues:Effects of Social Networking 506

Key Terms 507

Exercises 507

Thought Questions 511

Chapter 16 The World Wide Web 513

16.1 Spinning the Web 514

Search Engines 515

Instant Messaging 516

Weblogs 516

Cookies 517

16.2 HTML 518

Basic HTML Formatting 521

Images and Links 522

HTML5 524

16.3 Interactive Web Pages 525

Java Applets 525

Java Server Pages 526

16.4 XML 527

16.5 Social Networks 530

Summary 532

Ethical Issues:Gambling and the Internet 534

Key Terms 534

Exercises 535

Thought Questions 539

Chapter 17 Computer Security 541

17.1 Security at All Levels 542

Information Security 542

17.2 Preventing Unauthorized Access 544

Passwords 545

CAPTCHA 547

Fingerprint Analysis 548

17.3 Malicious Code 549

Antivirus Software 550

Security Attacks 551

17.4 Cryptography 552

17.5 Protecting Your Information Online 555

Security and Portable Devices 557

WikiLeaks 558

Summary 559

Ethical Issues:Blogging 561

Key Terms 562

Exercises 563

Thought Questions 565

8 In Conclusion 566

Chapter 18 Limitations of Computing 567

18.1 Hardware 568

Limits on Arithmetic 568

Limits on Components 574

Limits on Communications 575

18.2 Software 576

Complexity of Software 577

Current Approaches to Software Quality 578

Notorious Software Errors 582

18.3 Problems 585

Comparing Algorithms 585

Turing Machines 592

Halting Problem 595

Classification of Algorithms 597

Summary 599

Ethical Issues:Therac-25:Anatomy of a Disaster 600

Key Terms 600

Exercises 601

Thought Questions 605

Glossary 607

Endnotes 625

Index 633

Photo Credits 663