Jeff Erickson的《算法》第1版：理论与实践

需积分: 0 74 浏览量更新于2024-07-17 收藏 23.89MB PDF 举报

"《算法》（Algorithms）是由Jeff Erickson撰写的一本权威计算机科学教材，该书在不同的阶段经历了预出版草稿的形式，包括第0版（2018年12月30日）和第½版（2019年4月9日）。正式的1st paperback edition于2019年6月13日发布。本书共123456789页，ISBN号码为978-1-792-64483-2（平装本）。版权方面，作者保留了Creative Commons Attribution 4.0 International License的许可，允许在指定条件下进行分享和再利用。《算法》是一本实践性强的教程，涵盖了广泛的算法设计与分析主题，旨在帮助读者理解和应用基础到高级的计算机科学原理。书中不仅深入讲解了诸如排序、搜索、图论、动态规划等经典算法，还可能包括现代算法的探讨，如并行算法、近似算法以及数据结构的优化。每一章节都经过精心编排，以清晰的逻辑和易于理解的方式阐述复杂的概念。作者在序言中引用了历史上的文献，展示了算法历史的渊源，例如中世纪学者Ioannis Hispalensis（约瑟夫·塞维利亚）的著作，以及Henry Home, Lord Kames在17世纪末对算法重要性的强调。这体现了本书对学术传统的尊重和对学习者人文素养的培养。在技术层面，部分章节可能涉及编程示例，这些代码是通过机械复制的方式呈现的，旨在让学生通过实践掌握理论知识。同时，作者鼓励读者在遇到错误或有任何问题时通过GitHub上的官方报告渠道（<https://github.com/jeffgerickson/algorithms>）来提出反馈，体现了作者对读者参与和持续改进的重视。总而言之，《算法》（Algorithms-JeffErickson）是一本实用且具有教育价值的计算机科学教材，适合学生、教师和专业人员参考，无论是初学者还是高级研究者，都能从中获益匪浅。通过网络资源，如jeffe.cs.illinois.edu、algorithms.wtf和archive.org，读者可以方便地获取和分享这本书的内容，共同促进算法领域的知识传播和进步。"

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

6 Depth-First Search 225

6.1 Preorder and Postorder . . . . . . . . . . . . . . . . . . . . . . . . . 227

Classifying Vertices and Edges

6.2 Detecting Cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231

6.3 Topological Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

Implicit Topological Sort

6.4 Memoization and Dynamic Programming . . . . . . . . . . . . . . 234

Dynamic Programming in Dags

6.5 Strong Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . 237

6.6 Strong Components in Linear Time . . . . . . . . . . . . . . . . . . 238

Kosaraju and Sharir’s Algorithm •

Tarjan’s Algorithm

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244

7 Minimum Spanning Trees 257

7.1 Distinct Edge Weights . . . . . . . . . . . . . . . . . . . . . . . . . . 257

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

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

This is the MST Algorithm You Want

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

Improving Jarník’s Algorithm

7.5 Kruskal’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 268

8 Shortest Paths 273

8.1 Shortest Path Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274

8.2

Negative Edges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274

8.3 The Only SSSP Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 276

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

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

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

No Negative Edges •

Negative Edges

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

Moore’s Improvement • Dynamic Programming Formulation

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297

9 All-Pairs Shortest Paths 309

9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309

9.2 Lots of Single Sources . . . . . . . . . . . . . . . . . . . . . . . . . . 310

9.3 Reweighting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311

9.4 Johnson’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 312

9.5 Dynamic Programming . . . . . . . . . . . . . . . . . . . . . . . . . 313

9.6 Divide and Conquer . . . . . . . . . . . . . . . . . . . . . . . . . . . 315

xii

Table of Contents

9.7 Funny Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . . 316

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

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320

10 Maximum Flows & Minimum Cuts 327

10.1 Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328

10.2 Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329

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

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

Irrational Capacities

10.5 Combining and Decomposing Flows . . . . . . . . . . . . . . . . . 336

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

Fattest Augmenting Paths • Shortest Augmenting Paths

10.7 Further Progress . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344

11 Applications of Flows and Cuts 353

11.1 Edge-Disjoint Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353

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

11.3 Bipartite Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355

11.4 Tuple Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357

Exam Scheduling

11.5 Disjoint-Path Covers . . . . . . . . . . . . . . . . . . . . . . . . . . . 360

Minimal Faculty Hiring

11.6 Baseball Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . 363

11.7 Project Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 366

Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 368

12 NP-Hardness 379

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

12.2 P versus NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 381

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

12.4

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

12.5 Reductions and Sat . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385

12.6 3Sat (from CircuitSat) . . . . . . . . . . . . . . . . . . . . . . . . . 388

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

12.8 The General Pattern . . . . . . . . . . . . . . . . . . . . . . . . . . . 392

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

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

12.11 Hamiltonian Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398

From Vertex Cover • From 3Sat • Variants and Extensions

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

xiii

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

(

ἄλγος

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

Persian scholar 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 this latter treatise, 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

Europe in the 13th century—not because written decimal ﬁgures were 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 440bce, Herodotus

wrote in his Histories 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.

剩余471页未读，继续阅读

dmn0123

粉丝: 13
资源: 17

Jeff Erickson的《算法》第1版：理论与实践

pyannote.algorithms-0.7-py3-none-any.whl：Python库的官方压缩包

PyPI发布新Python库：dsatools-0.1.60支持分布式系统

Python库input_algorithms-0.5.9功能介绍及安装教程

Algorithms-JeffE.7z

Data-Structures-and-Algorithms-with-Python-Undergraduate-Topics-in-Computer-Science.pdf.pdf

10Algorithms-08.pdf

Bandit+Algorithms-book.pdf

Sammie Bae - JavaScript Data Structures and Algorithms - 2019.pdf

Combinatorial.Optimization.Theory.And.Algorithms-Theory.And.Algorithms

algorithms-源码.rar

最新资源