《算法》：Jeff Erickson的讲义汇编

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

"这是一本由教授Jeff Erickson编写的算法讲义，源自他在UIUC的教学内容，全书共448页，涵盖了12个章节的算法知识。该讲义名为《算法》(Algorithms)，并且以创作共享 Attribution 4.0 国际许可协议发布，可以在指定网址免费下载，并鼓励报告错误以持续改进。" 本书《算法》是Jeff Erickson教授二十年教学经验的结晶，旨在深入浅出地介绍计算机科学中的核心算法。虽然标题直接而简洁，但内容却包含丰富的理论与实践。讲义分为12个章节，涉及了多个关键算法领域： 1. **排序与搜索**：这是计算机科学的基础，可能包括快速排序、归并排序、二分查找等经典算法，以及相关的数据结构如堆和平衡二叉树。 2. **图论**：可能会讲解图的遍历（深度优先搜索和广度优先搜索）、最短路径问题（Dijkstra算法、Floyd-Warshall算法）、最小生成树（Prim算法或Kruskal算法）等。 3. **动态规划**：这部分内容会涵盖基本的动态规划概念，如背包问题、最长公共子序列、斐波那契数列等，帮助读者理解如何通过状态转移解决复杂问题。 4. **贪心算法**：可能讨论如何通过局部最优解来寻找全局最优解，例如霍夫曼编码、活动选择问题等。 5. **字符串处理**：可能包括模式匹配算法（如KMP算法）、字符串排序和压缩等。 6. **计算几何**：这部分可能涵盖线段树、最近点对问题、凸包算法等，将几何问题与算法相结合。 7. **概率与随机化算法**：可能介绍如何利用概率分析优化算法，如鸽巢原理、随机化排序算法（如快速选择和快速排序的随机版本）。 8. **数据压缩与编码**：可能探讨哈夫曼编码、LZ77和LZ78压缩算法，以及熵编码的概念。 9. **网络流与最大匹配**：可能会讲解 Ford-Fulkerson方法、Edmonds-Karp算法，以及二分图的最大匹配问题。 10. **计算复杂性理论**：可能会介绍P、NP、NPC等相关概念，以及时间复杂性和空间复杂性的分析。 11. **近似算法**：对于某些难以求解的优化问题，可能介绍如何设计近似算法以达到接近最优解。 12. **并行与分布式算法**：可能涵盖多处理器环境下的算法设计，如MapReduce模型、分布式一致性算法等。这本书不仅适合计算机科学的学生，也对从事软件开发、数据科学和其他相关领域的专业人士非常有帮助。它以易于理解的方式阐述了复杂的算法思想，是学习和复习算法知识的宝贵资源。通过阅读和实践，读者可以提升自己的算法思维能力和解决问题的能力。

T  C

6 Depth-First Search 223

6.1 Preorder and Postorder . . . . . . . . . . . . . . . . . . . . . . . . . 225

Classifying Vertices and Edges

6.2 Detecting Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229

6.3 Topological Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230

Implicit Topological Sort

6.4 Memoization and Dynamic Programming . . . . . . . . . . . . . . 232

Dynamic Programming in Dags

6.5 Strong Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . 235

6.6 Strong Components in Linear Time . . . . . . . . . . . . . . . . . . 236

Koraraju and Sharir’s Algorithm •

Tarjan’s Algorithm

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242

7 Minimum Spanning Trees 255

7.1 Distinct Edge Weights . . . . . . . . . . . . . . . . . . . . . . . . . . 255

7.2 The Only Minimum Spanning Tree Algorithm . . . . . . . . . . . 257

7.3 Borůvka’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 259

This is the MST Algorithm You Want

7.4 Jarník’s (“Prim’s”) Algorithm . . . . . . . . . . . . . . . . . . . . . . 261

Improving Jarník’s Algorithm

7.5 Kruskal’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265

8 Shortest Paths 271

8.1 Shortest Path Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272

8.2

Negative Edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272

8.3 The Only SSSP Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 274

8.4 Unweighted Graphs: Breadth-First Search . . . . . . . . . . . . . . 276

8.5 Directed Acyclic Graphs: Depth-First Search . . . . . . . . . . . . 280

8.6 Best-First: Dijkstra’s Algorithm . . . . . . . . . . . . . . . . . . . . . 283

No Negative Edges •

Negative Edges

8.7 Relax ALL the Edges: Bellman-Ford . . . . . . . . . . . . . . . . . . 287

Moore’s Improvement • Dynamic Programming Formulation

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 295

9 All-Pairs Shortest Paths 307

9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307

9.2 Lots of Single Sources . . . . . . . . . . . . . . . . . . . . . . . . . . 308

9.3 Reweighting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309

9.4 Johnson’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 310

9.5 Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . 311

9.6 Divide and Conquer . . . . . . . . . . . . . . . . . . . . . . . . . . . 313

xii

Table of Contents

9.7 Funny Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . 314

9.8 (Kleene-Roy-)Floyd-Warshall(-Ingerman) . . . . . . . . . . . . . . 316

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 318

10 Maximum Flows & Minimum Cuts 325

10.1 Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326

10.2 Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327

10.3 The Maxﬂow-Mincut Theorem . . . . . . . . . . . . . . . . . . . . . 329

10.4 Ford and Fulkerson’s augmenting-path algorithm . . . . . . . . . 332

Irrational Capacities

10.5 Combining and Decomposing Flows . . . . . . . . . . . . . . . . . 334

10.6 Edmonds and Karp’s Algorithms . . . . . . . . . . . . . . . . . . . . 338

Fattest Augmenting Paths • Shortest Augmenting Paths

