算法设计技巧与分析. 英文版 (清晰版)
|
|
|
【推荐级别】
|
☆☆☆☆☆
查看网友评价 |
|
【下载次数】 |
225 次 |
|
【作者】 |
M. H. Alsuwaiyel (阿苏外耶)
|
【出版社】 |
电子工业出版社, World Scientific Publishing Compan
|
|
【文件格式】 |
PDF
|
【ISBN】 |
7-5053-8084-2
|
|
【资料语言】 |
英文
|
【文件大小】 |
25.38MB
|
|
【上传时间】 |
2008-05-10
|
【共享者】 |
greatcode
查看他还共享了哪些书籍
|
|
|
资料说明：
|
--------------------------------
算法设计技巧与分析. 英文版 (清晰版)
--------------------------------
作 者: (沙特)阿苏外耶 著
出 版 社: 电子工业出版社
出版时间: 2003-1-1
字 数: 531000
版 次: 1
页 数: 540
纸 张: 胶版纸
I S B N : 7-5053-8084-2
包 装: 平装
编辑推荐
全书分七部分19章，从算法设计和算法分析的基本概念和方法入手，先后介绍了递归技术、分治、动态规划、贪心算法、图的遍历等技术，对NP完全问题进行了基本但清楚的讨论。对概率算法、近似算法和计算几何这些近年来发展迅猛的领域也用一定的篇幅讲述了基本内容。书中每章后都附有大量的练习题，有利于读者对书中内容的理解和应用。
内容简介
本书是国际著名算法专家李德财教授主编的系列丛书 "Lecture Notes Series on Computing" 中的一本。本书涵盖了绝大多数算法设计中的一般技术，在表达每一种技术时，阐述它的应用背景，注意用与其他技术比较的方法说明它的特征，并提供大量相应实际问题的例子。本书同时也强调了对每一种算法的详细的复杂性分析。全书分七部分19章，从算法设计和算法分析的基本概念和方法入手，先后介绍了递归技术、分治、动态规划、贪心算法、图的遍历等技术，对NP完全问题进行了基本但清楚的讨论。对概率算法、近似算法和计算几何这些近年来发展迅猛的领域也用一定的篇幅讲述了基本内容。书中每章后都附有大量的练习题，有利于读者对书中内容的理解和应用。
本书结构简明，内容丰富，适合于作为计算机学科以及相关学科算法课程的教材和参考书，尤其适宜于学过数据结构和离散数学课程之后的算法课教材。同时也可作为从事算法研究的一本好的入门书。
前言摘要
多年来，我一直想录找一本适合中国计算机系学生用的算法方面的国外教材。尽管有些不错的国外教材在中国出版，但总有篇幅过多、内容略显陈旧或数据结构内容夹杂其中等等这样或那样的不甚满意之处。 去年我有幸看到世界科学图书出版社出版的由M．H．Alsuwaiyel撰写的《Algorithms Design Techniques and Analysis》，它是以国际著名算法专家，我国台湾出身的李德财教授所主编的系列丛书——Lecture Notes Series on Computing——中的一本。虽然此书不是美国的大学教材，而是沙特阿拉伯的大学计算机系教材。但是我很快就被该书的组织简明、概括，且包含当前市面上算法一＃较少涉及的概率算法和近似算法..
目录
第一部分 基本概念和算法导引
第1章 算法分析基本概念
第2章 数学预备知识
第3章 数据结构
第4章 堆和不相交集数据结构
第二部分 基于递归的技术
第5章 归纳法
第6章 分治
第7章 动态规划
第三部分 最先割技术
第8章 念心算法
第9章 图的遍历
第四部 问题复杂性
第10章 NP完全问题
第11章 计算机杂性引论
第12章 下界
第五部分 克服困难性
第13章 回溯法
第14章 随机算法
第15章 近似算法
第六部分 域指定问题的迭代改进
第16章 网络流
第17章 匹配
第七部分 计算几何技术
第18章 几何扫描
第19章 Voronoi图解
参考文献
-------------------------------------------
Algorithms Design Techniques and Analysis
-------------------------------------------
Author: M. H. Alsuwaiyel
Publisher: World Scientific Publishing Company
Number Of Pages: 540
Publication Date: 1998-11
ISBN-10/ASIN: 9810237405
ISBN-13/EAN: 9789810237400
Binding: Hardcover
Summary: A "MUST" book for any Computer Science student
Rating: 5
I have been using this book as a second reference in my Algorithm
Engineering class during the whole semester. I found it extremely useful for its nice structure, content and diversity of subjects treated, especially the ones in computational geometry such as Geometric Sweeping and Voronoi diagrams, for instance. I believe this book should be useful to any student taking algorithms class for its structureness, clearness, and completeness.
Summary: From M. H. Suwaiyel's student
Rating: 5
I have studied both undergrad and grad algorithm courses from this book at KFUPM. For a beginner, the author provides a moderate level of mathematical analysis which helps in building a solid foundation, but avoids minor details that may obscure the overall grasp of the subject. The Exercise sets at the end of each chapter vary from easy to challenging....
Summary: An excellent book on algorithm analysis
Rating: 5
The book represents a well written, consistent and easy to follow view on the area of algorithm analysis. It gives an excellent overview of various mathematical and computer science areas, including but not limited to combinatorial geometry, NP-problems, complexity theory, graph theory, algorithm analysis, dynamic programming and even computational geometry.
Most of the chapters are intended for a senior level undergraduate and graduate student, but some (such as part 4 devoted to complexity problems) are more suitable for "mature" audience and require some preliminary knowledge in the area.
I found chapters on sorting, data structures, recursion and functional programming well written and structured, and examples to be practical as well as informative.
Sections on amortized analysis, randomized algorithms, approximation algorithms and iteration improvement deal with current directions in the algorithmic research and provide an excellent overview of the "state-of-the-art" in these areas. I also enjoyed reading through the section on greedy algorithms (shortest path and minimum spanning tree problems).
Section on computational complexity and analysis of the relationship between complexity classes seems to be a bit complicated, those who are interested in this area should probably do some preliminary reading.
The last section on computational geometry (my area of expertise) and applications of Voronoi diagrams could be extended, but even in the current state it givs a pretty good idea of what computational geometry is all about.
Overall, I give to this book a "5 star" review and recommend it for anyone who is seriously interested in learning exactly how algorithm design and analysis work. I thoroughly enjoyed reading this book and can only wish that author would write more books like that in the future!
Summary: Better than the other books.. but not perfect
Rating: 4
This is a great book overall, but I give it 4 stars as it lacks the mathematical explanations that I personally was looking for. I am graduate student in Computer Science and a E-Commerce Consultant by profession. This book is more detailed than the Sedweick (I can't spell his name) in the sense that it has some more of a mathematical approach. It lacks the level of explanation that the Sedweick book provided. It has some math, but overlooks some steps thus targeting someone with a pretty solid math background, not someone with sophomore level undergraduate math background.
Overall.. if you're a student taking an algorithms or advanced algorithms class (especially a graduate class), you might want to invest in this book.
Contents
Preface
PART 1 Basic Concepts and Introduction to Algorithms 1
Chapter 1 Basic Concepts in Algorithmic Analysis 5
1.1 Introduction 5
1.2 Historical Background 6
1.3 Binary Search 8
1.3.1 Analysis of the binary search algorithm 10
1.4 Merging Two Sorted Lists 12
1.5 Selection Sort 14
1.6 Insertion Sort 15
1.7 Bottom-Up Merge Sorting 17
1.7.1 Analysis of bottom-up merge sorting 19
1.8 Time Complexity 20
1.8.1 Order of growth 21
1.8.2 The O-notation 25
1.8.3 The Ω-notation 26
1.8.4 The θ-notation 27
1.8.5 Examples 29
1.8.6 Complexity classes and the o-notation 31
1.9 Space Complexity 32
1.10 Optimal Algorithms 34
1.11 How to Estimate the Running Time of an Algorithm 35
1.11.1 Counting the number of iterations 35
1.11.2 Counting the frequency of basic operations 38
1.11.3 Using recurrence relations 41
1.12 Worst case and average case analysis 42
1.12.1 Worst case analysis 44
1.12.2 Average case analysis 46
1.13 Amortized Analysis 47
1.14 Input Size and Problem Instance 50
1.15 Exercises 52
1.16 Bibliographic Notes 59
Chapter 2 Mathematical Preliminaries 61
2.1 Sets, Relations and Functions 61
2.1.1 Sets 62
2.1.2 Relations 63
2.1.2.1 Equivalence relations 64
2.1.3 Functions 64
2.2 Proof Methods 65
2.2.1 Direct proof 65
2.2.2 Indirect proof 66
2.2.3 Proof by contradiction 66
2.2.4 Proof by counterexample 67
2.2.5 Mathematical induction 68
2.3 Logarithms 69
2.4 Floor and Ceiling Functions 70
2.5 Factorial and Binomial Coefficients 71
2.5.1 Factorials 71
2.5.2 Binomial coefficients 73
2.6 The Pigeonhole Principle 75
2.7 Summations 76
2.7.1 Approximation of summations by integration 78
2.8 Recurrence Relations 82
2.8.1 Solution of linear homogeneous recurrences 83
2.8.2 Solution of inhomogeneous recurrences 85
2.8.3 Solution of divide-and-conquer recurrences 87
2.8.3.1 Expanding the recurrence 87
2.8.3.2 Substitution 91
2.8.3.3 Change of variables 95
2.9 Exercises 98
Chapter 3 Data Structures 103
3.1 Introduction 103
3.2 Linked Lists 103
3.2.1 Stacks and queues 104
3.3 Graphs 104
3.3.1 Representation of graphs 106
3.3.2 Planar graphs 107
3.4 Trees 108
3.5 Rooted Trees 108
3.5.1 Tree traversals 109
3.6 Binary Trees 109
3.6.1 Some quantitative aspects of binary trees 111
3.6.2 Binary search trees 112
3.7 Exercises 112
3.8 Bibliographic Notes 114
Chapter 4 Heaps and the Disjoint Sets Data Structures 115
4.1 Introduction 115
4.2 Heaps 115
4.2.1 Operations on heaps 116
4.2.2 Creating a heap 120
4.2.3 Heapsort 124
4.2.4 Min and max heaps 125
4.3 Disjoint Sets Data Structures 125
4.3.1 The union by rank heuristic 127
4.3.2 Path compression 129
4.3.3 The union-find algorithms 130
4.3.4 Analysis of the union-find algorithms 132
4.4 Exercises 134
4.5 Bibliographic Notes 137
PART 2 Techniques Based on Recursion 139
Chapter 5 Induction 143
5.1 Introduction 143
5.2 Two Simple Examples 144
5.2.1 Selection sort 144
5.2.2 Insertion sort 145
5.3 Radix Sort 145
5.4 Integer Exponentiation 148
5.5 Evaluating Polynomials(Horner s Rule) 149
5.6 Generating Permutations 150
5.6.1 The first algorithm 150
5.6.2 The second algorithm 152
5.7 Finding the Majority Element 154
5.8 Exercises 155
5.9 Bibliographic Notes 158
Chapter 6 Divide and Conquer 161
6.1 Introduction 161
6.2 Binary Search 163
6.3 Mergesort 165
6.3.1 How the algorithm works 166
6.3.2 Analysis of the mergesort algorithm 167
6.4 The Divide and Conquer Paradigm 169
6.5 Selection: Finding the Median and the kth Smallest Element 172
6.5.1 Analysis of the selection algorithm 175
6.6 Quicksort 177
6.6.1 A partitioning algorithm 177
6.6.2 The sorting algorithm 179
6.6.3 Analysis of the quicksort algorithm 181
6.6.3.1 The worst case behavior 181
6.6.3.2 The average case behavior 184
6.6.4 Comparison of sorting algorithms 186
6.7 Multiplication of Large Integers 187
6.8 Matrix Multiplication 188
6.8.1 The traditional algorithm 188
6.8.2 Recursive version 188
6.8.3 Strassen s algorithm 190
6.8.4 Comparisons of the three algorithms 191
6.9 The Closest Pair Problem 192
6.9.1 Time complexity 194
6.10 Exercises 195
6.11 Bibliographic Notes 202
Chapter 7 Dynamic Programming 203
7.1 Introduction 203
7.2 The Longest Common Subsequence Problem 205
7.3 Matrix Chain Multiplication 208
7.4 The Dynamic Programming Paradigm 214
7.5 The All-Pairs Shortest Path Problem 215
7.6 The Knapsack Problem 217
7.7 Exercises 220
7.8 Bibliographic Notes 226
PART 3 First-Cut Techniques 227
Chapter 8 The Greedy Approach 231
8.1 Introduction 231
8.2 The Shortest Path Problem 232
8.2.1 A linear time algorithm for dense graphs 237
8.3 Minimum Cost Spanning Trees (Kruskal s Algorithm) 239
8.4 Minimum Cost Spanning Trees (Prim s Algorithm) 242
8.4.1 A linear time algorithm for dense graphs 246
8.5 File Compression 248
8.6 Exercises 251
8.7 Bibliographic Notes 255
Chapter 9 Graph Traversal 257
9.1 Introduction 257
9.2 Depth-First Search 257
9.2.1 Time-complexity of depth-first search 261
9.3 Applications of Depth-First Search 262
9.3.1 Graph acyclicity 262
9.3.2 Topological sorting 262
9.3.3 Finding articulation points in a graph 263
9.3.4 Strongly connected components 266
9.4 Breadth-First Search 267
9.5 Applications of Breadth-First Search 269
9.6 Exercises 270
9.7 Bibliographic Notes 273
PART 4 Complexity of Problems 275
Chapter 10 NP-Complete Problems 279
10.1 Introduction 279
10.2 The Class P 282
10.3 The Class NP 283
10.4 NP-Complete Problems 285
10.4.1 The satisfiability problem 285
10.4.2 Vertex cover,independent set and clique problems 288
10.4.3 More NP-complete Problems 291
10.5 The Class co-NP 292
10.6 The Class NPI 294
10.7 The Relationships Between the Four Classes 295
10.8 Exercises 296
10.9 Bibliographic Notes 298
Chapter 11 Introduction to Computational Complexity 299
11.1 Introduction 299
11.2 Model of Computation: The Turing Machine 299
11.3 k-tape Turing Machines and Time complexity 300
11.4 Off-Line Turing Machines and Space Complexity 303
11.5 Tape Compression and Linear Speed-Up 305
11.6 Relationships Between Complexity Classes 306
11.6.1 Space and time hierarchy theorems 309
11.6.2 Padding arguments 311
11.7 Reductions 313
11.8 Completeness 318
11.8.1 NLOGSPACE-complete problems 318
11.8.2 PSPACE-complete problems 319
11.8.3 P-complete problems 321
11.8.4 Some conclusions of completeness 323
11.9 The Polynomial Time Hierarchy 324
11.10 Exercises 328
11.11 Bibliographic Notes 332
Chapter 12 Lower Bounds 335
12.1 Introduction 335
12.2 Trivial Lower Bounds 335
12.3 The Decision Tree Model 336
12.3.1 The search problem 336
12.3.2 The sorting problem 337
12.4 The Algebraic Decision Tree Model 339
12.4.1 The element uniqueness problem 341
12.5 Linear Time Reductions 342
12.5.1 The convex hull problem 342
12.5.2 The closest pair problem 343
12.5.3 The Euclidean minimum spanning tree problem 344
12.6 Exercises 345
12.7 Bibliographic Notes 346
PART 5 Coping with Hardness 349
Chapter 13 Backtracking 353
13.1 Introduction 353
13.2 The 3-Coloring Problem 353
13.3 The 8-Queens Problem 357
13.4 The General Backtracking Method 360
13.5 Branch and Bound 362
13.6 Exercises 367
13.7 Bibliographic notes 369
Chapter 14 Randomized Algorithms 371
14.1 Introduction 371
14.2 Las Vegas and Monte Carlo Algorithms 372
14.3 Randomized Quicksort 373
14.4 Randomized Selection 374
14.5 Testing String Equality 377
14.6 Pattern Matching 379
14.7 Random Sampling 381
14.8 Primality Testing 384
14.9 Exercises 390
14.1O Bibliographic Notes 392
Chapter 15 Approximation Algorithms 393
15.1 Introduction 393
15.2 Basic Definitions 393
15.3 Difference Bounds 394
15.3.1 Planar graph coloring 395
15.3.2 Hardness result: the knapsack problem 395
15.4 Relative Performance Bounds 396
15.4.1 The bin packing problem 397
15.4.2 The Euclidean traveling salesman problem 399
15.4.3 The vertex cover problem 401
15.4.4 Hardness result:the traveling salesman problem 402
15.5 Polynomial Approximation Schemes 404
15.5.1 The knapsack problem 404
15.6 Fully Polynomial Approximation Schemes 407
15.6.1 The subset-sum problem 408
15.7 Exercises 410
15.8 Bibliographic Notes 413
PART 6 Iterative Improvement for Domain-Specific Problems 415
Chapter 16 Network Flow 419
16.1 Introduction 419
16.2 Preliminaries 419
16.3 The Ford-Fulkerson Method 423
16.4 Maximum Capacity Augmentation 424
16.5 Shortest Path Augmentation 426
16.6 Dinic s Algorithm 429
16.7 The MPM Algorithm 431
16.8 Exercises 434
16.9 Bibliographic Notes 436
Chapter 17 Matching 437
17.1 Introduction 437
17.2 Preliminaries 437
17.3 The Network Flow Method 440
17.4 The Hungarian Tree Method for Bipartite Graphs 441
17.5 Maximum Matching in General Graphs 443
17.6 An O(n2.5) Algorithm for Bipartite Graphs 450
17.7 Exercises 455
17.8 Bibliographic Notes 457
PART 7 Techniques in Computational Geometry 459
Chapter 18 Geometric Sweeping 463
18.1 Introduction 463
18.2 Geometric Preliminaries 465
18.3 Computing the Intersections of Line Segments 467
18.4 The Convex Hull Problem 471
18.5 Computing the Diameter of a Set of Points 474
18.6 Exercises 478
18.7 Bibliographic Notes 480
Chapter 19 Voronoi Diagrams 481
19.1 Introduction 481
19.2 Nearest-Point Voronoi Diagram 481
19.2.1 Delaunay triangulation 484
19.2.2 Construction of the Voronoi diagram 486
19.3 Applications of the Voronoi Diagram 489
19.3.1 Computing the convex hull 489
19.3.2 All nearest neighbors 490
19.3.3 The Euclidean minimum spanning tree 491
19.4 Farthest-Point Voronoi Diagram 492
19.4.1 Construction of the farthest-point Voronoi diagram 493
19.5 Applications of the Farthest-Point Voronoi Diagram 496
19.5.1 All farthest neighbors 496
19.5.2 Smallest enclosing circle 497
19.6 Exercises 497
19.7 Bibliographic Notes 499
Bibliography 501
Index 511
|
|
资料下载
|
打开下载链接
点此链接需花费积分5分。如何获取积分？
注册新会员
积分不够？请用手机短信充值
·请先登录 ，然后下载
·下载后，您的积分会减少5分
·48小时内重复下载该资料不另外扣分
·下载前，请先阅读下载声明
·管理员对书籍只进行了初步审核，如果您发现该书违反了分享规则，请向管理员投诉！
|
·本服务的所有资料文件是其作者提供和网友推荐收集整理的，如有侵犯版权敬请指出。
·所有资料文件的准确性、安全性和完整性未经验证，NetYi不承担用户因使用这些下载内容而造成的任何形式的损失或伤害。
|
|
|
| 客户服务 |
 
 |
电话：028-66868000
13568916094
下班时间请点击此处留言 |
| 注：客服服务时间为周一至周五09：00—17：30，周六周日休息。 |
|
|