计算理论_计算机基础理论_计算机类_最新资料_得益网

Introduction to Algorithms

2008-10-25 23:16:48

Book Info: 简称为CLRS的<<算法导论>>,被称作"计算机算法的圣经".
　　本书的主要作者来自麻省理工大学计算机,作者之一Ronald L.Rivest 由于其在公开秘钥密码算法RSA上的贡献获得了图灵奖,目前是算法的标准教材,美国许多名校的计算机系都使用它,国内有些院校也将本书作为算法课程的教材.另外许多专业人员也经常引用它.由于TAOCP只出版了3卷,CLRS比较起前者来则显得内容更为全面,基本包含了所有的经典算法.本书程序全部由伪代码实现,这更增添了本书的通用性,使得利用各种程序设计语言的程序员都可以作为参考.语言方面通俗,很适合作为算法教材和自学算法之用.国内的很多作品名为数据结构,从本书中断章取义,把数据结构与算法混为一谈,搞得作者自己都迷迷糊糊.这也是我不十分愿意向大家推荐国内作品的原因.你会发现现在基本上所有的数据结构与算法书籍都会将本书作为参考文献之一,更可以说明一个问题,本书是作为读者进行算法学习的最佳选择.

通信中的自适应信号处理

2008-10-24 20:30:15

【摘要和目录】：
本书主要介绍自适应信号处理的基本理论和方法，着重介绍了自适应信号处理在通信技术中的应用。全书分为11章。在简要介绍有关自适应信号处理基本原理的基础上，详细介绍了通信信号波形的数字表示，通信中的自适应系统辨识，码间干扰与信道均衡，通信中的自适应噪声抵消（ANC）技术，自适应时间延迟估计，自适应阵列信号处理与波束形成，自适应天线系统，移动通信中的自适应信号处理，以及网络通信中的自适应信号处理等。
本书可作为高等院校电子信息类专业高年级本科生和研究生的教学参考书，也可供相关领域的科研开发人员和工程技术人员阅读。

第1章绪论
1.1 自适应滤波器的基本概念
1.2 通信系统的一般概念
1.3 通信中自适应信号得理的典型应用
参考文献
第2章自适应滤波器的基本原理
2.1 维纳滤波器
2.2 横向自适应滤波器
2.3 最小均方(LMS)算法
2.4 递归最小二乘(RLS)自适应滤波器
2.5 其他自适应滤波器算法与结构
参考文献
第3章通信信号波形的数字表示
3.1 连续时间信号的采样与采样定理
3.2 量化与脉冲编码调制(PCM)
3.3 自适应差分脉冲编码调制(ADPCM)与增量调制(DM)
3.4 其他编码方式
3.5 第三代移动通信系统中应用的编码技术
参考文献
第4章通信中的自适应系统辩识
4.1 自适应系统辩识的要领
4.2 全极点模型的估计
4.3 极点-零点模型的辨识
4.4 多径通信道中的自适应辩识
参考文献
第5章码间干扰与信道均衡
5.1 通信信道的非理想特性与码间干扰(ISI)
5.2 信道的线性均衡
5.3 自适应信道均衡
5.4 其他信道均衡方法
5.5 通信信道的盲均衡
5.6 基于分数低阶统计量的均衡方法
参考文献
第6章通信中的自适应噪声抵消(ANC)技术
……
第7章自适应时间延迟估计
第8章自适应阵列信号处理
第9章自适应天线系统
第10章移动通信中的自适应信号处理
第11章网络通信中的自适应信号处理

数字逻辑基础

2008-10-14 14:00:40

太好了！！

强调数字推算的100道趣题

2008-10-10 18:59:55

强调数字推算的100道趣题(2006年6月第1版)
丛书名：加德纳趣味数学系列
编辑推荐
本书是加德纳趣味数学系列之一，书中有100道数字推算趣题，都经过仔细筛选或精心设计(有许多是由作者或插图画家原创)，使得其中没有一道会难得让那些并非数学家的普通读者解决不了，但同时也没有一道会太容易。这些题目叙述简明清晰，书后有准确的答案。不管你是否解决了它们，在解题过程中都会有很多的乐趣。
本书可作为初中学生、高中学生、大学低年级学生的课外读物，也可用作中学教师教学时选题参考和辅导数学竞赛的参考读物，具有中学以上文化水平的干部、职工中的数学爱好者，阅读此书将是一种精神享受。
目录
1 挥霍一空
2 读出ACE
3 互成直角
4 四个2
5 狭路相逢
6 四个3
7 钟声当当
8 四个4
9 泉水淙淙
10 四阶幻方
1l 鸡蛋与小麦
12 读出POP
13 大链圈
14 四个5
15 里程碑
16 四个6
17 两个“另类”
18 四个7
19 二比一
20 五阶幻方
21 自行车大赛
22 读出LEVEL
23 平均速度
24 四个8
25 合理分担
26 四个9
27 聚餐
28 巧填符号
29 小镇上的男人们
30 又一个五阶幻方
31 市场调查
32 读出SPICE
33 滴水不漏
34 天下归一
35 两艘船
36 殊途同归
37 国际会议
38 六颗星
39 巧装牛奶
40 六阶幻方
41 驰骋纵横
42 读出12121
43 必胜之道
44 XYZ
45 蒂莫西回家
46 星号背后的数码
47 水乳交融
48 数码之和
49 加加减减
50 三个好朋友
51 又一个六阶幻方
52 七只足矣
53 混合酒
54 读出OSLO
55 平均分摊
56 奇偶相乘
57 步行
58 还是滴水不漏
59 四个素数
60 人马问题，
61 选头儿
62 牛奶、水和油
63 未知可否的幻方
64 蒂莫西卖布
65 读出REVIVER
66 梯子
67 怪钟
68 缺失的数码
69 加薪方案
70 准素数幻方
71 汽车比赛
72 年龄问题
73 读出LAVAL
74 蒂莫西的钱袋子
75 七阶幻方
76 骰子上的数字
77 旅行家的问题
78 读 ANNA
79 有颜色的骰子
80 八阶幻方
81 挖洞
82 搬运工
83 读 123343321
84 跑马钟
85 又一个七阶幻方
86 120个奇数之和
87 无法支付
88 再次读 12121
89 偶数迷
90 九阶幻方
91 西瓜的重量
92 制作砝码
93 读／]3 DEIFIED
94 银行出纳
95 二进制乘式
96 新车站
97 法国大使的招待会
98 二进制除式
99 通向户外的门
100 十阶幻方
答案

The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Tu

2008-09-27 11:57:23

《Programming Windows》作者 Charles Petzold 的最新巨作。

Mathematician Alan Turing invented an imaginary computer known as the Turing Machine; in an age before computers, he explored the concept of what it meant to be computable, creating the field of computability theory in the process, a foundation of present-day computer programming.

The book expands Turing’s original 36-page paper with additional background chapters and extensive annotations; the author elaborates on and clarifies many of Turing’s statements, making the original difficult-to-read document accessible to present day programmers, computer science majors, math geeks, and others.

Interwoven into the narrative are the highlights of Turing’s own life: his years at Cambridge and Princeton, his secret work in cryptanalysis during World War II, his involvement in seminal computer projects, his speculations about artificial intelligence, his arrest and prosecution for the crime of "gross indecency," and his early death by apparent suicide at the age of 41.

哈工大课堂录像集合论与图论51-54

2008-09-24 13:39:15

哈工大课堂录像集合论与图论46-50

2008-09-23 15:13:49

哈工大课堂录像集合论与图论41-45

2008-09-23 15:13:48

哈工大课堂录像集合论与图论36-40

2008-09-23 15:13:45

哈工大课堂录像集合论与图论31-35

2008-09-23 15:13:44

哈工大课堂录像集合论与图论26-30

2008-09-23 15:13:43

哈工大课堂录像编译原理56-58

2008-09-22 14:45:44

哈工大课堂录像编译原理51-55

2008-09-22 14:45:42

哈工大课堂录像编译原理46-50

2008-09-22 14:45:39

哈工大课堂录像编译原理41-45

2008-09-22 14:45:35

哈工大课堂录像编译原理36-40

2008-09-22 14:45:33

哈工大课堂录像编译原理31-35

2008-09-22 14:45:31

哈工大课堂录像编译原理26-30

2008-09-22 14:45:28

Computational Dynamics Second Edition

2008-09-15 19:57:03

