Vocking B., Alt H., Dietzfelbinger M., Reischuk R., Scheideler C., Vollmer H., Wagner D. Algorithms Unplugged
Подождите немного. Документ загружается.
400 Peter Rossmanith
Fig. 41.5. The exercise sheets come out of the printing machine. The edges are not
aligned. The paper jogger shakes them, and in the end we get a perfectly aligned
stack of paper
Further Reading
Simulated annealing was presented in this chapter in a simplified way. Al-
though you can achieve good results by using the method as presented, there
are many details whose observance leads to much better results. The en-
try on simulated annealing in Wikipedia is a good starting point to learn
more (http://en.wikipedia.org/wiki/Simulated
annealing). Textbooks
on simulated annealing quite often are too specialized for the casual reader. To
learn more you can consult a book that contains, besides simulated annealing,
other interesting methods for the solution of hard problems:
Juraj Hromkoviˇc. Algorithmics for Hard Problems (Introduction to Combina-
torial Optimization, Randomization, Approximation, and Heuristics). Springer,
Heidelberg, 2nd edition, 2002.
You can also find many applets on the Internet for the interactive demon-
stration of simulated annealing. Just look for them using a search engine.
Author Details
Susanne Albers, Institut f¨ur Informatik, Humboldt-Universit¨at zu Berlin,
Germany [Chap. 37, Online Algorithms]
Helmut Alt, Institut f¨ur Informatik, Freie Universit¨at Berlin, Germany
[Chap. 3, Fast Sorting Algorithms; Overview of Part III, Planning, Coor-
dination and Simulation]
Michael Behrisch, Institut f¨ur Informatik, Humboldt-Universit¨at zu Berlin,
Germany [Chap. 28, Eulerian Circuits]
Rene Beier, Max-Planck-Institut f¨ur Informatik, Saarbr¨ucken, Germany
[Chap. 39, The Knapsack Problem]
Johannes Bl¨omer, Institut f¨ur Informatik, Universit¨at Paderborn, Ger-
many [Chap. 17, How to Share a Secret]
Norbert Blum, Institut f¨ur Informatik V, Rheinische Friedrich-Wilhelms-
Universit¨at Bonn, Germany [Chap. 31, Dynamic Programming – Evolutionary
Distance]
Dirk Bongartz, Gymnasium St. Wolfhelm, Schwalmtal, Germany [Chap. 16,
Public-Key Cryptography]
Ulrik Brandes, Fachbereich Informatik & Informationswissenschaft, Uni-
versit¨at Konstanz, Germany [Chap. 10, PageRank – What Is Really Relevant
in the World-Wide Web]
Volker Claus, Institut f¨ur Formale Methoden der Informatik, Universit¨at
Stuttgart, Germany [Chap. 35, Marriage Broker]
Amin Coja-Oghlan, Mathematics and Computer Science, University of
Warwick, UK [Chap. 28, Eulerian Circuits]
B. V¨ocking et al. (eds.), Algorithms Unplugged,
DOI 10.1007/978-3-642-15328-0,
c
Springer-Verlag Berlin Heidelberg 2011
402 Author Details
Volker Diekert, Institut f¨ur Formale Methoden der Informatik, Universit¨at
Stuttgart, Germany [Chap. 35, Marriage Broker]
Martin Dietzfelbinger, Institut f¨ur Theoretische Informatik, Fakult¨at f¨ur
Informatik und Automatisierung, Technische Universit¨at Ilmenau, Germany
[Chap. 19, Fingerprinting; Overview of Part I (Searching and Sorting)]
Michael Dom, Lehrstuhl Theoretische Informatik I, Friedrich-Schiller-Uni-
versit¨at Jena, Germany [Chap. 7, Depth-First Search (Ariadne & Co.)]
Gabi Dorfm¨uller, Fachbereich Informatik & Informationswissenschaft, Uni-
versit¨at Konstanz, Germany [Chap. 10, PageRank – What Is Really Relevant
in the World-Wide Web]
Arno Eigenwillig, Max-Planck-Institut f¨ur Informatik, Saarbr¨ucken, Ger-
many; now at Google, Z¨urich, Switzerland [Chap. 11, Multiplication of Long
Integers – Faster than Long Multiplication]
Friedrich Eisenbrand, Chair of Discrete Optimization, EPFL, Lausanne,
Switzerland [Chap. 12, The Euclidean Algorithm]
Jost Enderle, Lehrstuhl f¨ur Informatik 9 (Datenmanagement und -explor-
ation), RWTH Aachen University, Germany [Chap. 1, Binary Search]
Thomas Erlebach, Dept. of Computer Science, University of Leicester, UK
[Chap. 24, Majority – Who Gets Elected Class Rep?]
Christoph Freundl, Lehrstuhl f¨ur Informatik 10 (Systemsimulation),
Friedrich-Alexander-Universit¨at Erlangen-N¨urnberg, Germany [Chap. 30,
Gauß–Seidel Iterative Method for the Computation of Physical Problems]
Joachim Gehweiler, Heinz Nixdorf Institut und Institut f¨ur Informatik,
Universit¨at Paderborn, Germany [Chap. 38, Bin Packing or “How Do I Get
My Stuff into the Boxes?”]
Robert G¨orke, Institut f¨ur Theoretische Informatik, Karlsruher Institut f¨ur
Technologie (KIT), Germany [Chap. 34, Maximum Flows – Towards the Sta-
dium During Rush Hour]
Markus Hinkelmann, Institut f¨ur Theoretische Informatik, Universit¨at zu
L¨ubeck, Germany [Chap. 14, One-Way Functions. Mind the Trap – Escape
Only for the Initiated]
Hagen H¨opfner, Mobile Medien, Fakult¨at Medien, Bauhaus-Universit¨at
Weimar, Germany [Chap. 5, Topological Sorting – How Should I Begin to
Complete My To Do List?]
Author Details 403
Falk H ¨uffner, Institut f¨ur Informatik, Humboldt-Universit¨at zu Berlin, Ger-
many [Chap. 7, Depth-First Search (Ariadne & Co.)]
Tim Jonischkat, Institut f¨ur Informatik und Wirtschaftsinformatik, Uni-
versit¨at Duisburg-Essen, Germany [Chap. 25, Random Numbers – How Can
We Create Randomness in Computers?]
Tom Kamphans, Institut f¨ur Betriebssysteme und Rechnerverbund (IBR),
Technische Universit¨at Braunschweig, Germany [Chap. 8, Pledge’s Algorithm]
Rolf Klein, Lehrstuhl f¨ur Informatik I, Rheinische Friedrich-Wilhelms-Uni-
versit¨at Bonn, Germany [Chap. 8, Pledge’s Algorithm]
Sigrid Knust, Institut f¨ur Informatik, Universit¨at Osnabr¨uck, Germany
[Chap. 27, Scheduling of Tournaments or Sports Leagues]
Leif Kobbelt, Lehrstuhl f¨ur Informatik 8 (Computergraphik und Multime-
dia), RWTH Aachen University, Germany [Chap. 29, High-Speed Circles]
Jochen K¨onemann, Dept. of Combinatorics and Optimization, University
of Waterloo, Canada [Chap. 26, Winning Strategies for a Matchstick Game]
Wolfgang P. Kowalk, Dept. f¨ur Informatik (Rechnernetze), Carl-von-Os-
sietzky-Universit¨at Oldenburg, Germany [Chap. 2, Insertion Sort]
Matthias Kretschmer, Institut f¨ur Informatik V, Rheinische Friedrich-
Wilhelms-Universit¨at Bonn, Germany [Chap. 31, Dynamic Programming –
Evolutionary Distance]
Peter Liske, Institut f¨ur Informatik, Humboldt-Universit¨at zu Berlin, Ger-
many [Chap. 28, Eulerian Circuits]
Steffen Mecke, Institut f¨ur Theoretische Informatik, Karlsruher Institut f¨ur
Technologie (KIT), Germany [Chap. 34, Maximum Flows – Towards the Sta-
dium During Rush Hour]
Kurt Mehlhorn, Algorithmen und Komplexit¨at, Max-Planck-Institut f¨ur
Informatik, Saarbr¨ucken, Germany [Chap. 11, Multiplication of Long Integers
– Faster than Long Multiplication]
Friedhelm Meyer auf der Heide, Heinz Nixdorf Institut und Institut f¨ur
Informatik, Universit¨at Paderborn, Germany [Chap. 38, Bin Packing or “How
Do I Get My Stuff into the Boxes?”]
Michael Mitzenmacher, School of Engineering and Applied Sciences, Har-
vard University, USA [Chap. 21, Codes – Protecting Data Against Errors and
Loss]
404 Author Details
Rolf M¨ohring, Institut f¨ur Mathematik, Technische Universit¨at Berlin, Ger-
many [Chap. 13, The Sieve of Eratosthenes – How Fast Can We Compute a
Prime Number Table?]
Bruno M¨uller-Clostermann, Lehrstuhl f¨ur Praktische Informatik (Sys-
temmodellierung), Institut f¨ur Informatik und Wirtschaftsinformatik, Uni-
versit¨at Duisburg-Essen, Germany [Chap. 25, Random Numbers – How Can
We Create Randomness in Computers?]
Stefan N¨aher, Fachbereich IV – Informatik, Universit¨at Trier, Germany
[Chap. 40, The Travelling Salesman Problem]
Markus E. Nebel, Fachbereich Informatik, AG Algorithmen und Kom-
plexit¨at, TU Kaiserslautern, Germany [Chap. 6, Searching Texts – But Fast!
The Boyer–Moore–Horspool Algorithm]
Rolf Niedermeier, Institut f¨ur Softwaretechnik und Theoretische Infor-
matik, Technische Universit¨at Berlin, Germany [Chap. 7, Depth-First Search
(Ariadne & Co.)]
Martin Oellrich, Fachbereich II – Mathematik, Physik, Chemie, Beuth
Hochschule f¨ur Technik Berlin, Germany [Chap. 13, The Sieve of Eratosthenes
–HowFastCanWeComputeaPrimeNumberTable?]
Holger Petersen, Institut f¨ur Formale Methoden der Informatik, Univer-
sit¨at Stuttgart, Germany [Chap. 35, Marriage Broker]
R¨udiger Reischuk, Institut f¨ur Theoretische Informatik, Universit¨at zu
L¨ubeck, Germany [Chap. 14, One-Way Functions. Mind the Trap – Escape
Only for the Initiated; Overview of Part III, Planning, Coordination and Sim-
ulation]
Peter Rossmanith, Lehr- und Forschungsgebiet Theoretische Informatik,
RWTH Aachen University, Germany [Chap. 41, Simulated Annealing]
Ulrich R¨ude, Lehrstuhl f¨ur Informatik 10 (Systemsimulation), Friedrich-
Alexander-Universit¨at Erlangen-N¨urnberg, Germany [Chap. 30, Gauß–Seidel
Iterative Method for the Computation of Physical Problems]
Peter Sanders, Institut f¨ur Theoretische Informatik, Karlsruher Institut f¨ur
Technologie, Germany [Chap. 32, Shortest Paths]
Christian Scheideler, Institut f¨ur Informatik, Universit¨at Paderborn, Ger-
many [Chap. 22, Broadcasting – How Can I Quickly Disseminate Informa-
tion?; Overview of Part I, Searching and Sorting]
Christian Schindelhauer, Rechnernetze und Telematik, Institut f¨ur Infor-
matik, Albert-Ludwigs-Universit¨at Freiburg, Germany [Chap. 20, Hashing]
Author Details 405
Holger Schlingloff, Institut f¨ur Informatik, Humboldt-Universit¨at zu Berlin,
Germany [Chap. 9, Cycles in Graphs]
Swen Schmelzer, Lehrstuhl f¨ur Informations- und Kodierungstheorie,
Albert-Ludwigs-Universit¨at Freiburg, Germany [Chap. 37, Online Algorithms]
Lothar Schmitz, Institut f¨ur Softwaretechnologie, Fakult¨at f¨ur Informatik,
UniBw M¨unchen, Germany [Chap. 23, Converting Numbers into English
Words]
Thomas Seidl, Lehrstuhl f¨ur Informatik 9 (Datenmanagement und -explor-
ation), RWTH Aachen University, Germany [Chap. 1, Binary Search]
Dominik Sibbing, Lehrstuhl f¨ur Informatik 8 (Computergraphik und Mul-
timedia), RWTH Aachen University, Germany [Chap. 29, High-Speed Circles]
Detlef Sieling, Lehrstuhl Informatik 2 (Effiziente Algorithmen und Kom-
plexit¨atstheorie), Technische Universit¨at Dortmund, Germany [Chap. 18,
Playing Poker by Email]
Johannes Singler, Institut f¨ur Theoretische Informatik, Karlsruher Institut
f¨ur Technologie, Germany [Chap. 32, Shortest Paths]
Katharina Skutella, Institut f¨ur Mathematik, Technische Universit¨at
Berlin, Germany [Chap. 33, Minimum Spanning Trees]
Martin Skutella, Institut f¨ur Mathematik, Technische Universit¨at Berlin,
Germany [Chap. 33, Minimum Spanning Trees]
Till Tantau, Institut f¨ur Theoretische Informatik, Universit¨at zu L¨ubeck,
Germany [Chap. 15, The One-Time Pad Algorithm – The Simplest and Most
Secure Way to Keep Secrets]
Walter Unger, Lehrstuhl f¨ur Informatik 1, Algorithmen und Komplexit¨at,
RWTH Aachen University, Germany [Chap. 16, Public-Key Cryptography]
Berthold V¨ocking, Lehrstuhl f¨ur Informatik 1, Algorithmen und Kom-
plexit¨at, RWTH Aachen University, Germany [Chap. 39, The Knapsack Prob-
lem; Overview of Part II, Arithmetic and Encryption]
Heribert Vollmer, Institut f¨ur Theoretische Informatik, Leibniz Universit¨at
Hannover, Germany [Overview of Part IV, Optimization]
Dorothea Wagner, Institut f¨ur Theoretische Informatik, Karlsruher Insti-
tut f¨ur Technologie (KIT), Germany [Chap. 34, Maximum Flows – Towards
the Stadium During Rush Hour; Overview of Part IV, Optimization]
406 Author Details
Rolf Wanka, Lehrstuhl f¨ur Informatik 12 (Hardware-Software-Co-Design),
Universit¨at Erlangen-N¨urnberg, Germany [Chap. 4, Parallel Sorting – The
Need for Speed]
Emo Welzl, Institut f¨ur Theoretische Informatik, ETH Z¨urich, Switzerland
[Chap. 36, The Smallest Enclosing Circle – A Contribution to Democracy
from Switzerland?]