Algorithms-JeffE书籍

2744557306

书籍介绍

这本教材源自于我在伊利诺伊大学香槟分校教授各种算法课程时所编写的一系列讲义。自1999年1月以来，我每年大约会教授一次这些课程。由于本科理论课程体系的变化，我在2016年对我的讲义进行了重大修订；本书则是我的修订笔记中关于最基础课程内容的一个子集，主要反映了我们新的必修大三级理论课程的算法内容。

2 |9 i, c* K& V' w! d先决条件
5 C7 u5 R* P' A, E8 j# }, ?7 I
我在伊利诺伊大学教授的算法课程有两个重要的先决条件：
% i2 ]3 ^0 r5 ~* t1. **离散数学**课程
2. **基础数据结构**课程  

. f0 ~9 e9 T$ z4 g% ?因此，这本教材可能不适合大多数学生作为入门书籍。
& G; T: k2 }* X! d) n/ l' M
- J! @9 @1 ]5 b% }主要内容

书中的内容涉及以下几个方面：

- **基本数据结构**：
4 n. l  e. u& r6 F) C  - 队列、映射/字典、排序映射/字典、优先队列
  - 数组、链表（单向和双向、线性和循环）、二叉搜索树，至少一种形式的平衡二叉搜索树（如AVL树、红黑树、Treap、跳表或伸展树）、哈希表、二叉堆，以及最重要的，前面列表与此列表之间的区别。
" [" v7 d) m0 l! u" a4 _
3 f. x/ m1 b: L* u6 y  b% o- **基本计算问题**：
  - 基本算术、排序、搜索、枚举、树的遍历（先序、中序、后序、层序等）。

- **基本算法**：
& V/ K% {. f! m, K3 t  - 基本算法、顺序搜索、二分搜索、各种排序算法（选择排序、插入排序、归并排序、堆排序、快速排序、基数排序等）、在（至少二叉）树中的广度优先搜索和深度优先搜索，以及前面列表与此列表之间的区别。
: X2 G6 m, U6 ~9 ^, S! R8 s* j+ g1 P
- **初步算法分析**：
  - 渐近符号（o, O, Θ, Ω, ω）、将循环转换为求和以及递归调用转换为递归关系、评估简单求和和递归关系。

- c  E) Y, b2 y* T9 s2 m: L5 {- **数学成熟度**：
% T% ^/ r8 i0 [6 j5 B# e- k  - 对抽象、形式（尤其是递归）定义的熟悉程度，书写和理解数学论证的能力，识别和避免句法、语义和/或逻辑上的错误。
% |0 S# E$ E3 c
- F3 a4 m. }$ k6 W/ }) b# K### 书籍特点
5 t8 \  s. g5 Z% T: J( [1 z# \
( I5 p' \. X6 b* y* {4 e+ b2 x8 L这本书在适当上下文中简要涵盖了一些先决条件材料，但更多的是作为提醒而不是全面的介绍。对于更深入的概述，我强烈推荐以下一些免费提供的参考资料。
4 a# S. P/ |! X  \* S; s
5 I6 U, h( ]( V# P- X本书旨在为希望深入研究算法及其理论的学生提供一个扎实的基础，然后他们可以在此基础上进一步学习更复杂和高级的算法概念。

, x" C% N4 \& F. ]5 U
. h2 I) R+ C' T% p: x; ?% [& g