Contents
Preface xi
1
Introduction
1
1.1 Computational Dynamics 2
1.2 Motion and Constraints 4
1.3 Degrees of Freedom 6
1.4 Kinematic Analysis 9
1.5 Force Analysis 12
1.6 Dynamic Equations and Their Different Forms 12
1.7 Forward and Inverse Dynamics 14
1.8 Planar and Spatial Dynamics 16
1.9 Computer and Numerical Methods 18
1.10 Organization, Scope, and Notations of the Book 20
2
Linear Algebra
22
2.1 Matrices 23
2.2 Matrix Operations 25
2.3 Vectors 35
2.4 Three-Dimensional Vectors 45
2.5 Solution of Algebraic Equations 52
2.6 Triangular Factorization 60
*2.7 QR Decomposition 65*2.8 Singular Value Decomposition / 81
Problems / 90
KINEMATICS
3.1 Mechanical Joints / 96
3.2 Coordinate Transformation / 104
3.3 Position, Velocity, and Acceleration Equations / 105
3.4 Kinematics of a Point Moving on a Rigid Body / 124
3.5 Constrained Kinematics / 132
3.6 Formulation of the Joint Constraints / 136
3.7 Computational Methods in Kinematics / 150
3.8 Computer Implementation / 159
3.9 Kinematic Modeling and Analysis / 171
3.10 Concluding Remarks / 180
Problems / 181
FORMS OF THE DYNAMIC EQUATIONS
4.1 D’Alembert’s Principle / 189
4.2 Constrained Dynamics / 194
4.3 Augmented Formulation / 196
4.4 Elimination of the Dependent Accelerations / 197
4.5 Embedding Technique / 199
4.6 Amalgamated Formulation / 202
4.7 Open and Closed Chains / 203
4.8 Concluding Remarks / 215
Problems / 216
VIRTUAL WORK AND LAGRANGIAN DYNAMICS
5.1 Virtual Displacements / 218
5.2 Kinematic Constraints and Coordinate Partitioning / 221
5.3 Virtual Work / 233
5.4 Examples of Force Elements / 240
5.5 Workless Constraints / 256
5.6 Principle of Virtual Work in Statics / 257
5.7 Principle of Virtual Work in Dynamics / 268
5.8 Lagrange’s Equation / 274
5.9 Gibbs–Appel Equation / 279
*5.10 Hamiltonian Formulation / 2805.11 Relationship between Virtual Work and Gaussian
Elimination / 286
Problems / 288
6 CONSTRAINED DYNAMICS 295
6.1 Generalized Inertia / 295
6.2 Mass Matrix and Centrifugal Forces / 301
6.3 Equations of Motion / 307
6.4 System of Rigid Bodies / 309
6.5 Elimination of the Constraint Forces / 314
6.6 Lagrange Multipliers / 323
6.7 Constrained Dynamic Equations / 332
6.8 Joint Reaction Forces / 339
6.9 Elimination of Lagrange Multipliers / 342
6.10 State Space Representation / 345
6.11 Numerical Integration / 349
6.12 Differential and Algebraic Equations / 358
*6.13 Inverse Dynamics / 368
*6.14 Static Analysis / 371
Problems / 372
7 SPATIAL DYNAMICS 378
7.1 General Displacement / 379
7.2 Finite Rotations / 380
7.3 Euler Angles / 388
7.4 Velocity and Acceleration / 391
7.5 Generalized Coordinates / 397
7.6 Generalized Inertia Forces / 401
7.7 Generalized Applied Forces / 414
7.8 Dynamic Equations of Motion / 423
7.9 Constrained Dynamics / 427
7.10 Formulation of the Joint Constraints / 430
7.11 Newton–Euler Equations / 439
7.12 Linear and Angular Momentum / 441
7.13 Recursive Methods / 443
Problems / 4608 OTHER TOPICS IN SPATIAL DYNAMICS 467
8.1 Gyroscopes and Euler Angles / 467
8.2 Rodriguez Formula / 472
8.3 Euler Parameters / 476
8.4 Rodriguez Parameters / 479
8.5 Quaternions / 481
8.6 Rigid Body Contact / 485
Problems / 491
REFERENCES 493
INDEX 497

工程矩阵理论07-09

2008-09-11 16:39:07

哈工大课堂录像编译原理04-05

2008-09-11 16:39:05

哈工大课堂录像编译原理21-25

2008-09-11 16:07:15

哈工大课堂录像编译原理16-20

2008-09-11 16:07:14

哈工大课堂录像编译原理11-15

2008-09-11 16:07:13

哈工大课堂录像编译原理06-10

2008-09-11 16:07:11

哈工大课堂录像编译原理01-03

2008-09-11 16:07:10

哈工大课堂录像集合论与图论16-20

2008-09-11 15:29:36

哈工大课堂录像集合论与图论21-25

2008-09-11 15:28:51

哈工大课堂录像集合论与图论11-15

2008-09-11 15:28:51

Neural Networks Algorithms, Applications and Programming Techniques

2008-09-09 21:37:40

Chapter 1
Introduction to ANS Technology 1
1.1 Elementary Neurophysiology 8
1.2 From Neurons to ANS 17
1.3 ANS Simulation 30
Bibliography 41
Chapter 2
Adaline and Madaline 45
2.1 Review of Signal Processing 45
2.2 Adaline and the Adaptive Linear Combiner 55
2.3 Applications of Adaptive Signal Processing 68
2.4 The Madaline 72
2.5 Simulating the Adaline 79
Bibliography 86
Chapter 3
Backpropagation 89
3.1 The Backpropagation Network 89
3.2 The Generalized Delta Rule 93
3.3 Practical Considerations 103
3.4 BPN Applications 106
3.5 The Backpropagation Simulator 114
Bibliography 124
Chapter 4
The BAM and the Hopfield Memory 727
4.1 Associative-Memory Definitions 128
4.2 The BAM 131
xi
xii Contents
4.3 The Hopfield Memory 141
4.4 Simulating the BAM 156
Bibliography 167
Chapter 5
Simulated Annealing 769
5.1 Information Theory and Statistical Mechanics 171
5.2 The Boltzmann Machine 179
5.3 The Boltzmann Simulator 189
5.4 Using the Boltzmann Simulator 207
Bibliography 212
Chapter 6
The Counterpropagation Network 273
6.7 CPN Building Blocks 215
6.2 CPN Data Processing 235
6.3 An Image-Classification Example 244
6.4 the CPN Simulator 247
Bibliography 262
Chapter 7
Self-Organizing Maps 263
7.7 SOM Data Processing 265
7.2 Applications of Self-Organizing Maps 274
7.3 Simulating the SOM 279
Bibliography 289
Chapter 8
Adaptive Resonance Theory 297
8.1 ART Network Description 293
8.2 ART1 298
8.3 ART2 316
8.4 The ART1 Simulator 327
8.5 ART2 Simulation 336
Bibliography 338
Chapter 9
Spatiotemporal Pattern Classification 347
9.7 The Formal Avalanche 342
9.2 Architectures of Spatiotemporal Networks (STNS) 345
Contents xiii
9.3 The Sequential Competitive Avalanche Field 355
9.4 Applications of STNS 363
9.5 STN Simulation 364
Bibliography 371
Chapter 10
The Neocognitron 373
10.1 Neocognitron Architecture 376
10.2 Neocognitron Data Processing 381
10.3 Performance of the Neocognitron 389
10.4 Addition of Lateral Inhibition and Feedback to the
Neocognitron 390
Bibliography 393

算法概论（Algorithm）

2008-09-09 10:27:17

本书系统全面地介绍了算法的基本知识。这些知识和技巧既是高等院校“算法与数据结构”课程的主要内容，也是计算机科学蓬勃发展的理论基础。.
本书涵盖了绝大多数算法设计中的常用技术。在表达每一种技术时，阐述它的应用背景，强调每个算法运转背后的简洁数学思想，注意运用与其他技术类比的方法来说明它的特征，并提供了大量相应实际问题的例子。本书同时也注重了对每一种算法的复杂性分析。全书共10章，从基本的数字算法人手，先后介绍了分治、图的遍历、贪心算法、动态规划、线性规划等技术，对NP完全问题进行厂基本而清晰的阐述，对随机算法、近似算法和量子算法这些近年来发展迅猛的领域也花费了一定的笔墨。书中每章后面都附有大量的习题，有利于读者对书中内容的理解和应用。
0 Prologue 11
0.1 Books and algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
0.2 Enter Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
0.3 Big-O notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1 Algorithms with numbers 21
1.1 Basic arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.2 Modular arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.3 Primality testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
1.4 Cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
1.5 Universal hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
Randomized algorithms: a virtual chapter 38
2 Divide-and-conquer algorithms 51
2.1 Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
2.2 Recurrence relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2.3 Mergesort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.4 Medians . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
2.5 Matrix multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
2.6 The fast Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
3 Decompositions of graphs 87
3.1 Why graphs? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.2 Depth-rst search in undirected graphs . . . . . . . . . . . . . . . . . . . . . . . . 89
3.3 Depth-rst search in directed graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.4 Strongly connected components . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
3
4 Paths in graphs 109
4.1 Distances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
4.2 Breadth-rst search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
4.3 Lengths on edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4.4 Dijkstra's algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4.5 Priority queue implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
4.6 Shortest paths in the presence of negative edges . . . . . . . . . . . . . . . . . . . 122
4.7 Shortest paths in dags . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
5 Greedy algorithms 133
5.1 Minimum spanning trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
5.2 Huffman encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
5.3 Horn formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
5.4 Set cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
6 Dynamic programming 161
6.1 Shortest paths in dags, revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
6.2 Longest increasing subsequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
6.3 Edit distance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
6.4 Knapsack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
6.5 Chain matrix multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
6.6 Shortest paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
6.7 Independent sets in trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
7 Linear programming and reductions 189
7.1 An introduction to linear programming . . . . . . . . . . . . . . . . . . . . . . . . 189
7.2 Flows in networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 199
7.3 Bipartite matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206
7.4 Duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
7.5 Zero-sum games . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
7.6 The simplex algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
7.7 Postscript: circuit evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225
8 NP-complete problems 233
8.1 Search problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
8.2 NP-complete problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
8.3 The reductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
4
9 Coping with NP-completeness 269
9.1 Intelligent exhaustive search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
9.2 Approximation algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275
9.3 Local search heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
10 Quantum algorithms 295
10.1 Qubits, superposition, and measurement . . . . . . . . . . . . . . . . . . . . . . . 295
10.2 The plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
10.3 The quantum Fourier transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300
10.4 Periodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302
10.5 Quantum circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
10.6 Factoring as periodicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307
10.7 The quantum algorithm for factoring . . . . . . . . . . . . . . . . . . . . . . . . . . 308
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311

Algorithms

2008-09-05 21:34:04

