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

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.

《编译原理第二版》

2008-09-04 18:31:14

【内容简介】
本书全面、深入地探讨了编译器设计方面的重要主题，包括词法分析、语法分析、语法制导定义和语法制导翻译、运行时刻环境、目标代码生成、代码优化技术、并行性检测以及过程间分析技术，并在相关章节中给出大量的实例。与上一版相比，本书进行了全面的修订，涵盖了编译器开发方面的最新进展。每章中都提供了大量的系统及参考文献。
本书是编译原理课程方面的经典教材，内容丰富，适合作为高等院校计算机及相关专业本科生及研究生的编译原理课程的教材，也是广大技术人员的极佳参考读物。

目录信息】

目录
前言
第1章引论 2
1.1 语言处理器 2
1.1.1 1.1节的练习 4
1.2 一个编译器的结构 4
1.2.1 词法分析 5
1.2.2 语法分析 6
1.2.3 语义分析 7
1.2.4 中间代码生成 7
1.2.5 代码优化 8
1.2.6 代码生成 8
1.2.7 符号表管理 9
1.2.8 将多个步骤组合成趟 9
1.2.9 编译器构造工具 9
1.3 程序设计语言的发展历程 10
1.3.1 走向高级程序设计语言 10
1.3.2 对编译器的影响 11
。。。。。。。

哈工大课堂录像集合论与图论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 机器翻译系统评价的实践
附录一
附录二
参考文献

计算智能的数学基础

2008-06-19 21:11:07

【内容简介】
由于计算机网络的迅速发展，对海量数据的信息处理受到理论和工程界的广泛关注，其中尤以基于仿生学原理的计算智能在高级信息处理中占据重要的地位，本书着重介绍了人工神经网络、遗传算法和模糊逻辑的基本模型、理论及算法及其在工程技术中的应用，如分类器、数据挖掘、现代优化方法和模糊控制，并且给出了基于MATLAB的数值实验，本书每章后均配有习题，以供学生复习，巩固书中所学知识。

