Hugendubel.info - Die B2B Online-Buchhandlung 

Merkliste
Die Merkliste ist leer.
Bitte warten - die Druckansicht der Seite wird vorbereitet.
Der Druckdialog öffnet sich, sobald die Seite vollständig geladen wurde.
Sollte die Druckvorschau unvollständig sein, bitte schliessen und "Erneut drucken" wählen.
E-BookPDF1 - PDF WatermarkE-Book
406 Seiten
Englisch
Springer Berlin Heidelbergerschienen am10.12.20102011
Algorithms specify the way computers process information and how they execute tasks. Many recent technological innovations and achievements rely on algorithmic ideas - they facilitate new applications in science, medicine, production, logistics, traffic, communi¬cation and entertainment. Efficient algorithms not only enable your personal computer to execute the newest generation of games with features unimaginable only a few years ago, they are also key to several recent scientific breakthroughs - for example, the sequencing of the human genome would not have been possible without the invention of new algorithmic ideas that speed up computations by several orders of magnitude. The greatest improvements in the area of algorithms rely on beautiful ideas for tackling computational tasks more efficiently. The problems solved are not restricted to arithmetic tasks in a narrow sense but often relate to exciting questions of nonmathematical flavor, such as: How can I find the exit out of a maze? How can I partition a treasure map so that the treasure can only be found if all parts of the map are recombined? How should I plan my trip to minimize cost? Solving these challenging problems requires logical reasoning, geometric and combinatorial imagination, and, last but not least, creativity - the skills needed for the design and analysis of algorithms. In this book we present some of the most beautiful algorithmic ideas in 41 articles written in colloquial, nontechnical language. Most of the articles arose out of an initiative among German-language universities to communicate the fascination of algorithms and computer science to high-school students. The book can be understood without any prior knowledge of algorithms and computing, and it will be an enlightening and fun read for students and interested adults.mehr
Verfügbare Formate
BuchGebunden
EUR117,69
E-BookPDF1 - PDF WatermarkE-Book
EUR106,99

Produkt

KlappentextAlgorithms specify the way computers process information and how they execute tasks. Many recent technological innovations and achievements rely on algorithmic ideas - they facilitate new applications in science, medicine, production, logistics, traffic, communi¬cation and entertainment. Efficient algorithms not only enable your personal computer to execute the newest generation of games with features unimaginable only a few years ago, they are also key to several recent scientific breakthroughs - for example, the sequencing of the human genome would not have been possible without the invention of new algorithmic ideas that speed up computations by several orders of magnitude. The greatest improvements in the area of algorithms rely on beautiful ideas for tackling computational tasks more efficiently. The problems solved are not restricted to arithmetic tasks in a narrow sense but often relate to exciting questions of nonmathematical flavor, such as: How can I find the exit out of a maze? How can I partition a treasure map so that the treasure can only be found if all parts of the map are recombined? How should I plan my trip to minimize cost? Solving these challenging problems requires logical reasoning, geometric and combinatorial imagination, and, last but not least, creativity - the skills needed for the design and analysis of algorithms. In this book we present some of the most beautiful algorithmic ideas in 41 articles written in colloquial, nontechnical language. Most of the articles arose out of an initiative among German-language universities to communicate the fascination of algorithms and computer science to high-school students. The book can be understood without any prior knowledge of algorithms and computing, and it will be an enlightening and fun read for students and interested adults.
Details
Weitere ISBN/GTIN9783642153280
ProduktartE-Book
EinbandartE-Book
FormatPDF
Format Hinweis1 - PDF Watermark
FormatE107
Erscheinungsjahr2010
Erscheinungsdatum10.12.2010
Auflage2011
Seiten406 Seiten
SpracheEnglisch
Dateigrösse12371 Kbytes
IllustrationenX, 406 p. 237 illus., 183 illus. in color.
Artikel-Nr.1038738
Rubriken
Genre9200

Inhalt/Kritik