This book is intended to survey the most important algorithms in use on
computers today and to teach fundamental techniques to the growing number
of people who are interested in becoming serious computer users. It is ap-
propriate for use as a textbook for a second, third or fourth course in computer
science: after students have acquired some programming skills and familiarity
with computer systems, but before they have specialized courses in advanced
areas of computer science or computer applications. Additionally, the book
may be useful as a reference for those who already have some familiarity with
the material, since it contains a number of computer implementations of useful
algorithms.
The book consists of forty chapters which are grouped into seven major
parts: mathematical algorithms, sorting, searching, string processing, geomet-
ric algorithms, graph algorithms and advanced topics. A major goal in the
development of this book has been to bring together the fundamental methods
from these diverse areas, in order to provide access to the best methods
that we know for solving problems by computer for as many people as pos-
sible. The treatment of sorting, searching and string processing (which may
not be covered in other courses) is somewhat more complete than the treat-
ment of mathematical algorithms (which may be covered in more depth in
applied mathematics or engineering courses), or geometric and graph algo-
rithms (which may be covered in more depth in advanced computer science
courses). Some of the chapters involve mtroductory treatment of advanced
material. It is hoped that the descriptions here can provide students with
some understanding of the basic properties of fundamental algorithms such
as the FFT or the simplex method, while at the same time preparing them
to better appreciate the methods when they learn them in advanced courses.
The orientation of the book is towards algorithms that are likely to be
of practical use. The emphasis is on t,eaching students the tools of their
trade to the point that they can confidently implement, run and debug useful
algorithms. Full implementations of the methods discussed (in an actual
programming language) are included in the text, along with descriptions of
the operations of these programs on a consistent set of examples. Though not
emphasized, connections to theoretical computer science and the analysis of
algorithms are not ignored. When appropriate, analytic results are discussed
to illustrate why certain algorithms are preferred. When interesting, the
relationship of the practical algorithms being discussed to purely theoretical
results is described. More information of the orientation and coverage of the
material in the book may be found in the Introduction which follows.

哈工大课堂录像集合论与图论6-10

2008-09-03 11:51:03

哈工大课堂录像集合论与图论1-5

2008-09-03 11:51:03

注册表实用手册v5.2

2008-08-04 03:43:25

使用说明

本手册全称“注册表实用手册”，收录的是大量简单,通俗易懂而又确实实用的windows系列注册表修改技巧。经实践证明，不但对电脑初学者有很大的帮助，对"大哥级"的电脑爱好者也有很高的参考价值。毫不夸大的说，这是一本非常实用的windows系列注册表工具书，确实是您学习和维护电脑的好帮手。

试用版提供【注册表修改】部分功能试用，有(R)标记的为注册版本目录，包括win98，NT，2K，XP，2003全套注册表修改和优化技巧。本手册目前在一定程度上来说已经相当完善，各项修改都很全面。本手册会结合实际，追踪注册表最新动态，努力提供最好最全的注册表实用技术。

版权信息：本手册分注册版和试用版两种。试用版免费，你可以免费使用，自由传播，但请保留其版权；注册版本只提供给本手册注册用户使用。

更新信息：5.2版本改原来的"电脑应用技术"版块为"windows应用技巧"，主要提供各种实用的windows应用技术，涉及各种常见的电脑问题，力求能较好的解决疑难问题。

注册问题：为什么要注册？本手册是共享教学软件，您的付费注册是对作者的支持，将鼓励作者做出更多更好的电子图书，为您提供更好的服务，注册购买本手册后，也即成为本站（www.happydrips.com）的永久注册用户，可以继续免费获得本站制作的各种计算机电子图书和技术资料。

本人力求手册完美，但因有些内容涉及系统内核，所以对使用本手册可能造成的损失由使用者承担，本人不保证所有内容都准确无误。因手册内容太多，如果您在使用本手册过程中发现什么问题或错误请来信指正，欢迎交流！

Encyclopedia of Algorithms

2008-07-03 14:46:36