【目录】
第一章概述
1.1 信息科学与机器智能
1.1.1 信息与信息科学
1.1.2 智能与机器智能
1.1.3 机器智能的三个学派
1.2 计算智能的主要分支
1.2.1 人工神经网络
1.2.2 遗传算法
1.2.3 模糊逻辑
1.3 计算智能研究的主要问题
1.3.1 学习
1.3.2 搜索
1.3.3 推理
1.4 计算智能研究的主要方法
1.4.1 模型
1.4.2 算法
1.4.3 实验
第二章感知器
2.1 分类问题
2.2 感知器
2.2.1 感知器模型
2.2.2 感知器学习
2.2.3 线性可分
2.2.4 收敛性
2.2.5 复杂性
2.3 算法的容量
2.3.1 概念
2.3.2 随机MP模型容量估计
2.4 非线性感知器
2.4.1 非线性权感知器
2.4.2 Newton迭代法
2.4.3 Newton法的收敛性
2.5 高阶感知器
2.5.1 高阶感知器模型
2.5.2 Bonlean函数
2.6 模糊感知器
2.6.1 模糊感知器模型
2.6.2 算法的收敛性
第三章人工神经网络
3.1 单层前向网
3.1.1 单层前向网模型
3.1.2 线性单层网
3.2 最优化方法
3.2.1 多元函数的极值
3.2.2 梯度法
3.2.3 最小二乘法
3.3 多层前向网
3.3.1 双层前向网
3.3.2 学习目标
3.3.3 误差的后向传播
3.3.4 前向网络的学习算法
3.4 径向基函数
3.4.1 插值
3.4.2 径向基函数网
3.5 回归神经网络
3.5.1 Hopfield网模型
3.5.2 系统的稳定性
3.5.3 系统的收敛性
3.5.4 纠错学习问题
第四章支撑向量机
4.1 最优分离超平面
4.1.1 最优分离超平面
4.1.2 二次规划
4.1.3 KKT条件
4.1.4 分类超曲面
4.2 支撑向量机
4.2.1 线性支撑向量机
4.2.2 Gauss核支撑向量机
4.3 SVM学习算法
4.3.1 SMO算法
4.3.2 SMO算法的实现
4.3.3 SMO算法的改进
4.4 数值实验
第五章遗传算法
5.1 简单遗传算法
5.1.1 得意遗传算法
5.1.2 模式(Schema)
5.2 个体与种群
5.2.1 个体
5.2.2 种群
5.3 遗传算子
5.3.1 选择算子
5.3.2 杂交算子
5.3.3 变异算子
5.3.4 删除算子
5.4 模式
5.4.1 最小模式
5.4.2 杂交算子的整体性质
第六章数值实验
6.1 数学软件MATLAB相关函数
6.1.1 MATLAB简介
6.1.2 相关函数
6.2 感知器数值实验
6.2.1 感知器生成与实例
6.2.2 线性神经网络生成与实例
6.3 BP算法数值实验
6.4 自适应网络
6.4.1 自适应网络简介
6.4.2 自适应网络实验
第七章应用
7.1 旅行商问题
7.1.1 TSP问题描述
7.1.2 连续Hopfield方法
7.1.3 TSP的HNNS模型
7.2 神经网络优化算法
7.2.1 线性规划及对偶问题
7.2.2 神经网络优化模型
7.2.3 凸函数
7.2.4 网络模型的收敛性
7.2.5 数值方法
7.3 TSP的遗传算法
7.3.1 算法描述
7.3.2 程序实现
第八章模糊集与模糊系统
8.1 模糊集与隶属函数
8.1.1 特征函数
8.1.2 模糊集与隶属函数
8.1.3 模糊集合的表示法
8.2 模糊集上的运算
8.2.1 模糊集上的基本运算
8.2.2 模糊集运算的基本性质
8.2.3 模糊集合的代数和、代数积、有界和、有界积
8.3 凸模糊集及其性质
8.3.1 凸模糊集
8.3.2 模糊数
8.3.3 2型模糊集与条件模糊集
8.4 模糊系统与模糊算法
8.4.1 模糊系统与状态
8.4.2 模糊系统的状态方程
第九章模糊逻辑与模糊推理
9.1 基本概念
9.1.1 模糊逻辑
9.1.2 模糊语言
9.1.3 模糊推理
9.2 模糊命题与模糊逻辑公式
9.2.1 模糊命题与模糊关系
9.2.2 析取范式与合取范式
9.3 模糊逻辑公式的化简
9.3.1 主析取范式
9.3.2 最简析取范式
9.4 模糊逻辑函数的分析合成
9.4.1 模糊逻辑函数的分解
9.4.2 模糊逻辑函数的合成
9.5 模糊语言与模糊推理
9.5.1 模糊语言及基本性质
9.5.2 模糊推理及其规则
第十章模糊模式识别与模糊控制
10.1 模糊模式识别的直接方法
10.1.1 最在隶属原则与图形识别
10.1.2 手写数学和字母的识别
10.2 贴近度与模糊模式识别的间接方法
10.2.1 贴近度及有关概念
10.2.2 模糊度与择近原则
10.2.3 利用择近原则朝廷模糊模式识别举例
10.3 模糊控制原理
10.3.1 模糊控制及其类型
10.3.2 模糊控制过程
附录 TSP的遗传算法程序
主要参考文献

计算语言学刘颖编著

2008-06-19 20:58:23

