Optimization Algorithms in Physics

The past few years have witnessed a substantial growth in the number of applications for optimization algorithms in solving problems in the field of physics. Examples include determining the structure of molecules, estimating the parameters of interacting galaxies, the ground states of electronic quantum systems, the behavior of disordered magnetic materials, and phase transitions in combinatorial optimization problems. This book serves as an introduction to the field, while also presenting a complete overview of modern algorithms. The authors begin with the relevant foundations from computer science, graph theory and statistical physics, before moving on to thoroughly explain algorithms - backed by illustrative examples. They include pertinent mathematical transformations, which in turn are used to make the physical problems tractable with methods from combinatorial optimization. Throughout, a number of interesting results are shown for all physical examples. The final chapter provides numerous practical hints on software development, testing programs, and evaluating the results of computer experiments. Straff und doch leicht verständlich kommt diese Einführung daher. Anders als der Titel zunächst annehmen lässt, ist dieses Werk durchaus als Einführung in die Computerphysik geeignet. Es gibt einen auf das Wesentliche reduzierten Überblick über die heute wichtigen Themen der computerorientierten Physik. Die einfachen Beispiele und der Pseudocode ermöglichen die rasche Umsetzung der vorgestellten Konzepte. Optimierung, Percoaltion, Monte Carlo usw. - die Verfahren und Algorithmen lassen sich nicht nur in der Physik, sondern auch in vielen anderen Bereichen, wie etwa der Bioinformatik (z.B. Sequenzalignment) anwenden. Alles in Allem ein leicht verständliches Buch, für den angehenden Computerphysiker unbedingt zu empfehlen. Cover......Page 1 Preface......Page 6 Contents......Page 8 Ch1 Introduction to Optimization......Page 12 Ch2 Complexity Theory......Page 20 Ch3 Graphs......Page 48 Ch4 Simple Graph Algorithms......Page 64 Ch5 Introduction to Statistical Physics......Page 84 Ch6 Maximum-Flow Methods......Page 102 Ch7 Minimum-Cost Flows......Page 140 Ch8 Generic Algorithms......Page 170 Ch9 Approximation Methods for Spin Glasses......Page 196 Ch10 Matchings......Page 238 Ch11 Monte Carlo Methods......Page 266 Ch12 Branch-&-Bound Methods......Page 284 Ch13 Practical Issues......Page 304 Index......Page 370