Table of Contents
AbelianHiddenSubgroupProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1995; Kitaev
AdaptivePartitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1986; Du, Pan, Shing
AdwordsPricing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2007; Bu, Deng, Qi
AlgorithmDC-Tree for kServersonTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1991; Chrobak, Larmore
AlgorithmicCooling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1999; Schulman, Vazirani
2002; Boykin, Mor, Roychowdhury, Vatan, Vrijen
AlgorithmicMechanismDesign . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1999; Nisan, Ronen
AlgorithmsforSpannersinWeightedGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2003; Baswana, Sen
AllPairsShortestPathsinSparseGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2004; Pettie
AllPairsShortestPathsviaMatrixMultiplication. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2002; Zwick
AlternativePerformanceMeasuresinOnlineAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2000; Koutsoupias, Papadimitriou
AnalyzingCacheMisses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2003;Mehlhorn, Sanders
ApplicationsofGeometricSpannerNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2002; Gudmundsson, Levcopoulos, Narasimhan, Smid
ApproximateDictionaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2002; Buhrman, Miltersen, Radhakrishnan, Venkatesh
ApproximateRegularExpressionMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
1995; Wu, Manber, Myers
VIII Table of Contents
ApproximateTandemRepeats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
2001; Landau, Schmidt, Sokol
2003; Kolpakov, Kucherov
ApproximatingMetricSpacesbyTreeMetrics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
1996; Bartal, Fakcharoenphol, Rao, Talwar
2004; Bartal, Fakcharoenphol, Rao, Talwar
ApproximationsofBimatrixNashEquilibria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
2003; Lipton, Markakis,Mehta
2006; Daskalaskis,Mehta, Papadimitriou
2006; Kontogiannis, Panagopoulou, Spirakis
ApproximationSchemesforBinPacking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
1982; Karmarker, Karp
ApproximationSchemesforPlanarGraphProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
1983; Baker
1994; Baker
ArbitrageinFrictionalForeignExchangeMarket . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
2003; Cai, Deng
ArithmeticCodingforDataCompression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
1994; Howard, Vitter
AssignmentProblem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
1955; Kuhn
1957;Munkres
AsynchronousConsensusImpossibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
1985; Fischer, Lynch, Paterson
AtomicBroadcast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
1995; Cristian, Aghili, Strong, Dolev
Attribute-EfficientLearning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
1987; Littlestone
AutomatedSearchTreeGeneration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
2004; Gramm, Guo, Hüffner, Niedermeier
Backtracking Based k-SATAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
2005; Paturi, Pudlák, Saks, Zane
BestResponseAlgorithmsforSelfishRouting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
2005; Fotakis, Kontogiannis, Spirakis
Bidimensionality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
2004; Demaine, Fomin, Hajiaghayi, Thilikos
BinaryDecisionGraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
1986; Bryant
Table of Contents IX
BinPacking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
1997; Coffman, Garay, Johnson
BoostingTextualCompression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
2005; Ferragina, Giancarlo,Manzini, Sciortino
BranchwidthofGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
2003; Fomin, Thilikos
BroadcastinginGeometricRadioNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
2001; Dessmark, Pelc
B-trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
1972; Bayer,McCreight
Burrows–WheelerTransform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
1994; Burrows,Wheeler
ByzantineAgreement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
1980; Pease, Shostak, Lamport
Cache-ObliviousB-Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
2005; Bender, Demaine, Farach-Colton
Cache-ObliviousModel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
1999; Frigo, Leiserson, Prokop, Ramachandran
Cache-ObliviousSorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
1999; Frigo, Leiserson, Prokop, Ramachandran
CausalOrder,LogicalClocks,StateMachineReplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
1978; Lamport
CertificateComplexityandExactLearning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
1995; Hellerstein, Pilliapakkamnatt, Raghavan,Wilkins
ChannelAssignmentandRoutinginMulti-RadioWirelessMeshNetworks . . . . . . . . . . . . . . . . . . . 134
2005; Alicherry, Bhatia, Li
CircuitPartitioning:ANetwork-Flow-BasedBalancedMin-CutApproach . . . . . . . . . . . . . . . . . . . . 138
1994; Yang,Wong
CircuitPlacement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
2000; Caldwell, Kahng, Markov
2002; Kennings,Markov
2006; Kennings, Vorwerk
CircuitRetiming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
1991; Leiserson, Saxe
CircuitRetiming:AnIncrementalApproach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
2005; Zhou
X TableofContents
ClockSynchronization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
1994; Patt-Shamir, Rajsbaum
ClosestStringandSubstringProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
2002; Li, Ma, Wang
ClosestSubstring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
2005;Marx
ColorCoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
1995; Alon, Yuster, Zwick
CommunicationinAdHocMobileNetworksUsingRandomWalks . . . . . . . . . . . . . . . . . . . . . . . . 161
2003; Chatzigiannakis, Nikoletseas, Spirakis
CompetitiveAuction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
2001; Goldberg, Hartline, Wright
2002; Fiat, Goldberg, Hartline, Karlin
ComplexityofBimatrixNashEquilibria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
2006; Chen, Deng
ComplexityofCore . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
2001; Fang, Zhu, Cai, Deng
CompressedPatternMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
2003; Kida, Matsumoto, Shibata, Takeda, Shinohara, Arikawa
CompressedSuffixArray . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
2003; Grossi, Gupta, Vitter
CompressedText Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
2005; Ferragina,Manzini
CompressingIntegerSequencesandSets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
2000;Moffat, Stuiver
ComputingPureEquilibriaintheGameofParallelLinks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183
2002; Fotakis, Kontogiannis, Koutsoupias, Mavronicolas, Spirakis
2003; Even-Dar, Kesselman,Mansour
2003; Feldman, Gairing, Lücking, Monien, Rode
ConcurrentProgramming,MutualExclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
1965; Dijkstra
ConnectedDominatingSet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191
2003; Cheng, Huang, Li,Wu, Du
ConnectivityandFault-ToleranceinRandomRegularGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 195
2000; Nikoletseas, Palem, Spirakis, Yung
ConsensuswithPartialSynchrony . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
1988; Dwork, Lynch, Stockmeyer
Table of Contents XI
ConstructingaGalledPhylogeneticNetwork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202
2006; Jansson, Nguyen, Sung
CPUTimePricing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
2005; Deng, Huang, Li
CriticalRangeforWirelessNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
2004; Wan, Yi
CryptographicHardnessofLearning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
1994; Kearns, Valiant
CuckooHashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212
2001; Pagh, Rodler
DataMigration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
2004; Khuller, Kim, Wan
DataReductionforDominationinGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220
2004; Alber, Fellows, Niedermeier
DecodingReed–SolomonCodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
1999; Guruswami, Sudan
DecrementalAll-PairsShortestPaths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226
2004; Demetrescu, Italiano
Degree-BoundedPlanarSpannerwithLowWeight . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 228
2005; Song, Li, Wang
Degree-BoundedTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
1994; Fürer, Raghavachari
DeterministicBroadcastinginRadioNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
2000; Chrobak, Ga?sieniec, Rytter
DeterministicSearchingontheLine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
1988; Baeza-Yates, Culberson, Rawlins
Dictionary-BasedDataCompression. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 236
1977; Ziv, Lempel
DictionaryMatchingandIndexing(ExactandwithErrors) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240
2004; Cole, Gottlieb, Lewenstein
DilationofGeometricNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244
2005; Ebbers-Baumann, Grüne, Karpinski, Klein, Kutz, Knauer, Lingas
DirectedPerfectPhylogeny(BinaryCharacters) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
1991; Gusfield
DirectRoutingAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248
2006; Busch, Magdon-Ismail, Mavronicolas, Spirakis
XII Table of Contents
Distance-BasedPhylogenyReconstruction(Fast-Converging) . . . . . . . . . . . . . . . . . . . . . . . . . . . 251
2003; King, Zhang, Zhou
Distance-BasedPhylogenyReconstruction(OptimalRadius) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253
1999; Atteson
2005; Elias, Lagergren
DistributedAlgorithmsforMinimumSpanningTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
1983; Gallager, Humblet, Spira
DistributedVertexColoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258
2004; Finocchi, Panconesi, Silvestri
DynamicTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260
2005; Tarjan,Werneck
EditDistanceUnderBlockOperations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265
2000; Cormode, Paterson, Sahinalp, Vishkin
2000;Muthukrishnan, Sahinalp
EfficientMethodsforMultipleSequenceAlignmentwithGuaranteedErrorBounds . . . . . . . . . . . . . 267
1993; Gusfield
EngineeringAlgorithmsforComputationalBiology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270
2002; Bader, Moret, Warnow
EngineeringAlgorithmsforLargeNetworkApplications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272
2002; Schulz,Wagner, Zaroliagis
EngineeringGeometricAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274
2004; Halperin
EquivalenceBetweenPriorityQueuesandSorting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 278
2002; Thorup
EuclideanTravelingSalespersonProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
1998; Arora
ExactAlgorithmsforDominatingSet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284
2005; Fomin, Grandoni, Kratsch
ExactAlgorithmsforGeneralCNFSAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286
1998; Hirsch
2003; Schuler
ExactGraphColoringUsingInclusion–Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 289
2006; Bj?rklund, Husfeldt
ExperimentalMethodsforAlgorithmAnalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290
2001;McGeoch
ExternalSortingandPermuting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291
1988; Aggarwal, Vitter
Table of Contents XIII
FacilityLocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
1997; Shmoys, Tardos, Aardal
FailureDetectors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304
1996; Chandra, Toueg
False-Name-ProofAuction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308
2004; Yokoo, Sakurai, Matsubara
FastMinimalTriangulation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310
2005; Heggernes, Telle, Villanger
Fault-TolerantQuantumComputation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313
1996; Shor, Aharonov, Ben-Or, Kitaev
FloorplanandPlacement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317
1994; Kajitani, Nakatake,Murata, Fujiyoshi
FlowTimeMinimization. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320
2001; Becchetti, Leonardi,Marchetti-Spaccamela, Pruhs
FPGATechnologyMapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322
1992; Cong, Ding
FractionalPackingandCoveringProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
1991; Plotkin, Shmoys, Tardos
1995; Plotkin, Shmoys, Tardos
FullyDynamicAllPairsShortestPaths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329
2004; Demetrescu, Italiano
FullyDynamicConnectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331
2001; Holm, de Lichtenberg, Thorup
FullyDynamicConnectivity:UpperandLowerBounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332
2000; Thorup
FullyDynamicHigherConnectivity. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335
1997; Eppstein, Galil, Italiano, Nissenzweig
FullyDynamicHigherConnectivityforPlanarGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337
1998; Eppstein, Galil, Italiano, Spencer
FullyDynamicMinimumSpanningTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 339
2000; Holm, de Lichtenberg, Thorup
FullyDynamicPlanarityTesting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342
1999; Galil, Italiano, Sarnak
FullyDynamicTransitiveClosure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343
1999; King
GateSizing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345
2002; Sundararajan, Sapatnekar, Parhi
XIV Table of Contents
GeneralEquilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 347
2002; Deng, Papadimitriou, Safra
GeneralizedSteinerNetwork . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
2001; Jain
GeneralizedTwo-ServerProblem. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351
2006; Sitters, Stougie
GeneralizedVickreyAuction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353
1995; Varian
GeographicRouting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355
2003; Kuhn,Wattenhofer, Zollinger
GeometricDilationofGeometricNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358
2006; Dumitrescu, Ebbers-Baumann, Grüne, Klein, Knauer, Rote
GeometricSpanners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 360
2002; Gudmundsson, Levcopoulos, Narasimhan
Gomory–HuTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364
2007; Bhalgat, Hariharan, Kavitha, Panigrahi
GraphBandwidth . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366
1998; Feige
2000; Feige
GraphColoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368
1994; Karger, Motwani, Sudan
1998; Karger, Motwani, Sudan
GraphConnectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 371
1994; Khuller, Vishkin
GraphIsomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
1980;McKay
GreedyApproximationAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 376
2004; Ruan, Du, Jia, Wu, Li, Ko
GreedySet-CoverAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379
1974–1979, Chvátal, Johnson, Lovász, Stein
HamiltonCyclesinRandomIntersectionGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
2005; Efthymiou, Spirakis
HardnessofProperLearning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
1988; Pitt, Valiant
HighPerformanceAlgorithmEngineeringforLarge-scaleProblems . . . . . . . . . . . . . . . . . . . . . . . 387
2005; Bader
Table of Contents XV
Hospitals/ResidentsProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
1962; Gale, Shapley
ImplementationChallengeforShortestPaths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395
2006; Demetrescu, Goldberg, Johnson
ImplementationChallengeforTSPHeuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
2002; Johnson, McGeoch
ImplementingSharedRegistersinAsynchronousMessage-PassingSystems . . . . . . . . . . . . . . . . . . 400
1995; Attiya, Bar-Noy, Dolev
IncentiveCompatibleSelection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403
2006; Chen, Deng, Liu
IndependentSetsinRandomIntersectionGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405
2004; Nikoletseas, Raptopoulos, Spirakis
IndexedApproximateStringMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408
2006; Chan, Lam, Sung, Tam, Wong
InductiveInference . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411
1983; Case, Smith
I/O-model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413
1988; Aggarwal, Vitter
KineticDataStructures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
1999; Basch, Guibas, Hershberger
Knapsack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 419
1975; Ibarra, Kim
LearningwiththeAidofanOracle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 423
1996; Bshouty, Cleve, Gavaldà, Kannan, Tamon
LearningAutomata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425
2000; Beimel, Bergadano, Bshouty, Kushilevitz, Varricchio
LearningConstant-DepthCircuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 429
1993; Linial,Mansour, Nisan
LearningDNFFormulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
1997; Jackson
LearningHeavyFourierCoefficientsofBooleanFunctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434
1989; Goldreich, Levin
LearningwithMaliciousNoise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436
1993; Kearns, Li
LearningSignificantFourierCoefficientsoverFiniteAbelianGroups . . . . . . . . . . . . . . . . . . . . . . . 438
2003; Akavia, Goldwasser, Safra
XVI Table of Contents
LEDA:aLibraryofEfficientAlgorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 442
1995;Mehlhorn, N?her
LeontiefEconomyEquilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444
2005; Codenotti, Saberi, Varadarajan, Ye
2005; Ye
LinearityTesting/TestingHadamardCodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 446
1990; Blum, Luby, Rubinfeld
Linearizability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450
1990; Herlihy, Wing
ListDecodingnearCapacity:FoldedRSCodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453
2006; Guruswami, Rudra
ListScheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455
1966; Graham
LoadBalancing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457
1994; Azar, Broder, Karlin
1997; Azar, Kalyanasundaram, Plotkin, Pruhs,Waarts
LocalAlignment(withAffineGapWeights) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459
1986; Altschul, Erickson
LocalAlignment(withConcaveGapWeights) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461
1988;Miller,Myers
LocalApproximationofCoveringandPackingProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463
2003–2006; Kuhn, Moscibroda, Nieberg, Wattenhofer
LocalComputationinUnstructuredRadioNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466
2005;Moscibroda,Wattenhofer
Local Search Algorithms for kSAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468
1999; Sch?ning
Local Search for K-mediansandFacilityLocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470
2001; Arya, Garg, Khandekar,Meyerson,Munagala, Pandit
LowerBoundsforDynamicConnectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473
2004; P?atra?scu, Demaine
LowStretchSpanningTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
2005; Elkin, Emek, Spielman, Teng
LPDecoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 478
2002 and later; Feldman, Karger, Wainwright
MajorityEquilibrium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483
2003; Chen, Deng, Fang, Tian
Table of Contents XVII
MarketGamesandContentDistribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485
2005;Mirrokni
MaxCut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489
1994; Goemans, Williamson
1995; Goemans, Williamson
MaximumAgreementSubtree(of2BinaryTrees) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 492
1996; Cole, Hariharan
MaximumAgreementSubtree(of3orMoreTrees) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495
1995; Farach, Przytycka, Thorup
MaximumAgreementSupertree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497
2005; Jansson, Ng, Sadakane, Sung
MaximumCompatibleTree. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 499
2001; Ganapathy, Warnow
Maximum-DensitySegment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 502
1994; Huang
MaximumMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504
2004;Mucha, Sankowski
Maximum-scoringSegmentwithLengthRestrictions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 506
2002; Lin, Jiang, Chao
MaximumTwo-Satisfiability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 507
2004; Williams
MaxLeafSpanningTree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 511
2005; Estivill-Castro, Fellows, Langston, Rosamond
MetricalTaskSystems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 514
1992; Borodin, Linial, Saks
MetricTSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 517
1976; Christofides
MinimumBisection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519
1999; Feige, Krauthgamer
MinimumCongestionRedundantAssignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 522
2002; Fotakis, Spirakis
MinimumEnergyBroadcastinginWirelessGeometricNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . 526
2005; Ambühl
MinimumEnergyCostBroadcastinginWirelessNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 528
2001; Wan, Calinescu, Li, Frieder
MinimumFlowTime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 531
1997; Leonardi, Raz
XVIII Table of Contents
MinimumGeometricSpanningTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 533
1999; Krznaric, Levcopoulos, Nilsson
Minimumk-ConnectedGeometricNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 536
2000; Czumaj, Lingas
MinimumMakespanonUnrelatedMachines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539
1990; Lenstra, Shmoys, Tardos
MinimumSpanningTrees. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 541
2002; Pettie, Ramachandran
MinimumWeightedCompletionTime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544
1999; Afrati et al.
MinimumWeightTriangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546
1998; Levcopoulos, Krznaric
MobileAgentsandExploration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 548
1952; Shannon
MulticommodityFlow,Well-linkedTerminalsandRoutingProblems . . . . . . . . . . . . . . . . . . . . . . . 551
2005; Chekuri, Khanna, Shepherd
Multicut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 554
1993; Garg, Vazirani, Yannakakis
1996; Garg, Vazirani, Yannakakis
MultidimensionalCompressedPatternMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556
2003; Amir, Landau, Sokol
MultidimensionalStringMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 559
1999; K?rkk?inen, Ukkonen
Multi-levelFeedbackQueues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 562
1968; Coffman, Kleinrock
MultipleUnitAuctionswithBudgetConstraint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563
2005; Borgs, Chayes, Immorlica, Mahdian, Saberi
2006; Abrams
MultiplexPCRforGapClosing(Whole-genomeAssembly) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565
2002; Alon, Beigel, Kasif, Rudich, Sudakov
MultiwayCut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 567
1998; Calinescu, Karloff, Rabani
NashEquilibriaandDominantStrategiesinRouting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 571
2005; Wang, Li, Chu
NearestNeighborInterchangeandRelatedDistances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573
1999; DasGupta, He, Jiang, Li, Tromp, Zhang
Table of Contents XIX
NegativeCyclesinWeightedDigraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576
1994; Kavvadias, Pantziou, Spirakis, Zaroliagis
Non-approximabilityofBimatrixNashEquilibria. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578
2006; Chen, Deng, Teng
Non-sharedEdges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 579
1985; Day
Nucleolus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 581
2006; Deng, Fang, Sun
ObliviousRouting. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585
2002; R?cke
ObstacleAvoidanceAlgorithmsinWirelessSensorNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588
2007; Powell, Nikoletseas
O(log log n)-competitiveBinarySearchTree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 592
2004; Demaine, Harmon, Iacono, Patrascu
OnlineIntervalColoring. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594
1981; Kierstead, Trotter
OnlineListUpdate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 598
1985; Sleator, Tarjan
OnlinePagingandCaching. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601
1985–2002;multiple authors
OptimalProbabilisticSynchronousByzantineAgreement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604
1988; Feldman,Micali
OptimalStableMarriage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 606
1987; Irving, Leather, Gusfield
P2P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611
2001; Stoica, Morris, Karger, Kaashoek, Balakrishnan
PacketRouting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 616
1988; Leighton, Maggs, Rao
PacketSwitchinginMulti-QueueSwitches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 618
2004; Azar, Richter; Albers, Schmidt
PacketSwitchinginSingleBuffer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 621
2003; Bansal, Fleischer, Kimbrel,Mahdian, Schieber, Sviridenko
PACLearning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 622
1984; Valiant
PageRankAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624
1998; Brin, Page
XX Table of Contents
Paging . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625
1985; Sleator, Tarjan, Fiat, Karp, Luby, McGeoch, Sleator, Young
1991; Sleator, Tarjan; Fiat, Karp, Luby, McGeoch, Sleator, Young
ParallelAlgorithmsforTwoProcessorsPrecedenceConstraintScheduling . . . . . . . . . . . . . . . . . . . 627
2003; Jung, Serna, Spirakis
ParallelConnectivityandMinimumSpanningTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629
2001; Chong, Han, Lam
ParameterizedAlgorithmsforDrawingGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 631
2004; Dujmovic,Whitesides
ParameterizedMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 635
1993; Baker
ParameterizedSAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 639
2003; Szeider
PeptideDeNovoSequencingwithMS/MS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 640
2005;Ma, Zhang, Liang
PerceptronAlgorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 642
1959; Rosenblatt
PerfectPhylogeny(BoundedNumberofStates) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644
1997; Kannan, Warnow
PerfectPhylogenyHaplotyping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 647
2005; Ding, Filkov, Gusfield
Performance-DrivenClustering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 650
1993; Rajaraman, Wong
PhylogeneticTreeConstructionfromaDistanceMatrix . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 651
1989; Hein
PlanarGeometricSpanners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653
2005; Bose, Smid, Gudmundsson
PlanarityTesting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 656
1976; Booth, Lueker
PointPatternMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 657
2003; Ukkonen, Lemstr?m, M?kinen
PositionAuction. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 660
2005; Varian
PredecessorSearch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 661
2006; P?atra?scu, Thorup
PriceofAnarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665
2005; Koutsoupias
Table of Contents XXI
PriceofAnarchyforMachinesModels . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667
2002; Czumaj, V?cking
ProbabilisticDataForwardinginWirelessSensorNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671
2004; Chatzigiannakis, Dimitriou, Nikoletseas, Spirakis
QuantizationofMarkovChains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677
2004; Szegedy
QuantumAlgorithmforCheckingMatrixIdentities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 680
2006; Buhrman, Spalek
QuantumAlgorithmfortheCollisionProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 682
1998; Brassard, Hoyer, Tapp
QuantumAlgorithmfortheDiscreteLogarithmProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 683
1994; Shor
QuantumAlgorithmforElementDistinctness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 686
2004; Ambainis
QuantumAlgorithmforFactoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 689
1994; Shor
QuantumAlgorithmforFindingTriangles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 690
2005;Magniez, Santha, Szegedy
QuantumAlgorithmfortheParityProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 693
1985; Deutsch
QuantumAlgorithmsforClassGroupofaNumberField . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 694
2005; Hallgren
QuantumAlgorithmforSearchonGrids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 696
2005; Ambainis, Kempe, Rivosh
QuantumAlgorithmforSolvingthePell’sEquation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 698
2002; Hallgren
QuantumApproximation oftheJonesPolynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 700
2005; Aharonov, Jones, Landau
QuantumDenseCoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 703
1992; Bennett, Wiesner
QuantumErrorCorrection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 705
1995; Shor
QuantumKeyDistribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 708
1984; Bennett, Brassard
1991; Ekert
QuantumSearch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 712
1996; Grover
XXII Table of Contents
Quorums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715
1985; Garcia-Molina, Barbara
RadiocoloringinPlanarGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 721
2005; Fotakis, Nikoletseas, Papadopoulou, Spirakis
RandomizationinDistributedComputing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 723
1996; Chandra
RandomizedBroadcastinginRadioNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725
1992; Reuven Bar-Yehuda, Oded Goldreich, Alon Itai
RandomizedEnergyBalanceAlgorithmsinSensorNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 728
2005; Leone, Nikoletseas, Rolim
RandomizedGossipinginRadioNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 731
2001; Chrobak, Ga?sieniec, Rytter
RandomizedMinimumSpanningTree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 732
1995; Karger, Klein, Tarjan
RandomizedParallelApproximationstoMaxFlow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734
1991; Serna, Spirakis
RandomizedRounding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 737
1987; Raghavan, Thompson
RandomizedSearchingonRaysor theLine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 740
1993; Kao, Reif, Tate
RandomPlanted3-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 742
2003; Flaxman
RankedMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 744
2005; Abraham, Irving, Kavitha, Mehlhorn
RankandSelectOperationsonBinaryStrings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 748
1974; Elias
Rate-MonotonicScheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 751
1973; Liu, Layland
RectilinearSpanningTree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 754
2002; Zhou, Shenoy, Nicholls
RectilinearSteinerTree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 757
2004; Zhou
Registers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 761
1986; Lamport, Vitanyi, Awerbuch
RegularExpressionIndexing. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 764
2002; Chan, Garofalakis, Rastogi
Table of Contents XXIII
RegularExpressionMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 768
2004; Navarro, Raffinot
ReinforcementLearning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 771
1992; Watkins
Renaming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 774
1990; Attiya, Bar-Noy, Dolev, Peleg, Reischuk
RNASecondaryStructureBoltzmannDistribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 777
2005;Miklós, Meyer, Nagy
RNASecondaryStructurePredictionIncludingPseudoknots . . . . . . . . . . . . . . . . . . . . . . . . . . . . 780
2004; Lyngs?
RNASecondaryStructurePredictionbyMinimumFreeEnergy . . . . . . . . . . . . . . . . . . . . . . . . . . . 782
2006; Ogurtsov, Shabalina, Kondrashov, Roytberg
Robotics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 785
1997; (Navigation) Blum, Raghavan, Schieber
1998; (Exploration) Deng, Kameda, Papadimitriou
2001; (Localization) Fleischer, Romanik, Schuierer, Trippen
RobustGeometricComputation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 788
2004; Li, Yap
Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 791
2003; Azar, Cohen, Fiat, Kaplan, R?cke
RoutinginGeometricNetworks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 793
2003; Kuhn,Wattenhofer, Zhang, Zollinger
RoutinginRoadNetworkswithTransitNodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 796
2007; Bast, Funke, Sanders, Schultes
R-Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 800
2004; Arge, de Berg, Haverkort, Yi
SchedulersforOptimisticRateBasedFlowControl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 803
2005; Fatourou, Mavronicolas, Spirakis
SchedulingwithEquipartition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 806
2000; Edmonds
SelfishUnsplittableFlows:AlgorithmsforPureEquilibria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 810
2005; Fotakis, Kontogiannis, Spirakis
Self-Stabilization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 812
1974; Dijkstra
SeparatorsinGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 815
1998; Leighton, Rao
1999; Leighton, Rao
XXIV Table of Contents
SequentialApproximateStringMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 818
2003; Crochemore, Landau, Ziv-Ukelson
2004; Fredriksson, Navarro
SequentialCircuitTechnologyMapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 820
1998; Pan, Liu
SequentialExactStringMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 824
1994; Crochemore, Czumaj, Ga?sieniec, Jarominek, Lecroq, Plandowski, Rytter
SequentialMultipleStringMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 826
1999; Crochemore, Czumaj, G?asieniec, Lecroq, Plandowski, Rytter
SetAgreement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 829
1993; Chaudhuri
SetCoverwithAlmostConsecutiveOnes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 832
2004;Mecke, Wagner
ShortestElapsedTimeFirstScheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 834
2003; Bansal, Pruhs
ShortestPathsApproachesforTimetableInformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 837
2004; Pyrga, Schulz,Wagner, Zaroliagis
ShortestPathsinPlanarGraphswithNegativeWeightEdges . . . . . . . . . . . . . . . . . . . . . . . . . . . . 838
2001; Fakcharoenphol, Rao
ShortestVectorProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 841
1982; Lenstra, Lenstra, Lovasz
SimilaritybetweenCompressedStrings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 843
2005; Kim, Amir, Landau, Park
Single-SourceFullyDynamicReachability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 846
2005; Demetrescu, Italiano
Single-SourceShortestPaths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 847
1999; Thorup
SkiRentalProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 849
1990; Karlin,Manasse,McGeogh, Owicki
SlicingFloorplanOrientation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 852
1983; Stockmeyer
SnapshotsinSharedMemory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 855
1993; Afek, Attiya, Dolev, Gafni, Merritt, Shavit
SortingSignedPermutationsbyReversal(ReversalDistance) . . . . . . . . . . . . . . . . . . . . . . . . . . . 858
2001; Bader, Moret, Yan
SortingSignedPermutationsbyReversal(ReversalSequence) . . . . . . . . . . . . . . . . . . . . . . . . . . . 860
2004; Tannier, Sagot
Table of Contents XXV
SortingbyTranspositionsandReversals(ApproximateRatio1.5) . . . . . . . . . . . . . . . . . . . . . . . . . 863
2004; Hartman, Sharan
SparseGraphSpanners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 867
2004; Elkin, Peleg
SparsestCut . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 868
2004; Arora, Rao, Vazirani
SpeedScaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 870
1995; Yao, Demers, Shenker
SpherePackingProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 871
2001; Chen, Hu, Huang, Li, Xu
SquaresandRepetitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 874
1999; Kolpakov, Kucherov
StableMarriage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 877
1962; Gale, Shapley
StableMarriageandDiscreteConvexAnalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 880
2000; Eguchi, Fujishige, Tamura, Fleiner
StableMarriagewithTiesandIncompleteLists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 883
2007; Iwama, Miyazaki, Yamauchi
StablePartitionProblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 885
2002; Cechlárová, Hajduková
StackelbergGames:ThePriceofOptimum. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 888
2006; Kaporis, Spirakis
StatisticalMultipleAlignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 892
2003; Hein, Jensen, Pedersen
StatisticalQueryLearning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 894
1998; Kearns
SteinerForest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 897
1995; Agrawal, Klein, Ravi
SteinerTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 900
2006; Du, Graham, Pardalos,Wan,Wu, Zhao
StochasticScheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 904
2001; Glazebrook, Nino-Mora
StringSorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 907
1997; Bentley, Sedgewick
SubstringParsimony . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 910
2001; Blanchette, Schwikowski, Tompa
XXVI Table of Contents
SuccinctDataStructuresforParenthesesMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 912
2001;Munro, Raman
SuccinctEncodingofPermutations:ApplicationstoText Indexing . . . . . . . . . . . . . . . . . . . . . . . . 915
2003;Munro, Raman, Raman, Rao
SuffixArrayConstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 919
2006; K?rkk?inen, Sanders, Burkhardt
SuffixTreeConstructioninHierarchicalMemory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 922
2000; Farach-Colton, Ferragina,Muthukrishnan
SuffixTreeConstructioninRAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 925
1997; Farach-Colton
SupportVectorMachines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 928
1992; Boser, Guyon, Vapnik
SymbolicModelChecking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 932
1990; Burch, Clarke,McMillan, Dill
Synchronizers,Spanners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 935
1985; Awerbuch
TableCompression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 939
2003; Buchsbaum, Fowler, Giancarlo
TailBoundsforOccupancyProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 942
1995; Kamath, Motwani, Palem, Spirakis
TechnologyMapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 944
1987; Keutzer
TeleportationofQuantumStates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 947
1993; Bennett, Brassard, Crepeau, Jozsa, Peres,Wootters
Text Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 950
1993;Manber, Myers
Thresholds of Randomk-SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 954
2002; Kaporis, Kirousis, Lalas
TopologyApproach inDistributedComputing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 956
1999; Herlihy Shavit
Trade-OffsforDynamicGraphProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 958
2005; Demetrescu, Italiano
TravelingSalesPersonwithFewInnerPoints . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 961
2004; De??neko, Hoffmann, Okamoto, Woeginger
TreeCompressionandIndexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 964
2005; Ferragina, Luccio, Manzini,Muthukrishnan
Table of Contents XXVII
TreewidthofGraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 968
1987; Arnborg, Corneil, Proskurowski
TruthfulMechanismsforOne-ParameterAgents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 970
2001; Archer, Tardos
TruthfulMulticast . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 973
2004; Wang, Li, Wang
TSP-BasedCurveReconstruction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 976
2001; Althaus, Mehlhorn
Two-DimensionalPatternIndexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 979
2005; Na, Giancarlo, Park
Two-DimensionalScaledPatternMatching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 982
2006; Amir, Chencinski
Two-IntervalPatternProblems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 985
2004; Vialette
2007; Cheng, Yang, Yuan
Two-LevelBooleanMinimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 989
1956;McCluskey
UndirectedFeedbackVertexSet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 995
2005; Dehne, Fellows, Langston, Rosamond, Stevens;
2005; Guo, Gramm, Hüffner, Niedermeier,Wernicke
UtilitarianMechanismDesignforSingle-MindedAgents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 997
2005; Briest, Krysta, V?cking
VertexCoverKernelization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1003
2004; Abu-Khzam, Collins, Fellows, Langston, Suters, Symons
VertexCoverSearchTrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1006
2001; Chen, Kanj, Jia
VisualizationTechniquesforAlgorithmEngineering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1008
2002; Demetrescu, Finocchi, Italiano, N?her
VoltageScheduling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1011
2005; Li, Yao
Wait-FreeSynchronization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1015
1991; Herlihy
WeightedConnectedDominatingSet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1020
2005; Wang,Wang, Li
WeightedPopularMatchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1023
2006;Mestre
XXVIII Table of Contents
WeightedRandomSampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1024
2005; Efraimidis, Spirakis
WellSeparatedPairDecomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1027
2003; Gao, Zhang
WellSeparatedPairDecompositionforUnit–DiskGraph. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1030
1995; Callahan, Kosaraju
WireSizing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1032
1999; Chu, Wong
Work-FunctionAlgorithmforkServers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1035
1994; Koutsoupias, Papadimitriou
Chronological Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1039
Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1053
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1157

