本手册的用法 1
第一编 基础 1
1.数学中定理的证明 1
1.1.数学归纳法 1
1.2.反证法 3
2.集合·映射·关系 4
2.1.集合 4
2.2.映射 7
2.3.关系 9
2.4.图与树 11
3.1.1.半群与群 12
3.1.群 12
3.代数基础知识 12
3.1.2.群的基本性质 14
3.1.3.置换群 15
3.1.4.子群 17
3.1.5.剩余类 20
3.1.6.正规子群与剩余(类)群 22
3.1.7.同态映射 23
3.1.8.合成列 25
3.2.环与域 26
3.2.1.环 26
3.2.2.理想与剩余环 29
3.2.3.域 30
3.2.4.域上的多项式环 32
3.2.5.多项式理想 34
3.2.6.伽罗瓦域 37
4.线性映射与矩阵 38
4.1.矩阵及线性映射的多项式 39
4.2.特征向量与特征值 40
4.3.特征多项式 43
4.4.矩阵的三角化 44
4.5.不变子空间 45
4.6.再论特征多项式 51
4.7.对角化 52
4.8.以多项式为元的矩阵及其初等因子 53
4.9.第一种标准形 57
4.10.约当标准形(第二种标准形) 64
5.范畴 67
5.1.范畴 67
5.2.单射、满射、双射、同构射 69
5.3.余等化射、等化射 70
5.4.(?，?)-分解 71
5.5.回拖、前推 74
5.6.函子 75
5.7.自由、上自由 76
5.8.自然变换 78
6.距离空间与赋范空间 79
6.1.距离空间 80
6.2.赋范空间 84
第二编 自动机 86
1.自动机理论的发展 86
1.1.自动机理论的起源 86
1.2.自动机理论的意义 87
1.3.有限自动机理论的确立 88
1.4.各种自动机的发展 88
1.5.自动机和语言的关系 89
1.6.作为新分支的自动机理论 89
2.各种各样的自动机 92
2.1.有限自动机 92
2.1.1.有限自动机 92
2.1.2.同余类系和有限自动机 95
2.1.3.非确定性有限自动机 97
2.2.概率自动机 98
2.2.1.概率自动机的定义 98
2.2.2.概率自动机的等价性 99
2.2.3.概率自动机定义的输入字函数 100
2.2.4.拟正则函数和线性空间自动机 102
2.2.5.概率自动机定义的断点语言 103
2.2.6.补充 105
2.3.时序机 105
2.3.1.时序机的定义 105
2.3.2.状态等价和最简型时序机 107
2.3.3.时序机实现函数f？ ∑+→△+的条件 108
2.3.4.时序机的状态分配和线路实现 109
2.4.线性时序机 110
2.4.1.定义 112
2.4.2.浅性时序机的简化 113
2.5.下推自动机 115
2.5.1.非确定的下推自动机 116
2.5.2.确定的下推自动机 118
2.6.堆栈自动机 118
2.7.气球自动机 121
2.8.树自动机 125
2.9.细胞自动机 131
2.9.1.基本定义 131
2.9.2.自生长 134
2.9.3.其它问题 136
2.10.线性有界自动机 137
3.自动机和其它分支的关系 140
3.1.自动机和数集 140
3.2.自动机和拓扑 145
3.3.自动机和范畴 146
3.3.1.一个自动机的转移范畴 147
3.3.2.机器范畴和自动机范畴 148
3.3.3.行为范畴 149
3.3.4.语言范畴 150
3.3.5.函子——机器和行为的桥梁 150
3.3.6.自动机范畴 150
3.4.自动机和代数 151
3.4.2.理论和代数 152
3.4.1.范畴 152
3.4.3.T自动机和可识别集合 154
3.4.4.自由理论和关系代数，关系自动机 154
3.4.5.代数集合和主要结果 155
第三编 计算机 157
1.计算机的发展 157
1.1.计算机时代 157
1.2.元件的进展 158
1.3.计算机使用形式的变化 159
1.4.计算机应用领域的扩大 159
2.1.定点运算方式 160
2.二进制数及其运算 160
2.2.浮点运算方式 162
2.3.二进制及其运算 163
2.4.p进制及其运算 168
2.5.编码 170
3.布尔函数 172
3.1.布尔代数(1) 172
3.1.1.布尔代数的定义 172
3.1.2.布尔格 175
3.1.3.布尔代数的表示 175
3.2.布尔函数 175
3.2.1.布尔函数的布尔代数 175
3.2.2.布尔函数的标准展开 177
3.2.3.布尔函数的完全系 178
3.2.4.布尔函数的对偶性 178
3.2.5.布尔函数的性质 179
3.2.6.布尔函数的简化 180
3.3.布尔函数的几何表示 180
3.3.1.n维超立方体表示法 180
3.3.2.卡诺图 182
4.逻辑设计 183
4.1.组合线路 183
4.2.时序线路 187
4.3.各种运算线路 190
4.4.何谓逻辑设计 194
5.MIX1009 198
5.1.MIX 的构成 199
5.2.字的构成 200
5.3.指令格式 200
5.4.MIX1009的指令 202
第四编 语言 209
1.语言理论的变迁 209
1.1.语言理论的起源 209
1.2.语言理论的意义 210
1.3.范式的发现 210
1.4.自动机和语言的联系 211
1.5.语法分析的发展 211
2.1.2.有限自动机和正规语言 212
2.1.1.正规文法 212
2.形式语言 212
2.1.正规语言 212
2.1.3.正规语言的性质 213
2.1.4.正规表示 216
2.1.5.正规表示代数 219
2.2.上下文无关语言 220
2.3.Greibach 定理 224
2.4.Chomsky 定理 226
2.5.Chomsky—Schutzenberger 定理 229
2.6.Parikh 定理 231
2.6.1.定理的内容 231
2.6.2.派生树 232
2.6.3.Parikh定理的证明 234
2.7.加标文法 237
2.8.具有控制集合的文法 240
2.9.状态文法 242
2.9.1.文法.派生.生成语言的定义 243
2.9.2.状态语言的性质 244
2.10.上下文有关文法 245
2.10.1.上下文有关文法的定义 245
2.10.2.上下文有关语言族的大小 247
2.10.3.单侧上下文有关文法 248
2.10.4.与线性有界自动机的关系 249
2.11.有关语言的运算 250
2.12.语言的导映射 254
2.13.语言的结构图及其应用 259
2.13.1.语言的结构图 259
2.13.2.正规语言的结构图和有限自动机 261
2.13.3.自由语言的结构图和下推自动机 265
2.14.有关语言的判定问题 265
3.语言的语法分析 269
3.1.何谓语法分析? 269
3.2.算符优先语言 275
3.3.优先语言 279
3.4.依语法规则的编译 282
3.5.LR(k)文法 287
3.6.Floyd 生成语言 292
第五编 程序设计 297
1.程序设计语言的发展 297
2.程序设计语言 299
2.1.机器语言 299
2.2.汇编语言 300
2.3.编译语言 302
2.4.ALGOL 302
2.5.EULER 306
2.6.PASCAL 306
2.7.FORTRAN 307
2.8.PL/1 310
2.8.1.PL/1的特点 310
2.8.2.PL/1程序的例子 312
3.编译技巧 313
3.1.编译程序 313
3.2.堆栈 315
4.程序设计技巧 315
4.1.数据结构 317
4.2.结构化程序设计 320
4.3.递归程序设计 321
5.符号处理与公式处理 324
5.1.什么叫符号处理? 324
5.2.串处理 327
5.3.表处理 331
5.4.什么叫公式处理? 334
5.5.IPL—V 335
5.6.McCarthy条件表达式 338
5.7.LISP 1.5 341
5.8.L? 345
5.9.SLIP 348
5.10.SNOBOL 352
第六编 计算理论 356
1.计算理论的发展 356
1.1.计算理论的起源 356
1.2.计算理论的意义 357
1.3.理想计算机 357
1.4.计算量与计算复杂性 358
1.5.程序理论 359
2.可计算性 359
2.1.图灵机 359
2.2.可计算性 364
2.3.递归函数 368
2.4.Godel 数 372
2.5.通用图灵机 376
2.6.递归可枚举集 379
2.7.停机问题 382
2.8.Markov 算法 383
2.8.2.作为字变换过程的算法 384
2.8.1.公式化的准备 384
2.8.3.Markov 标准算法 385
2.8.4.标准算法的简单例子 387
2.8.5.算法的合成 389
3.各种理想计算机 390
3.1.王氏—李氏型理想计算机 390
3.1.1.李氏计算机 390
3.1.2.李氏计算机的变形 392
3.2.Shepherdson—Sturgis 的理想计算机 392
3.3.Elgot 的 RASP 393
3.3.1.RASP 的定义 394
3.3.2.RASP 的例子P? 395
4.1.计算复杂性理论 397
4.1.1.关于时间的理论 397
4.计算量问题和计算复杂性 397
4.1.2.关于带用量的理论 398
4.1.3.关于巡回序列的理论 398
4.1.4.关于程序长度的理论 398
4.1.5.原始递归函数的层次 399
4.2.变形图灵机 401
4.2.1.图灵的定义和Post的定义 401
4.2.2.单向无限带的图灵机 402
4.2.3.不使用抹去功能的图灵机 402
4.2.4.多带图灵机 403
4.2.5.多维带图灵机 403
4.2.8.其它图灵机 404
4.3.Stearns—Hartmanis—Lewis 理论 404
4.2.7.非确定的图灵机 404
4.2.6.多读写头图灵机 404
4.3.1.C?的基本性质 405
4.3.2.识别非正规集合所需的带用量 406
4.4.Hartmanis—Stearns 理论 407
4.4.1.S?的基本性质 408
4.4.2.计算装置与计算时间的关系 409
4.4.3.实时可计数性和复杂性类 411
4.4.4.可计算实数的分类 411
4.5.加速定理 412
4.6.Blum理论 413
4.6.1.基本性质 414
4.6.2.压缩定理和空隙定理 416
5.程序理论 417
5.1.程序图式 417
5.1.1.流图型程序图式 418
5.1.2.图式的解释 420
5.1.3.关于F图式的主要结果 422
5.1.4.递归程序图式 424
5.1.5.While 程序图式 425
5.2.程序验证 426
5.3.程序的不动点理论 430
5.3.1.递归程序和泛函的最小不动点 431
5.3.2.不动点归纳法 434
6.1.布尔代数(2) 437
6.定理的证明 437
6.2.命题逻辑 440
6.3.谓词逻辑 445
6.4.定理的证明 453
6.5.消解定理 456
6.6.消解的技巧 461
第七编 数值分析 467
1.数分析的发展 467
1.1.计算机与数值计算 467
1.2.值分析的意义 468
1.3.计算方法的发展 468
2.式子的计算与误差 470
2.1多项式的计算 470
2.2误差 474
3.函数的插值与逼近 482
3.1.插值 482
3.2.样条逼近 486
3.3.最佳逼近 492
3.4.Pade 逼近 499
3.5.Maehly 逼近 503
3.6.连分数逼近 504
4.数值微分与数值积分 510
4.1.Newton—Cotes 型公式 510
4.2.Gauss 型公式 513
4.4.Romberg 数值积分法 521
4.3.Chebyshev 型公式 521
4.5.Richardson 外推法 528
4.6.数值微分 536
4.7.多重数值积分 539
5.代数方程的数值解法 544
5.1.Lehmer—Schur 方法 544
5.2.Deion—Nickel 方法 546
5.3.Henrichi 方法 549
6.线性方程组的数值解法 554
6.1.高斯消去法 554
6.2.共轭斜量法 558
6.3.谱半径 560
6.4.逐次超松弛法 563
6.5.交替方向法 568
7.矩阵特征值的计算 570
7.1.Givens 方法 570
7.2.Jacobi 方法 572
7.3.LR 方法 575
7.4.QR 方法 580
8.非线性方程组的数值解法 583
8.1.简单迭代法 583
8.2.牛顿法 587
9.常微分方程的数值解法 594
9.1.Runge—Kutta—Gill 方法 594
9.3.Bickley 方法 599
9.2.Hammning 方法 599
10.其它 604
10.1.快速付氏变换 604
10.2.拉普拉斯逆变换 607
附录1 数值分析需要的基础数学 614
1.初等函数论 614
1.1.复数序列与级数 614
1.2.复函数序列与函数项级数 615
1.3.正则函数 620
1.4.复积分 621
1.5.基本定理 622
1.6.残数定理与定积分的计算 627
2.1.拓扑空间的定义 629
2.拓扑空间 629
2.2.豪斯道夫空间 630
2.3.连续函数 630
2.4.积拓扑.诱导拓扑 631
2.5.紧空间.紧集合 632
2.6.极限 633
2.8.商空间 633
3.拓扑向量空间 634
3.1.距离空间 634
3.2.赋范空间.巴拿赫空间 635
3.3.希尔伯特空间 636
3.4.拓扑向量空间与半范数 637
3.5.希尔伯特空间的弱拓扑 639
3.6.赋范空间及其对偶空间的弱拓扑 640
3.7.局部凸空间 640
3.8.具体的函数空间及其性质 641
3.9.广义函数 643
附录2 数表与公式 645
1.常数 645
2.nlge 表 645
3.nln10表 645
4.ex 表 646
5.自然对数表 647
6.1.含 a+bx 的函数的不定积分 649
6.2.含a2+x2，a2-x2，a+bx2函数的不定积分 649
6.不定积分公式 649
6.3.含?a+bx函的函数的不定积分 650
6.4.含?x2+a2的函数的不定积分 650
6.5.含?a2-x2的函数的不定积分 651
6.6.含?x2-a2的函数的不定积分 651
6.7.指数函数和三角函数的不定积分 652
6.8.对数函数的不定积分 654
7.幂级数展开 654
8.Chebvshev 多项式的系数 655
9.x?的Chebyshev 展开系数 655
10.Chebyshev 展开的例子 656
11.调和多项式 656
12.1.正交多项式 657
12.正交多项式 657
12.2.勒让德多项式 659
12.3.Chebyshev 多项式 660
12.4.Hermite 多项式 661
12.5.L?guerre 多项式 661
13.样条函数 662
13.1.H?空间 662
13.2.样条函数空间 662
13.3.线性泛函的逼近 664
13.4.泛函在Sard意义下的最佳逼近 665
附录3 杂志一览 665
附录4 参考文献 666
附录5 术语索引 692