Inhaltsverzeichnis
1;Preface;4
2;Contents;6
3;Part I Searching and Sorting;10
3.1;Overview;11
3.2;1 Binary Search;13
3.2.1;Sequential Search;14
3.2.2;Binary Search;14
3.2.3;Recursive Implementation;15
3.2.4;Number of Search Steps;16
3.2.5;Guessing Games;17
3.2.6;Further Reading;19
3.3;2 Insertion Sort;20
3.3.1;To Read on;23
3.4;3 Fast Sorting Algorithms;24
3.4.1;The Algorithms;25
3.4.2;Detailed Explanations About These Sorting Algorithms;26
3.4.3;Experimental Comparison of the Sorting Algorithms;27
3.4.4;Determining the Runtimes Theoretically;28
3.4.5;Implementation in Java;30
3.4.6;Further Reading and Experiments;32
3.5;4 Parallel Sorting - The Need for Speed;33
3.5.1;Sorting in Hardware: Comparators and Sorting Circuits;34
3.5.2;The Bitonic Sorting Circuit: Its Architecture;35
3.5.3;The Bitonic Sorting Circuit: Its Correctness and Running Time;37
3.5.4;Concluding Remarks;42
3.5.5;Further Reading;42
3.6;5 Topological Sorting - How Should I Begin to Complete My To Do List?;44
3.6.1;Further Applications;50
3.6.2;Additional Reading;50
3.7;6 Searching Texts - But Fast! The Boyer-Moore-Horspool Algorithm;51
3.7.1;The Naive Algorithm;51
3.7.2;The Boyer-Moore-Horspool Algorithm;55
3.7.3;Further Reading;59
3.8;7 Depth-First Search (Ariadne&Co.);61
3.8.1;Algorithmic Idea and Implementation;61
3.8.2;Applications;64
3.8.2.1;Example: Web Search;65
3.8.2.2;Example: Labyrinth Creation;67
3.8.2.3;Example: Television Shows;67
3.8.2.4;Example: Traffic Planning;69
3.8.3;Breadth-First Search;70
3.8.4;Further Reading;72
3.8.5;Acknowledgement;72
3.9;8 Pledge's Algorithm;73
3.9.1;Further Reading;78
3.9.2;Acknowledgement;79
3.10;9 Cycles in Graphs;80
3.10.1;Scenario 1;80
3.10.2;Scenario 2;81
3.10.2.1;Finding Cycles by Depth-First Search;82
3.10.2.2;Strongly Connected Components;85
3.10.2.3;Searching for Cycles with Breadth-First Search;88
3.10.2.4;Historical Notes;90
3.10.3;References;91
3.10.3.1;Acknowledgement;91
3.11;10 PageRank - What Is Really Relevant in the World-Wide Web?;92
3.11.1;Tourist Trails;93
3.11.2;Trails on the Web;94
3.11.3;Solutions;96
3.11.4;Conclusion;98
3.11.5;Further Reading;99
4;Part II Arithmetic and Encryption;100
4.1;Overview;101
4.2;11 Multiplication of Long Integers - Faster than Long Multiplication;103
4.2.1;The Addition of Long Numbers;104
4.2.2;Short Multiplication: A Number Times a Digit;104
4.2.3;The Analysis of Long Multiplication;105
4.2.4;Karatsuba's Method;106
4.2.4.1;Karatsuba's Method for 4-Digit Numbers;108
4.2.4.2;Karatsuba's Method for Numbers of Any Length;109
4.2.5;Summary;110
4.2.6;Further Reading;111
4.2.7;Acknowledgements;111
4.3;12 The Euclidean Algorithm;112
4.3.1;The Greatest Common Divisor;114
4.3.2;An Observation That Speeds up the Algorithm;115
4.3.2.1;Analysis;116
4.3.2.2;An Example;117
4.3.3;Further Reading;117
4.3.4;Acknowledgement;118
4.4;13 The Sieve of Eratosthenes - How Fast Can We Compute a Prime Number Table?;119
4.4.1;From the Idea to a Method;120
4.4.1.1;A Simple Idea;120
4.4.2;How Fast Is the Computation?;121
4.4.3;How Does the Algorithm Spend Its Time?;122
4.4.3.1;Do We Need Every i Value?;123
4.4.3.2;Can We Get Even Faster?;125
4.4.3.3;What Can We Learn from This Example?;127
4.4.4;Further Considerations;127
4.4.5;Further Reading;129
4.5;14 One-Way Functions. Mind the Trap - Escape Only for the Initiated;131
4.5.1;The Mirror Image of Multiplication: Factorization;131
4.5.2;One-Way Functions;133
4.5.3;A Practical Problem: Searching a Telephone Book;135
4.5.4;Security and Googles;138
4.5.5;Further Reading;138
4.6;15 The One-Time Pad Algorithm - The Simplest and Most Secure Way to Keep Secrets;140
4.6.1;Encrypting Messages;141
4.6.2;The Algorithm;143
4.6.3;Breaking the Code;144
4.6.4;Further Reading;145
4.7;16 Public-Key Cryptography;146
4.7.1;Public Keys;147
4.7.2;A Limited Algebra;148
4.7.2.1;Construction of the Keys;148
4.7.2.2;Encryption;149
4.7.2.3;Decryption;151
4.7.2.4;The Eavesdropper;151
4.7.2.5;Without Limited Mathematics;152
4.7.3;ElGamal's Method;152
4.7.3.1;Modular Multiplication and Modular Exponentiation;153
4.7.3.2;Description of ElGamal's Cryptosystem;155
4.7.3.3;Further Methods;156
4.7.4;Security;156
4.7.5;Further Reading;157
4.8;17 How to Share a Secret;158
4.8.1;A Simple Method to Share a Secret;159
4.8.2;General Secret Sharing;163
4.8.3;Secret Sharing, Information Theory and Cryptography;164
4.8.4;Further Reading;166
4.9;18 Playing Poker by Email;168
4.9.1;Dealing Cards by Snail Mail;168
4.9.1.1;How to Shuffle and Distribute the Cards;168
4.9.1.2;How to Bid;170
4.9.1.3;How to Replace Cards;170
4.9.1.4;The Showdown;171
4.9.1.5;How to Verify That No One Has Cheated;172
4.9.1.6;Discussion;172
4.9.2;Dealing Cards by Email;172
4.9.2.1;Electronic Envelopes;172
4.9.2.2;How to Shuffle the Cards and Distribute Them to Bob;173
4.9.2.3;One-Way Functions;173
4.9.2.4;How to Replace Cards;174
4.9.2.5;A Mathematical Description;175
4.9.2.6;Distribution of Cards to Both Players;175
4.9.2.7;Commitment to the Selected Coding Tables;176
4.9.2.8;Putting Cards into Envelopes;176
4.9.2.9;Distributing Cards to Alice;177
4.9.2.10;Distributing Cards to Bob;177
4.9.2.11;Dropping Cards;177
4.9.2.12;Properties of the Electronic Envelopes;177
4.9.2.13;How to Check Whether the Opponent Has Cheated;178
4.9.3;Poker with More than Two Players;178
4.9.4;Further Reading;178
4.10;19 Fingerprinting;180
4.10.1;How to Compare Long Texts over the Telephone;180
4.10.2;Texts as Sequences of Numbers and Modular Arithmetic;181
4.10.3;Fingerprints;183
4.10.4;Fingerprints with Random Numbers;185
4.10.5;The Protocol;188
4.10.6;Summary;190
4.10.7;Remarks on the Fingerprinting Theorem;190
4.10.8;Further Reading;192
4.10.9;Acknowledgement;192
4.11;20 Hashing;193
4.11.1;Message Digest;194
4.11.2;Secure Hashing;195
4.11.3;Hashing for Dictionaries;196
4.11.3.1;Storing a Data Item z with Key x;197
4.11.3.2;Searching a Data Item Corresponding to Key x;198
4.11.3.3;External Links and References;199
4.12;21 Codes - Protecting Data Against Errors and Loss;200
4.12.1;Introduction;200
4.12.1.1;Where Are Codes Used?;202
4.12.2;Reed-Solomon Codes;203
4.12.3;New Coding Techniques: Low-Density Parity-Check Codes;208
4.12.4;Network Codes;210
4.12.5;Places to Start Looking for More Information;213
4.12.6;Acknowledgement;214
5;Part III Planning, Coordination and Simulation;215
5.1;Overview;216
5.2;22 Broadcasting - How Can I Quickly Disseminate Information?;218
5.2.1;References;224
5.3;23 Converting Numbers into English Words;225
5.3.1;Stepwise Development of an Algorithm;226
5.3.1.1;Splitting Numbers into Three-Digit Groups ...;226
5.3.1.2;...and Generating the English Words;227
5.3.1.3;Function generateGroup;227
5.3.1.4;Function generateWeight;229
5.3.2;Lessons Learned;229
5.3.3;What to Read and Try out for Yourself;230
5.4;24 Majority - Who Gets Elected Class Rep?;232
5.4.1;Majority Algorithm;233
5.4.2;Correctness of the Majority Algorithm;236
5.4.3;How Many Comparisons Are Necessary?;236
5.4.4;Applications and Extensions;239
5.4.5;What Can We Learn from the Solutions to the Majority Problem?;240
5.4.6;Further Reading;240
5.5;25 Random Numbers - How Can We Create Randomness in Computers?;241
5.5.1;A Tactical Game: "Rock, Paper, Scissors";242
5.5.2;Means for the Generation of Random Numbers: Modular Arithmetic;242
5.5.3;Examples for Modular Arithmetic;243
5.5.4;Illustration of Modular Arithmetic;243
5.5.5;An Algorithm for the Generation of Pseudorandom Numbers;244
5.5.6;Periodic Behavior;245
5.5.7;Simulation of True Random Number Generators;245
5.5.8;The Algorithm for Rock, Paper, Scissors;245
5.5.9;Monte Carlo Simulation: Determination of Areas Using "Random Rain";248
5.5.10;Further Reading;250
5.6;26 Winning Strategies for a Matchstick Game;251
5.6.1;Learning from Small Examples;252
5.6.2;An Algorithm to Compute a Winning Strategy;253
5.6.2.1;The Running Time of the Algorithm;255
5.6.3;Extensions and Background;256
5.6.4;Further Reading;257
5.7;27 Scheduling of Tournaments or Sports Leagues;258
5.7.1;Generation of Schedules;259
5.7.2;Schedules with Home-Away Assignments;263
5.7.3;Further Reading;265
5.8;28 Eulerian Circuits;267
5.8.1;When Does an Eulerian Circuit Exist?;268
5.8.2;Finding Eulerian Circuits;269
5.8.3;The Algorithm;270
5.8.4;The House of Santa Claus;271
5.8.5;Of Postmen and Garbage Collectors;272
5.8.6;Further Reading;272
5.9;29 High-Speed Circles;274
5.9.1;Drawing Circles: Keep It Simple!;275
5.9.2;Bresenham's Algorithm for Circles;277
5.9.3;A Racing Duel;281
5.9.4;Further Reading;282
5.10;30 Gauß-Seidel Iterative Method for the Computation of Physical Problems;283
5.10.1;Warmup: Soccer;283
5.10.2;Temperature Calculation in a Rod (1D);285
5.10.3;Temperature Computation on a Plate (2D);287
5.10.4;Further Reading;291
5.11;31 Dynamic Programming - Evolutionary Distance;293
5.11.1;Mathematical Modeling;293
5.11.2;Calculation of the Evolutionary Distance;295
5.11.3;The Algorithm;296
5.11.4;Conclusion;298
5.11.5;References;299
6;Part IV Optimization;300
6.1;Overview;301
6.2;32 Shortest Paths;303
6.2.1;Dijkstra's Algorithm;305
6.2.2;FAQs and Further Reading;308
6.3;33 Minimum Spanning Trees (Sometimes Greed Pays Off ...);311
6.3.1;The Bridge Project of the Algos;312
6.3.2;Building Bridges After the Hurricane;313
6.3.3;The Algorithms of Prim and Kruskal;315
6.3.4;Further Reading;316
6.4;34 Maximum Flows - Towards the Stadium During Rush Hour;318
6.4.1;The Algorithm;320
6.4.1.1;Some Open Questions;327
6.4.2;Why Does It Work?;327
6.4.3;Epilogue;328
6.4.4;Solution;328
6.4.5;Further Reading;328
6.5;35 Marriage Broker;330
6.5.1;Problem;330
6.5.2;The Basic Principle of the Procedure;331
6.5.3;The Construction of a Maximum Matching;332
6.5.4;The Algorithm;336
6.5.5;The Marriage Theorem;337
6.5.6;Where Is the Marriage Theorem Needed by the Algorithm;338
6.5.7;Time Analysis;339
6.5.8;Further Reading;339
6.5.9;Acknowledgements;340
6.6;36 The Smallest Enclosing Circle - A Contribution to Democracy from Switzerland?;341
6.6.1;Why It Works;344
6.6.2;Further Reading;344
6.7;37 Online Algorithms - What Is It Worth to Know the Future?;345
6.7.1;The Ski Rental Problem;345
6.7.2;The Paging Problem;348
6.7.3;Further Reading;350
6.8;38 Bin Packing or "How Do I Get My Stuff into the Boxes?";351
6.8.1;The Online Problem "Moving Inexpensively";352
6.8.2;Analysis of the Algorithms;353
6.8.3;How Well Can Online Algorithms for Bin Packing Perform?;356
6.8.4;Further Reading;358
6.9;39 The Knapsack Problem;359
6.9.1;Pareto-Optimal Solutions;361
6.9.2;The Nemhauser-Ullmann Algorithm;363
6.9.3;Further Reading;365
6.10;40 The Travelling Salesman Problem;366
6.10.1;Introduction;366
6.10.2;The Brute-Force Method;367
6.10.3;Dynamic Programming;368
6.10.4;Approximative Solutions;370
6.10.5;MST Algorithm;371
6.10.6;Some Final Remarks;373
6.10.7;Further Reading;374
6.11;41 Simulated Annealing;375
6.11.1;What Is Simulated Annealing?;376
6.11.2;The Travelling Salesperson Problem;379
6.11.3;Further Applications;380
6.11.4;Further Reading;382
7;Author Details;383mehr

Autor