ebook ebooks e-book e-books downloaden bei MyEbooks.ch downloaden

Algorithms Unplugged

:	Dorothea Wagner, Heribert Vollmer, Christian Scheideler, Rüdiger Reischuk, Martin Dietzfelbinger, He
:	Berthold Vöcking, Helmut Alt, Martin Dietzfelbinger, Rüdiger Reischuk, Christian Scheideler, Heriber
:	Algorithms Unplugged
:	Springer-Verlag
:	9783642153280
:	1
:	CHF 95.00
:

:	Naturwissenschaft
:	English

:	406
:	Wasserzeichen
:	PC/MAC/eReader/Tablet
:	PDF

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.

	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	59
	61	59
	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