国外优秀信息科学与技术系列教学用书 计算机科学基础 从数据操纵到计算理论 影印版PDF电子书下载

PART Ⅰ COMPUTER AND DATA 1

Chapter 1 Introduction 2

1.1 The Computer as a Black Box 3

Data Processor 3

Programmable Data Processor 3

1.2 von Neumann Model 5

Four Subsystems 5

Stored Program Concept 6

Sequential Execution of Instructions 6

1.3 Computer Hardware 6

1.4 Data 6

Storing Data 6

Organizing Data 7

1.5 Computer Software 7

Programs Must Be Stored 7

A Sequence of Instructions 7

Algorithms 8

Languages 8

Software Engineering 8

Operating Systems 8

1.6 History 9

Mechanical Machines(Before 1930) 9

Birth of Electronic Computers(1930-1950) 9

1.7 Key Terms 11

1.8 Summary 11

1.9 Practice Set 11

Chapter 2 Data Representation 14

2.1 Data Types 15

2.2 Data inside the Computer 15

Bit 16

Bit Pattern 16

Byte 16

2.3 Representing Data 17

Text 17

Numbers 19

Images 19

Audio 20

Video 21

2.4 Hexadecimal Notation 21

Conversion 22

2.5 Octal Notation 23

Conversion 23

2.6 Key Terms 24

2.7 Summary 24

2.8 Practice Set 25

Chapter 3 Number Representation 27

3.1 Decimal and Binary 28

Decimal System 28

Binary System 28

3.2 Conversion 29

Binary to Decimal Conversion 29

Decimal to Binary Conversion 29

3.3 Integer Representation 30

Unsigned Integers Format 31

Sign-and-Magnitude Format 33

One's Complement Format 35

Two's Complement Format 37

Summary of Integer Representation 39

3.4 Excess System 40

3.5 Floating-Point Representation 40

Converting to Binary 40

Normalization 42

Sign,Exponent,and Mantissa 42

IEEE Standards 42

3.6 Hexadecimal Notation 44

3.7 Key Terms 44

3.8 Summary 45

3.9 Practice Set 45

Chapter 4 Operations on Bits 50

4.1 Arithmetic Operations 51

Arithmetic Operations on Integers 51

Arithmetic Operations on Floating-Point Numbers 54

4.2 Logical Operations 55

Truth Tables 56

Unary Operator 56

Binary Operators 57

Applications 60

4.3 Shift Operations 63

4.4 Key Terms 64

4.5 Summary 65

4.6 Practice Set 65

PART Ⅱ COMPUTER HARDWARE 69

Chapter 5 Computer Organization 70

5.1 Central Processing Unit(CPU) 71

Arithmetic Logic Unit(ALU) 71

Registers 71

Control Unit 72

5.2 Main Memory 72

Address Space 72

Memory Types 74

Memory Hierarchy 75

Cache Memory 75

5.3 Input/Output 76

Nonstorage Devices 76

Storage Devices 76

5.4 Subsystem Interconnection 83

Connecting CPU and Memory 83

Connecting I/O Devices 84

Addressing Input/Output Devices 86

5.5 Program Execution 87

Machine Cycle 87

A Machine Cycle Example 88

Input/Output Operation 89

5.6 Two Different Architectures 92

CISC 92

RISC 93

5.7 Key Terms 93

5.8 Summary 93

5.9 Practice Set 94

Chapter 6 Computer Networks 99

6.1 Networks,Large and Small 100

Model and Protocol 100

6.2 OSI Model 100

Seven Layers 100

Functions of the Layers 101

6.3 Categories of Networks 103

Local Area Network(LAN) 103

Metropolitan Area Network(MAN) 104

Wide Area Network(WAN) 104

6.4 Connecting Devices 105

Repeaters 106

Bridges 107

Routers 108

Gateways 108

6.5 The Internet and TCP/IP 109

Physical and Data-Link Layers 110

Network Layer 110

Transport Layer 111

Application Layer 111

6.6 Key Terms 116

6.7 Summary 116

