《算法统一：串行与并行方法》第二版概要

需积分: 10 153 浏览量更新于2024-07-17 收藏 1.95MB PDF 举报

"《算法：顺序与并行——统一方法》第二版（Algorithms Sequential and Parallel: A Unified Approach, 2005）是一本探讨计算机算法设计的经典教材。该书将顺序算法和并行算法的概念进行了一次全面而深入的整合，试图提供一种统一的视角来理解和学习这两类算法。作者通过精心编排的内容，引导读者理解算法的核心原理，同时强调了在实际应用中的性能和结果可能受到多种因素的影响。本书的章节涵盖了广泛的算法主题，从基础的排序、搜索和图论到高级的数据结构和计算复杂性分析。对于顺序算法，它详细讲解了线性时间复杂度、递归和分治策略等核心概念，强调算法的时间效率和空间效率之间的权衡。而对于并行算法部分，读者将学习如何利用多核处理器、分布式系统和GPU进行并发处理，以及并行计算的基本原理，如任务调度和数据划分。然而，值得注意的是，书中提供的所有文本材料和代码示例都附带有限的保修和责任声明。作者和出版社尽管尽力确保内容的准确性和功能性，但并不对使用书中的程序或内容可能产生的性能结果做出任何明确或隐含的保证。这意味着读者在使用时需自行承担风险，包括但不限于经济损失、业务影响等可能的间接或后果性损失。《算法：顺序与并行——统一方法》不仅是一本理论教材，还包含了一些实践性的编程示例，旨在帮助读者掌握算法设计的技巧，并理解如何在实际场景中实现算法的优化和并行化。尽管如此，用户在使用时应清楚地认识到，书中所介绍的方法可能存在局限性，需要根据具体应用场景灵活调整和验证。"

Preface

major thrust of computer science is the design, analysis, implementation, and

scientific evaluation of algorithms to solve critical problems. In addition, new

challenges are being offered in the field of computational science and engineering,

an emerging discipline that unites computer science and mathematics with disci-

plinary expertise in biology, chemistry, physics, and other applied scientific and

engineering fields. Computational science and engineering is often referred to as

the “third science,” complementing both theoretical and laboratory science. These

multidisciplinary efforts typically require efficient algorithms that run on high-

performance (typically parallel) computers in order to generate the necessary com-

puter models and simulations.

With advances in computational science and engineering, parallel computing

continues to merge into the mainstream of computing. It is therefore critical that

students and scientists understand the application and analysis of algorithmic par-

adigms to both the (traditional) sequential model of computing and to a variety of

parallel models.

Many computer science departments offer courses in “Analysis of Algo-

rithms,” “Algorithms,” “An Introduction to Algorithms,” or “Data Structures and

Their Algorithms” at the junior or senior level. In addition, a course in “Analysis

of Algorithms” is required of most graduate students pursuing a degree in com-

puter science. Throughout the 1980s, the vast majority of these course offerings

focused on algorithms for sequential (von Neumann) computers. In fact, not until

the late-1980s did courses covering an introduction to parallel algorithms begin to

appear in research-oriented departments. Furthermore, these courses in parallel

algorithms were typically presented to advanced graduate students. However, by

the early 1990s, courses in parallel computing began to emerge at the undergradu-

ate level, especially at progressive four-year colleges.

It is interesting to note that throughout much of the 1990s, traditional algo-

rithms-based courses changed very little. Gradually, such courses began to incor-

porate a component of parallel algorithms, typically one to three weeks near the

end of the semester. During the later part of the 1990s, however, it was not uncom-

mon to find algorithms courses that contained as much as 1/3 of the material

devoted to parallel algorithms.

In this book, we take a very different approach to an algorithms-based course.

Parallel computing has moved into the mainstream, with clusters of commodity-

off-the-shelf (COTS) machines dominating the list of top supercomputers in the

world (www.top500.org), and smaller versions of such machines being exploited in

many research laboratories. Therefore, the time is right to teach a fundamental

course in algorithms that covers paradigms for both sequential and parallel models.

The approach we take in this book is to integrate the presentation of sequential

and parallel algorithms. Specifically, we employ a philosophy of presenting a par-

adigm, such as divide-and-conquer, and then discussing implementation issues for

both sequential and parallel models. Due to the fact that we present design and

analysis of paradigms for sequential and parallel models, the reader might notice

that the number of paradigms we can treat within a semester is limited when com-

pared to a traditional sequential algorithms text.

This book has been used successfully at a wide variety of colleges and

universities.

Prerequisites: We assume a basic knowledge of data structures and mathemati-

