Algorithmic Adventures : From Knowledge to Magic

The ?rst and foremost goal of this lecture series was to show the beauty, depth and usefulness of the key ideas in computer science. While working on the lecture notes, we came to understand that one can recognize the true spirit of a scienti?c discipline only by viewing its contributions in the framework of science as a whole. We present computer science here as a fundamental science that, interacting with other scienti?c disciplines, changed and changes our view on the world, that contributes to our understanding of the fundamental concepts of science and that sheds new light on and brings new meaning to several of these concepts. We show that computer science is a discipline that discovers spectacular, unexpected facts, that ?nds ways out in seemingly unsolvable s- uations, and that can do true wonders. The message of this book is that computer science is a fascinating research area with a big impact on the real world, full of spectacular ideas and great ch- lenges. It is an integral part of science and engineering with an above-average dynamic over the last 30 years and a high degree of interdisciplinarity. The goal of this book is not typical for popular science writing, whichoftenrestrictsitselftooutliningtheimportanceofaresearch area. Whenever possible we strive to bring full understanding of the concepts and results presented. There is a considerable, satisfying and underappreciated depth in the science of computing, it offers so much more than simply a driving licence for using a computer. The author of this book is a top researcher working on the fundamentals of informatics, and he has considerable experience teaching complex subjects in a simple manner. In this book he invites the reader to explore the science of computing, convinced that a good explanation of even the most basic techniques can demonstrate the power and magic of the underlying principles. The author starts with the development of computer science, algorithms and programming, and then explains and shows how to exploit the concepts of infinity, computability, computational complexity, nondeterminism and randomness. Finally, he offers some insight into emerging computing paradigms such as biological computing and quantum computing. This book is a fascinating read for students of all levels, and for those curious to learn about the science and magic of algorithmics and its role in other scientific disciplines. Front Matter....Pages I-XIII A Short Story About the Development of Computer Science or Why Computer Science Is Not a Computer Driving Licence....Pages 1-35 Algorithmics, or What Have Programming and Baking in Common?....Pages 37-71 Infinity Is Not Equal to Infinity, or Why Infinity Is Infinitely Important in Computer Science....Pages 73-116 Limits of Computability or Why Do There Exist Tasks That Cannot Be Solved Automatically by Computers....Pages 117-159 Complexity Theory or What to Do When the Energy of the Universe Doesn’t Suffice for Performing a Computation?....Pages 161-199 Randomness in Nature and as a Source of Efficiency in Algorithmics....Pages 201-237 Cryptography, or How to Transform Drawbacks into Advantages....Pages 239-275 Computing with DNA Molecules, or Biological Computer Technology on the Horizon....Pages 277-298 Quantum Computers, or Computing in the Wonderland of Particles....Pages 299-324 How to Make Good Decisions for an Unknown Future or How to Foil an Adversary....Pages 325-358 Back Matter....Pages 359-363 "There is a considerable, satisfying and underappreciated depth in the science of computing, it offers so much more than simply a driving licence for using a computer. The author of this book is a top researcher working on the fundamentals of informatics, and he has considerable experience teaching complex subjects in a simple manner. In this book he invites the reader to explore the science of computing, convinced that a good explanation of even the most basic techniques can demonstrate the power and magic of the underlying principles. The author starts with the development of computer science, algorithms and programming, and then explains and shows how to exploit the concepts of infinity, computability, computational complexity, nondeterminism and randomness. Finally, he offers some insight into emerging computing paradigms such as biological computing and quantum computing."--Back cover