6.8 Practice Set 117

PART Ⅲ COMPUTER SOFTWARE 121

Chapter 7 Operating Systems 122

7.1 Definition 123

7.2 Evolution 123

Batch Systems 123

Tune-Sharing Systems 123

Personal Systems 124

Parallel Systems 124

Distributed Systems 124

7.3 Components 124

Memory Manager 125

Process Manager 129

Device Manager 135

File Manager 135

User Interface 136

7.4 Popular Operating Systems 136

Windows 2000 136

UNIX 136

Linux 136

7.5 Key Terms 137

7.6 Summary 137

7.7 Practice Set 138

Chapter 8 Algorithms 141

8.1 Concept 142

Informal Definition 142

Example 142

Defining Actions 144

Refinement 144

Generalization 144

8.2 Three Constructs 145

Sequence 146

Decision 146

Repetition 146

8.3 Algorithm Representation 146

Flowchart 146

Pseudocode 146

8.4 More Formal Definition 150

Ordered Set 150

Unambiguous Steps 150

Produce a Result 150

Terminate in a Finite Time 150

8.5 Subalgorithms 150

Structure Chart 152

8.6 Basic Algorithms 152

Summation 152

Product 152

Smallest and Largest 153

Sorting 153

Searching 158

8.7 Recursion 160

Iterative Definition 160

Recursive Definition 161

8.8 Key Terms 162

8.9 Summary 162

8.10 Practice Set 163

Chapter 9 Programming Languages 166

9.1 Evolution 167

Machine Languages 167

Symbolic Languages 168

High-Level Languages 168

Natural Languages 169

9.2 Building a Program 169

Writing and Editing Programs 169

Compiling Programs 170

Linking Programs 170

9.3 Program Execution 171

9.4 Categories of Languages 171

Procedural(Imperative)Languages 172

Object-Oriented Languages 173

Functional Languages 175

Declarative(Logic)Languages 176

Special Languages 177

9.5 A Procedural Language:C 179

Identifiers 179

Data Types 179

Variables 180

Constants 181

Input and Output 182

Expressions 182

Statements 183

Functions 184

Selection 186

Repetition 187

Derived Data Types 189

Recursion 189

9.6 Key Terms 189

9.7 Summary 190

9.8 Practice Set 191

Chapter 10 Software Engineering 195

10.1 Software Life Cycle 196

Analysis Phase 197

Design Phase 197

Implementation Phase 197

Testing Phase 198

10.2 Development Process Models 198

Waterfall Model 198

Incremental Model 199

10.3 Modularity 200

Tools 200

Coupling 200

Cohesion 201

10.4 Quality 202

Quality Defined 202

Quality Factors 203

The Quality Circle 205

10.5 Documentation 206

User Documentation 206

System Documentation 206

Documentation as an Ongoing Process 207

10.6 Key Terms 207

10.7 Summary 208

10.8 Practice Set 208

PART Ⅳ DATA ORGANIZATION 213

Chapter 11 Data Structures 214

11.1 Arrays 215

Array Applications 217

Two-Dimensional Arrays 218

11.2 Records 219

Accessing Records 220

11.3 Linked Lists 220

Nodes 221

Pointers to Linked Lists 221

Operations on Linked Lists 221

11.4 Key Terms 223

11.5 Summary 224

11.6 Practice Set 224

Chapter 12 Abstract Data Types 227

12.1 Background 228

Definition 228

Model for an Abstract Data Type 229

Operations on ADTs 229

12.2 Linear Lists 229

Operations on Linear Lists 230

Implementation of a General Linear List 232

Linear List Applications 232

12.3 Stacks 232

Operations on Stacks 233

Implementation of a Stack 234

Stack Applications 234

12.4 Queues 235

Operations on Queues 235

Implementation of a Queue 237

Queue Applications 237

12.5 Trees 237

Basic Tree Concepts 237

Operations on Trees 239

12.6 Binary Trees 239

Operations on Binary Trees 241

Implementation of a Binary Tree 243

Binary Tree Applications 243

