دسترسی نامحدود
برای کاربرانی که ثبت نام کرده اند
برای ارتباط با ما می توانید از طریق شماره موبایل زیر از طریق تماس و پیامک با ما در ارتباط باشید
در صورت عدم پاسخ گویی از طریق پیامک با پشتیبان در ارتباط باشید
برای کاربرانی که ثبت نام کرده اند
درصورت عدم همخوانی توضیحات با کتاب
از ساعت 7 صبح تا 10 شب
ویرایش: 2
نویسندگان: Skiena. Steven S.
سری:
ISBN (شابک) : 9781848000704
ناشر: Springer
سال نشر: 2008
تعداد صفحات: 0
زبان: English
فرمت فایل : EPUB (درصورت درخواست کاربر به PDF، EPUB یا AZW3 تبدیل می شود)
حجم فایل: 5 مگابایت
در صورت تبدیل فایل کتاب The Algorithm Design Manual به فرمت های PDF، EPUB، AZW3، MOBI و یا DJVU می توانید به پشتیبان اطلاع دهید تا فایل مورد نظر را تبدیل نمایند.
توجه داشته باشید کتاب کتابچه راهنمای طراحی الگوریتم نسخه زبان اصلی می باشد و کتاب ترجمه شده به فارسی نمی باشد. وبسایت اینترنشنال لایبرری ارائه دهنده کتاب های زبان اصلی می باشد و هیچ گونه کتاب ترجمه شده یا نوشته شده به فارسی را ارائه نمی دهد.
این نسخه دوم بهتازگی گسترش یافته و بهروز شده از پرفروشترین کلاسیک، همچنان «معمای» طراحی الگوریتمها و تجزیه و تحلیل اثربخشی و کارایی آنها را از بین میبرد. با گسترش نسخه اول، این کتاب اکنون به عنوان کتاب درسی اصلی انتخابی برای دوره های طراحی الگوریتم عمل می کند و در عین حال وضعیت خود را به عنوان راهنمای مرجع عملی برتر الگوریتم ها برای برنامه نویسان، محققان و دانشجویان حفظ می کند. کتابچه راهنمای طراحی الگوریتم خواننده پسند، دسترسی مستقیم به فناوری الگوریتمهای ترکیبی را فراهم میکند و بر طراحی بیش از تحلیل تاکید میکند. بخش اول، تکنیک ها، دستورالعمل های قابل دسترس در مورد روش های طراحی و تجزیه و تحلیل الگوریتم های کامپیوتری را ارائه می دهد. بخش دوم، منابع، برای مرور و ارجاع در نظر گرفته شده است و شامل فهرست منابع الگوریتمی، پیاده سازی ها و کتابشناسی گسترده است. جدید به نسخه دوم: • مطالب آموزشی و تمرین ها را نسبت به نسخه اول دو برابر می کند • پشتیبانی آنلاین کامل را برای اساتید ارائه می دهد و یک جزء وب سایت کاملاً به روز و بهبود یافته با اسلایدهای سخنرانی، صوتی و تصویری • حاوی یک کاتالوگ منحصر به فرد است که 75 مشکل الگوریتمی را شناسایی می کند. که اغلب در عمل به وجود می آیند و خواننده را به مسیر درست برای حل آنها هدایت می کنند • شامل چندین "داستان جنگ" جدید مربوط به تجربیات از برنامه های کاربردی دنیای واقعی است. ، C++ و جاوا
This newly expanded and updated second edition of the best-selling classic continues to take the "mystery" out of designing algorithms, and analyzing their efficacy and efficiency. Expanding on the first edition, the book now serves as the primary textbook of choice for algorithm design courses while maintaining its status as the premier practical reference guide to algorithms for programmers, researchers, and students. The reader-friendly Algorithm Design Manual provides straightforward access to combinatorial algorithms technology, stressing design over analysis. The first part, Techniques, provides accessible instruction on methods for designing and analyzing computer algorithms. The second part, Resources, is intended for browsing and reference, and comprises the catalog of algorithmic resources, implementations and an extensive bibliography. NEW to the second edition: • Doubles the tutorial material and exercises over the first edition • Provides full online support for lecturers, and a completely updated and improved website component with lecture slides, audio and video • Contains a unique catalog identifying the 75 algorithmic problems that arise most often in practice, leading the reader down the right path to solve them • Includes several NEW "war stories" relating experiences from real-world applications • Provides up-to-date links leading to the very best algorithm implementations available in C, C++, and Java
Preface Contents 1 Introduction to Algorithm Design 1.1 Robot Tour Optimization 1.2 Selecting the Right Jobs 1.3 Reasoning about Correctness 1.3.1 Expressing Algorithms 1.3.2 Problems and Properties 1.3.3 Demonstrating Incorrectness 1.3.4 Induction and Recursion 1.3.5 Summations 1.4 Modeling the Problem 1.4.1 Combinatorial Objects 1.4.2 Recursive Objects 1.5 About the War Stories 1.6 War Story: Psychic Modeling Chapter Notes 1.7 Exercises 2 Algorithm Analysis 2.1 The RAM Model of Computation 2.1.1 Best, Worst, and Average-Case Complexity 2.2 The Big Oh Notation 2.3 Growth Rates and Dominance Relations 2.3.1 Dominance Relations 2.4 Working with the Big Oh 2.4.1 Adding Functions 2.4.2 Multiplying Functions 2.5 Reasoning About Efficiency 2.5.1 Selection Sort 2.5.2 Insertion Sort 2.5.3 String Pattern Matching 2.5.4 Matrix Multiplication 2.6 Logarithms and Their Applications 2.6.1 Logarithms and Binary Search 2.6.2 Logarithms and Trees 2.6.3 Logarithms and Bits 2.6.4 Logarithms and Multiplication 2.6.5 Fast Exponentiation 2.6.6 Logarithms and Summations 2.6.7 Logarithms and Criminal Justice 2.7 Properties of Logarithms 2.8 War Story: Mystery of the Pyramids 2.9 Advanced Analysis (*) 2.9.1 Esoteric Functions 2.9.2 Limits and Dominance Relations Chapter Notes 2.10 Exercises 3 Data Structures 3.1 Contiguous vs. Linked Data Structures 3.1.1 Arrays 3.1.2 Pointers and Linked Structures 3.1.3 Comparison 3.2 Stacks and Queues 3.3 Dictionaries 3.4 Binary Search Trees 3.4.1 Implementing Binary Search Trees 3.4.2 How Good Are Binary Search Trees? 3.4.3 Balanced Search Trees 3.5 Priority Queues 3.6 War Story: Stripping Triangulations 3.7 Hashing and Strings 3.7.1 Collision Resolution 3.7.2 Efficient String Matching via Hashing 3.7.3 Duplicate Detection Via Hashing 3.8 Specialized Data Structures 3.9 War Story: String ’em Up Chapter Notes 3.10 Exercises 4 Sorting and Searching 4.1 Applications of Sorting 4.2 Pragmatics of Sorting 4.3 Heapsort: Fast Sorting via Data Structures 4.3.1 Heaps 4.3.2 Constructing Heaps 4.3.3 Extracting the Minimum 4.3.4 Faster Heap Construction (*) 4.3.5 Sorting by Incremental Insertion 4.4 War Story: Give me a Ticket on an Airplane 4.5 Mergesort: Sorting by Divide-and-Conquer 4.6 Quicksort: Sorting by Randomization 4.6.1 Intuition: The Expected Case for Quicksort 4.6.2 Randomized Algorithms 4.6.3 Is Quicksort Really Quick? 4.7 Distribution Sort: Sorting via Bucketing 4.7.1 Lower Bounds for Sorting 4.8 War Story: Skiena for the Defense 4.9 Binary Search and Related Algorithms 4.9.1 Counting Occurrences 4.9.2 One-Sided Binary Search 4.9.3 Square and Other Roots 4.10 Divide-and-Conquer 4.10.1 Recurrence Relations 4.10.2 Divide-and-Conquer Recurrences 4.10.3 Solving Divide-and-Conquer Recurrences (*) Chapter Notes 4.11 Exercises 5 Graph Traversal 5.1 Flavors of Graphs 5.1.1 The Friendship Graph 5.2 Data Structures for Graphs 5.3 War Story: I was a Victim of Moore’s Law 5.4 War Story: Getting the Graph 5.5 Traversing a Graph 5.6 Breadth-First Search 5.6.1 Exploiting Traversal 5.6.2 Finding Paths 5.7 Applications of Breadth-First Search 5.7.1 Connected Components 5.7.2 Two-Coloring Graphs 5.8 Depth-First Search 5.9 Applications of Depth-First Search 5.9.1 Finding Cycles 5.9.2 Articulation Vertices 5.10 Depth-First Search on Directed Graphs 5.10.1 Topological Sorting 5.10.2 Strongly Connected Components Chapter Notes 5.11 Exercises 6 Weighted Graph Algorithms 6.1 Minimum Spanning Trees 6.1.1 Prim’s Algorithm 6.1.2 Kruskal’s Algorithm 6.1.3 The Union-Find Data Structure 6.1.4 Variations on Minimum Spanning Trees 6.2 War Story: Nothing but Nets 6.3 Shortest Paths 6.3.1 Dijkstra’s Algorithm 6.3.2 All-Pairs Shortest Path 6.3.3 Transitive Closure 6.4 War Story: Dialing for Documents 6.5 Network Flows and Bipartite Matching 6.5.1 Bipartite Matching 6.5.2 Computing Network Flows 6.6 Design Graphs, Not Algorithms Chapter Notes 6.7 Exercises 7 Combinatorial Search and Heuristic Methods 7.1 Backtracking 7.1.1 Constructing All Subsets 7.1.2 Constructing All Permutations 7.1.3 Constructing All Paths in a Graph 7.2 Search Pruning 7.3 Sudoku 7.4 War Story: Covering Chessboards 7.5 Heuristic Search Methods 7.5.1 Random Sampling 7.5.2 Local Search 7.5.3 Simulated Annealing 7.5.4 Applications of Simulated Annealing 7.6 War Story: Only it is Not a Radio 7.7 War Story: Annealing Arrays 7.8 Other Heuristic Search Methods 7.9 Parallel Algorithms 7.10 War Story: Going Nowhere Fast Chapter Notes 7.11 Exercises 8 Dynamic Programming 8.1 Caching vs. Computation 8.1.1 Fibonacci Numbers by Recursion 8.1.2 Fibonacci Numbers by Caching 8.1.3 Fibonacci Numbers by Dynamic Programming 8.1.4 Binomial Coefficients 8.2 Approximate String Matching 8.2.1 Edit Distance by Recursion 8.2.2 Edit Distance by Dynamic Programming 8.2.3 Reconstructing the Path 8.2.4 Varieties of Edit Distance 8.3 Longest Increasing Sequence 8.4 War Story: Evolution of the Lobster 8.5 The Partition Problem 8.6 Parsing Context-Free Grammars 8.6.1 Minimum Weight Triangulation 8.7 Limitations of Dynamic Programming: TSP 8.7.1 When are Dynamic Programming Algorithms Correct? 8.7.2 When are Dynamic Programming Algorithms Efficient? 8.8 War Story: What’s Past is Prolog 8.9 War Story: Text Compression for Bar Codes Chapter Notes 8.10 Exercises 9 Intractable Problems and Approximation Algorithms 9.1 Problems and Reductions 9.1.1 The Key Idea 9.1.2 Decision Problems 9.2 Reductions for Algorithms 9.2.1 Closest Pair 9.2.2 Longest Increasing Subsequence 9.2.3 Least Common Multiple 9.2.4 Convex Hull (*) 9.3 Elementary Hardness Reductions 9.3.1 Hamiltonian Cycle 9.3.2 Independent Set and Vertex Cover 9.3.3 Clique 9.4 Satisfiability 9.4.1 3-Satisfiability 9.5 Creative Reductions 9.5.1 Integer Programming 9.5.2 Vertex Cover 9.6 The Art of Proving Hardness 9.7 War Story: Hard Against the Clock 9.8 War Story: And Then I Failed 9.9 P vs. NP 9.9.1 Verification vs. Discovery 9.9.2 The Classes P and NP 9.9.3 Why is Satisfiability the Mother of All Hard Problems? 9.9.4 NP-hard vs. NP-complete? 9.10 Dealing with NP-complete Problems 9.10.1 Approximating Vertex Cover 9.10.2 The Euclidean Traveling Salesman 9.10.3 Maximum Acyclic Subgraph 9.10.4 Set Cover Chapter Notes 9.11 Exercises 10 How to Design Algorithms 11 A Catalog of Algorithmic Problems Caveats 12 Data Structures 12.1 Dictionaries 12.2 Priority Queues 12.3 Suffix Trees and Arrays 12.4 Graph Data Structures 12.5 Set Data Structures 12.6 Kd-Trees 13 Numerical Problems 13.1 Solving Linear Equations 13.2 Bandwidth Reduction 13.3 Matrix Multiplication 13.4 Determinants and Permanents 13.5 Constrained and Unconstrained Optimization 13.6 Linear Programming 13.7 Random Number Generation 13.8 Factoring and Primality Testing 13.9 Arbitrary-Precision Arithmetic 13.10 Knapsack Problem 13.11 Discrete Fourier Transform 14 Combinatorial Problems 14.1 Sorting 14.2 Searching 14.3 Median and Selection 14.4 Generating Permutations 14.5 Generating Subsets 14.6 Generating Partitions 14.7 Generating Graphs 14.8 Calendrical Calculations 14.9 Job Scheduling 14.10 Satisfiability 15 Graph Problems: Polynomial-Time 15.1 Connected Components 15.2 Topological Sorting 15.3 Minimum Spanning Tree 15.4 Shortest Path 15.5 Transitive Closure and Reduction 15.6 Matching 15.7 Eulerian Cycle/Chinese Postman 15.8 Edge and Vertex Connectivity 15.9 Network Flow 15.10 Drawing Graphs Nicely 15.11 Drawing Trees 15.12 Planarity Detection and Embedding 16 Graph Problems: Hard Problems 16.1 Clique 16.2 Independent Set 16.3 Vertex Cover 16.4 Traveling Salesman Problem 16.5 Hamiltonian Cycle 16.6 Graph Partition 16.7 Vertex Coloring 16.8 Edge Coloring 16.9 Graph Isomorphism 16.10 Steiner Tree 16.11 Feedback Edge/Vertex Set 17 Computational Geometry 17.1 Robust Geometric Primitives 17.2 Convex Hull 17.3 Triangulation 17.4 Voronoi Diagrams 17.5 Nearest Neighbor Search 17.6 Range Search 17.7 Point Location 17.8 Intersection Detection 17.9 Bin Packing 17.10 Medial-Axis Transform 17.11 Polygon Partitioning 17.12 Simplifying Polygons 17.13 Shape Similarity 17.14 Motion Planning 17.15 Maintaining Line Arrangements 17.16 Minkowski Sum 18 Set and String Problems 18.1 Set Cover 18.2 Set Packing 18.3 String Matching 18.4 Approximate String Matching 18.5 Text Compression 18.6 Cryptography 18.7 Finite State Machine Minimization 18.8 Longest Common Substring/Subsequence 18.9 Shortest Common Superstring 19 Algorithmic Resources 19.1 Software Systems 19.1.1 LEDA 19.1.2 CGAL 19.1.3 Boost Graph Library 19.1.4 GOBLIN 19.1.5 Netlib 19.1.6 Collected Algorithms of the ACM 19.1.7 SourceForge and CPAN 19.1.8 The Stanford GraphBase 19.1.9 Combinatorica 19.1.10 Programs from Books 19.2 Data Sources 19.3 Online Bibliographic Resources 19.4 Professional Consulting Services Bibliography Index