Cantitate/Preț
Produs
Total produse
Vezi coșul
An Introduction to the Analysis of Algorithms de Robert Sedgewick

An Introduction to the Analysis of Algorithms

Autor Robert Sedgewick, Philippe Flajolet
en Limba Engleză Hardback – 18 ian 2013

Descoperim în An Introduction to the Analysis of Algorithms o resursă fundamentală care necesită un nivel de experiență intermediar spre avansat, presupunând cunoștințe solide de structuri de date și un fundament matematic în calcul diferențial și algebră. Reținem că această lucrare nu se rezumă la simpla implementare, ci se concentrează pe metodele matematice necesare pentru a prezice cu precizie performanța algoritmilor în infrastructurile computaționale moderne. Structura volumului reflectă o progresie riguroasă: prima jumătate este dedicată tehnicilor de calcul, explorând ecuațiile de recurență, funcțiile generatoare și aproximările asimptotice. În a doua parte, atenția se mută către structuri specifice, precum permutările, arborii și mapările. Dacă Methods in Algorithmic Analysis de Vladimir A. Dobrushkin v-a oferit cadrul teoretic și o selecție vastă de exerciții graduate, această carte de Robert Sedgewick și Philippe Flajolet oferă instrumentele practice de modelare matematică, integrând combinatorica analitică direct în fluxul de analiză al algoritmilor. În contextul operei sale, această carte reprezintă puntea teoretică dintre volumul său aplicat, Algorithms, și cercetările de profunzime din Analytic Combinatorics. Față de abordările pedagogice din Introduction to Programming in Java, aici autorul elimină abstractizarea excesivă în favoarea unei metodologii științifice riguroase. Ediția a doua revizuită aduce un plus de claritate prin diagrame actualizate și derivări simplificate, pregătind terenul pentru studiul seriilor clasice semnate de Donald Knuth.

Citește tot Restrânge

Preț: 48035 lei

Preț vechi: 56512 lei
-15%

Puncte Express: 721

Carte tipărită la comandă

Livrare economică 03-17 iunie

 Adaugă în coș

Wish list
Gift list
Am citit!
Adaugă în listă

Specificații

ISBN-13: 9780321905758
ISBN-10: 032190575X
Pagini: 592
Dimensiuni: 192 x 238 x 40 mm
Greutate: 1.15 kg
Ediția:2nd Revised edition
Editura: Pearson Education

De ce să citești această carte

Recomandăm această carte cercetătorilor și studenților la informatică care doresc să treacă de la intuiție la predicție matematică exactă. Cititorul câștigă o înțelegere profundă a modului în care structurile de date influențează timpul de execuție și resursele utilizate. Este un titlu esențial pentru cei care vizează optimizarea sistemelor complexe și doresc să stăpânească tehnicile de analiză asimptotică și combinatorică.

Despre autor

Robert Sedgewick deține titlul de profesor „William O. Baker” în informatică la Universitatea Princeton și este o autoritate mondială în domeniul algoritmilor. Opera sa este definită de un echilibru între rigoarea matematică și aplicabilitatea practică, fiind co-autor alături de Philippe Flajolet, cel care a pus bazele combinatoricii analitice moderne. Expertiza lui Sedgewick transformă concepte matematice dense în instrumente de analiză accesibile pentru programatori.

Descriere scurtă

[Sedgewick and Flajolet] are not only worldwide leaders of the field, they also are masters of exposition. I am sure that every serious computer scientist will find this book rewarding in many ways. -From the Foreword by Donald E. Knuth Despite growing interest, basic information on methods and models for mathematically analyzing algorithms has rarely been directly accessible to practitioners, researchers, or students. An Introduction to the Analysis of Algorithms, Second Edition, organizes and presents that knowledge, fully introducing primary techniques and results in the field. Robert Sedgewick and the late Philippe Flajolet have drawn from both classical mathematics and computer science, integrating discrete mathematics, elementary real analysis, combinatorics, algorithms, and data structures. They emphasize the mathematics needed to support scientific studies that can serve as the basis for predicting algorithm performance and for comparing different algorithms on the basis of performance. Techniques covered in the first half of the book include recurrences, generating functions, asymptotics, and analytic combinatorics.Structures studied in the second half of the book include permutations, trees, strings, tries, and mappings. Numerous examples are included throughout to illustrate applications to the analysis of algorithms that are playing a critical role in the evolution of our modern computational infrastructure. Improvements and additions in this new edition include * Upgraded figures and code * An all-new chapter introducing analytic combinatorics * Simplified derivations via analytic combinatorics throughout The book's thorough, self-contained coverage will help readers appreciate the field's challenges, prepare them for advanced results-covered in their monograph Analytic Combinatorics and in Donald Knuth's Art of Computer Programming books-and provide the background they need to keep abreast of new research.

Notă biografică