cal maturity. The reader should be comfortable with notions of a stack, queue, list,

and binary tree, at a level that is typically taught in a CS2 course. The reader should

also be familiar with fundamentals of discrete mathematics and Calculus. Specifi-

cally, the reader should be comfortable with limits, summations, and integrals.

Overview of Chapters

Background material for the course is presented in Chapters 1, 2, and 3. Chapter 1

introduces the concept of asymptotic analysis. While the reader might have seen

some of this material in a course on data structures, we present this material in a

fair amount of detail. The reader who is uncomfortable with some of the funda-

mental material from a Freshman-level Calculus sequence might want to brush up

on notions such as limits, summations and integrals, and derivatives, as they natu-

rally arise in the presentation and application of asymptotic analysis. Chapter 2

focuses on fundamentals of induction and recursion. While many students have

seen this material in previous courses in computer science and/or mathematics, we

have found it important to review this material briefly and to provide the students

with a reference for performing the necessary review. In Chapter 3, we present the

Master Method, a very useful cookbook-type of system for evaluating recurrence

equations that are common in an algorithms-based setting.

Chapter 4 presents an overview of combinational circuits and sorting net-

works. This work is used to motivate the natural use of parallel models and to

demonstrate the blending of architectural and algorithmic approaches. In Chapter

5, we introduce fundamental models of computation, including the RAM (a formal

sequential architecture) and a variety of parallel models of computation. The par-

allel models introduced include the PRAM, mesh, hypercube, and the Coarse-

Grained Multicomputer, to name a few. In addition, Chapter 5 introduces

terminology such as shared-memory and distributed-memory.

xvi Preface

The focus of Chapter 6 is the important problem of matrix multiplication,

which is considered for a variety of models of computation. In Chapter 7, we

introduce the parallel prefix operation. This is a very powerful operation with a

wide variety of applications. We discuss implementations and analysis for a num-

ber of the models presented in Chapter 5 and give sample applications. In Chapter

8, we introduce pointer jumping techniques and show how some list-based algo-

rithms can be efficiently implemented in parallel.

In Chapter 9, we introduce the powerful divide-and-conquer paradigm. We

discuss applications of divide-and-conquer to problems involving data movement,

including sorting, concurrent reads/writes, and so forth. Algorithms and their

analysis are presented for a variety of models.

Chapters 10 and 11 focus on two important application areas, namely, Compu-

tational Geometry and Image Processing. In these chapters, we focus on interest-

ing problems chosen from these important domains as a way of solidifying the

approach of this book in terms of developing machine independent solution strate-

gies, which can then be tailored for specific models, as required.

Chapter 12 focuses on fundamental graph theoretic problems. Initially, we

present standard traversal techniques, including breadth-first search, depth-first

search, and pointer jumping. We then discuss fundamental problems, including

tree contraction and transitive closure. Finally, we couple these techniques with

greedy algorithms to solve problems, such as labeling the connected components

of a graph, determining a minimal spanning forest of a graph, and problems

involving shortest or minimal-weight paths in a graph.

Chapter 13 is an optional chapter concerned with some fundamental numeri-

cal problems. The focus of the chapter is on sequential algorithms for polynomial

evaluation and approximations of definite integrals.

Recommended Use

This book has been successfully deployed in both elective and required courses,

with students typically ranging from juniors (3rd-year undergraduates) to 2nd-year

graduates. A student in a course using this book need not be advanced in a mathe-

matical sense, but should have a basic, fundamental, background.

Correspondence

Please feel free to contact the authors directly with any comments or criticisms

(constructive or otherwise) of this book. Russ Miller may be reached at

miller@buffalo.edu and Laurence Boxer may be reached at boxer@niagara.edu.

In addition, a Web site for the book can be found from http://www.cse.buffalo.

edu/pub/WWW/faculty/miller/research.htm. This Web site contains information

related to the book, including pointers to education-based pages, relevant parallel

computing links, and errata.

Preface xvii

剩余400页未读，继续阅读

osakaanarg

粉丝: 30
资源: 474

《算法统一：串行与并行方法》第二版概要

Algorithms Sequential and Parallel A Unified Approach

分类算法有多少种？他们的应用场景都是什么。

memetic q-learning

Stack<ListNode> stack = new Stack<>();

数据结构与算法c语言思维导图

Algorithms for Creating a UUID from Truly Random or Pseudo-Random Numbers

Quasi-Polynomial Mapping-based Root-Finder

A border-following algorithm

Help me write a literature review of the research on path planning algorithms for satellite maps

Pattern Recognition and Machine Learning-01-Preface

最新资源