《离散数学与计算机科学之应用》求取 ⇩

第1章离散数学之导论1

1.1 何谓离散数学？2

1.2 工具、技术与方法论3

1.3 演算语言7

1.3.1 虚拟码8

1.3.2 指派叙述9

1.3.3 控制叙述10

1.3.4 有关演算法之注释17

1.4 总结18

1.5 复习问题19

第2章逻辑与集合23

2.1.1 命题24

2.1 逻辑与命题24

2.1.2 逻辑运算25

2.2 述语逻辑33

2.3 证明36

2.3.1 直接证法37

2.3.2 对偶证法37

2.3.3 矛盾证法38

2.3.4 存在证法38

2.3.5 反例39

2.4 数学归纳法40

2.4.1 数学归纳法之原则40

2.4.2 归纳式的定义43

2.5.1 确证46

2.5 演算法之正确性（选修教材）46

2.5.2 顺序叙述47

2.5.3 条件叙述48

2.5.4 反覆51

2.6 集合之基本性质55

2.6.1 集合之定义55

2.6.2 一些特别的集合56

2.6.3 集合的运算57

2.6.4 性质与恒等式60

2.7 再谈集合64

2.7.1 幂集合64

2.7.2 积集合65

2.7.3 集合之分割68

2.8 应用：浅谈以知识为基础的系统70

2.8.1 一个范例：有关家庭的事实71

2.8.2 推论规则71

2.8.3 查询72

2.9 总结73

2.10 复习问题76

2.11 自我评量解答82

第3章关系与函数85

3.1 关系86

3.1.1 二元关系86

3.1.2 关系之图形表示法87

3.1.3 关系之矩阵表示法90

3.2 关系之性质93

3.2.1 相等关系与分割96

3.2.2 有序关系99

3.2.3 递移封闭101

3.3 关系之合成104

3.3.1 逻辑矩阵乘积105

3.3.2 自等关系108

3.3.3 相反关系109

3.4 函数111

3.4.1 单射与全射113

3.4.2 函数与基数114

3.4.3 可逆函数116

3.4.4 二元运算118

3.4.5 在电脑语言上之函数119

3.5 应用：资料库管理系统122

3.5.1 n元关系之运算123

3.6 总结126

3.7 复习问题128

3.8 自我评量解答134

第4章组合数学139

4.1 自一集合中选择元素141

4.1.1 定义142

4.1.2 计数公式144

4.2 型样与分割154

4.2.1 型样155

4.2.2 分割157

4.3 演算法分析（选修教材）161

4.3.1 次方的种类162

4.3.2 常见的次方种类164

4.3.3 综合讨论166

4.4 应用：我们可以排序多快？168

4.5 总结170

4.6 复习问题172

4.7 自我评量解答176

第5章无向图形181

5.1 简单图形183

5.1.1 路径、循环与连通186

5.1.2 尤拉路径189

5.1.3 汉米顿循环191

5.1.4 同构关系194

5.2 树199

5.2.1 最小展开树203

5.2.2 有根树205

5.2.3 排序与搜寻207

5.3 应用：语言的语法213

5.3.1 文法214

5.3.2 衍生215

5.3.3 Bacus-Naur形式216

5.3.4 语法图218

5.4 总结221

5.5 复习问题222

5.6 自我评量解答225

第6章有向图229

6.1 有向图230

6.1.1 分支度、路径与循环231

6.1.2 一致性标记235

6.2 有向图的路径问题242

6.2.1 路径的存在性242

6.2.2 瓦谢勒演算法246

6.2.3 最短路径249

6.2.4 路径个数254

6.3.1 计算机网路的用途257

6.3 应用：通信网路的路线257

6.3.2 网路与图形模式258

6.3.3 路线问题259

6.3.4 动态路径程序259

6.4 总结261

6.5 复习问题263

6.6 自我评量解答268

第7章布耳代数271

7.1 布耳陈式272

7.1.1 陈式273

7.1.2 第摩根定律276

7.2 陈式的表示法278

7.2.1 全及项281

7.2.2 正规形式283

7.2.3 运算子的完整集合285

7.3 布耳陈式的极小化法288

7.3.1 卡诺图288

7.3.2 四个变数的卡诺图292

7.4 开关理论296

7.4.1 电路图296

7.4.2 逻辑闸之完整集合300

7.4.3 控制开关的例子301

7.5 应用：设计一个两位元加法器307

7.6 总结310

7.7 复习问题312

7.8 自我评量解答322

第8章代数系统327

8.1 半群、单群与群328

8.1.1 半群328

8.1.2 单群332

8.1.3 群335

8.1.4 子群337

8.2 建立新的代数342

8.2.1 积代数342

8.2.2 商代数343

8.2.3 傍系348

8.2.4 拉格朗治定理350

8.3.1 单群间之同态353

8.3 代数结构的映型353

8.3.2 单群之同构357

8.3.3 对於单群同态之基本定理358

8.3.4 群同态361

8.3.5 对於群同态之基本定理363

8.4 应用：群码364

8.4.1 错误侦测码365

8.4.2 错误更正码366

8.4.3 群码367

8.4.4 解码368

8.5 总结370

8.6 复习问题373

8.7 自我评量解答379

第9章机器与计算383

9.1 自动机模型384

9.2 不具输出之有限状态自动机385

9.2.1 有限状态自动机之定义387

9.2.2 有限状态自动机当作语言辨识机388

9.2.3 有限状态自动机当作语言辨识机的限制396

9.2.4 具有输出之有限状态自动机400

9.2.5 莫尔机器400

9.2.6 米利机器405

9.3 杜林机器（选修教材）410

9.3.1 有效程序410

9.3.2 杜林计算模型411

9.3.3 杜林机器当作语言辨识机415

9.3.4 杜林机器当作函数计算机417

9.3.5 邱吉－杜林命题419

9.4 应用：解决问题421

9.4.1 有限状态自动机当作解决问题模型421

9.5 总结423

9.6 复习问题425

9.7 自我评量解答429

第10章机率433

10.1 机率的基本特性434

10.1.1 均匀机率空间436

10.2 条件机率440

10.2.1 贝氏定理444

10.2.2 独立事件445

10.3 重复试验及期望值449

10.3.1 二项式分布451

10.3.2 随机变数及分布454

10.3.3 期望值456

10.4 应用：一个平均数个案分析463

10.4.1 选择法排序463

10.4.2 插入法排序464

10.5 总结467

10.6 复习问题470

10.7 自我评量解答472

辞汇解释475

解答483