Mathematics for the analysis of algorithms (2nd ed.)
Mathematics for the analysis of algorithms (2nd ed.)
复制标题
DOI：
10.1109/proc.1986.13628
复制
发表时间：
1986-09
影响因子：
20.6
通讯作者：
Rob Haskins
中科院分区：
文献类型：
--
作者：
Rob Haskins
这本专著是计算机科学或应用数学研究生的理想伴侣。这些材料取自斯坦福大学的一门高级课程。它以复变量理论和组合分析为背景。它涵盖了二项式恒等式、递归关系、算子方法和渐近分析。专著的其余部分致力于考试问题及其解决方案。有了这本书和Knuth的《计算机程序设计艺术》第三卷的副本，读者几乎可以重现讲座。对于该领域的研究人员来说，这本书的优势在于它的紧凑性。可以快速查找主题，如果讨论不完整，可以跟踪许多适当的参考资料。作者对与主题相关的许多难题的攻击也使本书对研究人员非常有用。在其中一个更吸引人的章节中，哈希的主题是通过运算符方法来探索的。在本专著的典型风格中，分析是通过例子来呈现的，在这种情况下，是饼干怪物问题。饼干怪物问题计算怪物成长到大小为kt1的概率，假设它捕获和吞噬饼干的能力与它当前存储的饼干(k)成正比。分析使用了特征算子方法，并讨论了菜鸟怪物算法，从而对合并哈希和开放寻址进行了令人耳目一新的清晰阐述。
This monograph is an ideal companion for a graduate student in computer science or applied mathematics. The material was taken from an advanced course at Stanford. It assumes a background in complex variable theory and combinatorial analysis. It, covers binomial identities, recurrence relations, operator methods, and asymptotic analysis. The remainder of the monograph is devoted to exam questions and their solutions. Armed with this and a copy of volume 3 of Knuth's The Art of Computer Programming, the reader can almost re-create the lectures. for a researcher in the field, the strength of this book lies in its compactness. A topic can be quickly looked up and, if the discussion is not complete, many appropriate references can be followed up. The authors' attack on many difficult problems associated with the topics also makes the book quite useful to researchers. In one of the more engaging chapters, the subject of hashing is explored via operator methods. In a fashion typical of the monograph, analysis is presented by example, in this case, the cookie monster problem. The cookie monster problem calculates the probability that the monster will grow to size k t 1, given that its ability to catch and devour cookies is proportional to its current store of cookies ( k ) . The analysis uses the eigenoperator approach and the discussion of the rookie monster algorithm leads into a refreshingly clear exposition of coalesced hashing and open addressing.