علوم کامپیوتر، الگوریتم‌ها و پیچیدگی

The book defines complexity as a numerical function T (n)-the relationship between time and input size n, as one of the basic ideas of computer science. The computational complexity is categorized by algorithm based on its nature and function. The (computational) complexity of the algorithm is a measurement of the ratio of computational resources (time and space) consumed when a particular algorithm is running. For these issues, the book tries to locate heuristic algorithms which can almost explain the problem and operate in a reasonable timeframe. Different kinds of algorithms are described such as graph and network algorithms, algebraic algorithms, parallel algorithms and randomized algorithms. Cover 1 Title Page 5 Copyright 6 ABOUT THE EDITOR 7 TABLE OF CONTENTS 9 List of Figures 13 List of Tables 15 List of Abbreviations 17 Preface 19 Chapter 1 Basic Techniques for Design and Analysis of Algorithms 21 1.1. Introduction 22 1.2. Divide-And-Conquer Algorithms 26 1.3 Dynamic Programming 30 1.4. Greedy Heuristics 33 1.5. Sentinel Linear Search 36 1.6. Backtracking 37 1.7. Brute Force/Exhaustive Search 39 1.8. Branch-And-Bound Algorithm 43 1.9. Randomized Algorithm 45 1.10. Branch-H And-Bound 46 Chapter 2 Computational Complexity Theory 49 2.1. Introduction 50 2.2. Brief History 51 2.3. Computation Models 53 2.4. Turing Machines 54 2.5. Computational Problems 56 2.6. Complexity Classes 59 2.7. Relationships Between Complexity Classes 64 2.8. Reducibility And Completeness 65 2.9. Relativization of P Vs. Np Problem 66 2.10. Polynomial Hierarchy 67 2.11. Alternating Complex Classes 67 2.12. Circuit Complexity 68 2.13. Probabilistic Complexity Classes 68 2.14. Interactive Models And Complexity Classes 69 2.15. Kolmogorov Complexity 70 Chapter 3 Graph and Network Algorithms 73 3.1. Introduction 74 3.2. Tree Traversals 75 3.3. Depth-First Search 76 3.4. Algorithm 77 3.5. Minimum Spanning Trees 87 Chapter 4 Cryptography 101 4.1. Introduction 102 4.2. Quantum Cryptography 102 4.3. Transmission Media 104 4.4. History Of Cryptography 108 4.5. Cryptography Notions Of Security 109 4.6. Cryptography Building Blocks 113 4.7. Benefits Of Cryptography 123 4.8. Drawbacks Of Cryptography 124 Chapter 5 Algebraic Algorithms 125 5.1. Introduction 126 5.2. Computational Methods 128 5.3. Systems Of Nonlinear Equations And Their Applications 134 5.4. Polynomial Factorization 138 Chapter 6 Parallel Algorithms 147 6.1. Introduction 148 6.2. Parallelizability 148 6.3. Dispersed Algorithms 150 6.4. Parallel Programming Models 156 6.5. Parallel Algorithm Techniques 159 6.6. Graphs 161 6.7. Sorting 162 6.8. Computational Geometry 164 6.9. Numerical Algorithms 168 Chapter 7 Randomized Algorithms 173 7.1. Introduction 174 7.2. The Basic Principles Underlying The Construction Of Randomized Algorithms 178 7.3. Randomized Increasing Constructions In Geometry 184 7.4. Algorithm Analysis 185 7.5. De-Randomization 185 7.6. Example Where Randomness Helps 185 Chapter 8 Pattern Matching And Text Compression Algorithms 187 8.1. Introduction 188 8.2. Processing Texts Efficiently 190 8.3. Choosing Ml Algorithms 193 8.4. String-Matching Algorithms 195 8.5. Two-Dimensional Pattern Matching Algorithms 198 8.6. Suffix Trees 205 8.7. Alignment 206 8.8. Approximate Strinng 207 8.9. Text Compression 209 8.10. Research Issues And Summary 210 8.11. Searching Compressed Dat 211 Chapter 9 Genetic Algorithms 215 9.1. Introduction 216 9.2. Initialization 218 9.3. Selection 218 9.4. Genetic Operations 219 9.5. Heuristics Method 219 9.6. Termination 220 9.7. Examples Of Genetic Algorithms 221 9.8. Underlying Principles In Genetic Algorithm 224 9.9. Genetic Parameters 226 9.10. Best Practices In Genetic Algorithm 228 9.11. Mathematical Analysis Of Genetic Algorithms 231 9.12. Building Block Hypothesis 233 9.13. Related Techniques In Genetic Algorithm 234 9.14. Applications Of Genetic Algorithms 236 Chapter 10 Combinational Optimization 241 10.1. Introduction 242 10.2. Integer Linear Plans 244 10.3. Algorithms 246 10.4. Polyhedral Combinatorics 248 10.5. Incomplete Enumeration Procedures 252 10.6. Linear Training 255 10.7. Crucial Substitute of The Algorithms 257 10.8. Numeral Programming 261 Bibliography 265 Index 269 Back Cover 276