【内容简介】
计算语言学是一门涉及语言学、计算机科学和数学等多门学科交叉的学科，覆盖面很广，本书侧重最经典的工作，阐述计算语言学的基本理论和方法。主要介绍现代句法理论和语义理论，词法、句法和语义阶段重要的分析算法及语料库和统计语言学。本书结构完整，层次分明，条理清楚，既便于教学，又便于自学。
【目录】
1 计算语言学简介
1.1 计算语言学
计算语言学概念
计算语言学与计算机科学
计算语言学与语言学的区别
计算语言学与数理语言学
计算语言学与自然语言
1.2 计算语言学主要研究的内容
1.3 广告牌语言学理论的主要用途
1.4 计算语言学研究的基本方法
理性主义和经验主义
计算语言学研究方法
1.5 计算语言学的发展历程
2 词法分析
2.1 汉语的自动分词
词与自动分词
汉语自动分词的重要性
汉语自动分词方法
汉语切分歧义及其处理
汉语分词的难点
2.2 屈折语的形态还原
屈折语的词法分析
屈折语的词法分析技术
为什么要词法分析
词法分析要分析到何种程度
2.3 小结
3 词性标注
3.1 词性标注
3.2 词性标注的研究方法
规则方法
统计方法朝廷词性标注
基于转换的错误驱动学习
3.3 小结
4 形式语言理论与自动机
4.1 形式语言理论
形式语法
形式语法包括哪些部分
形式语法的定义
形式语法的特点
研究形式语法的必要性
语法的类型
4.2 自动机理论
图灵机
线性有界自动机
有限自动机
下推自动机
4.3 乔姆斯基层级和自然语言
文法、自动机和语言的关系
哪一种语法最宜于用来生成自然语言的句子
4.4 小结
5 现代句法理论
5.1 转换生成语法
经典理论
乔姆斯基的标准理论
扩充式标准理论
5.2 广义的短语结构语法
引言
句法规则
特征制约系统
语义解释系统
5.3 树连接语法
5.4 中心词驱动的短语结构语法
5.5 功能合一文法
复杂特征集
合一运算
5.5 词汇功能文法
引言
基本成分
词库部分
LFG的两个语法层次结构
功能合格条件
词汇功能语法特点
5.7 范畴语法
5.8 依存语法
5.9 链语法
链语法的形式定义和基本概念
链语法的主要特点
5.10 小结
6 句法分析
6.1 句法分析概念
分析策略
句法分析
6.2 有限状态转移网络、递归转移网络和扩充转移网络
有限状态转移网络
递归转移网络
扩充转移网络
6.3 自顶向下剖析
6.4 厄尔利算法
6.5 LR分析算法
LR（0）算法
LR（1）算法
对LR（K）算法的评价
6.6 富田胜算法
6.7 自底向上的线图算法
6.8 自底向上与自顶向下结合的线图分析算法
6.9 本章进一步讨论
7 语义理论与语义分析
7.1 格语法
格的含义
格语法
词汇部分
转换部分
使用格语法朝廷语义分析：格框架约束分析技术
格语法描写汉语的局限性
7.2 语义网络方法
语义网络的概念
语义网络的概念关系
事件的语义网络表示
事物间语义关系
用语义网络朝廷推理
用语义网络来翻译
基于语义网络的汉语处理
7.3 义素分析法
7.4 优选语义学
语义元素
语义公式
语义模式
使用优选理论翻译英法句子和处理过程
优选语义学主要特点
7.5 蒙塔格语法
引言
MG句法部分
MG翻译部分
MG语义部分
7.6 本章进一步讨论
8 语料库与统计语言学
8.1 概率统计与信息论基础
8.2 语料库发展与加工技术
语料库的发展与加工
语料库的作用
8.3 概率语法
n元语法
陷马尔可夫模型及其应用
概率上下文无关语法及其应用
8.4 双语语料库中的对齐技术
基于长度的句子对齐
基于词汇的句子对齐
9 应用系统介绍--机器翻译系统
9.1 机器翻译的概念
9.2 机器翻译的发展
9.3 机器翻译方法
直接翻译法（第一代机器翻译系统）
基于转换的方法
基于中间语言方法
统计方法
基于实例方法
9.4 机器翻译难点
9.5 机器翻译系统采取的其他策略
9.6 机器翻译评估
参考文献

