Algorithmic Adventures (eBook)

Preface 6
Contents 9
A Short Story About the Development of Computer Science or Why Computer Science Is Not a Computer Driving Licence 12
What Do We Discover Here? 12
Does the Building of Science Sit on Unsteady Fundamentals? 13
Origin of Computer Science as the End of Euphoria 30
The History of Computer Science and the Concept of This Book 35
Summary 44
Algorithmics, or What Have Programming and Baking in Common? 47
What Do We Find out Here? 47
Algorithmic Cooking 48
What About Computer Algorithms? 55
How Can the Execution of a Program Unintentionally Become a Never-Ending Story? 71
Summary or What We Have Learnt Here 79
Infinity Is Not Equal to Infinity, or Why Infinity Is Infinitely Important in Computer Science 82
Why Do We Need Infinity? 82
Cantor's Concept for Comparing the Sizes of Infinite Sets 86
There Are Different Infinite Sizes, or Why There Are More Real Numbers than Natural Ones 116
The Most Important Ideas Once Again 123
Limits of Computability or Why Do There Exist Tasks That Cannot Be Solved Automatically by Computers 126
Aim 126
How Many Programs Exist? 127
YES or NO, That Is the Question, or Another Application of Diagonalization 134
Reduction Method or How a Successful Method for Solving Problems Can Be Used to Get Negative Results 142
Summary of the Most Important Discoveries 164
Complexity Theory or What to Do When the Energy of the Universe Doesn't Suffice for Performing a Computation? 169
Introduction to Complexity Theory 169
How to Measure Computational Complexity? 171
Why Is the Complexity Measurement Useful? 177
Limits of Tractability 182
How Do We Recognize a Hard Problem? 186
Help, I Have a Hard Problem … 198
Summary 203
Randomness in Nature and as a Source of Efficiency in Algorithmics 208
Aims 208
What Is Randomness and Does There Exist True Randomness? 210
The Abundance of Witnesses Is Support in Shortage or Why Randomness Can Be Useful 217
What to Do When a Customer Requires a Very High Reliability? 235
What Are Our Main Discoveries Here? 241
Cryptography, or How to Transform Drawbacks into Advantages 245
A Magical Science of the Present Time 245
The Concept of Cryptosystems or a Few Impressions from the Prehistory of Cryptography 247
When Is a Cryptosystem Secure? 252
Symmetric Cryptosystems 255
How to Agree on a Secret in Public Gossip? 259
Public-Key Cryptosystems 266
Milestones of Our Expedition in the Wonderland of Cryptography 278
Computing with DNA Molecules, or Biological Computer Technology on the Horizon 282
The Story So Far 282
How to Transform a Chemical Lab into a DNA Computer 287
Adleman's Experiment, or a Biosearch for a Path 293
The Future of DNA Computing 301
Quantum Computers, or Computing in the Wonderland of Particles 304
Prehistory 304
A Short Walk in the Wonderland of Quantum Mechanics 307
How to Compute in the World of Particles? 314
The Future of Quantum Computing 325
How to Make Good Decisions for an Unknown Future or How to Foil an Adversary 330
What Do We Want to Discover Here? 330
Quality Measurement of Online Algorithms and a Game Against a Mean Adversary 332
A Randomized Online Strategy 343
Summary or How to Foil an Adversary 361
References 364
Index 365