logo资料库

Algorithms Unplugged英文版PDF.pdf

发布时间：2022-06-15 发布人：admin 分类：说明书 资料大小：5.75M 资料格式：pdf 举报 版权申诉
第1页 / 共417页
第2页 / 共417页
第3页 / 共417页
第4页 / 共417页
第5页 / 共417页
第6页 / 共417页
第7页 / 共417页
第8页 / 共417页
资料共417页，剩余部分请下载后查看
    Cover
    Algorithms Unplugged
    Copyright
    9783642153273
    Preface
    Contents
    Part I - Searching and Sorting
    Overview
    1 Binary Search
    Sequential Search
    Binary Search
    Recursive Implementation
    Number of Search Steps
    Guessing Games
    Further Reading
    2 Insertion Sort
    To Read on
    3 Fast Sorting Algorithms
    3.1 The Algorithms
    3.2 Detailed Explanations About These Sorting Algorithms
    3.3 Experimental Comparison of the Sorting Algorithms
    3.4 Determining the Runtimes Theoretically
    3.5 Implementation in Java
    Further Reading and Experiments
    4 Parallel Sorting - The Need for Speed
    Sorting in Hardware: Comparators and Sorting Circuits
    The Bitonic Sorting Circuit: Its Architecture
    The Bitonic Sorting Circuit: Its Correctness and Running Time
    Concluding Remarks
    Further Reading
    5 Topological Sorting - How Should I Begin to Complete My To Do List?
    Further Applications
    Additional Reading
    6 Searching Texts - But Fast! The Boyer-Moore-Horspool Algorithm
    The Naive Algorithm
    The Boyer-Moore-Horspool Algorithm
    Further Reading
    7 Depth-First Search (Ariadne & Co.)
    Algorithmic Idea and Implementation
    Applications
    Example: Web Search
    Example: Labyrinth Creation
    Example: Television Shows
    Example: Traffic Planning
    Breadth-First Search
    Further Reading
    Acknowledgement
    8 Pledge's Algorithm
    Further Reading
    Acknowledgement
    9 Cycles in Graphs
    Scenario 1
    Scenario 2
    Finding Cycles by Depth-First Search
    Strongly Connected Components
    Searching for Cycles with Breadth-First Search
    Historical Notes
    References
    Acknowledgement
    10 PageRank - What Is Really Relevant in the World-Wide Web?
    Tourist Trails
    Trails on the Web
    Solutions
    Conclusion
    Further Reading
    Part II - Arithmetic and Encryption
    Overview
    11 Multiplication of Long Integers - Faster than Long Multiplication
    The Addition of Long Numbers
    Short Multiplication: A Number Times a Digit
    The Analysis of Long Multiplication
    Karatsuba's Method
    Karatsuba's Method for 4-Digit Numbers
    Karatsuba's Method for Numbers of Any Length
    Summary
    Further Reading
    Acknowledgements
    12 The Euclidean Algorithm
    The Greatest Common Divisor
    An Observation That Speeds up the Algorithm
    Analysis
    An Example
    Further Reading
    Acknowledgement
    13 The Sieve of Eratosthenes - How Fast Can We Compute a Prime Number Table?
    From the Idea to a Method
    A Simple Idea
    How Fast Is the Computation?
    How Does the Algorithm Spend Its Time?
    Do We Need Every i Value?
    Can We Get Even Faster?
    What Can We Learn from This Example?
    Further Considerations
    Further Reading
    14 One-Way Functions. Mind the Trap - Escape Only for the Initiated
    The Mirror Image of Multiplication: Factorization
    One-Way Functions
    A Practical Problem: Searching a Telephone Book
    Security and Googles
    Further Reading
    15 The One-Time Pad Algorithm - The Simplest and Most Secure Way to Keep Secrets
    Encrypting Messages
    The Algorithm
    Breaking the Code
    Further Reading
    16 Public-Key Cryptography
    Public Keys
    A Limited Algebra
    Construction of the Keys
    Encryption
    Decryption
    The Eavesdropper
    Without Limited Mathematics
    ElGamal's Method
    Modular Multiplication and Modular Exponentiation
    Description of ElGamal's Cryptosystem
    Further Methods
    Security
    Further Reading
    17 How to Share a Secret
    A Simple Method to Share a Secret
    General Secret Sharing
    Secret Sharing, Information Theory and Cryptography
    Further Reading
    18 Playing Poker by Email
    Dealing Cards by Snail Mail
    How to Shuffle and Distribute the Cards
    How to Bid
    How to Replace Cards
    The Showdown
    How to Verify That No One Has Cheated
    Discussion
    Dealing Cards by Email
    Electronic Envelopes
    How to Shuffle the Cards and Distribute Them to Bob
    One-Way Functions
    How to Replace Cards
    A Mathematical Description
    Distribution of Cards to Both Players
    Commitment to the Selected Coding Tables
    Putting Cards into Envelopes
    Distributing Cards to Alice
    Distributing Cards to Bob
    Dropping Cards
    Properties of the Electronic Envelopes
    How to Check Whether the Opponent Has Cheated
    Poker with More than Two Players
    Further Reading
    19 Fingerprinting
    How to Compare Long Texts over the Telephone
    Texts as Sequences of Numbers and Modular Arithmetic
    Fingerprints
    Fingerprints with Random Numbers
    The Protocol
    Summary
    Remarks on the Fingerprinting Theorem
    Further Reading
    Acknowledgement
    20 Hashing
    Message Digest
    Secure Hashing
    Hashing for Dictionaries
    Storing a Data Item z with Key x
    Searching a Data Item Corresponding to Key x
    External Links and References
    21 Codes - Protecting Data Against Errors and Loss
    22.1 Introduction
    22.1.1 Where Are Codes Used?
    21.2 Reed-Solomon Codes
    21.3 New Coding Techniques: Low-Density Parity-Check Codes
    21.4 Network Codes
    21.5 Places to Start Looking for More Information
    Acknowledgement
    Part III - Planning, Coordination and Simulation
    Overview
    22 Broadcasting - How Can I Quickly Disseminate Information?
    References
    23 Converting Numbers into English Words
    Stepwise Development of an Algorithm
    Splitting Numbers into Three-Digit Groups …
    …and Generating the English Words
    Function generateGroup
    Function generateWeight
    Lessons Learned
    What to Read and Try out for Yourself
    24 Majority - Who Gets Elected Class Rep?
    Majority Algorithm
    Correctness of the Majority Algorithm
    How Many Comparisons Are Necessary?
    Applications and Extensions
    What Can We Learn from the Solutions to the Majority Problem?
    Further Reading
    25 Random Numbers - How Can We Create Randomness in Computers?
    A Tactical Game: "Rock, Paper, Scissors"
    Means for the Generation of Random Numbers: Modular Arithmetic
    Examples for Modular Arithmetic
    Illustration of Modular Arithmetic
    An Algorithm for the Generation of Pseudorandom Numbers
    Periodic Behavior
    Simulation of True Random Number Generators
    The Algorithm for Rock, Paper, Scissors
    Monte Carlo Simulation: Determination of Areas Using "Random Rain"
    Further Reading
    26 Winning Strategies for a Matchstick Game
    Learning from Small Examples
    An Algorithm to Compute a Winning Strategy
    The Running Time of the Algorithm
    Extensions and Background
    Further Reading
    27 Scheduling of Tournaments or Sports Leagues
    Generation of Schedules
    Schedules with Home-Away Assignments
    Further Reading
    28 Eulerian Circuits
    When Does an Eulerian Circuit Exist?
    Finding Eulerian Circuits
    The Algorithm
    The House of Santa Claus
    Of Postmen and Garbage Collectors
    Further Reading
    29 High-Speed Circles
    Drawing Circles: Keep It Simple!
    Bresenham's Algorithm for Circles
    A Racing Duel
    Further Reading
    30 Gauß-Seidel Iterative Method for the Computation of Physical Problems
    Warmup: Soccer
    Temperature Calculation in a Rod (1D)
    Temperature Computation on a Plate (2D)
    Further Reading
    31 Dynamic Programming - Evolutionary Distance
    Mathematical Modeling
    Calculation of the Evolutionary Distance
    The Algorithm
    Conclusion
    References
    Part IV - Optimization
    Optimization
    32 Shortest Paths
    Dijkstra's Algorithm
    FAQs and Further Reading
    33 Minimum Spanning Trees (Sometimes Greed Pays Off …)
    The Bridge Project of the Algos
    Building Bridges After the Hurricane
    The Algorithms of Prim and Kruskal
    Further Reading
    34 Maximum Flows - Towards the Stadium During Rush Hour
    The Algorithm
    Some Open Questions
    Why Does It Work?
    Epilogue
    Solution
    Further Reading
    35 Marriage Broker
    35.1 Problem
    35.2 The Basic Principle of the Procedure
    35.3 The Construction of a Maximum Matching
    35.4 The Algorithm
    35.5 The Marriage Theorem
    35.6 Where Is the Marriage Theorem Needed by the Algorithm
    35.7 Time Analysis
    Further Reading
    Acknowledgements
    36 The Smallest Enclosing Circle - A Contribution to Democracy from Switzerland?
    Why It Works
    Further Reading
    37 Online Algorithms - What Is It Worth to Know the Future?
    The Ski Rental Problem
    The Paging Problem
    Further Reading
    38 Bin Packing or "How Do I Get My Stuff into the Boxes?"
    The Online Problem "Moving Inexpensively"
    Analysis of the Algorithms
    How Well Can Online Algorithms for Bin Packing Perform?
    Further Reading
    39 The Knapsack Problem
    Pareto-Optimal Solutions
    The Nemhauser-Ullmann Algorithm
    Further Reading
    40 The Travelling Salesman Problem
    Introduction
    The Brute-Force Method
    Dynamic Programming
    Approximative Solutions
    MST Algorithm
    Some Final Remarks
    Further Reading
    41 Simulated Annealing
    What Is Simulated Annealing?
    The Travelling Salesperson Problem
    Further Applications
    Further Reading
    Author Details
    Algorithms Unplugged
    Berthold V¨ocking r Helmut Alt r Martin Dietzfelbinger r R¨udiger Reischuk r Christian Scheideler r Heribert Vollmer r Dorothea Wagner Editors Algorithms Unplugged
    Prof. Dr. rer. nat. Christian Scheideler Institut f¨ur Informatik Universit¨at Paderborn F¨urstenallee 11 33102 Paderborn Germany Prof. Dr. rer. nat. Heribert Vollmer Institut f¨ur Theoretische Informatik Leibniz Universit¨at Hannover Appelstr. 4 30167 Hannover Germany Prof. Dr. rer. nat. Dorothea Wagner Institut f¨ur Theoretische Informatik Karlsruher Institut f¨ur Technologie (KIT) Am Fasanengarten 5 76131 Karlsruhe Germany Editors Prof. Dr. rer. nat. Berthold V¨ocking Lehrstuhl f¨ur Informatik 1 Algorithmen und Komplexit¨at RWTH Aachen University Ahornstr. 55 52074 Aachen Germany Prof. Dr. rer. nat. Helmut Alt Institut f¨ur Informatik Freie Universit¨at Berlin Takustr. 9 14195 Berlin Germany Prof. Dr. Martin Dietzfelbinger Institut f¨ur Theoretische Informatik Fakult¨at f¨ur Informatik und Automatisierung Technische Universit¨at Ilmenau Helmholtzplatz 1 98693 Ilmenau Germany Prof. Dr. math. R¨udiger Reischuk Institut f¨ur Theoretische Informatik Universit¨at zu L¨ubeck Ratzeburger Allee 160 23538 L¨ubeck Germany ISBN 978-3-642-15327-3 DOI 10.1007/978-3-642-15328-0 Springer Heidelberg Dordrecht London New York e-ISBN 978-3-642-15328-0 ACM Codes: K.3, F.2 c Springer-Verlag Berlin Heidelberg 2011 This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer. Violations are liable to prosecution under the German Copyright Law. The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Cover design: KuenkelLopka GmbH Printed on acid-free paper Springer is part of Springer Science+Business Media (www.springer.com)
    Preface Many of the technological innovations and achievements of recent decades have relied on algorithmic ideas, facilitating new applications in science, medicine, production, logistics, traffic, communication, and, last but not least, entertain- ment. Efficient algorithms not only enable your personal computer to execute the newest generation of games with features unthinkable only a few years ago, but they are also the 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. Algorithms specify the way computers process information and how they execute tasks. They organize data and enable us to search for information efficiently. Only because of clever algorithms used by search engines can we find our way through the information jungle in the World-Wide Web. Reliable and secure communication in the Internet is provided by ingenious coding and encryption algorithms that use fast arithmetic and advanced cryptographic methods. Weather forecasting and climate change analysis rely on efficient simulation algorithms. Production and logistics planning employs smart algo- rithms that solve difficult optimization problems. We even rely on algorithms that perform GPS localization and routing based on efficient shortest-path computation for finding our way to the next restaurant or coffee shop. Algorithms are not only executed on what people usually think of as com- puters but also on embedded microprocessors that can be found in industrial robots, cars and aircrafts, and in almost all household appliances and con- sumer electronics. For example, your MP3 player uses a clever compression algorithm that saves tremendous amounts of storage capacity. Modern cars and aircrafts contain not only one but several hundreds or even thousands of microprocessors. Algorithms regulate the combustion engine in cars, thereby reducing fuel consumption and air pollution. They control the braking sys- tem and the steering system in order to improve the vehicle’s stability for your safety. In the near future, microprocessors might completely take over the controls, allowing for fully automated car driving in certain standardized
    vi Preface situations. In modern aircraft, this is already put into practice for all phases of a flight from takeoff to landing. The greatest improvements in the area of algorithms rely on beautiful ideas for tackling or solving computational problems more efficiently. The problems solved by algorithms are not restricted to arithmetic tasks in a narrow sense but often relate to exciting questions of nonmathematical flavor, such as: • How to find an exit from inside a labyrinth or maze? • How to partition a treasure map so that the treasure can only be found if • How to plan a tour visiting several places in the cheapest possible order? Solving these challenging problems requires logical reasoning, geometric and combinatorial imagination, and, last but not least, creativity. Indeed, these are the main skills needed for the design and analysis of algorithms. all parts of the map are recombined? In this book we present some of the most beautiful algorithmic ideas in 41 articles written by different authors in colloquial and nontechnical language. Most of the articles arose out of an initiative among German-language uni- versities to communicate the fascination of algorithms and computer science to high-school students. The book can be understood without any particular previous knowledge about algorithms and computing. We hope it is enlight- ening and fun to read, not only for students but also for interested adults who want to gain an introduction to the fascinating world of algorithms. Berthold V¨ocking Helmut Alt Martin Dietzfelbinger R¨udiger Reischuk Christian Scheideler Heribert Vollmer Dorothea Wagner
    Contents Part I Searching and Sorting Overview Martin Dietzfelbinger and Christian Scheideler . . . . . . . . . . . . . . . . . . . . . . . 1 Binary Search Thomas Seidl and Jost Enderle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 5 2 Insertion Sort Wolfgang P. Kowalk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3 Fast Sorting Algorithms Helmut Alt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 4 Parallel Sorting – The Need for Speed Rolf Wanka . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5 Topological Sorting – How Should I Begin to Complete My To Do List? Hagen H¨opfner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6 Searching Texts – But Fast! The Boyer–Moore–Horspool Algorithm Markus E. Nebel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 7 Depth-First Search (Ariadne & Co.) Michael Dom, Falk H¨uffner, and Rolf Niedermeier . . . . . . . . . . . . . . . . . . . 57 8 Pledge’s Algorithm Rolf Klein and Tom Kamphans . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
    分享到：
    赞 收藏

    相关推荐

    资料库

    后端

    共收录2142份资料，累计10个分类，关注成员有19位，主要包括：Perl,Docker,Delphi,VB,PHP,Java,C,C#,Python,C++

    热门标签

    Perl Docker Delphi VB PHP Java C C# Python C++

    最新资料