算法设计与分析基础

2008-06-28 11:57:45

【编辑推荐】
作者在本书中采用了一种算法设计技术的新分类法，使得我们能以一种一致的方式涵盖许多经典的算法，而这在传统分类法中是无法做到的。作为解决问题的通用工具、算法设计技术得到了广泛的应用。尤其是用来解决一些流行的谜题时，它的威力得到了极大的体现。
本书相对同类教材来说，可读性更强，得益于多年来教授算法的经验，作者能够以一种清晰的方式、有条不紊地组织本书的脉络。
本书中的习题超过600道，其中有些习题还利用了网络资源，本书还为所有的习题提供了提示，以帮助读者们很好地达到学习目标。

【内容简介】
作者基于丰富的教学经验，开发了一套对算法进行分类的新方法。这套方法站在通用问题求解策略的高度，对现有的大多数算法都有能进行很好的分类，从而使本书的读者能够沿着一条清晰的、一致的、连贯的道路来探索算法设计与分析这一迷人领域。
本书十分适合计算机专业的本科高年级学生或研究生学习。另外，由于本书的介绍深入浅出，只要具备数据库存和离散数据学的知识，任何有兴趣探究算法秘密的读者也可以自学本书。

【作者简介】
Anany Lcvitin 是Villanova大学计算科学系的教授。他的论文《算法设计技术新途径：弥补传统分类法的缺憾》（A new road map of algorithm design techniques;picking up where the traditional classiflcation leaves off ）受到极高的评价。在SIGCSE会议上，作者做过多次关于算法教学的演讲。