FRONTIERS OF EVOLUTIONARY COMPUTATION

2008-06-12 21:02:23

Preface
This book is a collection of essays, authored by eminent scholars in evolutionary
computation (EC), artificial intelligence (AI), operations research,
complexity theory and mathematics. Each essay revolves around important,
interesting and unresolved questions in the field of evolutionary computation.
The book is designed to be a resource to at least three categories of readers.
First of all, graduate students will find this book a rich source of open research
issues. Imagine participating in an EC research seminar conducted by some of
the best scholars in and around the field! The book also gives experts a chance
to compare and contrast their understanding of the fundamental issues in EC
with the perspectives of their peers. Finally, to the interested scholar it offers a
sample of the kind of problems that are considered worth solving in EC.
Much has been written about how great solutions often have a certain aesthetic
appeal (symmetry, simplicity, originality, unity and so on). In sharp
contrast, characteristics of great problems remain something of a mystery. It is
useful to think of a problem as existing in at least one of four states: undiscovered,
unsolved, solved and hibernating. However, truly interesting problems
— great problems — manage a simultaneous, contrary existence in all four
quadrants. A great problem, to echo Walt Whitman, is often large and contains
multitudes. Every mature field has its great problems. Even fields with a
progressive tradition, like Physics and Mathematics, have problems that refuse
to stay solved. The problem of explaining the directionality of the thermodynamic
arrow of time, and the debate over whether mathematical objects are
invented or discovered are but two examples that comes to mind. Great problems
act as co-ordinate systems for the geography of our imaginations and
explain why we do what we do.
So it is gratifying (rather than alarming) that EC is also evolving its own
collection of really hard problems. For example, is an evolutionary process
an algorithmic process (in the sense of Church-Turing)? Are building blocks
theoretical rather than empirical constructs? Which results in EC are dependent
on problem representation and which ones independent of it? What precise
role does crossover play? Is there a way to unify the different formalisms used
to model evolutionary processes? What are the characteristics of problems
solvable by EC? Some of these problems are discussed at length in this volume.
This book grew out of a proposed session for the 2001 International Conference
on Artificial Intelligence in Las Vegas, Nevada. I had thought that
a collection of authoritative essays, each devoted to the description of a substantially
unsolved problem in EC, could help bring coherence to the field,
clarify its important issues, and provoke imaginations. The session was jokingly
dubbed the ‘Hilbert session’ in memory of David Hilbert’s outstanding
example almost a century ago. Unfortunately, time constraints prevented the
session from from going forward. But the highly positive response from the
invitees, as well as from others who had heard about the idea, suggested that
a book could be an alternate and appropriate forum for implementing the idea.
The stray mentions of Hilbert in some of the essays thus hark back to the origins
of this book. Needless to say, the essays were not written with the aim of
being either as definitive or as predictive as Hilbert’s talk turned out to be.
The authors in this collection are wonderfully varied in their backgrounds,
writing styles and interests. But their essays are related by several common
goals: extensions to EC theories, discussion of various formalisms, summaries
of the state of the art, and careful speculation on what could be done to resolve
various issues. The essays also leave no doubt that the ferment caused
by active trading is producing a watershed event in the marketplace of ideas.
Witness for example, the import of ideas from evolutionary theory into Algorithmics
(such as: population thinking, inheritance and recombination), and
the export of ideas from mathematics and computer science into evolutionary
theory (such as: stochastic models, complexity theory, computability). Ideally,
I would have liked to triple the size of the book, include at least a dozen
more authors, and reprint essays from relevant collections. On the other hand,
progress is a side-effect of achieving the possible. While the sample of ideas
and authors herein is certainly not comprehensive, it is very much representative
of what is possible in our field.
EC is a young discipline, and consequently, it is still a field that has the rare
chance to be defined in terms of its unsolved problems, rather than its solved
ones. No doubt, the many encounters offered in this book, the journeys it will
inspire, and the inevitable predilection of problems to get solved, will change
this situation in the next few decades. But till then, this book is meant to serve
as a beckoning toward the roads still not taken.

