程序设计的数学基础PDF电子书下载

目录 1

序言 1

第一章　能行的 1

1.1　能行性定义 1

8.1　它们是什么 26 2

1.2　现代毕达哥拉斯 5

1.3　算法 8

1.4　Berry悖论 11

练习 15

附录　数学基础中的能行性 17

1.5　数学原理以及无穷带来的麻烦 18

1.6　构造数学 23

1.7　物理学中的能行过程 28

1.8　物理的算术化 30

1.9　几个类比 33

第二章　数学基础Ⅰ 34

2.1 引言 34

2.2　函数的意义及其扩充 35

2.3　被看作由一个集合映射到另一个集合的函数 37

2.4　定义函数关系的几种方法 39

2.5　定义在非自然数对象上的函数 41

2.6　函数的函数 42

2.7　关系 44

2.8　函数的标记和λ表示 45

2.9　定义集合的发生法 48

2.10　形式系统 49

2.11　算术化 53

2.12　布尔代数 55

2.13　命题演算的公理化表示法 63

2.14　反证法 64

2.15　建立已知真值表的布尔表达式 65

2.16　关于“波兰表示法” 66

练习 67

第三章　数学基础Ⅱ（应用） 71

3 1 布尔代数的实现 71

3.2 二进制算术与布尔代数的完善结合 75

3.3　集合的布尔代数 80

3.4　各种专门表示法及其使用 84

3.6　集合论在数学和计算中所起的作用 86

3.5　集合的乘积 86

3.7　超穷数理论 90

3.8　超穷数理论在计算上的应用 95

练习 97

附录　图论基础 100

3.9 图论的一些基本概念 100

3.10　计算中图结构的各种例子 105

3.11 计算机中的图的编码 108

3.12　一个与图有关的问题——最短路径问题——的算法解的例子 112

第四章 递归函数 116

4.2　“递归”定义 117

4.1 引言 117

4.3　基本递归函数 119

4.4 可使函数生成运算得以实现的程序设计语言的特点 122

4.5　原始递归函数类 123

4.6　Ackermann函数 125

4.7　部分递归函数类 129

4.8 关于这些基本运算同任何通用计算机或语言所必须提供的设施之间的关系 132

4.9　建立在生成部分递归函数基础之上的程序设计语言PR ECL 133

4.10　关于术语“递归”与“迭代”的注记 135

4.11　原始递归与数学归纳 138

4.12　用迭代代替极小化 140

4.13　关于集合：原始递归集合，递归集合，递归可列集合 142

4.14　关于结构程序设计 146

练习 150

第五章 图灵机和可计算性 154

5.1 图灵机的研究动机 154

5.2　图灵机的组织 157

5.3 用图灵机计算函数 159

5.4　一个图灵机的瞬间描述 161

5.5　输入和输出数据的表示法 162

5.6　附加约定 163

5.7　某些基本的数据处理操作 168

5.8　一些更复杂的机器操作 170

5.9　图灵机的算术化 173

5.10　“证明”若一函数是图灵机可计算的，则它是部分递归的 176

5.11 在计算的“现实”世界中的一些推论 178

练习 180

第六章 通用图灵机，可计算性理论的一些推论，图灵机的变种 183

6.1　通用图灵机 185

6.2　停止问题 186

6.3 判定问题 189

6.4　停止问题的变种 190

6.5　一个不可计算的函数 193

6.6 一个不递归的递归可列集 195

6.7 图灵机是能行可列的 196

6.8　忙碌的海狸问题 197

6.9 图灵机的变种，有多于一个带子或有高维带子的机器 199

6.10　非确定性图灵机 200

6.11　王氏机器 203

6.12　She pherdson-Sturgis的寄存器机器 204

6.13　细胞状自动机 207

6.14　图灵机用作符号操作系统 209

6.15　“正规”重写规则的使用和某些特殊的符号操作系统 211

6.16　“捉人”游戏问题 214

