Computer Science Handbook, Second Edition

Computer Science Handbook: Second Edition......Page 1
Preface to the Second Edition......Page 3
Editor-in-Chief......Page 5
Contributors......Page 6
Contents......Page 10
1.1 Introduction......Page 18
1.2 Growth of the Discipline and the Profession......Page 19
1.2.1 Curriculum Development......Page 20
1.2.2 Growth of Academic Programs......Page 21
1.2.3 Academic R&D and Industry Growth......Page 22
1.3 Perspectives in Computer Science......Page 23
1.4 Broader Horizons: From HPCC to Cyberinfrastructure......Page 24
1.5 Organization and Content......Page 27
1.5.2 Architecture......Page 28
1.5.5 Human–Computer Interaction......Page 29
1.5.8 Net-Centric Computing......Page 30
1.5.11 Software Engineering......Page 31
References......Page 32
2.1 Introduction: Why a Chapter on Ethical Issues?......Page 34
2.2.1 Utilitarianism......Page 36
2.2.2 Deontological Theories......Page 37
2.2.3 Social Contract Theories......Page 38
2.2.4 A Paramedic Method for Computer Ethics......Page 39
2.3 Professional Ethics......Page 40
2.4 Ethical Issues That Arise from Computer Technology......Page 42
2.4.1 Privacy......Page 43
2.4.3 Risk, Reliability, and Accountability......Page 44
References......Page 45
Section I: Algorithms and Complexity......Page 46
3.2 Analyzing Algorithms......Page 48
3.2.1 Linear Recurrences......Page 49
3.2.2 Divide-and-Conquer Recurrences......Page 51
3.3.1 Sorting......Page 52
3.3.2 Priority Queues......Page 54
3.4 Divide-and-Conquer Algorithms......Page 57
3.5 Dynamic Programming......Page 59
3.6 Greedy Heuristics......Page 64
References......Page 68
4.1.1 Containers, Elements, and Positions or Locators......Page 69
4.1.3.4 Space vs. Time......Page 70
4.1.4.3 Dictionary......Page 71
4.2.2 Operations......Page 72
4.2.5 Implementation with a Doubly Linked List......Page 73
4.3.2 Operations......Page 74
4.3.3.3 Sorting......Page 75
4.3.4 Realization with a Heap......Page 76
4.3.4.1 Operation INSERT......Page 77
4.3.4.3 Operation REMOVE......Page 78
4.3.4.5 Sorting......Page 79
4.4.1 Operations......Page 80
4.4.2.2 Sorted Sequence......Page 81
4.4.2.3 Sorted Array......Page 82
4.4.3.1 Operation FIND......Page 83
4.4.3.2 Operation INSERT......Page 84
4.4.4 Realization with an......Page 85
4.4.4.1 Insertion......Page 86
4.4.5 Realization with an AVL-Tree......Page 88
4.4.5.1 Insertion......Page 90
4.4.5.3 Deletion......Page 91
4.4.6.2 Hashing......Page 93
References......Page 95
Further Information......Page 97
5.1 Introduction......Page 98
5.2.1 Computational Problems and Languages......Page 99
5.2.2 Turing Machines......Page 100
5.2.3 Universal Turing Machines......Page 101
5.3 Resources and Complexity Classes......Page 102
5.3.1 Time and Space......Page 103
5.11.1 Interactive Proofs......Page 120
5.4.1 Constructibility......Page 105
5.4.2 Basic Relationships......Page 106
5.4.4 Hierarchy Theorems and Diagonalization......Page 107
5.4.5 Padding Arguments......Page 108
5.5 Reducibility and Completeness......Page 109
5.5.3 Cook-Levin Theorem......Page 111
5.5.4 Proving NP-Completeness......Page 112
5.6 Relativization of the P vs. NP Problem......Page 114
5.7 The Polynomial Hierarchy......Page 115
5.8 Alternating Complexity Classes......Page 116
5.9 Circuit Complexity......Page 117
5.10 Probabilistic Complexity Classes......Page 119
5.12 Kolmogorov Complexity......Page 122
5.13 Research Issues and Summary......Page 123
Further Information......Page 126
References......Page 124
6.1 Introduction......Page 128
6.2 Computability and a Universal Algorithm......Page 129
6.2.1 Some Computational Problems......Page 130
6.2.1.3 Use of Subroutines......Page 132
6.2.2 A Universal Algorithm......Page 133
6.3.1 Diagonalization and Self-Reference......Page 134
6.3.2 Reductions and More Undecidable Problems......Page 136
6.4 Formal Languages and Grammars......Page 138
6.4.1 Representation of Languages......Page 139
6.4.2 Hierarchy of Grammars......Page 143
6.4.3 Context-Free Grammars and Parsing......Page 145
6.5.1 Finite Automata......Page 149
6.5.2 Turing Machines......Page 154
6.5.2.1 Time and Space Complexity......Page 156
6.5.2.2 Other Computing Models......Page 157
Defining Terms......Page 158
References......Page 159
Further Information......Page 160
7.1 Introduction......Page 162
7.2 Tree Traversals......Page 163
7.3.1 The Depth-First Search Algorithm......Page 164
7.3.3 Analysis......Page 165
7.3.6 Applications of Depth-First Search......Page 166
7.4.1 Sample Execution......Page 167
7.5.1 Dijkstra’s Algorithm......Page 168
7.5.2 Bellman–Ford Algorithm......Page 169
7.6.1 Prim’s Algorithm......Page 170
7.6.2.1 Analysis......Page 171
7.7.1 Matching Problem Definitions......Page 172
7.7.3 Matchings and Augmenting Paths......Page 173
7.7.4.1 High-Level Description......Page 174
7.7.5 Assignment Problem......Page 175
7.7.6 B-Matching Problem......Page 177
7.7.7 Network Flows......Page 178
7.7.8 Network Flow Problem Definitions......Page 179
7.7.9 Blocking Flows......Page 180
Acknowledgments......Page 181
References......Page 182
Further Information......Page 183
8.2 Matrix Computations and Approximation of Polynomial Zeros......Page 185
8.2.1 Products of Vectors and Matrices, Convolution of Vectors......Page 186
8.2.2 Some Computations Related to Matrix Multiplication......Page 187
8.2.4 Singular Linear Systems of Equations......Page 188
8.2.7 Parallel Matrix Computations......Page 189
8.2.9 Matrix Eigenvalues and Singular Values Problems......Page 190
8.2.10 Approximating Polynomial Zeros......Page 192
8.2.11 Fast Fourier Transform and Fast Polynomial Arithmetic......Page 193
8.3.1 Resultant Methods......Page 194
8.3.2 Grobner Bases......Page 196
8.4 Polynomial Factorization......Page 198
8.4.1 Polynomials in a Single Variable over a Finite Field......Page 199
8.4.2 Polynomials in a Single Variable over Fields of Characteristic Zero......Page 200
8.4.3 Polynomials in Two Variables......Page 201
8.4.4 Polynomials in Many Variables......Page 202
References......Page 203
Further Information......Page 208
9.1 Introduction......Page 209
9.2.1 Information-Theoretic Notions of Security......Page 210
9.2.2 Toward a Computational Notion of Security......Page 211
9.3 Building Blocks......Page 212
9.3.1 One-Way Functions......Page 213
9.3.2.1 RSA......Page 214
9.4 Cryptographic Primitives......Page 215
9.4.1 Pseudorandom Generators......Page 216
9.4.2 Pseudorandom Functions and Block Ciphers......Page 217
9.4.3 Cryptographic Hash Functions......Page 218
9.5 Private-Key Encryption......Page 219
9.6 Message Authentication......Page 222
9.7 Public-Key Encryption......Page 223
9.8 Digital Signature Schemes......Page 225
References......Page 228
Further Information......Page 230
10.1 Introduction......Page 232
10.2.1 Multiprocessor Models......Page 233
10.2.1.1 Network Topology......Page 234
10.2.1.2 Primitive Operations......Page 237
10.2.2 Work-Depth Models......Page 238
10.1......Page 239
Theorem 10.2......Page 240
10.2.5 Model Used in This Chapter......Page 241
10.3.1 Divide-and-Conquer......Page 242
10.3.3 Parallel Pointer Techniques......Page 244
10.4 Basic Operations on Sequences, Lists, and Trees......Page 245
10.4.2 Scans......Page 246
10.4.5 List Ranking......Page 247
10.4.6.1 Approach 1: Using an Array of Flags......Page 248
10.4.6.2 Approach 2: Hashing......Page 249
10.5.1 Graphs and Their Representation......Page 250
10.5.2 Breadth-First Search......Page 251
10.5.3.1 Random Mate Graph Contraction......Page 253
10.5.3.2 Deterministic Graph Contraction......Page 255
10.5.3.4 Extensions to Spanning Trees and Minimum Spanning Trees......Page 257
10.6.2 Radix Sort......Page 259
10.7 Computational Geometry......Page 260
10.7.1 Closest Pair......Page 261
10.7.2 Planar Convex Hull......Page 262
10.7.2.1 QuickHull......Page 263
10.7.2.2 MergeHull......Page 264
10.8 Numerical Algorithms......Page 266
10.8.2 Fourier Transform......Page 267
Defining Terms......Page 268
References......Page 269
11.1 Introduction......Page 273
Theorem 11.1......Page 274
11.2.2 Plane Sweep......Page 275
11.2.3 Geometric Duality......Page 276
11.2.5 Divide-and-Conquer......Page 277
Theorem 11.3......Page 278
11.2.6 Prune-and-Search......Page 279
Definition 11.1......Page 280
11.2.8 Random Sampling......Page 281
11.3 Classes of Problems......Page 282
11.3.1.1 Convex Hulls in Two and Three Dimensions......Page 283
11.3.2.1 Closest Pair......Page 284
11.3.2.2 Bichromatic Closest Pair......Page 285
11.3.2.3 Voronoi Diagrams......Page 286
11.3.2.5 Weighted Voronoi Diagrams......Page 287
11.3.3 Point Location......Page 289
11.3.4.1 Path Finding in Two Dimensions......Page 290
11.3.4.3 Motion Planning of Objects......Page 291
11.3.5.3 Minimum Enclosing Circle Problem......Page 292
11.3.6.1 Triangulation......Page 293
11.3.6.2 Other Decompositions......Page 294
11.3.7.2 Intersection Reporting/Counting Problems......Page 295
11.3.8 Geometric Searching......Page 296
11.3.8.2 Other Range Searching Problems......Page 297
References......Page 298
Further Information......Page 303
12.1 Introduction......Page 304
12.2 Sorting and Selection by Random Sampling......Page 305
12.2.1 Randomized Selection......Page 306
12.3 A Simple Min-Cut Algorithm......Page 307
12.4 Foiling an Adversary......Page 309
12.5 The Minimax Principle and Lower Bounds......Page 310
12.5.1 Lower Bound for Game Tree Evaluation......Page 311
12.6 Randomized Data Structures......Page 312
12.7 Random Reordering and Linear Programming......Page 316
12.8.1 Freivalds’ Technique and Matrix Product Verification......Page 318
12.8.2 Extension to Identities of Polynomials......Page 319
12.8.3 Detecting Perfect Matchings in Graphs......Page 322
References......Page 323
Further Information......Page 324
13.1 Processing Texts Efficiently......Page 326
13.2 String-Matching Algorithms......Page 327
13.2.1 Karp--Rabin Algorithm......Page 328
Example 13.2......Page 329
13.2.3 Boyer--Moore Algorithm......Page 330
Example 13.5......Page 331
Example 13.6......Page 332
13.2.4 Quick Search Algorithm......Page 333
Example 13.7......Page 334
13.2.6 Aho--Corasick Algorithm......Page 335
Example 13.8......Page 338
13.3.1 Zhu--Takaoka Algorithm......Page 339
13.3.2 Bird/Baker Algorithm......Page 340
Example 13.10......Page 341
13.4 Suffix Trees......Page 342
13.5 Alignment......Page 345
13.5.1 Global alignment......Page 348
13.5.2 Local Alignment......Page 350
13.5.3 Longest Common Subsequence of Two Strings......Page 352
13.5.4 Reducing the Space: Hirschberg Algorithm......Page 353
13.6 Approximate String Matching......Page 354
13.6.1 Shift-Or Algorithm......Page 355
13.6.2 String Matching with k Mismatches......Page 356
13.6.3 String Matching with k Differences......Page 357
13.6.4 Wu–Manber Algorithm......Page 359
13.7.1.1 Encoding......Page 361
13.7.1.2 Decoding......Page 364
13.7.2 Lempel–Ziv–Welsh (LZW) Compression......Page 365
13.7.2.2 Decompression Method......Page 366
13.7.2.3 Implementation......Page 367
13.7.3.1 Run Length Encoding......Page 368
13.7.3.3 Integrated Example......Page 369
13.8 Research Issues and Summary......Page 370
Defining Terms......Page 371
References......Page 372
Further Information......Page 373
14.2 Underlying Principles......Page 374
14.3 Best Practices......Page 377
14.3.1 Function Optimization......Page 378
14.3.2 Ordering Problems......Page 379
14.3.3 Automatic Programming......Page 380
14.4 Mathematical Analysis of Genetic Algorithms......Page 382
Acknowledgments......Page 385
Defining Terms......Page 386
References......Page 387
Further Information......Page 388
15.1 Introduction......Page 389
15.2 A Primer on Linear Programming......Page 391
15.2.1.1 Fourier’s Scheme for Linear Inequalities......Page 393
15.2.1.2 Simplex Method......Page 395
15.2.1.3 The Ellipsoid Algorithm......Page 397
15.2.1.4 Semidefinite Programming......Page 398
15.2.1.6 Interior Point Methods......Page 399
15.3 Large-Scale Linear Programming in Combinatorial Optimization......Page 401
15.3.1.1 Column Generation......Page 402
15.4.1.1 Covering and Packing Problems......Page 403
15.4.1.2 Packing and Covering Problems in a Graph......Page 404
15.4.1.4 Satisfiability and Inference Problems:......Page 405
15.4.1.5 Multiprocessor Scheduling......Page 406
15.4.3 Benders’s Representation......Page 407
15.5.1 Special Structures and Integral Polyhedra......Page 408
15.5.2.1 Matroid Optimization......Page 411
15.5.3 Valid Inequalities, Facets, and Cutting Plane Methods......Page 412
15.5.3.1 The Cutting Plane Method......Page 413
15.5.3.3 Other Combinatorial Problems......Page 414
15.6.1.2 Selection/Removal......Page 415
15.6.1.5 Separation/Branching......Page 416
15.6.2 Branch and Cut......Page 417
15.7 Approximation in Combinatorial Optimization......Page 418
15.7.2 Primal–Dual Approximation......Page 419
15.7.3 Semidefinite Relaxation and Rounding......Page 420
15.7.4 Neighborhood Search......Page 421
15.7.5 Lagrangian Relaxation......Page 422
15.8 Prospects in Integer Programming......Page 423
References......Page 424
Section II: Architecture and Organization......Page 430
16.1 Introduction......Page 432
16.3 Concept and Realization of a Digital Gate......Page 433
16.3.1 CMOS Binary Logic Is Low Power......Page 435
16.3.2 CMOS Switching Model for NOT, NAND, and NOR......Page 436
16.3.4 Doing It All with NAND......Page 437
16.4 Rules and Objectives in Combinational Design......Page 438
16.4.1 Boolean Realization: Half Adders, Full Adders, and Logic Minimization......Page 439
16.4.2 Axioms and Theorems of Boolean Logic......Page 441
16.4.3 Design, Gate-Count Reduction, and SOP/POS Conversions......Page 442
16.4.5 Adder/Subtractor......Page 446
16.4.6 Representing Negative Binary Numbers......Page 448
16.5.1.2 DEC......Page 450
16.5.1.3 MUX......Page 451
16.5.1.4 DEMUX/DECODER......Page 452
16.5.2 The Calculator Arithmetic and Logical Unit......Page 453
16.6.2.1 The SR Latch: Set, Reset, Hold, and Muddle......Page 455
16.6.2.2 The Transparent D-Latch......Page 456
16.6.2.3 Master–Slave DFF to Eliminate Transparency......Page 457
16.6.1 Concept of a Sequential Device......Page 454
16.6.3.1 A Stack for Holding Data......Page 458
16.6.4 Datapath for a 4-bit Calculator......Page 459
16.7 ASICs and FPGAs — Faster, Cheaper, More Reliable Logic......Page 461
16.7.1 FPGA Architecture......Page 462
16.7.1.1 The Configurable Logic Block......Page 463
16.7.1.2 Interconnect......Page 464
16.7.1.3 The Xilinx Input/Output Block......Page 465
16.7.1.4 Mapping the Simple Calculator to an FPGA......Page 466
Defining Terms......Page 467
References......Page 468
Further Information......Page 469
17.1.1 The Processor-Program Interface......Page 470
17.2 The Instruction Set......Page 471
17.2.2 Memory and Memory Referencing Instructions......Page 472
17.2.3 Control Transfer Instructions......Page 473
17.3.1 Register File......Page 474
17.3.4 Memory and Architecture......Page 475
17.4.1 Addressing Format......Page 476
17.4.2 Physical and Virtual Memory......Page 477
17.5 Instruction Execution......Page 478
17.5.4 Storeback Unit......Page 480
17.6.1 Data Hazards......Page 481
17.6.2 Control Hazards......Page 483
17.8 Very Long Instruction Word Computers......Page 484
References......Page 485
Further Information......Page 486
18.1 Introduction......Page 487
18.2 Memory Hierarchies......Page 488
18.3 Cache Memories......Page 490
18.4 Parallel and Interleaved Main Memories......Page 493
18.5 Virtual Memory......Page 496
18.6 Research Issues......Page 498
18.7 Summary......Page 499
Defining Terms......Page 500
Further Information......Page 501
19.1 Introduction......Page 502
19.2.1 Transmission-Line Concepts......Page 503
19.2.3 Wire-OR Glitches......Page 505
19.3.1 Centralized Arbitration......Page 506
19.3.2 Decentralized Arbitration......Page 507
19.4.1 Asynchronous Protocol......Page 508
19.4.3 Split-Transaction Protocol......Page 509
19.5 Issues in SMP System Buses......Page 510
19.5.1 Cache Coherence Protocols......Page 512
19.5.2 Bus Arbitration......Page 513
19.5.3 Bus Bandwidth......Page 514
19.5.5 Synchronization and Locking......Page 515
19.6 Putting It All Together — CCL-XMP System Bus......Page 516
19.7 Historical Perspective and Research Issues......Page 518
References......Page 520
Further Information......Page 522
20.1 Introduction......Page 523
20.2 Interaction Tasks, Techniques, and Devices......Page 524
20.4 Properties of Input Devices......Page 525
20.5 Discussion of Common Pointing Devices......Page 528
20.6 Feedback and Perception — Action Coupling......Page 529
20.7 Keyboards, Text Entry, and Command Input......Page 530
20.8.2 Pen-Based Gestures and Hand Gesture Input......Page 532
20.8.4 Passive Measurement: Interaction in the Background......Page 533
20.9.1 Properties of Displays and Human Visual Perception......Page 534
20.11 Luminance, Color Specification, and Color Gamut......Page 536
20.12.2 Color Information Coding......Page 538
20.12.3 Integrated Control/Display Objects......Page 539
20.13.1 Small Displays......Page 540
20.13.3 Large-Format Displays......Page 541
20.14 Force and Tactile Displays......Page 542
20.15.2 Speech Output......Page 543
20.16 Future Directions......Page 544
References......Page 545
21.1 Introduction......Page 555
21.2 Single Disk Organization and Performance......Page 558
21.2.1 Disk Organization......Page 559
21.2.2 Disk Arm Scheduling......Page 561
21.2.3.1 Disk Arm Prepositioning......Page 564
21.2.3.4 Active Disks and Free-Block Scheduling......Page 565
21.3.1 Motivation for RAID......Page 566
21.3.2.1 Striping......Page 567
21.3.3 RAID Fault-Tolerance and Classification......Page 568
21.3.5 RAID Reliability Modeling......Page 570
21.4.1 Request Scheduling with Mirrored Disks......Page 571
21.4.3 Mirrored Disk Layouts......Page 572
21.5.1 RAID5 Operation in Normal Mode......Page 573
21.5.3 RAID5 Operation in Rebuild Mode......Page 574
21.6.1 Single Disk Performance......Page 575
21.6.2 RAID Performance......Page 576
21.6.3.1 Fork-Join Synchronization......Page 577
21.6.3.2 Vacationing Server Model for Rebuild......Page 578
21.7.1 Requirements of a Storage Network......Page 579
21.8 Conclusions and Recent Developments......Page 580
Defining Terms......Page 581
References......Page 582
Further Information......Page 588
22.2 Fixed Point Number Systems......Page 589
22.2.2 Sign Magnitude......Page 590
22.2.3 One’s Complement......Page 591
22.3.1.1 Full Adder......Page 592
22.3.1.2 Ripple Carry Adder......Page 593
22.3.1.3 Carry Lookahead Adder......Page 594
22.3.1.4 Carry Skip Adder......Page 595
22.3.1.5 Carry Select Adder......Page 598
22.3.2 Fixed Point Subtraction......Page 599
22.3.3.1 Sequential Booth Multiplier......Page 600
22.3.3.4 Wallace Tree/Dadda Fast Multiplier......Page 601
22.3.4.1 Nonrestoring Divider......Page 603
22.3.4.2 Newton–Raphson Divider......Page 604
22.4.1.1 Floating Point Addition......Page 606
22.4.1.3 Floating Point Division......Page 607
22.5 Conclusion......Page 608
References......Page 609
23.2 The Stream Model......Page 611
23.3 SISD......Page 612
23.4.1 Array Processors......Page 615
23.4.2 Vector Processors......Page 616
23.6 MIMD......Page 618
23.7 Network Interconnections......Page 621
23.8 Afterword......Page 622
References......Page 623
Further Information......Page 624
24.1 Introduction......Page 625
24.2.1 LANs, WANs, MANs, and Topologies......Page 626
24.2.3 Protocol Stacks......Page 627
24.2.5 Data Representation: Modulation......Page 629
24.2.5.1 Multiplexing......Page 631
24.3.1 Media......Page 632
24.3.3 Voice Modems......Page 633
24.3.5 DSL......Page 634
24.3.6 Hubs and Other LAN Switching Devices......Page 635
24.4.2 An Example: Ethernet NIC......Page 637
24.5 Best Practices: Network Layer Examples......Page 638
Defining Terms......Page 639
References......Page 640
Further Information......Page 642
25.1 Introduction......Page 643
25.2.1 Failures......Page 644
25.2.3 Faults......Page 645
25.3.1 Metrics......Page 646
25.3.2 Evaluation......Page 647
25.4.1 Error on Output......Page 648
25.4.2 Error Masking......Page 649
25.4.3 Fault Secure Techniques......Page 650
25.4.3.2 Parity Prediction......Page 651
25.4.3.4 Application-Specific Techniques......Page 652
25.5 System Recovery......Page 653
25.6.2 Fail-Soft Techniques......Page 654
25.6.3.2 Hybrid Redundancy......Page 655
25.8 Fault Injection......Page 656
25.9 Conclusion......Page 657
References......Page 658
Section III: Computational Science......Page 663
26.1 Introduction......Page 665
26.1.1 Structured Grids......Page 666
26.1.3 Generation Process......Page 668
26.2.1 Terminology and Grid Characteristics......Page 669
26.2.2 Geometry Preparation......Page 671
26.2.3.1 Algebraic Generation Methods......Page 672
26.2.3.2 Elliptic Generation Method......Page 673
26.2.3.4 Multiblock Systems......Page 674
26.2.3.6 Adaptive Grid Generation......Page 675
26.2.4.2 Advancing Front Procedure......Page 676
26.2.4.3 Grid Adaption Methods......Page 677
26.3.1 Structured Grid Generation......Page 679
26.3.1.1 Transfinite Interpolation Method......Page 680
26.3.1.2 Elliptic Grid Generation......Page 682
26.3.2 The Delaunay Algorithm......Page 683
26.3.2.3 Boundary Integrity......Page 685
26.3.2.6 Boundary Face Recovery......Page 686
26.3.3 Hybrid Grid Generation......Page 687
26.3.3.1 Grid Adaption: Construction of Weight Functions......Page 688
26.4 Grid Systems......Page 689
26.5 Research Issues and Summary......Page 690
References......Page 691
Further Information......Page 693
27.2 Historic Overview......Page 694
27.2.1 The Motivation for Computer-Generated Visualization......Page 695
27.2.2 The Process of Computational Science in Relation to Visualization......Page 696
27.2.5 Application Areas......Page 697
27.3.1 The Goal of Scientific Visualization......Page 698
27.3.2.2 Representation Issues......Page 699
27.3.2.3 Accuracy......Page 700
27.4.1 Representation Techniques......Page 701
27.4.1.2 Color......Page 702
27.4.1.3.1 Two-Dimensional Plane......Page 703
27.4.1.3.4 Vectors: Arrows, Tracers, Streamlines, etc.......Page 704
27.4.1.3.5 Isosurfaces......Page 706
27.4.1.3.8 Alpha Shapes......Page 707
27.4.1.4 Motion......Page 708
27.4.2 The Visualization Process......Page 709
27.4.2.1 Still Imagery......Page 710
27.4.2.3 Interaction......Page 711
27.4.3 Visualization Tools......Page 712
27.4.3.2 Turnkey Visualization Packages......Page 713
27.4.3.3 Dataflow Packages......Page 714
27.4.3.4 Animation......Page 715
27.4.3.5 WYOS: Write Your Own Software......Page 716
27.4.4.1.1 Evolution of Atmospheric Simulations and Visualization......Page 717
27.4.4.1.2 What Does the Scientist Use Today?......Page 720
27.4.5 Visualizing Smog......Page 721
27.5 Research Issues and Summary......Page 722
Defining Terms......Page 723
References......Page 724
Further Information......Page 726
28.1 Introduction......Page 727
28.2.2 Different Classes of Structural Mechanics Problems......Page 728
28.3.1 Different Formulations of Structural Mechanics Problems......Page 729
28.4.1 Major Steps in the Application of Computational Structural Mechanics......Page 731
28.4.3 Discretization Techniques......Page 732
28.4.4 Model and Mesh Generation......Page 733
28.4.5.3 Adaptive Strategies......Page 734
28.5 Overview of Static, Stability, and Dynamic Analysis......Page 735
28.5.1.2 Incremental-Iterative Procedures......Page 736
28.5.2 Dynamic Analysis......Page 737
28.5.2.1 Direct Integration Techniques......Page 738
28.5.2.1.2 Newmark’s Method......Page 739
28.5.2.1.3 Modal Superposition Method......Page 740
28.5.4 Stability Analysis......Page 741
28.5.6 Sensitivity Analysis......Page 742
28.5.7 Strategies and Numerical Algorithms for New Computing Systems......Page 743
28.6 Brief History of the Development of Computational Structural Mechanics Software......Page 744
28.7 Characteristics of Future Engineering Systems and Their Implications on Computational Structural Mechanics......Page 745
28.8 Primary Pacing Items and Research Issues......Page 746
28.8.3 Hierarchical, Integrated Multiple Methods and Adaptive Modeling Techniques......Page 747
28.8.7 Related Tasks......Page 748
References......Page 749
Further Information......Page 752
29.1 Introduction......Page 753
29.2 Governing Equations......Page 755
29.3 Characteristic-Based Formulation......Page 757
29.4 Maxwell Equations in a Curvilinear Frame......Page 759
29.5 Eigenvalues and Eigenvectors......Page 762
29.6 Flux-Vector Splitting......Page 763
29.7 Finite-Difference Approximation......Page 766
29.8 Finite-Volume Approximation......Page 767
29.9 Summary and Research Issues......Page 768
References......Page 773
30.1 Introduction......Page 775
30.2.1 Fluid-Dynamical Background......Page 776
30.2.2 Treatment of Geometry......Page 780
30.2.2.1 Structured Grids......Page 781
30.3.1 Panel Methods......Page 782
30.3.2 Nonlinear Methods......Page 783
30.3.2.1 Nonlinear Potential-Equation Methods......Page 784
30.3.2.2 Euler-Equation Methods......Page 785
30.3.3.1 Turbulence Models......Page 787
30.3.3.3 Direct Numerical Simulations......Page 788
Defining Terms......Page 789
References......Page 790
Further Information......Page 792
31.1 Introduction......Page 793
31.2.2 Deep Basin or Shallow Coastal......Page 794
31.2.5 With Applications to Short-Term Simulations or Long- Term Climate Studies......Page 795
31.2.9 Process-Studies-Oriented or Application-Oriented......Page 796
31.2.11 Coupled to the Atmosphere or Uncoupled......Page 797
31.3 Best Practices......Page 800
31.3.1 Barotropic Models......Page 801
31.3.2 z-Level Models......Page 802
31.3.3 Sigma-Coordinate Models......Page 805
31.3.4 Layered Models......Page 806
31.3.6 Data Assimilation......Page 807
31.3.7 Computational Issues......Page 809
31.4 Nowcast/Forecast in the Gulf of Mexico (a Case Study)......Page 811
Defining Terms......Page 813
References......Page 814
Further Information......Page 816
32.1 Introduction......Page 818
32.2.1 Journal of Chemical Education......Page 819
32.2.2 Project SERAPHIM......Page 820
32.3.1 Numerical Solution of Differential Equations......Page 821
32.4 Molecular Dynamics Simulations......Page 822
32.4.1 The Methodology of Molecular Dynamics Simulations......Page 823
32.4.3 Concluding Comments on MD Simulations......Page 825
32.5 Modeling Organic Compounds......Page 826
32.5.1 Empirical Solutions......Page 827
32.5.3 Ab Initio Methods......Page 829
32.6 Computational Organometallic and Inorganic Chemistry......Page 830
32.6.2 Ab Initio Methods......Page 831
32.7.1 Hartree–Fock Approximation......Page 833
32.7.4 Notation......Page 834
32.7.5 Vibrational State and Spectra......Page 835
32.8 Research Issues and Summary......Page 836
Defining Terms......Page 838
References......Page 842
Further Information......Page 844
33.2 Astronomical Databases......Page 845
33.2.2 Data Collection......Page 846
33.2.3 Accessing Astronomical Databases......Page 847
33.3 Data Analysis......Page 848
33.3.1 Data Analysis Systems......Page 849
33.3.2 Data Mining......Page 850
33.3.3 Multi-Wavelength Studies......Page 851
33.3.4.2 Gamma-Ray Burst Data Analysis......Page 852
33.3.4.3 Time Series Analysis......Page 853
33.4.3 Hydrodynamics......Page 854
33.4.5 Planetary and Solar System Dynamics......Page 855
33.4.7 Star Formation and the Interstellar Medium......Page 856
33.4.9 Galaxy Clusters, Galaxy Formation, and Galactic Dynamics......Page 857
33.4.11 Compact Objects......Page 858
33.4.12 Parallel Computation in Astrophysics......Page 859
33.5 Research Issues and Summary......Page 860
Defining Terms......Page 861
References......Page 862
34.1 Introduction......Page 866
34.2 Databases......Page 868
34.2.2 Representation/Data Modeling......Page 870
34.3 Imaging, Microscopy, and Tomography......Page 871
34.4 Determination of Structures from X-Ray Crystallography and NMR......Page 872
34.4.2 X-Ray Structure Determination of Macromolecules......Page 873
34.5 Protein Folding......Page 875
34.6 Genomics......Page 876
34.6.2 Sequence Assembly......Page 877
34.6.3.1 Matching a Defined Pattern......Page 878
Defining Terms......Page 879
References......Page 881
Further Information......Page 883
Section IV: Graphics and Visual Computing......Page 884
35.2 Organization of a Three-Dimensional Computer Graphics System......Page 886
35.2.1.1 Coordinate Systems......Page 887
35.2.1.2 Geometric Modeling......Page 891
35.2.1.3 Materials......Page 892
35.2.1.4 Lights......Page 893
35.2.2.1 Camera......Page 895
35.2.3 Storage and Display......Page 896
35.2.3.2 Display Devices......Page 897
35.2.3.3 Framebuffers......Page 898
35.2.3.4 Image Files......Page 899
Defining Terms......Page 902
References......Page 903
Further Information......Page 904
36.1 Introduction......Page 905
36.3.1 Text......Page 906
36.3.2 Lines and Polylines......Page 907
36.5 Polygons......Page 908
36.6 The Triangular Facet......Page 909
36.7.1 Implicit Primitives......Page 910
36.7.2 CSG Objects......Page 911
36.8.1 Bezier Curves......Page 912
36.8.2 B-Spline Curves......Page 914
36.9.1 Bezier Surfaces......Page 916
36.9.1.2 Subdivision of the Bezier Surface Patch......Page 917
36.9.2 B-Spline Surfaces......Page 918
36.10 Standards......Page 919
References......Page 920
37.1 Introduction......Page 921
37.2 Fractals......Page 922
37.3 Grammar-Based Models......Page 924
37.4 Procedural Volumetric Models......Page 926
37.5 Implicit Surfaces......Page 932
37.6 Particle Systems......Page 934
37.7 Research Issues and Summary......Page 936
References......Page 937
Further Information......Page 939
38.1 Introduction......Page 940
38.2.1 Introduction......Page 941
38.2.2 Viewing and Clipping......Page 942
38.2.3 Clipping and Culling......Page 945
38.2.4 Projective Transformation and Three-Dimensional Screen Space......Page 948
38.2.5 Shading Algorithm......Page 950
38.2.5.1 Rasterization......Page 951
38.2.5.3 Local Reflection Models......Page 952
38.2.5.5 Gouraud Shading......Page 955
38.2.6 Hidden-Surface Removal......Page 956
38.3 Rendering Using Ray Tracing......Page 957
38.3.1 Intersection Testing......Page 959
38.4.1 Basic Theory......Page 960
38.4.2 Form-Factor Determination......Page 961
38.4.3 Problems with the Basic Method......Page 962
38.6 An OpenGL Example......Page 965
Defining Terms......Page 969
Further Information......Page 971
39.1 Introduction......Page 972
39.2 Sampling Theory......Page 973
39.2.1 Sampling......Page 974
39.3.1 Reconstruction Conditions......Page 975
39.3.3 Sinc Function......Page 976
39.3.4 Nonideal Reconstruction......Page 977
39.4.1 Box Filter......Page 979
39.4.4 Windowed Sinc Function......Page 980
39.4.5 Hann and Hamming Windows......Page 982
39.4.7 Kaiser Window......Page 983
39.5 Aliasing......Page 984
39.6 Antialiasing......Page 985
39.6.1 Point Sampling......Page 986
39.6.2 Area Sampling......Page 987
39.6.3 Supersampling......Page 988
39.7.1 Pyramids......Page 989
39.7.2 Summed-Area Tables......Page 991
39.8 Example: Image Scaling......Page 992
39.9 Research Issues and Summary......Page 996
Defining Terms......Page 1000
References......Page 1001
Further Information......Page 1002
40.1 Introduction......Page 1003
40.2.1.2 Motion Capture......Page 1004
40.2.1.3 Motion Retargeting......Page 1005
40.2.1.5 Inverse Kinematics......Page 1006
40.2.2 Character Deformations......Page 1007
40.3.2 Dynamic Simulation......Page 1008
40.3.2.2 Cloth Animation......Page 1009
40.4.1 Artificial and Virtual Life......Page 1010
40.5 Crowds and Groups......Page 1011
40.6 Facial Animation......Page 1012
40.7.1 Kochanek--Bartels Spline Interpolation......Page 1014
Defining Terms......Page 1016
References......Page 1017
Further Information......Page 1020
41.1 Introduction......Page 1022
41.3 Rendering via Geometric Primitives......Page 1023
41.5 Volumetric Function Interpolation......Page 1024
41.6.1 Image-Order Techniques......Page 1027
41.6.2 Object-Order Techniques......Page 1031
41.6.3 Hybrid Techniques......Page 1033
41.7 Acceleration Techniques......Page 1034
41.8 Classification and Transfer Functions......Page 1037
41.9 Volumetric Global Illumination......Page 1039
41.11 General-Purpose Rendering Hardware......Page 1040
41.12 Irregular Grids......Page 1041
41.14 Volume Graphics......Page 1043
41.14.2 Fundamentals of 3-D Discrete Topology......Page 1044
41.14.3 Binary Voxelization......Page 1045
41.14.4 Antialiased Voxelization......Page 1046
41.14.5 Block Operations and Constructive Solid Modeling......Page 1047
41.14.6 Texture Mapping and Solid Texturing......Page 1049
41.14.8 Natural Phenomena......Page 1050
41.14.9 Volume Sculpting......Page 1051
References......Page 1052
42.1 Introduction......Page 1063
42.2 Underlying Principles......Page 1064
42.3.1.1 Visual Display......Page 1067
42.3.1.2 Audio Displays......Page 1068
42.3.2.1 Position Tracker Data......Page 1069
42.3.2.2 Position Tracker Technologies......Page 1070
42.3.2.5 Using Head Tracker Data......Page 1071
42.3.2.7 Gesture Recognition......Page 1072
42.4.1 Polling vs. Events......Page 1073
42.4.1.2 Time-Critical Rendering......Page 1074
42.4.2 Navigation......Page 1075
42.4.3 Virtual Objects......Page 1076
42.5 Environment Design Concepts......Page 1077
42.7 Application Evaluation and Design......Page 1078
42.9 Research Issues......Page 1080
Defining Terms......Page 1081
Further Information......Page 1082
43.1 Introduction......Page 1084
43.2 Low-Level Vision......Page 1085
43.2.1 Local Edge Detectors......Page 1086
43.2.2 Image Smoothing and Filtering......Page 1088
43.2.4 Multiscale Processing......Page 1089
43.2.5 Visual Motion and Optical Flow......Page 1090
43.3.1 Stereopsis......Page 1092
43.3.2 Structure from Motion......Page 1095
43.3.3 Snakes: Active Contour Models......Page 1096
43.4.1 Object Recognition......Page 1097
43.4.2 Correspondence Search: Interpretation Tree......Page 1098
43.4.4 k-Tuple Search: Alignment and Linear Combinations......Page 1099
43.4.5 Invariants, Indexing, and Geometric Hashing......Page 1100
43.4.6 Dense Feature Matching: Hausdorff Distances......Page 1101
43.4.7 Appearance-Based Matching: Subspace Methods......Page 1102
Defining Terms......Page 1103
References......Page 1104
Further Information......Page 1106
Section V: Human–Computer Interaction......Page 1107
44.1 Introduction......Page 1109
44.3 Organizations and Their Components......Page 1110
44.3.2 Organizational Components......Page 1111
44.4 Organizational Modeling, Formal and Informal......Page 1113
44.5.1 The Emergence of Distinct Development Contexts in the U.S.......Page 1114
44.6 Organizational Contexts of Use......Page 1117
44.7.1 Initiation Phase......Page 1119
44.7.3 Implementation (Introduction) and Use......Page 1120
44.8 Conclusions......Page 1121
References......Page 1122
45.1 Introduction......Page 1125
45.2 Know the User......Page 1126
45.2.2 Task Analysis......Page 1127
45.2.4 International Use......Page 1128
45.3 Competitive Analysis......Page 1129
45.4 Goal Setting......Page 1130
45.4.1 Parallel Design......Page 1131
45.5 Coordinating the Total Interface......Page 1132
45.6 Heuristic Evaluation......Page 1133
45.7 Prototyping......Page 1135
45.8.2 Test Tasks......Page 1137
45.8.4 Test Stages......Page 1138
45.8.6 Severity Ratings......Page 1139
45.8.7 Usability Laboratories......Page 1140
45.9 Iterative Design......Page 1142
45.10 Follow-Up Studies of Installed Systems......Page 1143
References......Page 1144
Further Information......Page 1145
46.1 Introduction......Page 1146
46.2.1 The Critical Role of Task Analysis and Design of Functionality......Page 1147
46.2.1.1 The Role of Task Analysis in Development......Page 1148
46.3.1 The Contribution of Human Factors to Task Analysis......Page 1149
46.3.2 Contributions of Human–Computer Interaction to Task Analysis......Page 1151
46.4 Best Practices: How to Do a Task Analysis......Page 1153
46.4.1 Collecting Task Data......Page 1154
46.4.2 Representing Systems and Tasks......Page 1155
46.4.3 Task Analysis at the Whole-System Level......Page 1156
46.4.4.1 Representing What the User Must Know......Page 1157
46.4.4.2 Representing What the User Must Do......Page 1158
46.4.4.3 Representing What the User Sees and Interacts With......Page 1159
46.5 Using GOMS Task Analysis in Functionality and Interface Design......Page 1160
46.5.2 An Example of High-Level GOMS Analysis......Page 1161
46.5.2.1 Task-Driven Design Example......Page 1162
46.5.2.2 An Actual Design Example......Page 1165
46.6 Research Issues and Concluding Summary......Page 1167
References......Page 1168
For Further Information......Page 1170
47.1.1 The Changing IT Landscape......Page 1171
47.1.2 Human Dynamics Research......Page 1172
47.2.1.1 Distributed Systems......Page 1173
47.2.1.2 Ubiquitous Computing......Page 1174
47.2.1.3 The Emergence of Commercial Off-the-Shelf Applications......Page 1175
47.2.1.4 The Internet Revolution......Page 1176
47.2.2.1 System Development Methodologies......Page 1177
47.2.2.2 Process Improvement Initiatives......Page 1180
47.2.3 IT Personality......Page 1182
47.2.3.1 Psychology of the IT Professional......Page 1185
47.2.3.2 IT Team Dynamics......Page 1186
47.2.3.3 IT Meets the User......Page 1187
47.3.1 IT Developers......Page 1188
47.3.2 IT Managers......Page 1191
47.3.3 IT Educators......Page 1192
47.4 Research Issues and Summary......Page 1193
References......Page 1194
48.1 Introduction*......Page 1197
48.2 Importance of User Interface Tools......Page 1198
48.2.1.2 Windowing Systems......Page 1199
48.2.1.2.3 Output Model......Page 1200
48.2.1.2.4 Input Model......Page 1201
48.2.1.2.6 User Interface Layer......Page 1203
48.2.1.2.7 Presentation......Page 1204
48.2.1.3 Toolkits......Page 1205
48.2.1.3.1 Toolkit Intrinsics......Page 1206
48.2.1.3.3 Specialized Toolkits......Page 1207
48.2.1.4.1 Phases......Page 1208
48.2.1.4.3.1 State Transition Networks......Page 1209
48.2.1.4.3.4 Declarative Languages......Page 1210
48.2.1.4.3.8 Summary of Language Approaches......Page 1211
48.2.1.4.5 Model-Based Automatic Generation......Page 1212
48.2.1.4.6.1 Prototyping Tools......Page 1213
48.2.1.4.6.3 Interface Builders......Page 1214
48.2.2 Tools for the World Wide Web......Page 1215
48.5.1 New Programming Languages......Page 1216
48.5.3 Increased Breadth......Page 1217
Defining Terms......Page 1218
References......Page 1219
49.1 Introduction: Media and Multimedia Interfaces......Page 1226
49.2 Types of Media......Page 1228
49.2.1 Output Media......Page 1229
49.2.2 Input Media......Page 1230
49.2.3 Wearable Computers and Ubiquitous Computing......Page 1231
49.3.1 Compact Disc Secondary Storage Technology......Page 1232
49.3.3 Animations......Page 1233
49.3.4 Audio Technology — Digital Audio and the Musical Instrument Digital Interface......Page 1234
49.3.5 Other Input, Output, or Combination Devices......Page 1236
49.5 The ISO Multimedia Design Standard......Page 1237
49.6.2 Theories of Cognition......Page 1238
49.7 Case Study — An Investigation into the Effects of Media on User Performance......Page 1241
49.7.1 The Laboratory Task......Page 1242
49.7.2 The Media Investigated......Page 1243
49.7.4 The Effects of Sound......Page 1244
49.7.5 Effects of Mental Coding......Page 1245
49.7.6 Do Multimedia Interfaces Improve Operator Performance?......Page 1246
49.8 Authoring Software for Multimedia Systems......Page 1248
References......Page 1249
General Texts That Provide Extended Information......Page 1251
50.1 Introduction......Page 1252
50.2.1 Environmental Factors Affecting Collaboration......Page 1253
50.2.2 Visual and Auditory Cues in Face-to-Face Collaboration......Page 1255
50.2.4 Proxemic Effects......Page 1256
50.2.6 Social Context Cues......Page 1257
50.2.8 Effects of I/O Rates and Asynchrony......Page 1259
50.3.1 Process Gains and Losses......Page 1260
50.3.3 Anonymity and Free-Riding......Page 1261
50.3.4 Process and Task Structures......Page 1262
50.4 Information Sharing......Page 1263
50.4.2 Opinion Formation in Computer-Supported Groups......Page 1264
50.5 Groupware......Page 1265
50.6 Research Issues and Summary......Page 1266
Defining Terms......Page 1267
References......Page 1268
Further Information......Page 1271
51.1 Introduction......Page 1272
51.2.2 The IFIP Reference Model......Page 1274
51.2.2.1 Input/Output Interface......Page 1275
51.2.2.4 Principles of Design......Page 1276
51.2.3 Usability Test Criterion......Page 1278
51.2.4 Structure and Content of the Usability Standards......Page 1279
51.2.5 Standards in Relation to the European Council Directive......Page 1281
51.3.1 Standards as Guidelines......Page 1282
51.3.3 Analyzing the Context of Use......Page 1283
51.3.5 Conformity in Terms of Usability Test Criteria......Page 1284
51.3.6 Conformance Testing vs. Heuristic Evaluations......Page 1286
51.4 Research Issues and Summary......Page 1287
References......Page 1288
Further Information......Page 1291
Section VI: Information Management......Page 1292
52.2 The Relational Model......Page 1294
52.2.1 Formal Basis......Page 1295
52.2.3 Relational Database Design......Page 1297
52.3 Object-Based Models......Page 1298
52.3.1.1 Basics......Page 1299
52.3.1.2 Representing Data Constraints......Page 1301
52.3.1.3 Use of E-R Model in Database Design......Page 1302
52.3.2.1 Basics......Page 1303
52.3.2.3 The Unified Modeling Language UML......Page 1304
52.3.2.4 Object-Oriented Database Programming Languages......Page 1305
52.3.3 Object-Relational Data Models......Page 1306
52.4 XML......Page 1307
52.5 Further Reading......Page 1310
Defining Terms......Page 1311
References......Page 1312
53.1 Introduction......Page 1314
53.2.2 Performance Spoilers......Page 1315
53.3.1 Tuning Hardware......Page 1317
53.3.2.1 File Layout......Page 1318
53.3.3 Tuning Concurrency Control......Page 1319
53.3.3.1 Rearranging Transactions......Page 1320
53.3.4 Indexes......Page 1321
53.3.4.2 Clustering and Sparse Indexes......Page 1322
53.3.4.4 Final Remarks Concerning Indexes......Page 1324
53.3.5.1 To Normalize or Not to Normalize......Page 1325
53.3.5.2 Redundant Tables......Page 1327
53.4.1 Assemble Object Collections in Bulk......Page 1328
53.4.2 Cursors Cause Friction......Page 1329
53.4.3 The Art of Insertion......Page 1330
53.6 Tuning Rules of Thumb......Page 1331
Defining Terms......Page 1332
Further Information......Page 1334
54.1 Introduction......Page 1335
54.2 Underlying Principles......Page 1336
54.3.1 The B+-Tree......Page 1338
54.3.1.1 Fan-Out Calculations......Page 1339
54.3.1.2 Key Compression and Binary Search within Pages......Page 1340
54.3.1.3 Insertion and Deletion......Page 1341
54.3.1.5 Bounded Disorder......Page 1343
54.3.2 Hashing......Page 1344
54.3.2.1 Linear Hashing......Page 1345
54.3.2.2 Extendible Hashing......Page 1347
54.3.3.1 R-Tree and R*- Tree......Page 1348
54.3.3.2 hB.- Trees......Page 1350
54.3.4 Temporal Methods......Page 1352
54.3.4.1 The Write-Once B-Tree......Page 1354
54.3.4.3 Other Extensions of the Write-Once B-Tree......Page 1355
54.3.5 Spatio-Temporal Methods......Page 1356
54.4 Research Issues and Summary......Page 1358
Defining Terms......Page 1359
References......Page 1360
Further Information......Page 1361
55.1 Introduction......Page 1363
55.2.2.2 Planner......Page 1366
55.2.3 Description Focus......Page 1367
55.3 Algebraic Space......Page 1368
55.4.1 Dynamic Programming Algorithms......Page 1370
55.4.2.2 Results......Page 1373
55.4.3 Other Search Strategies......Page 1374
55.5.1 Histograms......Page 1375
55.6.1 Parallel Databases......Page 1377
55.7.1 Semantic Query Optimization......Page 1378
55.7.3 Parametric/Dynamic Query Optimization......Page 1379
References......Page 1380
56.1 Introduction......Page 1383
56.2.1.2 Transaction Schedules......Page 1386
56.2.1.3 Testing for Serializability......Page 1387
56.2.2.2 Buffer Management Issues......Page 1388
56.2.2.3 Logging......Page 1389
56.3.1.1 Two-Phase Locking......Page 1390
56.3.1.2 Isolation Levels......Page 1392
56.3.1.3 Hierarchical Locking......Page 1394
56.3.1.4 Other Concurrency Control Methods......Page 1395
56.3.2.1 Overview of ARIES......Page 1396
56.3.2.2 Analysis......Page 1397
56.4 Research Issues and Summary......Page 1399
Defining Terms......Page 1400
Reference......Page 1401
Further Information......Page 1402
57.1 Introduction......Page 1403
57.1.1 Transaction Processing Preliminaries......Page 1404
57.1.2 Transaction Processing Infrastructure......Page 1405
57.1.3 Distributed Transaction Processing......Page 1406
57.1.3.2 Data Sharing or Shared Disk Systems......Page 1408
57.2 Secure Distributed Transaction Processing: Cryptography......Page 1409
57.2.1 The iKP Protocol......Page 1410
57.3 Transaction Processing on the Web: Web Services......Page 1411
57.3.2 Components of Web Services......Page 1412
57.3.3 Web Services Transactions (WS-Transactions)......Page 1413
57.4 Concurrency Control for High-Contention Environments......Page 1414
57.4.2 Two-Phase Processing Methods......Page 1415
57.4.3 Reducing Data Contention......Page 1416
57.4.3.1 Further Information......Page 1417
57.5.1 Hardware Resource Contention......Page 1418
57.5.1.1 Analysis of an Open QNM......Page 1419
57.5.1.2 Analysis of a Closed QNM......Page 1420
57.5.1.3 Hierarchical Solution Method......Page 1421
57.5.2.1 Probability of Lock Conflict and Deadlock......Page 1422
57.5.2.2 Effect of Lock Contention on Response Time......Page 1423
57.6 Conclusion......Page 1424
References......Page 1425
Further Information......Page 1427
58.2 Underlying Principles......Page 1428
58.3.1 Architectural Issues......Page 1431
58.3.2 Data Integration......Page 1433
58.3.3 Concurrency Control......Page 1434
58.3.4 Reliability......Page 1435
58.3.5 Replication......Page 1438
58.3.6 Data Placement......Page 1439
58.3.7 Query Processing and Optimization......Page 1440
58.3.8 Load Balancing......Page 1442
58.4.1 Mobile Databases......Page 1443
58.4.2 Large-Scale Query Processing......Page 1444
Defining Terms......Page 1445
References......Page 1447
Further Information......Page 1450
59.1 Introduction......Page 1452
59.2.1 Low-Level Image Content Analysis......Page 1453
59.2.1.2 Texture......Page 1454
59.2.1.3 Shape......Page 1455
59.3.1 Visual Content Analysis......Page 1456
59.3.1.1 Video Shot Detection......Page 1457
59.3.1.2 Video Scene and Event Detection......Page 1458
59.3.2.1 Audio Segmentation and Classification......Page 1459
59.3.3.1 Video Skimming......Page 1460
59.3.3.2 Video Summarization......Page 1461
59.4 Bridging the Semantic Gap in Content Management......Page 1463
59.4.1 Computational Media Aesthetics......Page 1464
59.5.1 An Example Object-Relational Image Data Model......Page 1465
59.6 Modeling and Querying Videos......Page 1466
59.6.2 Annotation-Based Models......Page 1467
59.7 Multidimensional Indexes for Image and Video Features......Page 1468
59.7.1 Tree-Based Index Structures......Page 1469
59.7.2.1 Dimensionality Reduction......Page 1470
59.7.2.3 Indexing Metric Spaces......Page 1471
59.8 Multimedia Query Processing......Page 1472
59.10 Conclusion......Page 1473
References......Page 1474
60.1 Introduction......Page 1480
60.2 General Security Principles......Page 1481
60.3.1.3 Granting and Revoking Access......Page 1482
60.3.3 Mandatory Access Controls......Page 1484
60.3.3.2 Polyinstantiation......Page 1485
60.4 Assurance......Page 1486
60.5 General Privacy Principles......Page 1487
60.7.1 Discretionary Access Controls......Page 1488
60.7.3 Authorization for Advanced Database Management Systems......Page 1490
Defining Terms......Page 1491
Further Information......Page 1492
Section VII: Intelligent Systems......Page 1493
61.1 Introduction......Page 1495
61.2.1 Propositional Logic......Page 1496
61.2.3 First-Order Logic......Page 1497
61.3.1 Classical Logic......Page 1498
61.3.2 Resolution......Page 1499
61.3.3.1 Negation Normal Form......Page 1501
61.3.3.2 The Tableau Method......Page 1502
61.3.3.3 Path Dissolution......Page 1504
61.3.4 Model Finding in Propositional Logic......Page 1505
61.3.4.1 The Davis-Putnam Procedure......Page 1506
61.3.5 Nonclassical Logics......Page 1507
61.3.5.1 Multiple-Valued Logics......Page 1508
61.3.5.2 Fuzzy Logic......Page 1509
61.3.5.3 Nonmonotonic Logics......Page 1512
61.4 Research Issues and Summary......Page 1514
Defining Terms......Page 1515
References......Page 1516
Further Information......Page 1518
62.1 Introduction......Page 1519
62.2.1 Representing Quantity......Page 1520
62.2.2 Representing Mathematical Relationships......Page 1521
62.2.4 State, Time, and Behaviors......Page 1523
62.2.5 Space and Shape......Page 1525
62.2.6 Compositional Modeling, Domain Theories, and Modeling Assumptions......Page 1526
62.3.1 Model Formulation......Page 1527
62.3.2 Causal Reasoning......Page 1528
62.3.3 Simulation......Page 1529
62.3.6 Data Interpretation......Page 1530
62.4.1 Monitoring, Control, and Diagnosis......Page 1531
62.4.3 Intelligent Tutoring Systems and Learning Environments......Page 1533
62.5 Research Issues and Summary......Page 1534
References......Page 1535
Further Information......Page 1537
63.1 Introduction......Page 1538
63.2.2 State-Space Search......Page 1539
63.2.4 Depth-First Search......Page 1541
63.2.5 Bidirectional Search......Page 1542
63.3 Heuristic Search Methods......Page 1543
63.3.1 Hill Climbing......Page 1544
63.3.2 Best-First Search......Page 1545
63.3.3 The A* Algorithm......Page 1547
63.4.1 The Alpha-Beta Algorithms......Page 1548
63.4.2 SSS* Algorithm......Page 1549
63.4.3 The MTD(f) Algorithm......Page 1551
63.5 Parallel Search......Page 1552
63.5.1.1 Parallel A*......Page 1553
63.5.1.3 A Comparison with Parallel Window Search......Page 1554
63.5.2 Adversary Games......Page 1555
63.5.2.2 Advanced Tree-Splitting Methods......Page 1556
63.5.2.3 Dynamic Distribution of Work......Page 1557
63.6 Recent Developments......Page 1558
Defining Terms......Page 1560
References......Page 1561
For Further Information......Page 1563
64.1.1 Defining the Problem......Page 1564
64.1.2 System Architecture and Research Issues......Page 1566
64.2.1 Procedure for System Development......Page 1567
64.2.2 Data Collection......Page 1568
64.2.3 Speech Recognition......Page 1569
64.2.5 Speech Recognition/Natural Language Integration......Page 1570
64.2.7 Evaluation......Page 1571
64.3.1.1 The Air Travel Information Service (ATIS) Common Task......Page 1574
64.3.1.2 Other Advanced Research Projects Agency Projects......Page 1576
64.4.1 Working in Real Domains......Page 1577
64.4.2 The New Word Problem......Page 1578
64.4.3 Spoken Language Generation......Page 1579
Defining Terms......Page 1580
References......Page 1581
Further Information......Page 1583
65.1.1 Attribute-Value Representation......Page 1584
65.2.1 Method for Constructing Decision Trees......Page 1585
65.2.2 Choosing Tests......Page 1586
65.2.2.2 Gain Ratio......Page 1587
65.2.3.1 Cost-Complexity Pruning......Page 1588
65.2.4 Missing Attribute Values......Page 1589
65.2.5.1.2 Linear Multiattribute Tests......Page 1590
65.2.5.2 Multiclass Problems......Page 1591
65.2.5.4.2 Peepholing......Page 1592
65.3.2.1 Continuous Attributes......Page 1593
65.3.2.2 Discrete Attributes......Page 1594
65.3.4 How Many Neighbors?......Page 1595
65.4 Composite Classifiers......Page 1596
References......Page 1597
Further Information......Page 1599
66.1 Introduction......Page 1600
66.2.1 Density Estimation......Page 1601
66.2.2 Linear Regression and Linear Discriminants......Page 1602
66.2.3 Nonlinear Regression and Nonlinear Classification......Page 1604
66.2.5 General Mixture Models......Page 1606
66.3 Learning from Data......Page 1607
66.3.1 Likelihood-Based Cost Functions......Page 1608
66.3.2 Gradients of the Cost Function......Page 1609
66.3.4 Hessian Matrices, Error Bars, and Pruning......Page 1610
66.3.5 Complexity Control......Page 1611
66.3.6 Bayesian Viewpoint......Page 1613
66.3.7 Preprocessing, Invariances, and Prior Knowledge......Page 1614
66.4 Graphical Models......Page 1615
Defining Terms......Page 1618
References......Page 1619
Further Information......Page 1621
67.1.1 Planning and Scheduling Problems......Page 1622
67.1.2 Distinctions and Disciplines......Page 1623
67.2.1 Representing Dynamical Systems......Page 1624
67.2.3 Measuring Performance......Page 1626
67.3 Algorithms, Complexity, and Search......Page 1627
67.3.2 Planning with Deterministic Dynamics......Page 1628
67.3.2.2 Representing Partial Plans......Page 1630
67.3.2.3 Refinement Search......Page 1631
67.3.2.5 Plan-Space Refinements......Page 1632
67.3.2.6 Task-Reduction Refinements......Page 1634
67.3.2.8 Handling Incomplete Information......Page 1635
67.3.3.1 Scheduling and Constraint Satisfaction......Page 1636
67.3.3.3 Repair-Based Methods......Page 1637
67.3.4 Improving Efficiency......Page 1638
67.3.5 Approximation in Stochastic Domains......Page 1639
67.4 Research Issues and Summary......Page 1641
References......Page 1642
Further Information......Page 1644
68.1 Introduction......Page 1645
68.2 Background......Page 1647
68.3 Explanation-Based and Empirical Learning......Page 1649
68.4 Explanation-Based Learning......Page 1651
68.5 Constructing Explanations......Page 1652
68.6 Generalizing......Page 1653
68.6.2 Identity Elimination......Page 1655
68.6.3 Operationality Pruning......Page 1656
68.6.4 Disjunctive Augmentation......Page 1657
68.7 The Utility Problem: Selecting a Concept Descriptor......Page 1658
Defining Terms......Page 1660
References......Page 1661
69.1 Introduction......Page 1663
69.2.1 Psychology......Page 1664
69.2.2 Neuroscience......Page 1665
69.2.4 Evolutionary and Environmental Psychology......Page 1666
69.3.1 Are We Symbol Processors?......Page 1667
69.3.2 Grand Theories?......Page 1669
69.4 Best Practices......Page 1670
69.5 Summary......Page 1672
References......Page 1673
Further Information......Page 1675
70.1 Introduction......Page 1676
70.2 Historical Background......Page 1677
70.3.1 Formal Semantics......Page 1678
70.3.2 Inference Algorithms......Page 1679
70.3.4.1 Causal Discovery......Page 1680
70.4 Bayesian Networks as Carriers of Causal Information......Page 1681
70.4.1 Causal Theories, Actions, Causal Effect, and Identifiability......Page 1682
70.4.2 Acting vs Observing......Page 1684
70.4.3 Action Calculus......Page 1686
70.4.4 Historical Remarks......Page 1687
70.5.1 Formal Underpinning......Page 1688
70.5.2 Applications to Policy Analysis......Page 1689
References......Page 1690
Chapter 71: Robotics......Page 1694
71.2 Robot Workcells......Page 1695
71.3.1 Intelligent Control Architectures......Page 1697
71.3.2 Behaviors and Hybrid Systems Design......Page 1698
71.3.3 Workcell Planning, Coordination, and Control Structure......Page 1699
71.4 Commercial Robot Configurations and Types......Page 1700
71.4.2.1 Articulated Arms......Page 1701
71.4.2.4 Cartesian Coordinate Robots......Page 1702
71.4.4.1 Motion Trajectory Generation and Following......Page 1704
71.4.4.3 Human Integration......Page 1705
71.5.1.1.1 Link A Matrices......Page 1706
71.5.1.2.1 Transformation of Velocity and Acceleration......Page 1707
71.5.2.1 Robot Dynamics......Page 1708
71.5.3.1 Computed Torque Control......Page 1709
71.5.3.3 Adaptive and Robust Control......Page 1710
71.5.5 Motion Trajectory Generation......Page 1711
71.5.5.1.2 Trajectory Interpolation......Page 1712
71.6.1 Part Fixtures and Robot Tooling......Page 1714
71.6.2.1 Gripper Mechanisms......Page 1715
71.6.3 Robot Wrist Mechanisms......Page 1716
71.6.4 Robot/Tooling Process Integration and Coordination......Page 1717
71.7.2 Types of Sensors......Page 1718
71.7.2.4 Force and Torque Sensors......Page 1719
71.7.3 Sensor Data Processing......Page 1720
71.7.4.2.1 Image Coordinates of a Point in Base Coordinates......Page 1722
71.8 Workcell Planning......Page 1724
71.8.2.2 Computer Science Planning Tools......Page 1725
71.8.3 Task Matrix Approach to Workcell Planning......Page 1726
71.8.3.1.2 Sequencing State Vector and Job Start Equation......Page 1727
71.8.3.2.1 Resource Requirements (RR) Matrix......Page 1728
71.8.3.3 Petri Net from Task Plan Matrices......Page 1729
71.8.4 Path Planning......Page 1730
71.8.4.2.1 Road Map Based on Voronoi Diagram......Page 1731
71.8.4.3 Quadtree Approach......Page 1732
71.8.4.5.1 Emergent Behaviors......Page 1733
71.9.1.1 Rule-Based Matrix DE Coordinator......Page 1734
71.9.1.2 Deadlocks and Resource Dispatching Commands......Page 1735
71.9.2 Process Integration, Digital I/O, and Job Coordination Controller Implementation......Page 1736
71.10 Error Detection and Recovery......Page 1737
71.11.1 Levels of User Interface......Page 1738
71.11.2.2 Off-Line Robot Teaching and Workcell Programming......Page 1739
71.12.2 V+, A Representative Robot Language......Page 1740
71.12.2.4 Special Functions......Page 1741
71.13 Mobile Robots and Automated Guided Vehicles......Page 1742
71.13.1.2 Nonholonomic Constraints and the Steering System......Page 1743
71.13.2 Automated Guided Vehicle Systems......Page 1744
Defining Terms......Page 1745
References......Page 1747
Further Information......Page 1748
Section VIII: Net-Centric Computing......Page 1749
72.1 Transmission Control Protocol/Internet Protocol and Open Systems Interconnection......Page 1750
72.1.1.1 The Transmission Control Protocol/Internet Protocol Layers......Page 1751
72.1.1.2 Operation of Transmission Control Protocol and Internet Protocol......Page 1752
72.1.2.1 Overall Architecture......Page 1754
72.1.2.5 Transport Layer......Page 1756
72.2.1.1 Circuit Switching......Page 1757
72.2.1.2 Packet Switching......Page 1759
72.2.2.1 Frame Relay......Page 1760
72.2.2.2 Asynchronous Transfer Mode......Page 1763
72.2.3.1 Carrier-Sense Multiple Access/Collision Detection (Ethernet)......Page 1765
72.2.4.1 Fiber Distributed Data Interface......Page 1767
72.2.4.2 Fibre Channel......Page 1768
72.2.4.3 Asynchronous Transfer Mode Local-Area Networks......Page 1770
Defining Terms......Page 1772
Further Information......Page 1773
73.1 Introduction......Page 1774
73.2.1 Transparent Bridging......Page 1775
73.2.2 Spanning Tree Algorithm......Page 1776
73.2.4 Source Route Bridging......Page 1778
73.3 Routers......Page 1780
73.3.1.1 Hierarchy......Page 1781
73.3.1.2 Hierarchical Addressing......Page 1782
73.3.1.3 Domains......Page 1783
73.3.1.6 Distance Vector Routing Protocols......Page 1784
73.3.1.7 Count-to-Infinity......Page 1785
73.3.1.8 Link State Protocols......Page 1786
73.3.1.9 Reliable Distribution of Link State Packets......Page 1787
73.3.3 Interdomain Routing......Page 1788
References......Page 1789
74.1 Introduction......Page 1790
74.2.1 Authentication Failures......Page 1791
74.3 Routing......Page 1792
74.4 The Transmission Control Protocol/Internet Protocol (TCP/ IP) Protocol Suite......Page 1793
74.4.3 The r-Commands......Page 1794
74.5 The World Wide Web......Page 1795
74.6 Using Cryptography......Page 1796
74.6.1 Key Distribution Centers......Page 1797
74.7.1.1 Packet Filters......Page 1798
74.7.2 Limitations of Firewalls......Page 1799
Defining Terms......Page 1800
References......Page 1801
75.1 Introduction......Page 1804
75.2.1 Text Retrieval Issues......Page 1805
75.2.2 Text Retrieval Methods......Page 1806
75.2.3 Text Retrieval Systems and Models......Page 1807
75.2.4 Web and Multimedia Information Retrieval......Page 1808
75.2.5 Evaluating IR Systems......Page 1809
75.3.1 Concept Description......Page 1810
75.3.2 Association Rule Mining......Page 1811
75.3.3 Classification and Prediction......Page 1812
75.3.4 Clustering......Page 1813
75.4 Integrating IR and DM Techniques into Modern Search Engines......Page 1814
75.4.2 Vivisimo......Page 1815
75.4.5 E-Commerce Systems......Page 1816
Reference......Page 1817
76.1 Introduction......Page 1820
76.2.2 Metric: Information......Page 1821
76.2.3 Methods......Page 1822
76.2.3.1 Entropy Coding......Page 1823
76.2.3.2 Huffman Coding......Page 1824
76.2.3.3 Arithmetic Coding......Page 1828
76.2.4 Dictionary-Based Techniques......Page 1831
76.2.4.1 LZW Compression......Page 1833
76.2.5.2 Run-Length Coding......Page 1835
76.3.1.1 Quantization: Pulse Code Modulation (PCM)......Page 1837
76.3.1.2 Differential Pulse Code Modulation (DPCM)......Page 1838
76.3.1.3 Predictive Differential Pulse Code Modulation (DPCM)......Page 1839
76.3.1.4 Vector Quantization......Page 1841
76.3.2 Transform Domain Compression......Page 1842
76.3.2.1 Wavelets and Subband Coding......Page 1851
References......Page 1858
77.1 Introduction......Page 1860
References......Page 1863
Further Information......Page 1864
78.2 Culture of the Underground......Page 1865
78.2.2 Hacker......Page 1866
78.3.1.2 Trojan Mule......Page 1867
78.3.2 Boot Sector Viruses......Page 1868
78.3.3 File Infector Viruses......Page 1869
78.3.5.2 Stealth......Page 1870
78.3.7.1 Scanner......Page 1871
78.3.8.2 Anatomy of a Hack......Page 1872
78.3.8.3 Intelligence Gathering......Page 1873
78.3.8.5 Penetration......Page 1874
78.3.8.6 Vulnerabilities and Exploitation......Page 1875
78.3.8.7 Automated Penetration Tools......Page 1876
78.3.8.9 Advance......Page 1877
78.3.8.10.4 Community Action......Page 1878
78.3.8.11 Phreaking......Page 1879
78.3.8.11.5 PABX Penetration......Page 1880
78.4.1 Computer Security......Page 1881
Further Information......Page 1882
79.1 Introduction......Page 1883
79.2.1 Authentication by Passwords......Page 1885
79.2.2 Token-Based Authentication......Page 1886
79.3 Access Control......Page 1887
79.3.1 The Access Control Matrix......Page 1888
79.3.2.1 Access Control Lists......Page 1889
79.3.2.3 Authorization Relations......Page 1890
79.3.3 Access Control Policies......Page 1891
79.3.3.2 Classic Mandatory Policies......Page 1892
79.3.3.3 Role-Based Policies......Page 1894
79.3.4 Administration of Authorization......Page 1896
79.4.1 Intrusion Detection Systems......Page 1897
79.4.1.1 Threshold-Based Approach......Page 1898
79.4.1.3 Rule-Based Approach......Page 1899
79.4.1.5 State Transition-Based Approach......Page 1900
79.4.2 Audit Control Issues......Page 1901
References......Page 1903
Section IX: Operating Systems......Page 1904
80.2 Historical Perspective......Page 1905
80.2.2 Operator-Driven Shop Organization......Page 1906
80.2.3 Offline Loading......Page 1907
80.2.5 Batch Multiprogramming......Page 1908
80.2.6 Interactive Multiprogramming......Page 1909
80.2.8 Distributed Computing......Page 1910
80.3.1 Abstracting Reality......Page 1911
80.3.2 Managing Resources......Page 1913
80.3.3 User Interface......Page 1914
80.4.2 Virtual Machines......Page 1915
80.4.3 Components of the Kernel......Page 1917
80.5 Research Issues and Summary......Page 1918
81.1 Introduction......Page 1922
81.2.1 Address Spaces, Threads, and Multiprocessing......Page 1923
81.3 Issues in Thread Management......Page 1925
81.3.1.3 Granularity of Concurrency......Page 1926
81.3.2.2 Processor Scheduling......Page 1927
81.3.2.3 Kernel- vs User-Level Thread Management......Page 1929
81.3.3 Performance......Page 1930
81.4 Three Modern Thread Systems......Page 1931
81.5 Summary......Page 1932
References......Page 1933
82.1 Introduction......Page 1934
82.2.1 Processes......Page 1935
82.3 Resources and Scheduling......Page 1937
82.3.1 Processor Scheduling......Page 1938
82.3.2.2 Shortest Job First (SJF) Dispatching......Page 1939
82.3.2.4 Dynamic Dispatching Priority Adjustment......Page 1940
82.3.3.3 Cycle-Oriented Round Robin......Page 1941
82.3.4.1 Multilevel Feedback Queue Dispatching......Page 1942
82.3.4.2 Process Scheduling in UNIX......Page 1943
82.4 Memory Scheduling......Page 1944
82.5 Device Scheduling......Page 1945
82.5.1 Scheduling Shareable Devices......Page 1948
82.5.2 Evaluation and Selection of a Disk Scheduling Algorithm......Page 1950
82.5.3.2 Virtual Devices......Page 1951
82.6.1 Deadlock......Page 1952
82.6.1.2 Deadlock Avoidance......Page 1953
82.6.1.3 Deadlock Detection......Page 1954
82.6.1.5 The Eclectic Approach......Page 1956
82.7 High-Level Scheduling......Page 1957
82.8.1 Processor Scheduling......Page 1958
82.8.2 Disk Scheduling......Page 1960
82.8.3 Deadlock......Page 1964
References......Page 1965
Further Information......Page 1970
83.1 Introduction......Page 1971
83.2 Underlying Principles......Page 1972
83.3.1 Real-Time Scheduling......Page 1975
83.3.2 Real-Time Kernels......Page 1976
83.3.3 Real-Time Architecture and Fault Tolerance......Page 1977
83.3.5 Distributed Multimedia......Page 1978
83.3.7 Real-Time Formal Verification, Design, and Languages......Page 1980
83.3.8 Real-Time Artificial Intelligence......Page 1981
83.4 Research Issues and Summary......Page 1982
Defining Terms......Page 1983
References......Page 1984
Other Information......Page 1985
84.1 Introduction......Page 1986
84.2.1 Synchronization Problems......Page 1987
84.2.2 Synchronization Issues......Page 1989
84.2.3 Interprocess Communication Problems......Page 1990
84.2.4 Interprocess Communication Issues......Page 1991
84.3.1.2 Solutions Using Hardware Support......Page 1992
84.3.1.3 Operating System Support......Page 1994
84.3.1.4 Language Constructs......Page 1995
84.3.1.5 Hybrid Solutions......Page 1996
84.3.1.6 Other Solutions......Page 1997
84.3.2.2 Mailboxes/Ports......Page 1998
84.3.2.4 Software Interrupts......Page 2000
84.3.4 Deadlock and Starvation......Page 2002
Defining Terms......Page 2005
References......Page 2006
Further Information......Page 2007
85.2 History......Page 2008
85.3.1 Paging......Page 2011
85.3.3 Cache Memories......Page 2013
85.3.4 Object-Oriented Virtual Memory......Page 2014
85.3.7 Performance......Page 2016
85.4 Distributed Shared Memory......Page 2018
85.6 Conclusion......Page 2019
Defining Terms......Page 2020
References......Page 2021
86.1 Introduction......Page 2023
86.2.1 Magnetic Disks......Page 2024
86.2.2 Redundant Array of Inexpensive Disks (RAID)......Page 2026
86.2.3 CD-ROM Disks......Page 2027
86.3 Filesystems......Page 2028
86.3.2 Describing a File on Disk......Page 2029
86.3.3 Filesystem Input/Output......Page 2030
86.3.4 Disk Space Management......Page 2032
86.3.5 Log-Based Systems......Page 2033
86.3.6 Versioning Systems......Page 2035
References......Page 2036
Further Information......Page 2037
87.1 Introduction......Page 2038
87.2.1.1 Amoeba......Page 2039
87.2.1.2 DEC Global Name Server (GNS)......Page 2040
87.2.1.3 Domain Name Server (DNS)......Page 2041
87.2.1.4 Plan 9......Page 2042
87.2.2 Communication......Page 2043
87.2.2.2 Amoeba......Page 2044
87.2.2.3 Firefly Remote Procedure Call......Page 2045
87.2.3.1 Locus......Page 2046
87.2.3.2 Quicksilver......Page 2047
87.2.4 Group Management......Page 2048
87.2.4.1 ISIS......Page 2049
87.3.1 Failure Models......Page 2050
87.3.2 Naming......Page 2051
87.3.3 Communication......Page 2052
87.3.4 Binding......Page 2054
87.3.5 Transactions......Page 2056
87.3.6 Group Communication......Page 2059
References......Page 2060
88.1 Introduction......Page 2064
88.2 Issues in Multiprocessor Scheduling......Page 2065
88.2.1 Distributed Scheduling......Page 2066
88.2.2 Scheduling for Shared-Memory Parallel Systems......Page 2067
88.3.1.2 Static Analysis......Page 2068
88.3.1.3 Distributed-Memory Systems......Page 2069
88.3.2.1 Dynamic, Distributed, Cooperative, Suboptimal Algorithms......Page 2070
88.3.2.4 Static Algorithms......Page 2072
88.3.3.1 Messiahs......Page 2073
88.3.3.3 AppLeS......Page 2074
88.3.3.4 Prophet and Gallop......Page 2075
88.3.3.6 Co-allocation......Page 2077
Defining Terms......Page 2078
References......Page 2079
For Further Information......Page 2081
89.1 Introduction......Page 2083
89.2 Underlying Principles......Page 2084
89.2.1 Coherency of Data......Page 2085
89.2.3 Performance......Page 2089
89.2.4 Resilience......Page 2090
89.2.6 Replication......Page 2091
89.3.1 NFS......Page 2092
89.3.2 Distributed File System......Page 2095
89.3.3 IVY......Page 2097
89.4 Research Issues and Summary......Page 2098
References......Page 2100
Further Information......Page 2101
Section X: Programming Languages......Page 2102
90.1 Introduction......Page 2104
90.2.2 Variables......Page 2105
90.2.3 Types......Page 2106
90.2.4 Scope......Page 2107
90.2.5 Execution Units: Expressions, Statements, Blocks, and Programs......Page 2108
90.3.1.1 If Statements......Page 2109
90.3.1.2 Case Statements......Page 2110
90.3.2 Iterative Structures......Page 2111
90.3.3 Unconstrained Control Structures: Goto and Exceptions......Page 2112
90.3.4 Procedural Abstraction......Page 2113
90.3.5 Data Abstraction......Page 2116
90.4.1 Data Bindings: Variables, Types, Scope, and Lifetime......Page 2118
90.4.3 Control Structures......Page 2120
90.4.5 Data Abstraction and Separate Compilation......Page 2121
90.5 Research Issues and Summary......Page 2123
Defining Terms......Page 2124
Further Information......Page 2125
91.1 Introduction......Page 2126
91.2 Underlying Principles......Page 2128
91.3.1 Smalltalk......Page 2131
91.3.2 C++......Page 2138
91.3.3 Java......Page 2142
91.3.4 C#......Page 2146
91.4 Language Implementation Issues......Page 2149
91.5 Research Issues......Page 2150
References......Page 2151
Further Information......Page 2152
92.1 Introduction......Page 2153
92.2 History of Functional Languages......Page 2155
92.3 The Lambda Calculus: Foundation of All Functional Languages......Page 2156
92.5 SCHEME: A Functional Dialect of LISP......Page 2157
92.5.1 SCHEME Data Types......Page 2158
92.5.2 SCHEME Syntax......Page 2159
92.5.3 Predefined Functions......Page 2160
92.6 Standard ML: A Strict Polymorphic Functional Language......Page 2162
92.6.2 Expressions in ML......Page 2163
92.6.3 Declarations in ML......Page 2164
92.6.4 Pattern Matching......Page 2165
92.6.5 Type Definitions......Page 2166
92.6.6 Type Variables and Parametric Polymorphism......Page 2167
92.6.7 Type Constructors......Page 2168
92.6.8 The ML Module System......Page 2169
92.6.9 Impurities in ML: References and I/O......Page 2171
92.7 Nonstrict Functional Languages......Page 2172
92.8.1 The HASKELL Class System......Page 2174
92.8.3 Instance Declarations......Page 2175
92.8.4 List Comprehensions in HASKELL......Page 2176
92.9.1 Program Analysis and Optimization......Page 2177
92.9.4 State in Functional Programming......Page 2178
References......Page 2179
Further Information......Page 2180
93.1 Introduction......Page 2181
93.2 An Introductory Example......Page 2182
93.4 Historical Remarks......Page 2184
93.5.1 Resolution......Page 2186
93.5.2 Unification......Page 2189
93.5.3 Combining Resolution and Unification......Page 2191
93.6 Procedural Interpretation: Examples......Page 2192
93.7 Impure Features......Page 2195
93.8 Constraint Logic Programming......Page 2196
93.9 Recent Developments in CLP (2002)......Page 2197
93.9.2 Special Constraints......Page 2198
93.9.4 Optimization......Page 2199
93.9.6 SATisfiability Problems......Page 2200
93.11 Theoretical Foundations......Page 2201
93.12 Metalevel Interpretation......Page 2203
93.13 Implementation......Page 2205
93.13.3 Design and Implementation Issues in Constraint Logic Programming......Page 2206
93.14 Research Issues......Page 2207
93.14.3 Interval Constraints......Page 2208
93.15 Conclusion......Page 2209
Defining Terms......Page 2210
References......Page 2211
Further Information......Page 2212
94.1 Introduction......Page 2213
94.2 Perl......Page 2215
94.3 Tcl/Tk......Page 2219
94.3.1 The Main Program......Page 2220
94.3.2 The lookup uids Procedure......Page 2221
94.3.3 The lookup by name Procedure......Page 2223
94.3.4 The find uid from name Procedure......Page 2224
94.3.5 Summary......Page 2225
94.4 PHP......Page 2226
Further Information......Page 2229
Chapter 95: Event-Driven Programming......Page 2231
95.2 The Event-Driven Programming Paradigm......Page 2232
95.3 Applets......Page 2234
95.4.1 Mouse Clicks......Page 2236
95.4.2 Mouse Motion......Page 2237
95.4.3 Buttons......Page 2238
95.4.4 Labels, TextAreas, and TextFields......Page 2239
95.4.5 Choices......Page 2240
95.5 Example: A Simple GUI Interface......Page 2241
95.6.1 Interactive Games: Tic-Tac-Toe......Page 2248
95.6.2 Automated Teller Machine......Page 2249
95.6.3 Home Security Alarm System......Page 2250
Acknowlegdments......Page 2251
References......Page 2252
96.1 Introduction......Page 2253
96.3 Software Architectures......Page 2256
96.3.1 Busy-Wait: Concurrency without Abstractions......Page 2257
96.3.2 Semaphores......Page 2261
96.3.2.1 Semaphores and Producer-Consumer......Page 2262
96.3.2.2 Semaphores and Readers-Writers......Page 2263
96.3.3 Monitors......Page 2264
96.3.3.1 Monitors and Producer-Consumer......Page 2265
96.3.4 Message Passing......Page 2266
96.3.4.1 Message Passing and Producer-Consumer......Page 2267
96.3.4.2 Message Passing and Readers-Writers......Page 2269
96.3.4.4 The Remote Procedure Call and Rendezvous Abstractions......Page 2270
96.5 Formal Approaches......Page 2271
96.6 Existing Languages with Concurrency Features......Page 2272
96.7 Research Issues......Page 2273
Defining Terms......Page 2274
Further Information......Page 2275
97.1 Introduction......Page 2277
97.1.1.1 Typed and Untyped Languages......Page 2278
97.1.1.3 Execution Errors and Well-Behaved Programs......Page 2279
97.1.3 Should Languages Be Safe?......Page 2280
97.1.4 Should Languages Be Typed?......Page 2281
97.1.6 How Type Systems Are Formalized......Page 2282
97.1.7 Type Equivalence......Page 2283
97.2.1.1 Type Rules......Page 2284
97.2.1.2 Type Derivations......Page 2285
97.2.3 Type Soundness......Page 2286
97.3 First-Order Type Systems......Page 2287
97.4 First-Order Type Systems for Imperative Languages......Page 2294
97.5 Second-Order Type Systems......Page 2295
97.6 Subtyping......Page 2298
97.8.1 The Type Inference Problem......Page 2301
97.9.2 Future Directions......Page 2304
Defining Terms......Page 2305
References......Page 2306
Further Information......Page 2307
98.1 Introduction......Page 2309
98.2.1 Operational Semantics......Page 2310
98.2.2 Denotational Semantics......Page 2312
98.2.3 Natural Semantics......Page 2313
98.3.1 Language Syntax and Informal Semantics......Page 2314
98.3.2 Domains for Denotational Semantics......Page 2315
98.3.3 Denotational Semantics of Programs......Page 2316
98.3.4 Semantics of the While-Loop......Page 2318
98.3.6 The Natural Semantics of the Language......Page 2319
98.3.7 The Operational Semantics of the Language......Page 2320
98.3.8 An Axiomatic Semantics of the Language......Page 2321
98.4 Applications of Semantics......Page 2322
98.5 Research Issues in Semantics......Page 2323
Defining Terms......Page 2324
References......Page 2325
Further Information......Page 2326
99.1 Introduction......Page 2328
99.2.1 Finite Automata......Page 2331
99.2.2 Context-Free Grammars......Page 2332
99.2.3 Parsing Algorithms......Page 2333
99.2.4 Attribute Grammars......Page 2336
99.3 Best Practices......Page 2337
99.3.1 Specifying Syntax Using Regular Expressions and Grammars......Page 2338
99.3.2 Lex/Flex and Yacc/Bison......Page 2340
99.3.3 Purdue Compiler Construction Tool Set (PCCTS)......Page 2342
99.3.4 Dealing with Ambiguity......Page 2344
99.3.6 Intermediate Representations and Code Generation......Page 2346
99.3.7 Code Optimization......Page 2349
99.3.8 Error Recovery......Page 2351
99.4 Incremental Compilation......Page 2352
Defining Terms......Page 2353
References......Page 2355
Further Information......Page 2356
100.1 Introduction......Page 2358
100.2.1 Procedures and Functions......Page 2359
100.2.2 Design Issues......Page 2360
100.2.4 Activation Records......Page 2361
100.2.5 Activation Stack......Page 2362
100.2.6.1 SPARC Register Set......Page 2363
100.2.6.2 SPARC Procedure Call Protocol......Page 2364
100.2.6.3 SPARC save and restore Instructions......Page 2365
100.2.6.4 Function bcopy as a SPARC Nonleaf Procedure......Page 2367
100.3 Pointers and Heap Management......Page 2368
100.4.1 Reference Counting......Page 2369
100.4.2 Mark-Sweep......Page 2370
100.5 Summary......Page 2371
References......Page 2372
Further Information......Page 2373
Section XI: Software Engineering......Page 2374
Chapter 101: Software Qualities and Principles......Page 2376
101.1 Classification of Software Qualities......Page 2377
101.2 Representative Software Qualities......Page 2378
101.2.1.2 Reliability......Page 2379
101.2.1.3 Robustness......Page 2380
101.2.2 Performance......Page 2381
101.2.4 Verifiability......Page 2382
101.2.6 Maintainability......Page 2383
101.2.7 Reusability......Page 2384
101.2.10 Interoperability......Page 2385
101.2.11 Productivity......Page 2386
101.2.13 Visibility......Page 2387
101.3 Quality Assurance......Page 2388
101.4.1 Rigor and Formality......Page 2389
101.4.2 Separation of Concerns......Page 2390
101.4.3 Modularity......Page 2392
101.4.4 Abstraction......Page 2393
101.4.5 Anticipation of Change......Page 2394
101.4.7 Incrementality......Page 2395
101.5.2 Separation of Concerns......Page 2396
101.5.4 Abstraction......Page 2397
101.5.5 Anticipation of Change......Page 2398
101.6 Summarizing Remarks......Page 2399
Defining Terms......Page 2400
Further Information......Page 2401
102.1 Introduction......Page 2402
102.2 Specification-Driven Models......Page 2403
102.3 Evolutionary Development Models......Page 2408
102.4.1 Incremental Development......Page 2411
102.4.2 The Spiral Model......Page 2413
102.6 The Cleanroom Process......Page 2415
102.7 Process Model Applicability......Page 2416
102.8 Research Issues and Summary......Page 2417
Defining Terms......Page 2418
References......Page 2419
Further Information......Page 2420
103.1 Introduction......Page 2421
103.2 The High-Tech Supermarket System......Page 2422
103.3.1 Top-Down and Bottom-Up Design......Page 2423
103.3.2 Data-Flow Diagrams......Page 2424
103.3.3 Entity-Relationship Diagrams......Page 2427
103.3.4 Finite-State Machines......Page 2428
103.4.1 Modules......Page 2429
103.4.2 Abstract Data Types......Page 2431
103.5 Mathematical and Analytical Design......Page 2432
103.5.1 Queueing Network Models......Page 2433
103.5.3 Simulation Models......Page 2434
Defining Terms......Page 2435
References......Page 2436
Further Information......Page 2437
104.1 Introduction......Page 2438
104.2 Object-Oriented Concepts and Terms......Page 2439
104.3 Choosing Classes......Page 2440
104.4 Inheritance: Motivation, Usage, and Costs......Page 2441
104.5 Categories of Classes and Design Flaws......Page 2443
104.6 The Unified Modeling Language......Page 2444
104.6.1 Use-Case Diagrams......Page 2445
104.6.2 The Class Diagram......Page 2446
104.6.3 Sequence Diagrams......Page 2447
104.7 Design Patterns......Page 2448
104.7.2 Pattern Catalogs......Page 2449
104.7.3 Design Patterns to Solve Design Problems......Page 2450
104.7.4 Using a Design Pattern......Page 2451
Defining Terms......Page 2452
References......Page 2453
Further Information......Page 2455
105.1 Introduction......Page 2456
105.2.1 Terminology......Page 2457
105.2.2 Model of Execution-Based Software Testing......Page 2459
105.3.2 Fault/Failure Model......Page 2461
105.3.3 Program Building Blocks......Page 2464
105.3.4.1 Structurally-Based Criterion......Page 2465
105.3.4.2 Control Flow-Based Criterion......Page 2466
105.3.4.3 Data Flow-Based Criterion......Page 2467
105.3.4.4 Fault-Based Criterion......Page 2469
105.3.4.6 Comparing Test Adequacy Criteria......Page 2472
105.3.5 Test Case Generation......Page 2474
105.3.6 Test Execution......Page 2478
105.3.7 Test Adequacy Evaluation......Page 2479
105.3.8 Regression Testing......Page 2480
105.3.8.2 Regression Test Prioritization......Page 2482
105.3.9 Recent Software Testing Innovations......Page 2484
105.3.9.1 Robustness Testing......Page 2485
105.3.9.2 Testing Spreadsheets......Page 2486
105.3.9.3 Database-Driven Application Testing......Page 2487
105.3.9.4 Testing Graphical User Interfaces......Page 2488
Defining Terms......Page 2490
References......Page 2492
Further Information......Page 2498
106.2 Underlying Principles......Page 2499
106.2.1 Formal Methods......Page 2500
106.3 Best Practices......Page 2501
106.3.1 Specification Languages......Page 2502
106.3.2 Modeling Systems......Page 2503
106.4 A Case Study......Page 2504
106.4.3 Generic Definitions......Page 2505
106.4.4 Abstract System State......Page 2506
106.4.5 Operations......Page 2508
106.4.6 Error Conditions......Page 2509
106.4.7 Status Operations......Page 2510
106.5 Technology Transfer and Research Issues......Page 2511
106.6 Glossary of Z Notation......Page 2512
Sets and Expressions......Page 2513
Functions......Page 2514
Bags......Page 2515
Generic Definition......Page 2516
Defining Terms......Page 2517
References......Page 2518
Further Information......Page 2522
107.2 Approaches to Verification......Page 2524
107.3 Verifying Specifications of Systems......Page 2525
107.3.2.1 Reachability Analysis......Page 2526
107.3.2.2 Model Checking......Page 2527
107.4.1 General Properties......Page 2530
107.4.2.1 Axioms and Rules of Inference......Page 2535
107.4.2.2 Verifying a Small Program......Page 2536
107.4.2.4.1 Arrays......Page 2538
107.4.2.4.2 Procedure Invocations......Page 2539
107.4.2.4.3 User-Defined Data Types......Page 2540
107.4.2.4.4 Verifying User-Level Programs......Page 2543
107.4.2.4.5 Verifying Implementation-Level Programs......Page 2544
107.5 Current Status......Page 2545
Defining Terms......Page 2546
References......Page 2547
Further Information......Page 2548
108.1 Development Strategies......Page 2550
108.1.1 The Linear Sequential Model......Page 2551
108.1.2 The Prototyping Model......Page 2552
108.1.3 The RAD Model......Page 2553
108.1.4 Evolutionary Software Process Models......Page 2554
108.1.4.1 The Incremental Model......Page 2555
108.1.4.2 The Spiral Model......Page 2556
108.1.4.3 The Component Assembly Model......Page 2557
108.1.4.4 The Concurrent Development Model......Page 2558
108.1.4.6 Fourth Generation Techniques......Page 2559
108.2 The Management Spectrum......Page 2560
108.2.3 The Process......Page 2561
108.3.3 Risk Analysis......Page 2563
108.3.4 Scheduling......Page 2564
108.4 Software Quality Assurance......Page 2566
Acknowledgment......Page 2567
Defining Terms......Page 2568
References......Page 2569
Further Information......Page 2570
109.1 Introduction......Page 2571
109.2 Underlying Principles......Page 2572
109.3 Describing Individual Software Architectures......Page 2573
109.4 Architecture Description Languages......Page 2574
109.5 Describing Architectural Styles......Page 2576
Defining Terms......Page 2583
References......Page 2584
Appendix: A Quick Introduction to Z Notation......Page 2585
110.1 Introduction......Page 2588
110.2.1.2 Domain-Independent Era (Early Software Development Methodology)......Page 2589
110.2.2 Generic vs. Specialized Development......Page 2590
110.2.3 The Context of Problem Solving in Specialized System Development......Page 2591
110.3.1 Pervasive Software Development......Page 2592
110.3.3.1 E-business Software Systems......Page 2594
110.3.3.1.2 Legacy Applications......Page 2595
110.3.3.3 Customizable Web Applications......Page 2596
110.3.4 Security-Driven Software Development......Page 2597
110.3.4.1 Security-Driven Requirements Analysis......Page 2598
110.3.4.2 Security-Driven Systems Design......Page 2600
110.4 Research Issues and Summary......Page 2601
References......Page 2602
Further Information......Page 2604
A.2 The Computing Research Association (CRA)......Page 2606
A.7 Special Interest Group on Computer Graphics (SIGGRAPH)......Page 2607
A.8 The Society for Industrial and Applied Mathematics (SIAM)......Page 2608
B.1 Preamble......Page 2609
B.2.3 Be Honest and Trustworthy......Page 2610
B.2.8 Honor Confidentiality......Page 2611
B.3.5 Give Comprehensive and Thorough Evaluations of Computer Systems and Their Impacts, Including Analysis of Possible Risks......Page 2612
B.4.1 Background Note......Page 2613
B.4.7 Create Opportunities for Members of the Organization to Learn the Principles and Limitations of Computer Systems......Page 2614
B.6 Acknowledgments......Page 2615
C.1 The International Organization for Standardization (ISO)......Page 2616
C.5 The American Standard Code for Information Interchange (ASCII)......Page 2617
C.7 Floating-Point Arithmetic......Page 2618
D.1 ADA......Page 2619
D.4 COBOL......Page 2620
D.9 Java......Page 2621
D.12 ML......Page 2622
D.17 PROLOG......Page 2623
D.20 X Windows......Page 2624