计算机科学精粹PDF电子书下载

第1章 预备知识 1

1.1想法 1

1.1.1流程图 2

1.1.2伪代码 3

1.1.3数学模型 4

1.2逻辑 5

1.2.1运算符 6

1.2.2布尔代数 8

1.2.3真值表 9

1.2.4逻辑在计算中的应用 12

1.3计数 13

1.3.1乘法 13

1.3.2排列 14

1.3.3具有相同项的排列 15

1.3.4组合 16

1.3.5求和 17

1.4概率 19

1.4.1对结果计数 19

1.4.2独立事件 20

1.4.3互斥事件 20

1.4.4对立事件 21

1.4.5赌徒谬误 21

1.4.6高级概率 21

1.5小结 22

第2章 复杂度 23

2.1时间计算 25

2.2大O符号 28

2.3指数 29

2.4内存计算 30

2.5小结 31

第3章 策略 33

3.1迭代 33

3.2递归 36

3.3蛮力法 38

3.4回溯法 40

3.5启发法 43

3.5.1贪心法 43

3.5.2利用贪心法求解电网问题 45

3.6分治法 46

3.6.1利用分治法求解排序问题 46

3.6.2利用分治法求解最佳交易问题 49

3.6.3利用分治法求解背包问题 50

3.7动态规划 51

3.7.1利用记忆化求解斐波那契数 52

3.7.2利用记忆化求解背包问题 52

3.7.3利用自底向上法求解最佳交易问题 53

3.8分支定界法 54

3.8.1上界与下界 55

3.8.2背包问题中的上界与下界 56

3.9小结 58

第4章 数据 59

4.1抽象数据类型 60

4.2常见抽象 62

4.2.1基本数据类型 62

4.2.2栈 62

4.2.3队列 63

4.2.4优先队列 63

4.2.5列表 64

4.2.6排序列表 64

4.2.7映射 65

4.2.8集合 65

4.3数据结构 65

4.3.1数组 66

4.3.2链表 67

4.3.3双向链表 68

4.3.4数组与链表的比较 68

4.3.5树 69

4.3.6二叉查找树 70

4.3.7二叉堆 73

4.3.8图 74

4.3.9散列表 74

4.4小结 75

第5章 算法 77

5.1排序 77

5.2搜索 79

5.3图 80

5.3.1图的搜索 80

5.3.2图着色 83

5.3.3寻路 83

5.3.4 PageRank 86

5.4运筹学 86

5.4.1线性最优化问题 87

5.4.2网络流问题 88

5.5小结 89

第6章 数据库 91

6.1关系数据库 92

6.1.1关系 92

6.1.2模式迁移 95

6.1.3 SQL 95

6.1.4索引 97

6.1.5事务 99

6.2非关系数据库 99

6.2.1文档存储 100

6.2.2键值对存储 101

6.2.3图数据库 102

6.2.4大数据 103

6.2.5 SQL与NoSQL的比较 103

6.3分布式数据库 104

6.3.1单主机复制 104

6.3.2多主机复制 105

6.3.3分片 105

6.3.4数据一致性 107

6.4地理数据库 107

6.5序列化格式 108

6.6小结 109

第7章 计算机 111

7.1体系结构 111

7.1.1存储器 112

7.1.2 CPU 114

7.2编译器 118

7.2.1操作系统 121

7.2.2编译优化 121

7.2.3脚本语言 122

7.2.4反汇编与逆向工程 123

7.2.5开源软件 124

7.3存储器层次结构 125

7.3.1处理器与存储器之间的鸿沟 125

7.3.2时间局部性与空间局部性 126

7.3.3一级缓存 127

7.3.4二级缓存 127

7.3.5第一级存储器与第二级存储器 128

7.3.6外部存储器与第三级存储器 130

7.3.7存储技术的发展趋势 130

7.4小结 131

第8章 程序设计 133

8.1语言学 133

8.1.1值 134

8.1.2表达式 134

8.1.3语句 135

8.2变量 136

8.2.1变量类型 136

8.2.2变量作用域 137

8.3范式 138

8.3.1命令式编程 138

8.3.2声明式编程 140

8.3.3逻辑编程 144

8.4小结 145

附录 147

结语 151

后记 152