Computer science and engineering handbook

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