【目录】
第1章绪论
1.1 算法的概念
习题1.1
1.2 算法问题求解基础
习题1.2
1.3 重要的问题类型
习题1.3
1.4 基本数据结构
习题1.4
小结
第2章算法效率分析基础
2.1 分析框架
习题2.1
2.2 渐进符号和基本效率类型
习题2.2
2.3 非递归算法的数学分析
习题2.3
2.4 递归算法的数学分析
习题2.4
2.5 例题：斐波那契数列
习题2.5
2.6 算法的经验分析
习题2.6
2.7 算法可视法
习题2.7
小结
第3章蛮力法
3.1 选择排序和冒泡排序
习题3.1
3.2 顺序查找和蛮力字符串匹配
习题3.2
3.3 最近对和凸包问题的蛮力算法
习题3.3
3.4 穷举查找
习题3.4
小结
第4章分治法
4.1 合并排序
习题4.1
4.2 快速排序
习题4.2
4.3 折半查找
习题4.3
4.4 二叉树遍历及其相关特性
习题4.4
4.5 大整数乘法和Strassen矩阵乘法
习题4.5
4.6 用分治法解最近对问题和凸包问题
习题4.6
小结
第5章减治法
5.1 插入排序
习题5.1
5.2 深度优先查找和广度优先查找
习题5.2
5.3 拓扑排序
习题5.3
5.4 生成组合对象的算法
习题5.4
5.5 减常因子算法
习题5.5
5.6 减可变规模算法
习题5.6
小结
第6章变治法
6.1 预排序
习题6.1
6.2 高斯消去法
习题6.2
6.3 平衡查找树
习题6.3
6.4 堆和堆排序
习题6.4
6.5 霍纳法则和二进制幂
习题6.5
6.6 问题化简
习题6.6
小结
第7章时空权衡
7.1 计数排序
习题7.1
7.2 串匹配中的输入增强技术
习题7.2
7.3 散列法
习题7.3
7.4 B树
习题7.4
小结
第8章动态规划
8.1 计算二项式系数
习题8.1
8.2 Warshall算法和Floyd算法
习题8.2
8.3 最优二叉查找树
习题8.3
8.4 背包问题和记忆功能
习题8.4
小结
第9章贪婪技术
9.1 Prim算法
习题9.1
9.2 Kruskal算法
习题9.2
9.3 Dijkstra算法
习题9.3
9.4 哈夫曼树
习题9.4
小结
第10章算法能力的极限
10.1 如何求下界
习题10.1
10.2 决策树
习题10.2
10.3 P、NP和NP完全问题
习题10.3
10.4 数值算法的挑战
习题10.4
小结
第11章超越算法能力的极限
11.1 回溯
习题11.1
11.2 分支界限
习题11.2
11.3 NP困难问题的近似算法
习题11.3
11.4 解非线性方程的算法
习题11.4
小结
跋
附录A：算法分析的实用公式
对数的性质
组合学
重要的求和公式
求和乘法法则
用定积分逼近求和式
向下取整和向上取整公式
其他
附录B：递推关系简明指南
序列和递推关系
递推关系的求解方法
算法分析中的常见递推类型
习题提示
　第1章
　第2章
　第3章
　第4章
　第5章
　第6章
　第7章
　第8章
　第9章
　第10章
参考文献

