书籍详情
算法设计与分析导论（英文版）
作者：李家同 等著
出版社：机械工业出版社
出版时间：2007-02-01
ISBN：9787111208211
定价：¥69.00
购买这本书可以去
内容简介
通信网络设计，VLSI布局和DNA序列分析，都是重要而有难度的问题，无法单靠初级算法解决。因此，对于计算机科学家来说，有一个良好的算法设计和分析的知识系统是十分重要的。本书从策略的角度来描述算法设计。每个策略下都包含了许多基于此策略的算法设计，而且对子每个算法，都有丰富的实例对其进行诠释。另外，每个例子中都带有很多图示。.近年来，许多近似算法相继开发出来。本书清晰地描述了两个重要概念：PTAS和NPO-complete。另外，本书第12章还介绍了联机算法，每个联机算法都是通过先描述其内在的基本原理来展开介绍的。“平摊分析”是算法研究的一个新领域，本书对这个不易理解的新概念也进行了详细的介绍。..本书可以作为计算机专业本科生或硕士研究生的教材使用。...
作者简介
本书提供作译者介绍R．C．T．Lee（李家同）台湾“暨南大学”教授。李教授是美国电机电子学会的荣誉会士，并且曾担任过11种国际学术刊物的编辑委员。他在算法和逻辑方面的著作曾被译为多种文字出版。同时，李教授也是短篇小说作家，他的小说亲切、自然、发人深省，曾感动了无数人。.S．S．Tseng（曾宪雄）和R．C．Chang（张瑞川）台湾交通大学计算机与信息科学系教授。..Y．T．Tsai（蔡英德）台湾静宜大学信息传播工程学系教授兼系主任。...
目录
Preface
List of Figures
Chapter 1 INTRODUCTION
Chapter 2 THE COMPLEXITY OF ALGORITHMS AND THE LOWER BOUNDS OF PROBLEMS
2-1 The time complexity of an algorithm
2-2 The best-, average- and worst-case analysis of algorithms
2-3 The lower bound of a problem
2-4 The worst-case lower bound of sorting
2-5 Heap sort: A sorting algorithm which is optimal in worst cases
2-6 The average-case lower bound of sorting
2-7 Improving a lower bound through oracles
2-8 Finding the lower bound by problem transformation
2-9 Notes and references
2-10 Further reading materials
Exercises
Chapter 3 THE GREEDY METHOD
3-1 Kruskal's method to find a minimum spanning tree
3-2 Prim's method to find a minimum spanning tree
3-3 The single-source shortest path problem
3-4 The 2-way merge problem
3-5 The minimum cycle basis problem solved by the greedy algorithm
3-6 The 2-terminal one to any problem solved by the greedy method
3-7 The minimum cooperative guards problem for 1-spiral polygons solved by the greedy method
3-8 The experimental results
3-9 Notes and references
3-10 Further reading materials
Exercises
Chapter 4 THE DIVIDE-AND-CONQUER STRATEGY
4-1 The 2-dimensional maxima finding problem
4-2 The closest pair problem
4-3 The convex hull problem
4-4 The Voronoi diagrams constructed by the divide-and-conquer strategy
4-5 Applications of the Voronoi diagrams
4-6 The Fast Fourier Transform
4-7 The experimental results
4-8 Notes and references
4-9 Further reading materials
Exercises
Chapter 5 TREE SEARCHING STRATEGIES
5-1 Breadth-first search
5-2 Depth-first search
5-3 Hill climbing
5-4 Best-fIRst search strategy
5-5 Branch-and-bound strategy
5-6 A personnel assignment problem solved by the branch-and-bound strategy
5-7 The traveling salesperson optimization problem solved by the branch-and-bound strategy
5-8 The 0/1 knapsack problem solved by the branch-and-bound strategy
5-9 A job scheduling problem solved by the branch-and-bound approach
5-10 A* algorithm
5-11 A channel routing problem solved by a specialized A* algorithm
5-12 The linear block code decoding problem solved by the A* algorithm
5-13 The experimental results
5-14 Notes and references
5-15 Further reading materials
Exercises
Chapter 6 PRUNE-AND-SEARCH
6-1 The general method
6-2 The selection problem
6-3 Linear programming with two variables
6-4 The 1-center problem
6-5 The experimental results
6-6 Notes and references
6-7 Further reading materials
Exercises..
Chapter 7 DYNAMIC PROGRAMMING
7-1 The resource allocation problem
7-2 The longest common subsequence problem
7-3 The 2-sequence alignment problem
7-4 The RNA maximum base pair matching problem
7-5 0/1 knapsack problem
7-6 The optimal binary tree problem
7-7 The weighted perfect domination problem on trees
7-8 The weighted single step graph edge searching problem on trees
7-9 The m-watchmen routes problem for 1-spiral polygons solved by the dynamic programming approach
7-10 The experimental results
7-11 Notes and references
7-12 Further reading materials
Exercises
Chapter 8 THE THEORY OF NP-COMPLETENESS
8-1 An informal discussion of the theory of NP-completeness
8-2 The decision problems
8-3 The satisfiability problem
8-4 The NP problems
8-5 Cook's theorem
8-6 NP-complete problems
8-7 Examples of proving NP-completeness
8-8 The 2-satisfiability problem
8-9 Notes and references
8-10 Further reading materials
Exercises
Chapter 9 APPROXIMATION ALGORITHMS
9-1 An approximation algorithm for the node cover problem
9-2 An approximation algorithm for the Euclidean traveling salesperson problem
9-3 An approximation algorithm for a special bottleneck traveling salesperson problem
9-4 An approximation algorithm for a special bottleneck weighted k-supplier problem
9-5 An approximation algorithm for the bin packing problem
9-6 An optimal approximation algorithm for the rectilinear m-center problem
9-7 An approximation algorithm for the multiple sequence alignment problem
9-8 A 2-approximation algorithm for the sorting by transposition problem
9-9 The polynomial time approximation scheme
9-10 A 2-approximation algorithm for the minimum routing Cost spanning tree problem
9-11 A PTAS for the minimum routing cost spanning tree problem
9-12 NPO-completeness
9-13 Notes and references
9-14 Further reading materials
Exercises
Chapter 10 AMORTIZED ANALYSIS
10-1 An example of using the potential function
10-2 An amortized analysis of skew heaps
10-3 Amortized analysis of AVL-trees
10-4 Amortized analysis of self-organizing sequential search heuristics
10-5 Pairing heap and its amortized analysis
10-6 Amortized analysis of a disjoint set union algorithm
10-7 Amortized analysis of some disk scheduling algorithms
10-8 The experimental results
10-9 Notes and references
10-10 Further reading materials
Exercises
Chapter 11 RANDOMIZED ALGORITHMS
11-1 A randomized algorithm to solve the closest pair problem
11-2 The average performance of the randomized closest pair problem
11-3 A randomized algorithm to test whether a number is a prime
11-4 A randomized algorithm for pattern matching
11-5 A randomized algorithm for interactive proofs
11-6 A randomized linear time algorithm for minimum spanning trees
11-7 Notes and references
11-8 Further reading materials
Exercises
Chapter 12 ON-LINE ALGORITHMS
12-1 The on-line Euclidean spanning tree problem solved by the greedy method
12-2 The on-line k-server problem and a greedy algorithm to solve this problem defined on planar trees
12-3 An on-line obstacle traversal algorithm based on the balance strategy
12-4 The on-line bipartite matching problem solved by the compensation strategy
12-5 The on-line m-machine problem solved by the moderation strategy
12-6 On-line algorithms for three computational geometry problems based on the elimination strategy
12-7 An on-line spanning tree algorithm based on the randomization strategy
12-8 Notes and references
12-9 Further reading materials
Exercises
BIBLIOGRAPHY
auTHOR INDEX
SUBJECT INDEX
List of Figures
Chapter 1 INTRODUCTION
Chapter 2 THE COMPLEXITY OF ALGORITHMS AND THE LOWER BOUNDS OF PROBLEMS
2-1 The time complexity of an algorithm
2-2 The best-, average- and worst-case analysis of algorithms
2-3 The lower bound of a problem
2-4 The worst-case lower bound of sorting
2-5 Heap sort: A sorting algorithm which is optimal in worst cases
2-6 The average-case lower bound of sorting
2-7 Improving a lower bound through oracles
2-8 Finding the lower bound by problem transformation
2-9 Notes and references
2-10 Further reading materials
Exercises
Chapter 3 THE GREEDY METHOD
3-1 Kruskal's method to find a minimum spanning tree
3-2 Prim's method to find a minimum spanning tree
3-3 The single-source shortest path problem
3-4 The 2-way merge problem
3-5 The minimum cycle basis problem solved by the greedy algorithm
3-6 The 2-terminal one to any problem solved by the greedy method
3-7 The minimum cooperative guards problem for 1-spiral polygons solved by the greedy method
3-8 The experimental results
3-9 Notes and references
3-10 Further reading materials
Exercises
Chapter 4 THE DIVIDE-AND-CONQUER STRATEGY
4-1 The 2-dimensional maxima finding problem
4-2 The closest pair problem
4-3 The convex hull problem
4-4 The Voronoi diagrams constructed by the divide-and-conquer strategy
4-5 Applications of the Voronoi diagrams
4-6 The Fast Fourier Transform
4-7 The experimental results
4-8 Notes and references
4-9 Further reading materials
Exercises
Chapter 5 TREE SEARCHING STRATEGIES
5-1 Breadth-first search
5-2 Depth-first search
5-3 Hill climbing
5-4 Best-fIRst search strategy
5-5 Branch-and-bound strategy
5-6 A personnel assignment problem solved by the branch-and-bound strategy
5-7 The traveling salesperson optimization problem solved by the branch-and-bound strategy
5-8 The 0/1 knapsack problem solved by the branch-and-bound strategy
5-9 A job scheduling problem solved by the branch-and-bound approach
5-10 A* algorithm
5-11 A channel routing problem solved by a specialized A* algorithm
5-12 The linear block code decoding problem solved by the A* algorithm
5-13 The experimental results
5-14 Notes and references
5-15 Further reading materials
Exercises
Chapter 6 PRUNE-AND-SEARCH
6-1 The general method
6-2 The selection problem
6-3 Linear programming with two variables
6-4 The 1-center problem
6-5 The experimental results
6-6 Notes and references
6-7 Further reading materials
Exercises..
Chapter 7 DYNAMIC PROGRAMMING
7-1 The resource allocation problem
7-2 The longest common subsequence problem
7-3 The 2-sequence alignment problem
7-4 The RNA maximum base pair matching problem
7-5 0/1 knapsack problem
7-6 The optimal binary tree problem
7-7 The weighted perfect domination problem on trees
7-8 The weighted single step graph edge searching problem on trees
7-9 The m-watchmen routes problem for 1-spiral polygons solved by the dynamic programming approach
7-10 The experimental results
7-11 Notes and references
7-12 Further reading materials
Exercises
Chapter 8 THE THEORY OF NP-COMPLETENESS
8-1 An informal discussion of the theory of NP-completeness
8-2 The decision problems
8-3 The satisfiability problem
8-4 The NP problems
8-5 Cook's theorem
8-6 NP-complete problems
8-7 Examples of proving NP-completeness
8-8 The 2-satisfiability problem
8-9 Notes and references
8-10 Further reading materials
Exercises
Chapter 9 APPROXIMATION ALGORITHMS
9-1 An approximation algorithm for the node cover problem
9-2 An approximation algorithm for the Euclidean traveling salesperson problem
9-3 An approximation algorithm for a special bottleneck traveling salesperson problem
9-4 An approximation algorithm for a special bottleneck weighted k-supplier problem
9-5 An approximation algorithm for the bin packing problem
9-6 An optimal approximation algorithm for the rectilinear m-center problem
9-7 An approximation algorithm for the multiple sequence alignment problem
9-8 A 2-approximation algorithm for the sorting by transposition problem
9-9 The polynomial time approximation scheme
9-10 A 2-approximation algorithm for the minimum routing Cost spanning tree problem
9-11 A PTAS for the minimum routing cost spanning tree problem
9-12 NPO-completeness
9-13 Notes and references
9-14 Further reading materials
Exercises
Chapter 10 AMORTIZED ANALYSIS
10-1 An example of using the potential function
10-2 An amortized analysis of skew heaps
10-3 Amortized analysis of AVL-trees
10-4 Amortized analysis of self-organizing sequential search heuristics
10-5 Pairing heap and its amortized analysis
10-6 Amortized analysis of a disjoint set union algorithm
10-7 Amortized analysis of some disk scheduling algorithms
10-8 The experimental results
10-9 Notes and references
10-10 Further reading materials
Exercises
Chapter 11 RANDOMIZED ALGORITHMS
11-1 A randomized algorithm to solve the closest pair problem
11-2 The average performance of the randomized closest pair problem
11-3 A randomized algorithm to test whether a number is a prime
11-4 A randomized algorithm for pattern matching
11-5 A randomized algorithm for interactive proofs
11-6 A randomized linear time algorithm for minimum spanning trees
11-7 Notes and references
11-8 Further reading materials
Exercises
Chapter 12 ON-LINE ALGORITHMS
12-1 The on-line Euclidean spanning tree problem solved by the greedy method
12-2 The on-line k-server problem and a greedy algorithm to solve this problem defined on planar trees
12-3 An on-line obstacle traversal algorithm based on the balance strategy
12-4 The on-line bipartite matching problem solved by the compensation strategy
12-5 The on-line m-machine problem solved by the moderation strategy
12-6 On-line algorithms for three computational geometry problems based on the elimination strategy
12-7 An on-line spanning tree algorithm based on the randomization strategy
12-8 Notes and references
12-9 Further reading materials
Exercises
BIBLIOGRAPHY
auTHOR INDEX
SUBJECT INDEX
猜您喜欢