Robert Sedgewick is the William O. Baker Professor of Computer Science at Princeton University, where was founding chair of the computer science department and has been a member of the faculty since 1985. He is a Director of Adobe Systems and has served on the research staffs at Xerox PARC, IDA, and INRIA. He is the coauthor of the landmark introductory book, Algorithms, Fourth Edition. Professor Sedgewick earned his Ph.D from Stanford University under Donald E. Knuth. The late Philippe Flajolet was a Senior Research Director at INRIA, Rocquencourt, where he created and led the ALGO research group. He is celebrated for having opened new lines of research in the analysis of algorithms; having systematized and developed powerful new methods in the field of analytic combinatorics; having solved numerous difficult, open problems; and having lectured on the analysis of algorithms all over the world. Dr. Flajolet was a member of the French Academy of Sciences.

Cuprins

Chapter 1: Analysis of Algorithms 3 1.1 Why Analyze an Algorithm? 3 1.2 Theory of Algorithms 6 1.3 Analysis of Algorithms 13 1.4 Average-Case Analysis 16 1.5 Example: Analysis of Quicksort 18 1.6 Asymptotic Approximations 27 1.7 Distributions 30 1.8 Randomized Algorithms 33 Chapter 2: Recurrence Relations 41 2.1 Basic Properties 43 2.2 First-Order Recurrences 48 2.3 Nonlinear First-Order Recurrences 52 2.4 Higher-Order Recurrences 55 2.5 Methods for Solving Recurrences 61 2.6 Binary Divide-and-Conquer Recurrences and Binary Numbers 70 2.7 General Divide-and-Conquer Recurrences 80 Chapter 3: Generating Functions 91 3.1 Ordinary Generating Functions 92 3.2 Exponential Generating Functions 97 3.3 Generating Function Solution of Recurrences 101 3.4 Expanding Generating Functions 111 3.5 Transformations with Generating Functions 114 3.6 Functional Equations on Generating Functions 117 3.7 Solving the Quicksort Median-of-Three Recurrence with OGFs 120 3.8 Counting with Generating Functions 123 3.9 Probability Generating Functions 129 3.10 Bivariate Generating Functions 132 3.11 Special Functions 140 Chapter 4: Asymptotic Approximations 151 4.1 Notation for Asymptotic Approximations 153 4.2 Asymptotic Expansions 160 4.3 Manipulating Asymptotic Expansions 169 4.4 Asymptotic Approximations of Finite Sums 176 4.5 Euler-Maclaurin Summation 179 4.6 Bivariate Asymptotics 187 4.7 Laplace Method 203 4.8 "Normal" Examples from the Analysis of Algorithms 207 4.9 "Poisson" Examples from the Analysis of Algorithms 211 Chapter 5: Analytic Combinatorics 219 5.1 Formal Basis 220 5.2 Symbolic Method for Unlabelled Classes 221 5.3 Symbolic Method for Labelled Classes 229 5.4 Symbolic Method for Parameters 241 5.5 Generating Function Coefficient Asymptotics 247 Chapter 6: Trees 257 6.1 Binary Trees 258 6.2 Forests and Trees 261 6.3 Combinatorial Equivalences to Trees and Binary Trees 264 6.4 Properties of Trees 272 6.5 Examples of Tree Algorithms 277 6.6 Binary Search Trees 281 6.7 Average Path Length in Catalan Trees 287 6.8 Path Length in Binary Search Trees 293 6.9 Additive Parameters of Random Trees 297 6.10 Height 302 6.11 Summary of Average-Case Results on Properties of Trees 310 6.12 Lagrange Inversion 312 6.13 Rooted Unordered Trees 315 6.14 Labelled Trees 327 6.15 Other Types of Trees 331 Chapter 7: Permutations 345 7.1 Basic Properties of Permutations 347 7.2 Algorithms on Permutations 355 7.3 Representations of Permutations 358 7.4 Enumeration Problems 366 7.5 Analyzing Properties of Permutations with CGFs 372 7.6 Inversions and Insertion Sorts 384 7.7 Left-to-Right Minima and Selection Sort 393 7.8 Cycles and In Situ Permutation 401 7.9 Extremal Parameters 406 Chapter 8: Strings and Tries 415 8.1 String Searching 416 8.2 Combinatorial Properties of Bitstrings 420 8.3 Regular Expressions 432 8.4 Finite-State Automata and the Knuth-Morris-Pratt Algorithm 437 8.5 Context-Free Grammars 441 8.6 Tries 448 8.7 Trie Algorithms 453 8.8 Combinatorial Properties of Tries 459 8.9 Larger Alphabets 465 Chapter 9: Words and Mappings 473 9.1 Hashing with Separate Chaining 474 9.2 The Balls-and-Urns Model and Properties of Words 476 9.3 Birthday Paradox and Coupon Collector Problem 485 9.4 Occupancy Restrictions and Extremal Parameters 495 9.5 Occupancy Distributions 501 9.6 Open Addressing Hashing 509 9.7 Mappings 519 9.8 Integer Factorization and Mappings 532 List of Theorems 543 List of Tables 545 List of Figures 547 Index 551