10.7 Further Progress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342

11 Applications of Flows and Cuts 351

11.1 Edge-Disjoint Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351

11.2 Vertex Capacities and Vertex-Disjoint Paths . . . . . . . . . . . . . 352

11.3 Bipartite Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353

11.4 Tuple Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 354

Exam Scheduling

11.5 Disjoint-Path Covers . . . . . . . . . . . . . . . . . . . . . . . . . . . 357

Minimal Teaching Assignment

11.6 Baseball Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . 360

11.7 Project Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365

12 NP-Hardness 377

12.1 A Game You Can’t Win . . . . . . . . . . . . . . . . . . . . . . . . . . 377

12.2 P versus NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379

12.3 NP-hard, NP-easy, and NP-complete . . . . . . . . . . . . . . . . . . 380

12.4

Formal Deﬁnitions (HC SVNT DRACONES) . . . . . . . . . . . . . 382

12.5 Reductions and Sat . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383

12.6 3Sat (from Sat) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386

12.7 Maximum Independent Set (from 3Sat) . . . . . . . . . . . . . . . 388

12.8 The General Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . 390

12.9 Clique and Vertex Cover (from Independent Set) . . . . . . . . . 391

12.10 Graph Coloring (from 3Sat) . . . . . . . . . . . . . . . . . . . . . . 392

12.11 Hamiltonian Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395

From Vertex Cover • From 3Sat • Variants and Extensions

12.12 Subset Sum (from Vertex Cover) . . . . . . . . . . . . . . . . . . . . 400

xiii

. I

(

ἄλγος

), meaning “pain”. Rather, it is a corruption of the name of the 9th century

Persian mathematician Mu

ammad ibn M

a al-Khw

arizm

ı.

Al-Khw

arizm

ı is

perhaps best known as the writer of the treatise Al-Kit

ab al-mukhta

ar f

ıh

ıs

al-ğabr

wa’l-muq

abala,

from which the modern word algebra derives. In a

diﬀerent treatise, al-Khw

arizm

ı described the modern decimal system for writing

and manipulating numbers—in particular, the use of a small circle or

ifr to

represent a missing quantity—which had been developed in India several

centuries earlier. The methods described in Al-Kit

ab, using either written ﬁgures

or counting stones, became known in English as algorism or augrym, and its

ﬁgures became known in English as ciphers.

Although both place-value notation and al-Khw

arizm

ı’s works were already

known by some European scholars, the “Hindu-Arabic” numeric system was

popularized in Europe by the medieval Italian mathematician and tradesman

Leonardo of Pisa, better known as Fibonacci. Thanks in part to his 1202 book

Liber Abaci,

written ﬁgures began to replace the counting table (then known

as an abacus) and ﬁnger arithmetic

as the preferred platform for calculation

in Europe in the 13th century—not because written decimal ﬁgures were any

easier to learn or use, but because they provided an audit trail. Ciphers became

common in Western Europe only with the advent of movable type, and truly

ubiquitous only after cheap paper became plentiful in the early 19th century.

Eventually the word algorism evolved into the modern algorithm, via folk

etymology from the Greek arithmos (and perhaps the previously mentioned

algos).

Thus, until very recently, the word algorithm referred exclusively

“Mohammad, father of Adbdulla, son of Moses, the Kw

arizmian”. Kw

arizm is an ancient

city, now called Khiva, in the Khorezm Province of Uzbekistan.

“The Compendious Book on Calculation by Completion and Balancing”

While it is tempting to translate the title Liber Abaci as “The Book of the Abacus”, a more

accurate translation is “The Book of Calculation”. Both before and after Fibonacci, the Italian

word abaco was used to describe anything related to numerical calculation—devices, methods,

schools, books, and so on—much in the same way that “computer science” is used today in

English, or as the Chinese phrase for “operations research” translates literally as “the study of

using counting rods”.

+ Reckoning with digits!

The word calculate derives from the Latin word calculus, meaning “small rock”, referring to

the stones on a counting table, or as Chaucer called them, augrym stones. In 440bc, Herodotus

wrote in his Histories (II.36) that “The Greeks write and calculate (

λογίζεσθαι ψήφοις

, literally

“reckon with pebbles”) from left to right; the Egyptians do the opposite. Yet they say that their

way of writing is toward the right, and the Greek way toward the left.” (Herodotus is strangely

silent on which end of the egg the Egyptians ate ﬁrst.)

Some medieval sources claim that the Greek preﬁx “algo-” means “art” or “introduction”.

Others claim that algorithms were invented by a Greek philosopher, or a king of India, or perhaps

a king of Spain, named “Algus” or “Algor” or “Argus”. A few, possibly including Dante Alighieri,

even identiﬁed the inventor with the mythological Greek shipbuilder and eponymous argonaut.

It’s unclear whether any of these risible claims were intended to be historically accurate, or

merely mnemonic.

剩余447页未读，继续阅读

weixin_37187127

粉丝: 0
资源: 2

《算法》：Jeff Erickson的讲义汇编

国外经典算法 数据结构

算法与数据结构学习辅导及习题详解.张乃孝版.

国外很通俗的小波讲义及实现代码

卜东波 算法讲义pdf

数据结构 算法 讲义 PPT

数据结构与算法python讲义

国产商用密码算法和国外同类算法的优劣对比分析

捷联惯导matlab算法,捷联惯导算法与组合导航原理讲义.pdf

牛顿算法的国外研究现状

cordic算法国外研究现状

最新资源

国外经典算法数据结构

卜东波算法讲义pdf

数据结构算法讲义 PPT