Computer Science (eBook)

Computer Science 3
Contents 5
Contributors 9
Part I: 11
Chapter 1: Introduction and Prologue 12
Hardware Synopsis 15
Software Synopsis 17
Some General Remarks on the Nature of Computation 18
Reference 19
Chapter 2: Computation: Brief History Prior to the 1900s 20
Chapter 3: The Heart of Computer Science 26
The Decision Problem of Formalist Mathematics 27
The Turing Machine 30
The Turing Machine 31
The Universal Turing Machine. A Stored-Program Computer 34
A Program for a Universal Turing Machine 34
Other Models of Turing Machines 36
Unsolvable Computational Problems The Church-Turing Thesis37
Appendix 1 40
Symbolic Logic, Computer Science and the Godel Incompleteness Theorem 40
Propositional Logic and Boolean Algebra 41
Boolean Algebra and Circuits 44
Propositonal Logic and First-Order Predicate Logic 45
Additional Axioms of First-Order Predicate Logic 47
Peano´s Axioms 49
Beyond Computation. Formal Syntax and Informal Interpretation 52
Appendix 2 54
The Lambda Calculus 54
Syntax and Rules of Derivation of the Lambda Calculus 56
Turing´s Proof of the Unsolvability of the Decision Problem 60
Chapter4: The Software Side of Computer Science - Computer Programming 62
Appendix: The BNF Notation, Syntax of Programming Languages 67
Other Programming Languages 70
Parallel Computing Languages 71
Subroutines 72
A Footnote 73
Appendix: Java Applets, HTML and the Web 74
HTML 74
Applets 76
References 77
Part II: 78
Chapter 5: The Hardware Side 79
Appendix 1 87
Logic Circuits 87
Field Effect Transistor (FET) 89
The Metal Oxide Semiconductor Field-Effect Transistor (MOSFET) 90
Functional Model of an NPN Transistor 91
Darlington Pair Circuit 93
Using a Transistor as a Switch 94
Choosing a Suitable PNP Transistor 95
A Transistor Inverter (NOT Gate) Circuit 97
RS (Reset-Set) Flip-Flop 102
Appendix 2 103
Hardware for the User Interface 103
The Monitor as a Visual Output Display 103
Chapter6: Operating Systems (OS) 105
The OS Kernel and the Shell 107
File Systems 108
File Permission 110
Scheduling 111
Concluding Observations About OS´s 112
References 112
Chapter7: Computer Networks 113
The Internet 115
The Internet 115
Graphs of Networks 116
Graph Theory 117
The World Wide Web (The Web) 117
Protocols: The Technology of Network Transmission of Messages 118
Implementation of Computer Networks - The Ethernet 119
The ISO Open Systems Interconnection Model (OSI) 120
How the OSI Layers Work 121
Sockets 124
The Larger Contexts of Messages 124
Telephone and Data Transmission 125
Appendix 1 126
Sockets 126
Socket Send/Receive Functions 127
Blocking and Non-blocking Sockets 128
Creating a Client-Server Socket Pair under MPI Implementations 129
MPI Collective Communication 131
Appendix 2 132
Graph theory 132
Some Basics of Graph Theory 134
Random Graph Theory for General Degree Distributions 135
Random Subgraphs in a Given Host Graphs 137
PageRank and Local Partitioning 138
Network Games 141
Summary 142
References 142
References for Computer Networks: Sockets and MPI 145
Video-streaming 145
Chapter8: High Performance Computing and Communication (HPCC) 146
Introduction 146
The USC HPCC Center 148
The Clusters 148
Cluster Network Switch Fabrics 149
HPCC Disk Storage 151
Heat and Air Conditioning 152
Financing Clusters 153
OS and Applications Interface Software 153
HTC and HPC 154
Clouds 155
Some Conclusions 157
Appendix 158
Cloud Computing 158
Chapter9: Programming for Distributed Computing: From Physical to Logical Networks 161
Distributed and Parallel Programming 162
Levels of Parallelism 162
Tasks in Parallel Programming 163
Physical Computers and Networks 164
Concepts of Parallel Programming 164
Examples of API´s for Parallel Programs 165
Concurrent Programming Languages 167
A Brief Introduction to Erlang 168
Logical Networks 169
Service-Oriented Architectures: A Survey 170
Cloud Computing-A Survey and Critique 171
p2p Networks-a Survey and Critique 172
Conclusions 173
Reference 174
Chapter10: Databases 175
Introduction: Two Views of Database Research 175
The Relational Model 178
The Path to Relational Databases 178
A Tour of the Relational Paradigm 182
Abstraction 182
Declarative, Computationally Limited, Languages 183
Indexed Data Architecture 186
Algebraic Query Plans 187
Cost Estimation and Search 188
ACID Transactions 189
The Evaluation Pipeline of the Relational Paradigm 191
Core Database Research Sampler 193
Query Languages 193
Aggregation 193
Recursion 194
Stored Procedures 195
Logical Optimizations 196
Local Optimizations 197
Equivalence Rules 197
Unnesting Complex Queries 197
Global Optimizations: Static Analysis 198
Query Evaluation and Query Containment 199
Acyclic Queries 200
Query Minimization 201
Use of Static Analysis in DBMSs 202
Between Logical and Physical Optimizations: Views 202
Updates in Relational Databases 203
View Maintenance 204
View Update 205
Plan Generation 205
Cost Estimation and Histograms 206
The Cascades Optimizer 208
Data Indexing and Storage 208
Multidimensional Indexes 209
Column Stores 210
Stream Databases 210
Hardware and Why it Matters 211
SSDs vs Magnetic Hard Drives 212
Distributed Databases 213
Extending Database Functionality 215
Data Design 215
Advanced Data Definition 218
From Stored Data to Virtual Data 218
More Complex Virtual Databases 219
Integration vs. Extraction in Commercial Systems 220
More General Implicitly Specified Databases 220
Ontologies and Databases 221
New Models: Complex Objects 222
Nested Structures 223
Adding Support for Duplication 224
More Powerful Languages 225
Data Design for Nested Structures 225
Industrial Support and DBR for Complex Objects 226
XML and Tree-Structured Data 227
Conclusions 229
References 231
Chapter 11: Computer Security and Public Key Cryptography 236
Secure (Secret) Email 236
RSA Cryptosystems 238
RSA procedures for Encryption and Decryption 240
Finding Large Prime Numbers p and q 240
Signatures 241
The Diffie-Hellman Protocol 242
The El Gamal Public Key Cryptosystem System 242
Elliptic Curve Cryptography (ECC) 243
References 245
Chapter12: Complexity Theory 246
Introduction 246
Languages and Decision Problems 247
Models of Computation 247
Measures of Time Complexity 251
Time Complexity of Turing Machines 251
Simulating a Multitape Turing Machine with a Single-tape Turing Machine 252
Time Complexity of Nondeterministic Turing Machines 252
The Complexity Classes P and NP 253
The Complexity Class P 253
Examples of Problems in P 254
The Complexity Class NP 254
Examples of Problems in NP 255
NP-Completeness 256
Reducibility 257
The P Versus NP Question 258
Space Complexity 259
Space Complexity of Turing Machines 259
Sublinear Space Complexity Classes 259
The Class PSPACE 260
The Class EXPSPACE 261
NP-Optimization Problems 261
Brute-Force Algorithms 262
Heuristic Algorithms 262
Approximation Algorithms 262
Probabilistic Algorithms 263
Amplification 264
Does Randomness Help? 264
Interactive Proof Systems 264
The Class IP 265
Probabilistically Checkable Proofs 266
Locally Testable Proofs 267
PCP Verifiers 267
Constraint Satisfaction Problems 268
Relationships Among Complexity Classes 268
Time-Hierarchy Theorem 269
Space-Hierarchy Theorem 269
The Complexity Zoo 270
References 271
Chapter13: Multivariate Complexity Theory 273
Introduction 273
A Concrete Illustration 274
Parameterized Complexity: A Two-Dimensional Theory 276
Definition: Parameterized Language 278
Definition: FPT 278
Definition: XP 278
How to Parameterize? 279
The Multivariate Complexity Workflow 282
An Example of Principle 1: Enriching the Model 282
An Example of Principle 2: Deconstructing Hardness 283
A Parameterized Analog of the Cook/Levin Theorem 284
Definition: Parametric Transformation 284
Negative Toolkit - Induced Biclique Is Hard for W[1] 287
Positive Toolkit: FPT Techniques 288
Bounded Search Trees 288
Kernelization: Reduction to a Problem Kernel 289
Further Reading 291
Conclusions 294
References 294
Chapter14: Quantum Computing 298
Introduction to Quantum Computing 298
History of QM: Puzzles in the Classical World 299
Properties of Quantum Mechanics 299
Indeterminism 300
Interference 301
Uncertainty 301
Complementarity 301
Discrete Spectrum 302
Superposition 302
Entanglement 302
Quantum Information and Computation-A Prehistory 303
The Mathematical Structure of Quantum Theory 304
The Stern-Gerlach Experiment and Spin 304
Sequential Measurements 305
Complementarity and Randomness 306
The Mathematical Description of Spin 306
The Effect of Measurement 307
Global Phase 308
Evolution of the State 308
Systems of More than One Spin 310
Other Two-Level Systems 312
Quantum Information Processing 313
General Unitary Transformations 314
One-Bit Unitaries and Bloch Sphere Rotation 314
Building up Unitaries 314
Two-Qubit unitaries 315
Quantum Gates and Circuits 315
Quantum Algorithms 316
The Circuit Model 316
Boolean Circuits 316
Complexity Theory and Circuits 317
Quantum Circuits 318
Calculating Functions 320
Scratch Bits and Ancillas 321
Oracles 321
Quantum Parallelism 322
Deutsch´s Problem 324
Quantum Fourier Transform 325
Circuits for the Fourier Transform 326
Periodic States 327
Period Finding 328
Greatest Common Divisor 329
Order-Finding 329
Building a Quantum Algorithm 330
Order-Finding and Factoring 332
Searching an Unordered Database 333
The Grover Algorithm 333
Number of Iterations 334
Building the Circuit 336
Applications 336
Decoherence and Error Correction 337
Decoherence 337
Quantum Error Correction 338
Fault-Tolerance and Threshold Theorems 340
Physical Implementations of Quantum Computers 341
Physical Requirements for Quantum Computation 341
Ion Traps 342
Qubits 342
Quantum Gates 343
Measurement 344
Decoherence 344
Recent Developments 345
Performance 345
Superconducting Qubits 346
LC Circuits 346
Josephson Junctions and Superconducting Qubits 346
Quantum Gates 347
Measurement 348
Decoherence 348
State of the Art 348
Other Systems 349
Further Topics 349
Reference 350
Chapter 15: Numerical Thinking in Algorithm Design and Analysis 351
Numerical Thinking 351
Smoothed Analysis of Algorithms 352
The Laplacian Paradigm 352
Acknowledgements 353
Algorithm Design and Analysis with Perturbations 353
Smoothed Analysis 355
How to Model Real Data and How to Measure Practical Performance? 356
Smoothed Complexity 358
Smoothed Analysis of the Simplex Algorithm 360
A Key Perturbation Lemma 360
Smoothed Complexity of the Shadow-Vertex Method 360
Other Examples of Smoothed Analysis 361
Perturbation-Based Algorithm Design 362
Well-Shaped Mesh Generation 363
Problem Statement 363
A Key Perturbation Lemma of Weighted Points 363
Perturbation-Based Algorithms and Extensions 364
Polynomial-Time Simplex Algorithm 365
Problem Statement 365
A Key Perturbation Lemma of Polytopes 365
Perturbation-Based Simplex Algorithm 366
Robust Gaussian Elimination 367
Problem Statement 367
A Perturbation Lemma 367
A Robust Algorithm for Linear System 368
Other Algorithmic Applications of Smoothed Analysis 369
Smoothed Complexity Versus Approximation Complexity 369
The Laplacian Paradigm: Emerging Algorithms for Massive Graphs 370
Nearly-Linear Time Laplacian Primitive 371
The Laplacian Primitive and its Solver 371
A Suite of Nearly-Linear-Time Spectral Algorithms 372
Clustering and Partitioning 372
Spectral Graph Sparsification 373
Low Stretch Spanning Trees 374
The Laplacian Paradigm for Massive Graphs 375
Massive Data and Efficient Algorithm Design 375
The Laplacian Paradigm 376
Example I: Spectral Approximation 376
Example II: Learning from Labeled Data on a Directed Graph 377
Example III: Faster Maximum Flow Approximation 378
Other Applications of the Laplacian Paradigm 379
Next Generation Algorithms for Massive Graphs 380
Not Just Numerical Analysis 381
References 382
Chapter 16: Fuzzy Logic in Computer Science 387
What Is Fuzzy Logic? 387
Motivation 387
Graded Approach 388
Controversies 389
Fuzzy Logic and Probability 390
Various Meanings of ``Fuzzy Logic´´ 392
Basic Concepts of Fuzzy Logic 392
Truth Degrees and Truth Functions of Logical Connectives 392
Fuzzy Sets and Fuzzy Relations 394
Fuzzy Logic as Logic 396
Fuzzy Logic as Many-Valued Logic 396
Ordinary-Style Calculi 397
Graded-Style (Pavelka-Style) Calculi 398
Fuzzy Logic in a Broad Sense 398
Fuzzy Logic and Control 399
Mamdani-Assilian Controller 400
Takagi-Sugeno Controller 403
Approximate Reasoning 403
Success of Mamdani Control in Automobile Industry 405
Engine Idle Speed Control 406
Flowing Shift-Point Determination 409
Fuzzy Logic and Knowledge Discovery in Databases 410
Fuzzy Clustering 411
Fuzzy Rule Generation 414
Transfer Passenger Analysis Based on FCM 416
References 418
Chapter17: Statistics of the Field* 422
Statistics Part 1: Education 424
Production of Ph.D. Degrees in Computer Science 424
Women Earning Degrees in Computer Science 426
Minorities Earning Degrees in Computer Science 426
Foreign Students Earning Degrees in Computer Science 428
Curriculum 431
Science, Technology, Engineering, and Mathematics (STEM) 433
Statistics Part 2: Publishing 436
Productivity 436
Coauthorship 438
Peer Review 439
Impact Factor and H Factor 439
Blogs 441
Digital Archives, Libraries, and Bibiliographies 441
Dictionaries, Encyclopedias and Tutorials 443
Statistics Part 3: Funding 444
Federal and State Funding 444
UNESCO Science Report 2010 448
Private Funding for Computer Science 449
Statistics Part 4: Employment 450
Employment by Specialty 452
Foreign-Born SandE Academics 455
Computing in Industry 455
Prestige of the Occupation of ``Scientist´´ 457
Computer Science Job Prospects in 2010 458
Off-Shoring 459
The U.S. National Laboratories as Employers of CS Researchers 460
Statistics Part 5: Professional Associations 463
Conclusion 466
Epilogue 468