《程序设计的数学基础》求取 ⇩

目录1

序言1

第一章　能行的1

1.1　能行性定义1

8.1　它们是什么 262

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 ECL133

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