Contents

List of Figures xi
List of Tables xiii
Preface xv
Contributing Authors xvii
1
Towards a Theory of Organisms and Evolving Automata 1
Heinz Mühlenbein
1 Introduction 1
2 Evolutionary computation and theories of evolution 3
3 Darwin’s continental cycle conjecture 5
4 The system view of evolution 7
5 Von Neumann’s self-reproducing automata 9
6 Turing’s intelligent machine 11
7 What can be computed by an artificial neural network? 13
8 Limits of computing and common sense 14
9 A logical theory of adaptive systems 16
10 The for creating artificial intelligence 19
11 Probabilistic logic 20
11.1 Von Neumann’s probabilistic logics 20
11.2 The conditional probability computer 21
11.3 Modern probabilistic logic 22
12 Stochastic analysis of cellular automata 24
12.1 The nonlinear voter model 24
12.2 Stochastic analysis of one dimensional SCA 26
13 Stochastic analysis of evolutionary algorithms 27
13.1 Boltzmann selection 29
13.2 Factorization of the distribution 29
13.3 Holland’s schema analysis and the Boltzmann distribution
31
14 Stochastic analysis and symbolic representations 33
15 Conclusion 33
2
Two Grand Challenges for EC 37
Kenneth De Jong
1 Introduction 37
2 Historical Diversity 38
3 The Challenge of Unification 39
3.1 Modeling the Dynamics of Population Evolution 40
3.1.1 Choosing Population Sizes 40
3.1.2 Deletion Strategies 40
3.1.3 Parental Selection 40
3.1.4 Reproduction and Inheritance 41
3.2 Choice of Representation 42
3.3 Characteristics of Fitness Landscapes 42
4 The Challenge of Expansion 44
4.1 Representation and Morphogenesis 44
4.2 Non-random Mating and Speciation 45
4.3 Decentralized, Highly Parallel Models 45
4.4 Self-adapting Systems 45
4.5 Coevolutionary Systems 46
4.6 Inclusion of Lamarckian Properties 46
4.7 Modeling Evolutionary Systems 47
5 Summary and Conclusions 47
3
Evolutionary Computation: Challenges and duties 53
Carlos Cotta and Pablo Moscato
1 Introduction 53
2 Challenge #1: Hard problems for the paradigm – Epistasis and
Parameterized Complexity 55
3 Challenge #2: Systematic design of provably good recombination
operators 58
4 Challenge #3: Using Modal Logic and Logic Programming
methods to guide the search 62
4.1 Example 1 63
4.2 Example 2 64
5 Challenge #4: Learning from other metaheuristics and other
open challenges 67
6 Conclusions 69
4
Open Problems in the Spectral Analysis of Evolutionary Dynamics 73
Lee Altenberg
1 Optimal Evolutionary Dynamics for Optimization 76
1.1 Spectral Conditions for Global Attraction 78
1.2 Spectral Conditions for Rapid First Hitting Times 78
1.3 Rapid Mixing and Rapid First Hitting Times 80
1.4 Some Analysis 82
85 1.5 Transmission Matrices Minimizing
1.6 Rapid First Hitting Time and No Free Lunch Theorems 87
2 Spectra for Finite Population Dynamics 87
2.1 Wright-Fisher Model of Finite Populations 88
2.2 Rapid First Hitting Time in a Finite Population 90
3 Karlin’s Spectral Theorem for Genetic Operator Intensity 92
3.1 Karlin’s Theorem illustrated with the Deceptive Trap
Function 93
3.2 Applications for an Extended Karlin Theorem 95
3.3 Extending Karlin’s Theorem 96
3.4 Discussion 98
4 Conclusion 99
5
and Adaptive Memory Metaheuristics
Gary A. Kochenberger, Fred Glover, Bahram Alidaee and Cesar Rego
Solving Combinatorial Optimization Problems via Reformulation 103
1 Introduction 104
2 Transformations 105
3 Examples 106
4 Solution Approaches 108
4.1 Tabu Search Overview 108
5 Computational Experience 109
6 Summary 110
6
Problems in Optimization 115
William G. Macready
1 Introduction 115
2 Foundations 116
3 Connections 120
4 Applications 125
5 Conclusions 127
7
EC Theory - “In Theory” 129
Christopher R. Stephens and Riccardo Poli
8
Asymptotic Convergence of Scaled Genetic Algorithms 157
Lothar M. Schmitt
1 Notation and Preliminaries 162
1.1 Scalars and vectors 162
1.2 Matrices and operator norms 163
1.3 Stochastic matrices 164
1.4 Creatures and populations 167
2 The Genetic Operators 168
2.1 Multiple-spot mutation 169
2.2 Single-cutpoint regular crossover 171
2.3 The fitness function and selection 174
3 Convergence of Scaled Genetic Algorithms to Global Optima 177
3.1 The drive towards uniform populations 177
3.2 Weak ergodicity 179
3.3 Strong ergodicity 180
3.4 Convergence to global optima. 182
3.5 The Vose-Liepins version of mutation-crossover 186
4 Future Extensions of the Theory 187
4.1 Towards finite-length analysis on finite-state machines 187
4.2 Estimates for finite-length genetic algorithms à la Catoni 188
4.3 Adding sampling noise 189
4.4 Further analogy with simulated annealing: parallelism
and sparse mutation 189
4.5 Analysis from inside-out and outside-in 190
4.6 Non-monotone and self-adapting annealing sequences 191
4.7 Discrete vs. continuous alphabets 192
5 Appendix — Proof of some basic or technical results 192
9
of Genetic and Evolutionary Computation
John R. Koza, Matthew J. Streeter and Martin A. Keane
The Challenge of Producing Human-Competitive Results by Means 201
1 Turing’s Prediction Concerning Genetic and Evolutionary Computation
202
2 Definition of Human-Competitiveness 202
3 Desirable Attributes of the Pursuit of Human-Competitiveness 203
3.1 Utility 203
3.2 Objectivity 204
3.3 Complexity 204
3.4 Interminability 206
4 Human-Competitiveness as a Compass for Theoretical Work 206
5 Research Areas Supportive of Human-Competitive Results 207
6 Promising Application Areas for Genetic and Evolutionary Computation
207
7 Acknowledgements 208
10
Case Based Reasoning 211
Vivek Balaraman
1 Introduction 211
2 Case-Based Reasoning 213
3 Case Memory as an Evolutionary System 216
3.1 A Simple Model of ECM 217
3.1.1 Case-Base 217
3.1.2 Environment 217
3.1.3 Generate Solution 218
3.1.4 Evaluate 219
3.2 Reorganize 219
3.3 Discussion 219
4 Hybrid Systems 224
4.1 Type A - CBR as a memory, EA as the optimizer 225
4.2 Type B - EA as CBR System Parameter Optimizers 226
4.3 Discussion 227
5 Evolving Higher Levels 229
5.1 Schemas 229
5.2 A brief aside on levels of higher expertise 231
5.3 Towards memory based reasoning 232
5.3.1 C-Schemas as Building Blocks 233
6 Conclusions 237
11
The Challenge Of Complexity 243
Wolfgang Banzhaf and Julian Miller
1 GP Basics and State of the Art 245
2 The Situation in Biology 248
3 Nature’s way to deal with complexity 249
4 What we can learn from Nature? 254
5 A possible scenario: Transfer into Genetic Programming 256
6 Conclusion 258
Author Index 261
Index 267