Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox
Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox
复制标题
顺序和并行算法和数据结构：基本工具箱
DOI：
10.1007/978-3-030-25209-0
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
R. Dementiev
中科院分区：
文献类型：
--
作者：
P. Sanders;K. Mehlhorn;M. Dietzfelbinger;R. Dementiev
这一变化的原因是顺序处理器已经不再从增加的电路复杂性中获得成比例的性能改善。尽管集成电路中的晶体管数量（仍然）每两年翻一番（摩尔定律），但使用这种晶体管预算的唯一合理方法是在芯片上放置多个处理器内核。其结果是，现在每个性能关键的应用程序都必须并行化。此外，大数据（在许多应用程序中数据集大小的爆炸）产生了对可扩展到大量处理器的算法的巨大需求。这种范式转变对教学算法产生了深远的影响。并行算法不再是一个专门的主题保留给一小部分学生。相反，每个学生都需要接触并行算法，并且需要在早期教授并行解决方案范例。因此，并行算法应该紧密地集成到算法课程中。因此，我们决定在本书的第二版中加入并行算法。每一章现在都有一些关于并行算法的部分。目标与第一版相同：在简单性和效率之间，在理论和实践之间，在经典结果和研究前沿之间保持谨慎的平衡。我们在并行计算部分使用了稍微不同的风格。我们包括具体的编程示例，因为并行编程仍然比顺序编程更困难（程序可以在github上找到）。com/basic-toolbox-sample-code/basic-toolbox-sample-code/）。我们还直接在文本中引用原著，而不是在历史部分，因为平行部分更接近当前的研究。计算机科学是计算机科学的一个现代和活跃的领域，即使在基本工具箱的水平。我们已经确保我们以现代的方式呈现算法，包括显式制定的不变量。我们还讨论了重要的进一步的方面，如算法工程，内存层次结构，算法库，和certifying algorithm.We选择安排的问题域，而不是解决技术的大部分材料。关于优化技术的章节是个例外。我们发现，一个组织的问题域允许一个更简洁的介绍。然而，读者和学生很好地掌握可用的技术也很重要。因此，我们按照技术来组织优化章节，并且广泛的索引提供了相同技术的不同应用之间的交叉引用。索引中的粗体页码表示定义概念的页面。
viii Preface reason for this change is that sequential processors have ceased to get proportional performance improvements from increased circuit complexity. Although the number of transistors in an integrated circuit (still) doubles every two years (Moore’s law), the only reasonable way to use this transistor budget is to put multiple processor cores on a chip. The consequence is that nowadays every performance-critical application has to be parallelized. Moreover, big data–the explosion of data set sizes in many applications–has produced an enormous demand for algorithms that scale to a large number of processors. This paradigm shift has profound effects on teaching algorithms. Parallel algorithms are no longer a specialized topic reserved for a small percentage of students. Rather, every student needs some exposure to parallel algorithms, and parallel solution paradigms need to be taught early on. As a consequence, parallel algorithms should be integrated tightly and early into algorithms courses. We therefore decided to include parallel algorithms in the second edition of the book. Each chapter now has some sections on parallel algorithms. The goals remain the same as for the first edition: a careful balance between simplicity and efficiency, between theory and practice, and between classical results and the forefront of research. We use a slightly different style for the sections on parallel computing. We include concrete programming examples because parallel programming is still more difficult than sequential programming (the programs are available at github. com/basic-toolbox-sample-code/basic-toolbox-sample-code/). We also reference original work directly in the text instead of in the section on history because the parallel part is closer to current research. Algorithmics is a modern and active area of computer science, even at the level of the basic toolbox. We have made sure that we present algorithms in a modern way, including explicitly formulated invariants. We also discuss important further aspects, such as algorithm engineering, memory hierarchies, algorithm libraries, and certifying algorithms.We have chosen to arrange most of the material by problem domain and not by solution technique. The chapter on optimization techniques is an exception. We find that an organization by problem domain allows a more concise presentation. However, it is also important that readers and students obtain a good grasp of the available techniques. Therefore, we have structured the optimization chapter by techniques, and an extensive index provides cross-references between different applications of the same technique. Bold page numbers in the index indicate the pages where concepts are defined.