12.7 Graphs 244

Terminology 244

Operations on Graphs 245

Implementation of a Graph 247

Graph Applications 248

12.8 Key Terms 249

12.9 Summary 249

12.10 Practice Set 251

Chapter 13 File Structures 256

13.1 Access Methods 257

Sequential Access 257

Random Access 257

13.2 Sequential Files 257

Updating Sequential Files 258

13.3 Indexed Files 259

Inverted Files 260

13.4 Hashed Files 261

Hashing Methods 261

Collision 263

13.5 Text versus Binary 265

Text Files 265

Binary Files 266

13.6 Key Terms 266

13.7 Summary 266

13.8 Practice Set 267

Chapter 14 Databases 270

14.1 Database Management System 271

14.2 Architecture 272

Internal Level 272

Conceptual Level 272

External Level 272

14.3 Database Models 273

Hierarchical Model 273

Network Model 273

Relational Model 274

14.4 Relational Model 274

Relation 274

14.5 Operations on Relations 275

Insert 275

Delete 275

Update 276

Select 276

Project 277

Join 277

Union 277

Intersection 278

Difference 278

14.6 Structured Query Language 279

Statements 279

14.7 Other Database Models 282

Distributed Databases 282

Object-Oriented Databases 282

14.8 Key Terms 283

14.9 Summary 283

14.10 Practice Set 284

PART Ⅴ ADVANCED TOPICS 289

Chapter 15 Data Compression 290

15.1 Lossless Compression 291

Run-Length Encoding 291

Huffman Coding 292

Lempel Ziv Encoding 294

15.2 Lossy Compression Methods 298

Image Compression:JPEG 298

Video Compression:MPEG 301

15.3 Key Terms 303

15.4 Summary 303

15.5 Practice Set 303

Chapter 16 Security 306

Privacy 307

Authentication 307

Integrity 307

Nonrepudiation 307

16.1 Privacy 307

Encryption/Decryption 307

Privacy Using the Combination 311

16.2 Digital Signature 311

Signing the Whole Document 312

Signing the Digest 312

16.3 Key Terms 314

16.4 Summary 314

16.5 Practice Set 315

Chapter 17 Theory of Computation 317

17.1 Simple Language 318

Increment Statement 318

Decrement Statement 318

Loop Statement 318

Power of the Simple Language 318

Conclusion 321

17.2 Turing Machine 321

Turing Machine Components 321

Simulation of Simple Language 323

Conclusion 325

17.3 G？del Numbers 326

Representing a Program 326

Interpreting a Number 327

17.4 Halting Problem 327

Halting Problem is not Solvable 328

17.5 Solvable and Unsolvable Problems 329

Unsolvable Problems 329

Solvable Problems 330

17.6 Key Terms 331

17.7 Summary 331

17.8 Practice Set 332

Appendix A ASCII Code 335

Appendix B Unicode 339

Alphabets 340

Symbols and Punctuation Marks 341

CJK Auxiliaries 341

CJK Unified Ideographs 341

Surrogates 342

Private Use 342

Miscellaneous Characters and Symbols 342

Appendix C Flowcharts 343

C.1 Auxiliary Symbols 344

Start and Stop 344

Flow Lines 345

Connectors 345

C.2 Main Symbols 345

Sequence Statements 345

Selection Statements 347

Looping Statements 348

Appendix D Pseudocode 350

D.1 Components 351

Algorithm Header 351

Purpose,Conditions,and Return 351

Statement Numbers 351

Statement Constructs 351

Sequence 352

Selection 352

Loop 352

Appendix E Structure Charts 353

E.1 Structure Chart Symbols 354

Function Symbol 354

Selection in Structure Charts 355

Loops in Structure Charts 355

Data Flows 356

E.2 Reading Structure Charts 356

E.3 Rules of Structure Charts 357

Appendix F Discrete Cosine Transform 358

F.1 Discrete Cosine Transform 359

F.2 Inverse Transform 359

Appendix G Acronyms 360

Glossary 361

Index 377