书籍详情
计算机算法：设计与分析导论 英文版
作者：（美）Sara Baase，Allen Van Gelder著
出版社：高等教育出版社
出版时间：2001-01-01
ISBN：9787040100488
定价：¥39.50
购买这本书可以去
内容简介
本书的主要内容包括三部分，一是介绍了如何用算法解决在计算机应用中经常出现的现实问题，二是介绍了计算复杂性的基本原理与技术，最后讲解了NP-完备性问题及并行算法。本书强调算法设计技术，对每一个问题，首先讨论多个解决方法，然后设计、分析、修改或放弃某一算法，通过不断的深入研究，直到最后得到满意的结果。因此本书作者希望读者阅读此书，逐步培养形成一种新的分析问题的思维方式。本书在第二版的基础上，增加了三章新内容以及许多新的主题，同时对原有章节也做了重新调整。本版次还新增了100多道习题和Java实例，书中的所有程序均以Java伪码形式给出。内容：1. 算法分析原理 2. 数据抽象与基本数据结构 3. 递归与归纳 4. 分类 5. 选择 6. 动态集合与查找 7. 图与图的遍历 8. 图的优化问题与贪心算法 9. 传递闭包 10. 动态编程 11. 字符串匹配 12. 多项式与矩阵 13. NP-完备性问题 14. 并行算法 附录 Java实例与技术
作者简介
Sara Baase is professor of computer Science at San Diego University and has been teaching CS for 25years.Dr.Baase is a three-time recipient of the San State University Alumni Associations Outsatanding Faculty Award，adn she has written a number of textbooks in the areas of algorithms，assembly language，and social and ethical issues relate to computing.She earned her doctorate at the University of California，Berkeley.Allen Van Celder is professor of computer Science at the University of California at Santa Cruz，where he has been teaching CS for 12 years.He received his Ph.D.in Computer Science at Stanford University and is a past recipient of the Presidential Young Investigator Award.
目录
Contents
Preface vii
1 Analyzing Algorithms and Problems: Principles and Examples 1
1.1 Introduction 2
1.2 Java as an Algorithm Language 3
1.3 Mathematical Background 11
1.4 Analyzing Algorithms and Problems 30
1.5 Classifying Functions by Their Asymptotic Growth Rates 43
1.6 Searching an Ordered Array 53
Exercises 61
Notes and References 67
2 Data Abstraction and Basic Data Structures 69
2.1 Introduction 70
2.2 ADT Specification and Design Techniques 71
2.3 Elementary ADTs--Lists and Trees 73
2.4 Stacks and Queues 86
2.5 ADTs for Dynamic Sets 89
Exercises 95
Notes and References 100
3 Recursion and induction 101
3.1 introduction 102
3.2 Recursive Procedures 102
3.3 What is a Proof? 108
3.4 Induction Proofs 111
3.5 Proving Correctness of Procedures 1 18
3.6 Recurrence Equations 130
3.7 Recursion Trees 134
Exercises 141
Notes and References 146
4 Sorting 149
4.1 Introduction 150
4.2 Insertion Sort 151
4.3 Divide and Conquer 157
4.4 Quicksort 159
4.5 Merging Sorted Sequences 171
4.6 Mergesort 174
4.7 Lower Bounds for Sorting by Comparison of Keys 178
4.8 Heapsort 182
4.9 Comparison of Four Sorting Algorithms 197
4.10 Shellsort 197
4.11 Radix Sorting 201
Exercises 206
Programs 221
Notes and References 221
5 Selection and Adversary Arguments 223
5.1 Introduction 224
5.2 Finding max and min 226
5.3 Finding the Second-Largest Key 229
5.4 The Selection Problem 233
5.5 A Lower Bound for Finding the Median 238
5.6 Designing Against an Adversary 240
Exercises 242
Notes and References 246
6 Dynamic Sets and Searching 249
6.1 Introduction 250
6.2 Array Doubling 250
6.3 Amortized Time Analysis 251
6.4 Red-Black Trees 253
6.5 Hashing 275
6.6 Dynamic Equivalence Relations and Union-Find Programs 283
6.7 Priority Queues with a Decrease Key Operation 295
Exercises 302
Programs 309
Notes and References 309
7 Graphs and Graph Traversals 313
7.1 Introduction 314
7.2 Definitions and Representations 314
7.3 Traversing Graphs 328
7.4 Depth-First Search on Directed Graphs 336
7.5 Strongly Connected Components of a Directed Graph 357
7.6 Depth-First Search on Undirected Graphs 364
7.7 Biconnected Components of an Undirected Graph 366
Exercises 375
Programs 384
Notes and References 385
8 Graph Optimization Problems and Greedy Algorithms 387
8.1 Introduction 388
8.2 Prim's Minimum Spanning Tree Algorithm 388
8.3 Single-Source Shortest Paths 403
8.4 Kruskal's Minimum Spanning Tree Algorithm 412
Exercises 416
Programs 421
Notes and References 422
9 Transitive Closure, All-Pairs Shortest Paths 425
9.1 Introduction 426
9.2 The Transitive Closure of a Binary Relation 426
9.3 Warshall's Algorithm for Transitive Closure 430
9.4 All-Pairs Shortest Paths in Graphs 433
9.5 Computing Transitive Closure by Matrix Operations 436
9.6 Multiplying Bit Matrices-Kronrod's Algorithm 439
Exercises 446
Programs 449
Notes and References 449
10 Dynamic Programming 451
10.1 Introduction 452
10.2 Subproblem Graphs and Their Traversal 453
10.3 Multiplying a Sequence of Matrices 457
10.4 Constructing Optimal Binary Search Trees 466
10.5 Separating Sequences of Words into Lines 471
10.6 Developing a Dynamic Programming Algorithm 474
Exercises 475
Programs 481
Notes and References 482
11 String Matching 483
11.1 Introduction 484
11.2 A Straightforward Solution 485
11.3 The Knuth-Moms-Pratt Algorithm 487
11.4 The Boyer-Moors Algorithm 495
11.5 Approximate String Matching 504
Exercises 508
Programs 512
Notes and References 512
12 Polynomials and Matrices 515
12.1 Introduction 516
12.2 Evaluating Polynomial Functions 516
12.3 Vector and Matrix Multiplication 522
12.4 The Fast Fourier Transform and Convolution 528
Exercises 542
Programs 546
Notes and References 546
13 NP-Complete Problems 547
13.1 Introduction 548
13.2 T and ac 548
13.3 NP-Complete Problems 559
13.4 Approximation Algorithms 570
13.5 Bin Packing 572
13.6 The Knapsack and Subset Sum Problems 577
13.7 Graph Coloring 581
13.8 The Traveling Salesperson Problem 589
13.9 Computing with DNA 592
Exercises 600
Notes and References 608
14 Parallel Algorithms 611
14.1 Introduction 612
14.2 Parallelism, the PRAM, and Other Models 612
14.3 Some Simple PRAM Algorithms 616
14.4 Handling Write Conflicts 622
14.5 Merging and Sorting 624
14.6 Finding Connected Components 628
14.7 A Lower Bound for Adding n Integers 641
Exercises 643
Notes and References 647
A Java Examples and Techniques 649
A.1 introduction 650
A.2 A Java Main Program 651
A.3 A Simple input Library 656
A.4 Documenting Java Classes 658
A.5 Generic Order and the "Comparable" Interface 659
A.6 Subclasses Extend the Capability of Their Superclass 663
A.7 Copy via the "Cloneable" Interface 667
Bibliography 669
Index 679
Preface vii
1 Analyzing Algorithms and Problems: Principles and Examples 1
1.1 Introduction 2
1.2 Java as an Algorithm Language 3
1.3 Mathematical Background 11
1.4 Analyzing Algorithms and Problems 30
1.5 Classifying Functions by Their Asymptotic Growth Rates 43
1.6 Searching an Ordered Array 53
Exercises 61
Notes and References 67
2 Data Abstraction and Basic Data Structures 69
2.1 Introduction 70
2.2 ADT Specification and Design Techniques 71
2.3 Elementary ADTs--Lists and Trees 73
2.4 Stacks and Queues 86
2.5 ADTs for Dynamic Sets 89
Exercises 95
Notes and References 100
3 Recursion and induction 101
3.1 introduction 102
3.2 Recursive Procedures 102
3.3 What is a Proof? 108
3.4 Induction Proofs 111
3.5 Proving Correctness of Procedures 1 18
3.6 Recurrence Equations 130
3.7 Recursion Trees 134
Exercises 141
Notes and References 146
4 Sorting 149
4.1 Introduction 150
4.2 Insertion Sort 151
4.3 Divide and Conquer 157
4.4 Quicksort 159
4.5 Merging Sorted Sequences 171
4.6 Mergesort 174
4.7 Lower Bounds for Sorting by Comparison of Keys 178
4.8 Heapsort 182
4.9 Comparison of Four Sorting Algorithms 197
4.10 Shellsort 197
4.11 Radix Sorting 201
Exercises 206
Programs 221
Notes and References 221
5 Selection and Adversary Arguments 223
5.1 Introduction 224
5.2 Finding max and min 226
5.3 Finding the Second-Largest Key 229
5.4 The Selection Problem 233
5.5 A Lower Bound for Finding the Median 238
5.6 Designing Against an Adversary 240
Exercises 242
Notes and References 246
6 Dynamic Sets and Searching 249
6.1 Introduction 250
6.2 Array Doubling 250
6.3 Amortized Time Analysis 251
6.4 Red-Black Trees 253
6.5 Hashing 275
6.6 Dynamic Equivalence Relations and Union-Find Programs 283
6.7 Priority Queues with a Decrease Key Operation 295
Exercises 302
Programs 309
Notes and References 309
7 Graphs and Graph Traversals 313
7.1 Introduction 314
7.2 Definitions and Representations 314
7.3 Traversing Graphs 328
7.4 Depth-First Search on Directed Graphs 336
7.5 Strongly Connected Components of a Directed Graph 357
7.6 Depth-First Search on Undirected Graphs 364
7.7 Biconnected Components of an Undirected Graph 366
Exercises 375
Programs 384
Notes and References 385
8 Graph Optimization Problems and Greedy Algorithms 387
8.1 Introduction 388
8.2 Prim's Minimum Spanning Tree Algorithm 388
8.3 Single-Source Shortest Paths 403
8.4 Kruskal's Minimum Spanning Tree Algorithm 412
Exercises 416
Programs 421
Notes and References 422
9 Transitive Closure, All-Pairs Shortest Paths 425
9.1 Introduction 426
9.2 The Transitive Closure of a Binary Relation 426
9.3 Warshall's Algorithm for Transitive Closure 430
9.4 All-Pairs Shortest Paths in Graphs 433
9.5 Computing Transitive Closure by Matrix Operations 436
9.6 Multiplying Bit Matrices-Kronrod's Algorithm 439
Exercises 446
Programs 449
Notes and References 449
10 Dynamic Programming 451
10.1 Introduction 452
10.2 Subproblem Graphs and Their Traversal 453
10.3 Multiplying a Sequence of Matrices 457
10.4 Constructing Optimal Binary Search Trees 466
10.5 Separating Sequences of Words into Lines 471
10.6 Developing a Dynamic Programming Algorithm 474
Exercises 475
Programs 481
Notes and References 482
11 String Matching 483
11.1 Introduction 484
11.2 A Straightforward Solution 485
11.3 The Knuth-Moms-Pratt Algorithm 487
11.4 The Boyer-Moors Algorithm 495
11.5 Approximate String Matching 504
Exercises 508
Programs 512
Notes and References 512
12 Polynomials and Matrices 515
12.1 Introduction 516
12.2 Evaluating Polynomial Functions 516
12.3 Vector and Matrix Multiplication 522
12.4 The Fast Fourier Transform and Convolution 528
Exercises 542
Programs 546
Notes and References 546
13 NP-Complete Problems 547
13.1 Introduction 548
13.2 T and ac 548
13.3 NP-Complete Problems 559
13.4 Approximation Algorithms 570
13.5 Bin Packing 572
13.6 The Knapsack and Subset Sum Problems 577
13.7 Graph Coloring 581
13.8 The Traveling Salesperson Problem 589
13.9 Computing with DNA 592
Exercises 600
Notes and References 608
14 Parallel Algorithms 611
14.1 Introduction 612
14.2 Parallelism, the PRAM, and Other Models 612
14.3 Some Simple PRAM Algorithms 616
14.4 Handling Write Conflicts 622
14.5 Merging and Sorting 624
14.6 Finding Connected Components 628
14.7 A Lower Bound for Adding n Integers 641
Exercises 643
Notes and References 647
A Java Examples and Techniques 649
A.1 introduction 650
A.2 A Java Main Program 651
A.3 A Simple input Library 656
A.4 Documenting Java Classes 658
A.5 Generic Order and the "Comparable" Interface 659
A.6 Subclasses Extend the Capability of Their Superclass 663
A.7 Copy via the "Cloneable" Interface 667
Bibliography 669
Index 679
猜您喜欢
