本书是国际著名算法专家李德财教授主编的系列丛书“Lecture Notes Series on
Computing”中的一本。本书涵盖了绝大多数算法设计中的一般技术，在表达每一种技术时，阐述它的应用背景，注意用与其他技术比较的方法说明它的特征，并提供大量相应实际问题的例子。本书同时也强调了对每一种算法的详细的复杂性分析。
本书包含以下几部分
基本概念和算法导引
基于递归的技术
最先割技术
问题的复杂性
克服困难性
域指定问题的迭代改进
计算几何技术
內容簡介：
本书是国际著名算法专家李德财教授主编的系列丛书“Lecture Notes Series on
Computing”中的一本。本书涵盖了绝大多数算法设计中的一般技术，在表达每一种技术时，阐述它的应用背景，注意用与其他技术比较的方法说明它的特征，并提供大量相应实际问题的例子。全书分七部分19章，从算法设计和算法分析的基本概念和方法入手，先后介绍了递归技术、分治、动态规划、贪心算法、图的遍历等技术，并且对NP完全问题进行了基本但清楚的讨论。
關於作者：
M．H．Alsuwaiyel在沙特阿拉伯的King Fahd University of
Petroleum＆MineralsKFUPM，皇家法哈德石油矿业大学完成大学学业，在南加州USC大学获得计算机科学硕士和博士学位。作者曾任KFUPM的计算机科学系主任、工程与计算机学院院长。他在沙特阿拉伯有广泛的学术影响，是政府包括内务部和国防部在内的高级顾问。
目錄：
PART 1 Basic Concepts and Introduction to Algorithms
Chapter 1 Basic Concepts in Algorithmic Analysis
1.1 Introduction
1.2 Historical Background
1.3 Binary Search
1.3.1 Analysis of the binary search algorithm
1.4 Merging Two Sorted Lists
1.5 Selection Sort
1.6 Insertion Sort
1.7 BottomJ.Jp Merge Sorting
1.7.1 Analysis of bottom-up merge sorting
1.8 Time Complexity
1.9 Space Complexity
1.10 optimal Algorithms
1.11 How to Estimate the Running Time of an Algorithm
1.12 Worst case and average case analysis
1.13 Amortized Analysis
1.14 Input Size and Problem Instance
1.15 Exercises
1.16 Bibliographic Notes
Chapter 2 Mathematical Preliminaries
2.1 Sets, Relations and Functions
2.2 Proof Methods
2.3 Logarithms
2.4 Floor and Ceiling Functions
2.5 Factorial and Binomial Coefficients
2.6 The Pigeonhole Principle
2.7 summations
2.8 Recurrence Relations
2.9 Exercises
Chapter 3 Data Structures
3.1 Introduction
3.2 LinkedLists
3.3 Graphs
3.4 Trees
3.5 RootedTYees
3.5.1 Tree traversals
3.6 Binary Trees
3.7 Exercises
3.8 Bibliographic Notes
Chapter 4 Heaps and the Disjoint Sets Data Structures
4.1 Introduction
4.2 Heaps
4.3 Disjoint Sets Data Structures
4.4 Exercises
4.5 Bibliographic Notes
PART 2 Techniques Based on Recursion
Chapter 5 Induction
5.1 Introduction
5.2 Two Simple Examples
5.3 Radix Sort
5.4 Integer Exponentiation
5.5 Evaluating Polynomials Horner’s Rule
5.6 Generating Permutations
5.7 Finding the Majority Element
5.8 Bibliographic Notes
5.9 Exercises
Chapter 6 Divide and Conquer
6.1 Introduction
6.2 Binary Search
6.3 Mergesort
6.4 Selection: Finding the Median and the kth Smallest
Element
6.5 The Divide and Conquer Paradigm
6.6 Quicksort
6.7 Multiplication of Large Integers
6.8 Matrix Multiplication
6.9 The Closest Pair Problem
6.10 Exercises
6.11 Bibliographic Notes
Chapter 7 Dynamic Programming
7.1 Introduction
7.2 The Longest Common Subsequence Problem
7.3 Matrix Chain Multiplication
7.4 The Dynamic Programming Paradigm
7.5 The All-Pairs Shortest Path Problem
7.7 Exercises
7.6 The Knapsack Problem
7.8 Bibliographic Notes
PART 3 First-Cut Techniques
Chapter 8 The Greedy Approach
8.1 Introduction
8.2 The Shortest Path Problem
8.3 Minimum Cost Spanning Trees Kruskal’s Algorithm
8.4 Minimum Cost Spanning Trees Prim’s Algorithm
8.5 File Compression
8.6 Exercises
8.7 Bibliographic Notes
Chapter 9 Graph Traversal
9.1 Introduction
9.2 Depth-First Search
9.3 Applications of Depth-First Search
9.4 Breadth-First Search
9.5 Applications of Breadth-First Search
9.6 Exercises
9.7 Bibliographic Notes
PART 4 Complexity of Problems
Chapter 10 NP-complete Problems
10.1 Introduction
10.2 The Class P
10.3 The Class NP
10.4 NP-complete Problems
10.5 The Class co-NP
10.6 The Class NPI
10.7 The Relationships Between the Four Classes
10.8 Exercises
10.9 Bibliographic Notes
Chapter 11 Introduction to Computational Complexity
11.1 Introduction
11.2 Model of Computation: The Turing Machine
11.3 k-tape Turing Machines and Time complexity
11.4 Off-Line Turing Machines and Space Complexity
11.5 Tape Compression and Linear Speed-Up
11.6 Relationships Between Complexity Classes
11.7 Reductions
11.8 Completeness
11.9 The Polynomial Time Hierarchy
11.10Exercises
11.11 Bibliographic Notes
Chapter 12 Lower Bounds
12.1 Introduction
12.2 Trivial Lower Bounds
12.3 The Decision Tree Model
12.4 The Algebraic Decision Tree Model
12.5 Linear Time Reductions
12.6 Exercises
12.7 Bibliographic Notes
PART 5 Coping with Hardness
Chapter 13 Backtracking
13.1 Introduction
13.2 The 3-Coloring Problem
13.3 The 8-Queens Problem
13.4 The General Backtracking Method
13.5 Branch and Bound
13.6 Exercises
13.7 Bibliographic notes
Chapter 14 Randomized Algorithms
14.1 Introduction
14.2 Las Vegas and Monte Carlo Algorithms
14.3 Randomized Quicksort
14.4 Randomized Selection
14.5 Testing String Equality
14.6 Pattern Matching
14.7 Random Sampling
14.8 Primality Testing
14.9 Exercises
14.10Bibliographic Notes
Chapter 15 Approximation Algorithms
15.1 Introduction
15.2 Basic Definitions
15.3 Difference Bounds
15.4 Relative Performance Bounds
15.5 Polynomial Approximation Schemes
15.6 Fully Polynomial Approximation Schemes
15.7 Exercises
15.8 Bibliographic Notes
PART 6 Iterative Improvement for Domain-Specific Problems
Chapter 16 Network Flow
16.1 Introduction
16.2 Preliminaries
16.3 The Ford-Fulkerson Method
16.4 Maximum Capacity Augmentation
16.5 Shortest Path Augmentation
16.6 Dinic’s Algorithm
16.7 The MPM Algorithm
16.8 Exercises
16.9 Bibliographic Notes
Chapter 17 Matching
17.1 Introduction
17.2 Preliminaries
17.3 The Network Flow Method
17.4 The Hungarian Tree Method for Bipartite Graphs
17.5 Maximum Matching in General Graphs
17.6 An O n2.5Algorithm for Bipartite Graphs
17.7 Exercises
17.8 Bibliographic Notes
PART 7 Techniques in Computational Geometry
Chapter 18 Geometric Sweeping
18.1 Introduction
18.2 Geometric Preliminaries
18.3 Computing the Intersections of Line Segments
18.4 The Convex Hull Problem
18.5 Computing the Diameter of a Set of Points
18.6 Exercises
18.7 Bibliographic Notes
Chapter 19 Voronoi Diagrams
19.1 Introduction
19.2 Nearest-Point Voronoi Diagram
19.3 Applications of the Voronoi Diagram
19.4 Farthest-Point Voronoi Diagram
19.5 Applications of the Farthest-Point Voronoi Diagram
19.6 Exercises
19.7 Bibliographic Notes
Bibliography
Index
購物車/收銀台(0) | 在線留言板
| 付款方式
| 運費計算
| 聯絡我們
| 幫助中心 |
加入書簽
HOME
新書上架
