Suchen und Finden
Service
Algorithms Unplugged
Berthold Vöcking, Helmut Alt, Martin Dietzfelbinger, Rüdiger Reischuk, Christian Scheideler, Heriber
Verlag Springer-Verlag, 2010
ISBN 9783642153280 , 406 Seiten
Format PDF
Kopierschutz Wasserzeichen
Geräte
Preface
4
Contents
6
Part I Searching and Sorting
10
Overview
11
1 Binary Search
13
Sequential Search
14
Binary Search
14
Recursive Implementation
15
Number of Search Steps
16
Guessing Games
17
Further Reading
19
2 Insertion Sort
20
To Read on
23
3 Fast Sorting Algorithms
24
The Algorithms
25
Detailed Explanations About These Sorting Algorithms
26
Experimental Comparison of the Sorting Algorithms
27
Determining the Runtimes Theoretically
28
Implementation in Java
30
Further Reading and Experiments
32
4 Parallel Sorting - The Need for Speed
33
Sorting in Hardware: Comparators and Sorting Circuits
34
The Bitonic Sorting Circuit: Its Architecture
35
The Bitonic Sorting Circuit: Its Correctness and Running Time
37
Concluding Remarks
42
Further Reading
42
5 Topological Sorting - How Should I Begin to Complete My To Do List?
44
Further Applications
50
Additional Reading
50
6 Searching Texts - But Fast! The Boyer-Moore-Horspool Algorithm
51
The Naive Algorithm
51
The Boyer-Moore-Horspool Algorithm
55
Further Reading
59
7 Depth-First Search (Ariadne&Co.)
61
Algorithmic Idea and Implementation
61
Applications
64
Example: Web Search
65
Example: Labyrinth Creation
67
Example: Television Shows
67
Example: Traffic Planning
69
Breadth-First Search
70
Further Reading
72
Acknowledgement
72
8 Pledge's Algorithm
73
Further Reading
78
Acknowledgement
79
9 Cycles in Graphs
80
Scenario 1
80
Scenario 2
81
Finding Cycles by Depth-First Search
82
Strongly Connected Components
85
Searching for Cycles with Breadth-First Search
88
Historical Notes
90
References
91
Acknowledgement
91
10 PageRank - What Is Really Relevant in the World-Wide Web?
92
Tourist Trails
93
Trails on the Web
94
Solutions
96
Conclusion
98
Further Reading
99
Part II Arithmetic and Encryption
100
Overview
101
11 Multiplication of Long Integers - Faster than Long Multiplication
103
The Addition of Long Numbers
104
Short Multiplication: A Number Times a Digit
104
The Analysis of Long Multiplication
105
Karatsuba's Method
106
Karatsuba's Method for 4-Digit Numbers
108
Karatsuba's Method for Numbers of Any Length
109
Summary
110
Further Reading
111
Acknowledgements
111
12 The Euclidean Algorithm
112
The Greatest Common Divisor
114
An Observation That Speeds up the Algorithm
115
Analysis
116
An Example
117
Further Reading
117
Acknowledgement
118
13 The Sieve of Eratosthenes - How Fast Can We Compute a Prime Number Table?
119
From the Idea to a Method
120
A Simple Idea
120
How Fast Is the Computation?
121
How Does the Algorithm Spend Its Time?
122
Do We Need Every i Value?
123
Can We Get Even Faster?
125
What Can We Learn from This Example?
127
Further Considerations
127
Further Reading
129
14 One-Way Functions. Mind the Trap - Escape Only for the Initiated
131
The Mirror Image of Multiplication: Factorization
131
One-Way Functions
133
A Practical Problem: Searching a Telephone Book
135
Security and Googles
138
Further Reading
138
15 The One-Time Pad Algorithm - The Simplest and Most Secure Way to Keep Secrets
140
Encrypting Messages
141
The Algorithm
143
Breaking the Code
144
Further Reading
145
16 Public-Key Cryptography
146
Public Keys
147
A Limited Algebra
148
Construction of the Keys
148
Encryption
149
Decryption
151
The Eavesdropper
151
Without Limited Mathematics
152
ElGamal's Method
152
Modular Multiplication and Modular Exponentiation
153
Description of ElGamal's Cryptosystem
155
Further Methods
156
Security
156
Further Reading
157
17 How to Share a Secret
158
A Simple Method to Share a Secret
159
General Secret Sharing
163
Secret Sharing, Information Theory and Cryptography
164
Further Reading
166
18 Playing Poker by Email
168
Dealing Cards by Snail Mail
168
How to Shuffle and Distribute the Cards
168
How to Bid
170
How to Replace Cards
170
The Showdown
171
How to Verify That No One Has Cheated
172
Discussion
172
Dealing Cards by Email
172
Electronic Envelopes
172
How to Shuffle the Cards and Distribute Them to Bob
173
One-Way Functions
173
How to Replace Cards
174
A Mathematical Description
175
Distribution of Cards to Both Players
175
Commitment to the Selected Coding Tables
176
Putting Cards into Envelopes
176
Distributing Cards to Alice
177
Distributing Cards to Bob
177
Dropping Cards
177
Properties of the Electronic Envelopes
177
How to Check Whether the Opponent Has Cheated
178
Poker with More than Two Players
178
Further Reading
178
19 Fingerprinting
180
How to Compare Long Texts over the Telephone
180
Texts as Sequences of Numbers and Modular Arithmetic
181
Fingerprints
183
Fingerprints with Random Numbers
185
The Protocol
188
Summary
190
Remarks on the Fingerprinting Theorem
190
Further Reading
192
Acknowledgement
192
20 Hashing
193
Message Digest
194
Secure Hashing
195
Hashing for Dictionaries
196
Storing a Data Item z with Key x
197
Searching a Data Item Corresponding to Key x
198
External Links and References
199
21 Codes - Protecting Data Against Errors and Loss
200
Introduction
200
Where Are Codes Used?
202
Reed-Solomon Codes
203
New Coding Techniques: Low-Density Parity-Check Codes
208
Network Codes
210
Places to Start Looking for More Information
213
Acknowledgement
214
Part III Planning, Coordination and Simulation
215
Overview
216
22 Broadcasting - How Can I Quickly Disseminate Information?
218
References
224
23 Converting Numbers into English Words
225
Stepwise Development of an Algorithm
226
Splitting Numbers into Three-Digit Groups …
226
…and Generating the English Words
227
Function generateGroup
227
Function generateWeight
229
Lessons Learned
229
What to Read and Try out for Yourself
230
24 Majority - Who Gets Elected Class Rep?
232
Majority Algorithm
233
Correctness of the Majority Algorithm
236
How Many Comparisons Are Necessary?
236
Applications and Extensions
239
What Can We Learn from the Solutions to the Majority Problem?
240
Further Reading
240
25 Random Numbers - How Can We Create Randomness in Computers?
241
A Tactical Game: "Rock, Paper, Scissors"
242
Means for the Generation of Random Numbers: Modular Arithmetic
242
Examples for Modular Arithmetic
243
Illustration of Modular Arithmetic
243
An Algorithm for the Generation of Pseudorandom Numbers
244
Periodic Behavior
245
Simulation of True Random Number Generators
245
The Algorithm for Rock, Paper, Scissors
245
Monte Carlo Simulation: Determination of Areas Using "Random Rain"
248
Further Reading
250
26 Winning Strategies for a Matchstick Game
251
Learning from Small Examples
252
An Algorithm to Compute a Winning Strategy
253
The Running Time of the Algorithm
255
Extensions and Background
256
Further Reading
257
27 Scheduling of Tournaments or Sports Leagues
258
Generation of Schedules
259
Schedules with Home-Away Assignments
263
Further Reading
265
28 Eulerian Circuits
267
When Does an Eulerian Circuit Exist?
268
Finding Eulerian Circuits
269
The Algorithm
270
The House of Santa Claus
271
Of Postmen and Garbage Collectors
272
Further Reading
272
29 High-Speed Circles
274
Drawing Circles: Keep It Simple!
275
Bresenham's Algorithm for Circles
277
A Racing Duel
281
Further Reading
282
30 Gauß-Seidel Iterative Method for the Computation of Physical Problems
283
Warmup: Soccer
283
Temperature Calculation in a Rod (1D)
285
Temperature Computation on a Plate (2D)
287
Further Reading
291
31 Dynamic Programming - Evolutionary Distance
293
Mathematical Modeling
293
Calculation of the Evolutionary Distance
295
The Algorithm
296
Conclusion
298
References
299
Part IV Optimization
300
Overview
301
32 Shortest Paths
303
Dijkstra's Algorithm
305
FAQs and Further Reading
308
33 Minimum Spanning Trees (Sometimes Greed Pays Off …)
311
The Bridge Project of the Algos
312
Building Bridges After the Hurricane
313
The Algorithms of Prim and Kruskal
315
Further Reading
316
34 Maximum Flows - Towards the Stadium During Rush Hour
318
The Algorithm
320
Some Open Questions
327
Why Does It Work?
327
Epilogue
328
Solution
328
Further Reading
328
35 Marriage Broker
330
Problem
330
The Basic Principle of the Procedure
331
The Construction of a Maximum Matching
332
The Algorithm
336
The Marriage Theorem
337
Where Is the Marriage Theorem Needed by the Algorithm
338
Time Analysis
339
Further Reading
339
Acknowledgements
340
36 The Smallest Enclosing Circle - A Contribution to Democracy from Switzerland?
341
Why It Works
344
Further Reading
344
37 Online Algorithms - What Is It Worth to Know the Future?
345
The Ski Rental Problem
345
The Paging Problem
348
Further Reading
350
38 Bin Packing or "How Do I Get My Stuff into the Boxes?"
351
The Online Problem "Moving Inexpensively"
352
Analysis of the Algorithms
353
How Well Can Online Algorithms for Bin Packing Perform?
356
Further Reading
358
39 The Knapsack Problem
359
Pareto-Optimal Solutions
361
The Nemhauser-Ullmann Algorithm
363
Further Reading
365
40 The Travelling Salesman Problem
366
Introduction
366
The Brute-Force Method
367
Dynamic Programming
368
Approximative Solutions
370
MST Algorithm
371
Some Final Remarks
373
Further Reading
374
41 Simulated Annealing
375
What Is Simulated Annealing?
376
The Travelling Salesperson Problem
379
Further Applications
380
Further Reading
382
Author Details
383
Service
Shop
Kopierschutz
= Kopierschutzfrei
= Wasserzeichen
= DRM Kopierschutz