How to solve It Modern Heuristics （英文版）

2008-06-23 16:16:05

通过一系列贯穿于章节间的有趣难题，本书深入浅出地阐述了如何利用计算机来求解问题的一些现代启发式方法。
全书包括两部分，共分15章。第1章指出了造成问题求解困难的主要原因。第2章简要介绍了一些基本概念。第3章和第4章综述了传统的优化算法，包括穷举搜索法、局部搜索法、贪婪法、分而治之法、动态规划法和分枝定界法等。第5章阐明了两种现代搜索算法，即模拟退火法和禁忌搜索法。以上各章构成了本书的第— 部分。书中第二部分主要阐述求解问题的演化方法。第6章和第7章介绍了设计一般演化算法的细节问题。第8章至第10章分别对于TSP问题、约束处理问题以及如何调整算法等问题详细综述了如何采用演化方法来求解这些问题所作的大量努力。第11章讨论了随时间变化的环境和噪声问题。第12章和第13章分别提供了神经网络和模糊系统的有关内容。第14章对混合系统和扩展演化算法作了简短的一般性讨论。最后第15章总结了全书的内容并给出了在实际求解问题时部分有价值的提示。
本书是一本学习如何通过现代启发式方法利用计算机来求解问题的教材，读者对象是高等学校理工科和经济管理专业的广大师生。同时本书丰富的文献综述对于从事计算机特定领域(如算法设计、演化计算、工程优化、神经网络、模糊系统等)研究的科技人员也具有很大的参考价值。

自然语言理解的方法与策略

2008-06-19 21:38:05

【出版日期】 2000年1月
【开本】 32开
【页码】 300
【版次】1-1
中国版本图书馆CIP数据核字(1999)第68383号
【内容简介】
本书的宗旨，是力图对迄今为止已经发展起来的有关自然语言理解的各种方法和策略作一概要介绍、回顾和总结。
本书共分7章。第1章到第3章是从介绍一个简单的、面向微型世界（一个作图世界）的系统着手，引进有关自然语言理解的一些基本原则、方法和概念。诸如“语法的形式化定义”、“语法或知识的内部表达”、“模式匹配”、“转移网络”、“分析程序”等待。第4章到第6章进而探讨有关自然语言理解的一般方法，即面向真实世界的句法分析方法、语义分析方法和篇章分析方法。最后一章即第7章则着重讨论自然语言理解的策略问题，以及跟理解的策略有关的心理学问题。在所有这些讨论中，我们的立足点是在一般的自然语言理解问题上面，但是仍把注意力着重放在有关汉语的自动理解方面。由于迄今为止学术界所提出的各种自然语言理解的方法和策略，绝大部分是针对西洋语言的自动理解的，虽然许多方面也能适合于汉语的特点加以改造。在这一方面，本书也力争能有所贡献。

【目录】
《现代语言学系列》序
导言
1、一个简单的自然语言理解系统
1.1、自动作图世界
1.2、内部文本的分类及其形式
1.3、输入文本的大致范围
1.4、输入文本的分类和分析
1.4.1、赋值语句的分析
“点的名称”的自动分析
“动词短语”的自动分析
词以及词的分类概念
”座标短语“的自动分析
赋值语句自动分析的总有限状态图和Prolog程序
1..4.2、动作语句的分析
2、系统的扩展
2.1、引进代词的所指问题
2.2、引进省略的填补问题
2.3、引进三角形的概念问题
2.4、引进颜色词
2.5、“绿色三角形”问题和Prolog程序
3、系统的进一步扩展
3.1、图形的变化及其所指问题
3.1.1、图形的移动
3.1.2、图形移动所引起的所指问题
3.1.3、所指对象的多重化问题
3.1.4、所指对象的恒定性问题
3.1.5、图形形状的改变引起的所指问题
3.2、时间概念的表达和处理
3.2.1、时制的表态和处理
3.2.2、时态的表态和处理
3.3、从作图世界到真实世界
4、句法分析方法
4.1、句法分析的作用
4.2、汉语句法结构的类型
4.3、汉语句法分析的方法
5、语义分析方法
5.1、语义分析的作用
5.2、句子语义结构关系的分析
5.3、句子意义的表达和组合
5.3.1、句子意义的逻辑表达
命题逻辑
谓词逻辑
5.3.2、句子意义的组合
5.4、词语搭配上的语义限制问题
5.4.1、语义限制的性质
5.4.2、语义限制的范围
5.4.3、语义限制的说明
5.4.4、语义限制的实施
6、篇章分析方法
6.1、篇章分析的任务和依据
6.2、框架分析法
6.3、手本分析法
6.4、计划分析法
7、自然语言理解的策略及其心理学基础
7.1、自然语言机器理解的两种策略
7.2、自然语言机器理解策略的心理学基础
主要文献目录

现代汉语动词语义计算理论靳光瑾

2008-06-19 21:34:46

内容简介】
今天，没有人会怀疑计算机处理语言文字的迫切需要，但是也很少有人能说清自然语言处理将会有什么样的乐观前景。当人们考虑计算机如何不断适应处理本国语言文字问题的时候，面对汉语时不禁会增添一分困扰和责任感。目前汉语研究侧重在结构形式，况且还短少独立、完整、有共识的理论体系，计算语言学研究成果也限于句法分析和统计方法。就中文信息处理的发展看，迫切需要加强现代汉语和语义形式化的研究。
如果要清醒地总结国内语言学及语言信息处理研究领域的经验教训的话，与其只对所取得的种种成果的短效性和局限性感到不满，还不如对久久未能取得突破性进展的方法论上的缺憾作上点反思。
随着计算机科学的深入发展，越来越明显的表明在程序语言、自然语言、数理逻辑这三个不同领域之间存在着种种对应性和相似性。语言学的研究将语言现象总结为规律；数学的研究将语言规律和内在关系抽象为数学描述并使分析过程形式化和可计算化；计算机科学的研究将这些数学表达式及计算规则在计算机上具体实现。完成这样的一个大流程，需要三个领域知识的结合：汉语、数学、计算机科学。概括地说，就是两个步骤：第一，汉语表达式的量化与数学抽象；第二，抽象表达式在计算机上计算和实现。这两步根本不同于现在直接用数据结构表示汉语表达式的中文信息处理的方法。原有的研究方法不能确切地解释汉语语义，因为它没有涉及语句的内涵义，而把同一个表达式在不同环境中的多次出现都看作同一个外延义。
本书研究现代汉语的计算语义。计算语义研究的是一种可计算的语义表示形式。要使汉语语义分析过程像函数程序一样成为一个计算过程，最让中外学者关心而又感到困惑的是：汉语语义的表示形式是什么？表达式的计算规则是什么？如果汉语语义的抽象表示形式能与国际上的现代语言学、计算机科学理论、数理逻辑这三个不同学科交融，那么演算规则完全可以从这些领域中的现有理论成果中得到移植和借鉴，因此汉语语义的抽象表达形式是首要的研究内容。本书旨在定义汉语句子的语义抽象表达式，它兼有对人的可读性、机器的自动生成和适用于中文信息处理的特点。......

