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