6.17　可计算的数 216

6.18　哥德尔的结果的提示 219

6.19　关于不完备性结果以及人是否机器问题的一些可能推断的讨论 221

练习 222

第七章　关于自动机的一般评论 225

7.1　什么是自动机 226

7.2　“状态”和“机制”的概念 228

7.3　自动机的分类 231

7.4 自动机完成的功能 233

7.5　自动机的幅度 234

7.6　有下推存储的机器与有栈的机器 236

7.7 计算中的非确定性与蒙特卡罗方法 238

7.8　自动机的构造块 241

7.9　通用逻辑元素 246

7.10　反馈和记忆 250

7.11 判断器 253

7.12　自动机与思想——图灵测试 255

练习 258

第八章　有穷自动机 261

8.2　怎样描述它们 263

8.3　顺序机器 265

8.4　有穷自动机作为识别设备 267

8.5　翻译机能计算什么样的函数 270

8.6　非确定性的有穷自动机 274

8.7　在讨论有穷自动机时有用的各种概念 275

8.8　构造一个等价于一个给定NDFA的确定性有穷自动机 277

8.9　任一正规集总能由某有穷自动机识别 280

8.10　正规表达式，正规集的一个表示法 281

8.11　有穷自动机的最小化 282

8.12　能够反向地读带子的有穷自动机 284

8.13　树自动机 287

练习 289

第九章　形式语言——导论 294

9.1　自然语言与形式语言 295

9.2　符号处理系统——重写规则 298

9.3　这些系统的形式化 302

9.4　语言的分类 306

9.5　由文法定义的语言的例子 309

9.6　语法、语义和二义性 314

9.7　分析 319

9.8　有穷自动机在识别和分析上下文无关语言的句子中的某些应用 324

9.9　在分析中前缀的识别 329

9.10　一个具有足够长的句子的语言是上下文无关的必要条件 332

练习 335

第十章 形式语言——与自动机和程序设计语言的进一步关系 338

10.1　Chomsky体系中用自动机类给出的语言的定义 340

10.2 某些在分析程序设计语言的句子或程序中特别重要的有限制的上下文无关文法 343

10.3　ALGOL不是上下文无关的 347

10.4　POST的对应问题 348

10.5　关系的传递闭包 354

10.6　应用关系传递闭包于形式语言的一个问题 357

10.7　关于程序正确性证明 359

10.8　语义的定义 364

10.9　维也纳定义语言 365

10.10　LINCOS，一个用于宇宙交往的语言 368

练习 376

第十一章　计算复杂性的研究 380

11.1 复杂性与简单性 381

11.2　关于增长率的数学描述 383

11.3　信息的数学量度 385

11.4　有穷序列的信息容量 387

11.5　机器的复杂性 388

11.6　复杂性理论中的各类问题 390

11.7 公理化的、独立于机器的部分可计算函数复杂性的定义方法 396

11.8　加速定理 398

11.9　可由有穷自动机计算的函数 399

11.10　可预测的复杂性——初等算术函数的Ritchie分级结构 401

11.11 电路中“扇入”元件的使用及Winograd的关于加法和乘法的最小界限 403

11.12　时间与空间的交易 408

11.13 概率算法 410

11.14　“实时”计算 413

11.15　关于有穷序列的随机性 416

11.16　一个尚未解决的问题，？＝？吗？ 417

练习 418

第十二章 总结数学思想对计算的影响——剖析与评述 421

12.1　基本概念及有关几个重要历史发展阶段的扼要评述 421

12.2　皮亚诺公理 423

12.3 可计算性 424

12.4　现代数学的特征——抽象化和公理化 425

12.5　计算对数学产生的影响 428

12.6　四色定理 429

12.7　有关的主要数学概念一览 434

12.8　一般性评述，大事记 435

附录　现代代数的影响 437

12.9　计算机科学与代数 437

12.10　机器的范畴 441

参考文献 444

索引 453