认知语言学概论--语言的神经认知基础

2008-06-19 21:28:35

神经认知语言学是美国60年代兴起的生根语言学流派之一，创始人是著名语言学家Sydney Lamb。该理论注重语言学和其它学科的关系，强调语言学理论不悖于大脑神经事实，其朴实的理论论据引人深思。神经认知语言学让人看到语言学的确是门交叉学科，它涉及登记处科学、神经生理学、认知科学的连通主义理论、语符学等。该理论是一种语言学理论，同时，可以说又是一种神经生理理论、认知理论、语符理论，它在认知科学计算机工程方面的应用很有特色。本书努力反映理论的多视角特色，并以汉语为实例，介绍分层次语言关系系统的分析、综合和操作检验的主要策略。
【目录】
序
前言
第一章兰姆和语言学
第一节好奇和冒险
第二节走近语言学
第三节伯克利
第四节层次分析
第五节重归耶鲁
第六节关系网络
第七节莱思大学
第二章语言登记处系统
第一节语言是信息
第二节语言信息的过程
第三节两种内部语言信息
第四节语言信息的寄栽性
第五节语言信息的传递性
第六节内部语言是信息系统
第七节语言信息系统的共享性
第八节语言信息系统的自调节性
第九节自调节信息系统的研究方法
第十节语言信息和人
第十一节小结
第三章语言和大脑
第一节语言和大脑
第二节宏观大脑的功能区域
一、大脑的宏观构造
二、大脑的功能区域
第三节微观大脑的神经网络
一、神经元的功能构造
二、神经元的信息传递
第四节信息加工的大脑机制
一、语言的生成机制
二、语言的理解机制
第五节大脑记忆
第六节大脑的发育成熟
第七节大脑和心智
第八节小结
第四章语言研究的认知取向
第一节认知研究的范围
第二节认知研究的主要学科群
第三节为什么认知取向
第四节信息加工理论
第五节信息加工的过程
第六节符号主义
第七节认知研究的三平面
第八节连通主义
一、神经元的加权学习
二、神经网络的连接学习
三、网络的学习和记忆
第九节神经认知语言学的关系网络模式
一、关系网络和形式神经网络的区别
二、关系网络是个双向模式
第十节范畴化
一、典型论
二、亲属相似关系
三、优势规则
四、词网
五、关系网络
第十一节小结
第五章语符关系系统
第一节符号关系
一、索绪尔的观点
二、叶尔姆斯列夫的观点
三、兰姆的观点
第二节层次
第三节关系
一、基本类型
二、连元
第四节语符关系的特征
一、语词的临摹
二、句子的临摹
第五节语符关系的系统
一、关系和系统
二、系统的特征
三、功能和系统
第六节小结
第六章走入神经认知语言学
第一节语言观
第二节理论研究的若干问题
一、生理性和社会性
二、个性和共性
三、先天性和后天性
四、历时语言学和共时语言学
五、内部语言系统和外部语言现象
六、语言能力和语言运用
七、关系连通和成分模块
八、语言和思维
第三节理论目标
第四节理论模式
一、关系性
二、层次性
三、双向操作
四、并行操作
五、遵循科学理论四大原则
第五节方法论
第六节小结
第七章语篇概念系统
第一节概念也是关系
第二节概念关系的层级组织
第三节概念关系的有序组织
第四节谋篇的信息
一、口语和笔语
二、修改类和即兴类
三、交际者背景
四、交际场合
第五节独白的宏观结构
第六节对话的宏观结构
第七节语篇的信息流
第八节小结
第八章小句的概念结构
第一节事态视角
一、时空结构
二、动作结构
三、使役结构
第二节谓词
一、空间谓词
二、动作谓词
三、使役谓词
第三节谓元
第四节其它成分
第五节小句的概念结构
一、基本概念结构的重合
二、必有成分和可有成分
第六节语义域
一、语义域的分类
二、各语义域的异同
第七节小结
第九章语符体现关系
第一节小句的体现关系
第二节语气体现条件
第三节组篇体现条件
第四节短语、复句的体现
一、短语和小句
二、复句和小句
第五节语篇的体现关系
第六节语音体现
第七节字和音位的体现关系
第八节音位和语音特征的体现关系
第九节语流音变
第十节超音节语音特征
第十一节小结
第十章分析、综合、操作检验
第一节义词体现关系
一、分析
二、综合
三、操作验证
第二节词音体现关系
一、分析
二、综合
三、操作验证
第三节图式表述
一、模式构建
二、生成操作
三、理解操作
第十一章神经认知理论和其它理论流派
第一节美国后结构主义
一、新布龙菲尔德派
二、语位学
第二节欧洲各流派
一、哥本哈根派的语符学
二、布拉格派
三、伦敦派以及系统功能语法
第三节转换生成语法
第四节概念语义学
第十二章理论的形成、内部分歧和发展
第一节形成和发展
第二节贡献和内部分歧
第三节批评、成果和展望
第四节理论的重大应用前景
参考文献

机器翻译原理赵铁军

2008-06-19 21:20:26

【出版日期】 2000年6月
【版次】1-1
【内容简介】本书是国内第一本全面，系统

论述机器翻译实现原理和技术的著作。
本书以作者的实际研究与开发经验为基

础，全面介绍了当前国内外机器翻译研究的

最新进展，取材丰富，内容深入。每章后面

均配有思考题，便于教学。书后列出全部参

考文献，便于读者查找相关资料作进一步研

究。本书可作为高等院校高年级本科生和研

究生的教材，也可作为机器翻译与计算语言

学研究者的参考书。

【目录】
第一章机器翻译概述
1.1 机器翻译的任务和意义
1.2 机器翻译的实现过程
1.3 机器翻译方法、系统及评价
1.4 机器翻译的历史发展
第二章机器翻译基础与资源
2.1 自然语言歧义问题
2.2 自然语言知识表示
2.3 机器词典
2.4 语料库
2.5 语法概述
2.6 语法I--汉语语法概说
2.7 语法II--英语语法概说
2.8 语法III--日语语法概说
第三章词法分析
3.1 汉语分词规范片自动分词基本算法
3.2 未登录词的识别
3.3 汉语自动分词的切分歧义及其消除
3.4 英语形态还原
3.5 日语的形态素解析
第四章词性标注
4.1 词性兼类与词性标注
4.2 词性标注方法
4.3 隐马尔可夫模型与Viterbi算法
4.4 英语词性标注的实现
4.5 汉语词性标注的实现
第五间句法分析
5.1 句法分析概述
5.2 浅层分析
5.3 英语和汉语BaseNP的识别
5.4 上下文无关文法简介
5.5 LR分析算法
5.6 线图分析算法
5.7 移进归约分析方法
5.8 日语句子结构分析
第6章语法理论
6.1 短语结构语法和Chomsky文法体系
6.2 广义短语结构语法
6.3 中心语驱动的短语结构语法
6.4 语汇功能语法
6.5 树邻接语法
第七章语义分析
7.1 语义分析技术的发展
7.2 命题逻辑和谓词逻辑
7.3 格语法与语义分析
7.4 语义网络和剧本
7.5 汉语句子的语义分析
7.6 选择限制学说和优选语义分析
7.7 词汇语义分析方法
第8章译文转换与生成
8.1 机器翻译中转换与生成概述
8.2 句法层次的转换
8.3 语义层次的转换
8.4 混合转换方法
8.5 译文生成方法
第九章词义消歧
9.1 概述
9.2 基于AI的方法
9.3 基于知识的方法
9.4 基于语料库的方法
9.5 问题和展望
第十章非基于转换的机器翻译方法
10.1 机器翻译的中间语言方法
10.2 基于统计的机器翻译方法
10.3 基于实例的机器翻译方法
第十一章机器翻译评价
11.1 什么是机器翻译评价
11.2 机器翻译评价的复杂性
11.3 机器翻译的成败--对机器翻译研究的评

价
11.4 机器翻译的优劣--对机器翻译系统的评

价
11.5 机器翻译系统评价的实践
附录一
附录二
参考文献

计算理论_计算机基础理论_计算机类_最新资料_得益网

Introduction to Algorithms

通信中的自适应信号处理

数字逻辑基础

强调数字推算的100道趣题

The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Tu

哈工大课堂录像集合论与图论51-54

哈工大课堂录像集合论与图论46-50

哈工大课堂录像集合论与图论41-45

哈工大课堂录像集合论与图论36-40

哈工大课堂录像集合论与图论31-35

哈工大课堂录像集合论与图论26-30

哈工大课堂录像编译原理56-58

哈工大课堂录像编译原理51-55

哈工大课堂录像编译原理46-50

哈工大课堂录像编译原理41-45

哈工大课堂录像编译原理36-40

哈工大课堂录像编译原理31-35

哈工大课堂录像编译原理26-30

Computational Dynamics Second Edition

工程矩阵理论07-09

哈工大课堂录像编译原理04-05

哈工大课堂录像编译原理21-25

哈工大课堂录像编译原理16-20

哈工大课堂录像编译原理11-15

哈工大课堂录像编译原理06-10

哈工大课堂录像编译原理01-03

哈工大课堂录像集合论与图论16-20

哈工大课堂录像集合论与图论21-25

哈工大课堂录像集合论与图论11-15

Neural Networks Algorithms, Applications and Programming Techniques

算法概论（Algorithm）

Algorithms

哈工大课堂录像集合论与图论6-10

哈工大课堂录像集合论与图论1-5

注册表实用手册v5.2

Encyclopedia of Algorithms

算法设计与分析基础

How to solve It Modern Heuristics （英文版）

自然语言理解的方法与策略

现代汉语动词语义计算理论 靳光瑾

认知语言学概论--语言的神经认知基础

机器翻译原理 赵铁军

现代汉语动词语义计算理论靳光瑾

机器翻译原理赵铁军