【计算机专业考研数学】计算机科学数学理论(网上转载)

很多计算机学生总是对数学学习嗤之以鼻，认为没有太大的实用性，这是后来超越专业考试的重要动机，但随着后续学习的深入，逐渐在实际工作中体会到数学的分量。这种思考能力的运动在初期可能是无形的，但这确实存在。我的理解是数学可以说是一种内功运动，对语言和基础计算机知识的学习是机架学习，更多的人可能更喜欢后者。在开始阶段很明显。但是到了后期，如果只停留在后者的学习上，长期发展的结果只会是习惯使用各种开发工具和语言的熟练工人，无法进一步发展到高层水平。也许这种想法有些极端，只能代表一家之言。但这并不意味着计算机方面的基础知识不重要。反而是类似前提的实体。如果掌握不好，特别是没有良好的抽象能力，对数学基础知识(数学分析、高等代数、数值计算、数论等)就不会有好的感性认识。只能停留在死记硬背阶段。时间长。

今天看了一篇帖子，转载了。

从计算机诞生之日起，它的主要任务就是进行各种科学计算。文档处理、数据处理、图像处理、硬件设计、软件设计等都可以抽象为两大类：数值计算和非数值计算。作为研究计算机科学技术的人，我们大多数人对计算机科学对整个计算机科学的重要性有一定的了解。但是数学对我们专业研究和应用者有多大用处呢？

首先，让我们看一下以下流程图之一。

数学模型 数值计算方法

编程

非数值计算方法。

。

程序编译，查找计算结果

上图显示了利用计算机解决科学计算的步骤，将实际问题转换成程序，经过抽象问题的过程，构建了完美的数学模型，我们才能构建出设计良好的程序。(约翰f肯尼迪，计算机名言)。我们不难看出用计算机解决问题的计算数学理论的重要性。现在我们将逐步展开对这个问题的讨论。

计算机科学的数学理论体系相当复杂。笔者不能随意对计算机科学理论的学科体系进行分类。我们谈论的问题主要涉及数值计算、离散数学、数论和计算理论的四大方向。

[1]数值计算(Numerical Computation)

主要包括数值分析学、数学分析学、线性代数、计算几何学、概率论和数理统计学。数值分析学常被称为计算方法论，是计算理论数学中非常重要的分支，主要研究数值计算。研究内容首先要谈数值计算的误差分析。误差是衡量我们计算是否有效的标准，我们的算法解决问题。如果在误差允许范围内，算法有效。否则就是无效的问题解决。也是数值近似。研究利用数值计算简便的函数粗略替换任意函数的方法和过程。应用似乎比较广泛，因此可能需要提及体设备的接近和平方的接近。笔者尝试的是通过最佳平方近似拟合曲线。开发工具可以选择VC或Matlab。插值函数是另一个非常重要的方面。现代计算机程序控制加工机械零件，根据设计提供零件轮廓曲线的特定类型点、加工时的刀路方向和步数。插值函数计算零件轮廓曲线和其他点函数值。至于方程求根解线性方程，一般的计算性程序设计问题都会涉及到一定程度，这里就不赘述了。(威廉莎士比亚、温斯顿、线性、线性、线性、线性、线性、线性)关于数值分析学的一个学习误区是只学习理论知识，但很难与编程相结合，但实际上通过上述论述，我们已经初步认识到这门学科必须与编程紧密联系才能反映其重要性。关于理论学习，推荐华中科技大学李庆阳老师的《数值分析》。

但是理论学习是一个过程，所以最终目标是为了解决实际计算问题而编程。朝着这个方向努力的书很多。推荐高等教育出版社(CHEP)和斯普林格出版社(Springer)联合出版的《计算方法（Computational Methods）》，华中理工大学数学系写的。在这方面，华库斯特所做的工作在国内应该算是比较多的，个人认为，这种最好的，至少在编程方面，与任意数学函数的评估、方程的求根、线性方程的解、插值方法、数值积分、场微分方程的数值解法有关。数学分析学的很多学校近年来取代了高等数学，被分配到本科教育中。原因很简单。高等数学也是非常有用的工程数学，但介绍的问题方法也广泛适用，但你知道，高等数学不是很严格。基本上是偏向计算的数学分析。当然，数学分析省略了非常重要的推理证明，但我们认为这部分正是我们最需要的部分。

这对我们培养良好的分析能力和推理能力很有帮助。我的软件工程导师北工大水利学院王义华老师是数学系的学生，到软件企业，大部分都是做软件设计和分析工作的，计算机系的学生往往做初级程序员，因为数学系的学生分析推理能力从训练的角度远高于我们的平均水平。(威廉莎士比亚，温斯顿，《科学》。)关于这方面的书，北京大学张祝生老师的《数学分析新讲》公认是最好的。张祝生教授一辈子写的书并不多，但如果写的所有书都是这个领域的杰作，这当然更为突出。这种旧书似乎不是向你传授知识，而是让你体会科学方法和对事物的认识方法。目前使用较多的是复旦大学的《数学分析》，高等教育出版社，好像是很好的教材。但是，对于如何利用从中获得的推理证明能力，在出现具体问题时，以后可以详细讨论文章。线性代数是我们在工科大学学习的必修课，恐怕找不到这到底是什么。

①←—④

↑\ │

↓ \,↓

②←—③

令aij=1,表示从i市到j市有1条航线

令aij=0，表示从i市到j市没有单项航线

则图可用矩阵表示：

┌ ┐

│0 1 1 0 │

│1 0 0 0 │

A= (aij) = │0 1 0 0 │

│1 0 0 0 │

│1 0 1 0 │

└ ┘

我们可以采用程序设计实现这个问题，如果辅以权值，可以转化为最短路径的问题，再复杂化一点还可以转化为具有障碍物的最短路径问题，这就会涉及一些如Dijkstra算法等高级程序设计算法话题。这些都依靠着数组、矩阵的基本知识。数组的应用主要在图像处理以及一些程序设计理论。矩阵的运算领域极为广泛，比如在计算机图形学当中曲线曲面的构造，图像的几何变换，包括平移、镜像、转置、缩放。在高级图像问题更有广泛应用，例如在图像增强技术，投影技术中的应用。计算几何学研究的是几何外形信息的计算机表示。包括几何查找、多边形、凸包问题、交与并、几何体的排列、几何拓扑网络设计、随机几何算法与并行几何算法。它构成了计算机图形学中的基本算法，是动画设计，制造业计算机辅助设计的基础。如果从事这方面的深入研究，可以参考中国计算机学会周培德先生的《计算几何——算法分析与设计》。

概率论与数理统计学是这个领域最后一门关键的课程。概率论部分提供了很多问题的基本知识描述，比如模式识别当中的概率计算，参数估计等等。数理统计部分有很多非常经典的内容，比如伪随机数、蒙特卡罗法、回归分析、排队论、假设检验、以及经典的马科夫过程。尤其是随机过程部分，是分析网络和分布式系统，设计随机化算法和协议非常重要的基础。

二]离散数学（Discrete Mathematics）

随着计算机科学的出现与广泛应用,人们发现利用计算机处理的数学对象与传统的分析有明显的区别：分析研究的问题解决方案是连续的，因而微分，积分成为基本的运算；而这些分支研究的对象是离散的，因而很少有机会进行此类的计算。人们从而称这些分支为"离散数学"。离散数学经过几十年发展，方向上基本上稳定下来。当然不同时期还有很多新内容补充进来。就学科方向而言，一般认为，离散数学包含：集合论、逻辑学、代数学、图论、组合学。

逻辑学（Logics）我们主要指数理逻辑，形式逻辑在推理问题中也有比较广泛的应用。（比如我们学校还为此专门开设了选修课程）这方面的参考推荐中科院软件所陆钟万教授的《面向计算机科学的数理逻辑》。现在可以找到陆钟万教授的讲课录像，。总的来说，学集合/逻辑一定要站在理解的高度上去思考相关的问题。集合论（Set Theory）和逻辑学构成了计算机科学最重要的数学问题描述方式。

代数学（Algebra）包括：抽象代数、布尔代数、关系代数、计算机代数

（1）抽象代数（Abstract Algebra）研究的主要内容涵盖群、环、域。抽象代表的是将研究对象的本质提炼出来，加以高度概括，来描述其形象。“欧式环”就是在将整数和多项式的一些相同的特点加以综合提炼引入的。抽象代数提供的一些结论为我们研究一些具体问题时所需使用的一些性质提供了依据。推荐一个最简单的，最容易学的材料：

这本《Introductionto Linear and Abstra

ct Algebra》非常通俗易懂，而且把抽象代数和线性代数结合起来，对初学者来说非常理想。

（2）布尔代数（Boolean Algebra）是代数系统中最为基础的部分，也是最核心的基本

理论。主要包括了集合的基本概念与运算，自对偶的公理系统。是数据表示的重要基础。相信大家都很清楚它的重要性。

（3）关系代数（Relational Algebra）应用也是极为广泛，比如数据库技术中的关系数据库的构建就要用到关系代数的相关理论（2）布尔代数（Boolean Algebra）是代数系统中最为基础的部分，也是最核心的基本理论。主要包括了集合的基本概念与运算，自对偶的公理系统。是数据表示的重要基础。相信大家都很清楚它的重要性。

（3）关系代数（Relational Algebra）应用也是极为广泛，比如数据库技术中的关系数据库的构建就要用到关系代数的相关理论。

（4）计算机代数（Computer Algebra）大家可能比较生疏，其实它研究的主要内容即是围绕符号计算与公式演算展开的。是研究代数算法的设计、分析、实现及其应用的学科。主要求解非数值计算，输入输出用代数符号表示。计算机代数的开发语言主要有：ALTRAN,CAMAL,FORMAL。主要应用于：射影几何，工业设计，机器人手臂运动设计。

图论（Graph Theory）主要研究的内容包括：图的基本概念、基本运算、矩阵表示，路径、回路和连通性，二部图、平面图，树，以及网络流。图论的应用领域太过广泛，仅举两个例子：比如在计算机网络拓扑图的设计与结构描述中，就必须用到相当多的图的结构和基本概念。关于网络流更是在电流网络与信息网络的流量计算当中广泛应用。树的相关应用则无须多言了。

组合学（Combinatorics）有两部分单独的研究领域：组合数学与组合算法。组合学问题的算法，计算对象是离散的、有限的数学结构。从方法学的角度，组合算法包括算法设计和算法分析两个方面。关于算法设计，历史上已经总结出了若干带有普遍意义的方法和技术，包括动态规划、回溯法、分支限界法、分治法、贪心法等。应用是相当广泛的,比如旅行商问题、图着色问题、整数规划问题。关于组合数学，主要研究的内容有：鸽巢原理、排列与组合、二项式系数容斥原理及应用，递推关系和生成函数、特殊计数序列、二分图中的匹配、组合设计。推荐Richard A.Brualdi的《Introductory Combinatorics》作为参考。

[三]数论（Number Theory）

数论这门学科最初是从研究整数开始的，所以叫做整数论。后来更名为数论。它包括以下几个分支：

初等数论是不求助于其他数学学科的帮助，只依靠初等方法来研究整数性质的数论分支。比如在数论界非常著名的“中国剩余定理”，就是初等数论中很重要的内容。对于程序设计来说这部分也是相当有价值的，如果你对中国剩余定理比较清楚，利用它，你可以将一种表达式经过简单的转换后得出另一种表达式，从而完成对问题分析视角的转换。解析数论是使用数学分析作为工具来解决数论问题的分支。是解决数论中比较深刻问题的强有力的工具。我国数学家陈景润在尝试解决“哥德巴赫猜想”问题中使用的就是解析数论的方法。以素数定理为基础解决计算素数的问题及其算法实现应是我们多多关注的。

代数数论是把整数的概念推广到一般代数数域上去，建立了素整数、可除性等概念。程序设计方面涉及的比较多的是代数曲线的研究，比如说椭圆曲线理论的实现。几何数论研究的基本对象是“空间格网”。空间格网就是指在给定的直角坐标系上，坐标全是整数的点，叫做整点；全部整点构成的组就叫做空间格网。空间格网对计算几何学的研究有着重大的意义。几何数论涉及的问题比较复杂，必须具有相当的数学基础才能深入研究。

总的说来，由于近代计算机科学的发展，数论得到了广泛的应用。比如在计算方法、代数编码、组合学理论等方面都广泛使用了初等数论范围内的许多研究成果；现在有些国家应用“孙子定理”来进行测距，用原根和指数来计算离散傅里叶变换等。如果你曾经系统的学习过数论算法，你会发现这个分支学科研究的一些基本问题对程序设计是相当有用的，比如说素数问题、素性测试、因子分解、最大公约数、模取幂运算、求解同余线性方程。其中的很多问题都是程序设计的基本问题。但这些问题都不能小视，举个例子来说吧，关于求最大公约数的程序，笔者曾经尝试的就可以采用循环语句结构和递归结构。另外，以大素数为基础的密码体系的建立是近些年数论算法广泛应用的一个重要的原因。原理是大素数的乘积重新分解因数十分困难。RSA公钥加密系统的构建就是基于这个原理的（三位发明人因此也获得了2002年美国计算机协会颁发的图灵奖）。

四]计算理论（Theory of Computation）

涉及的内容是科学计算非常重要的一部分分支，也是大家研究相当多的一部分。主要包括：算法学，计算复杂性，程序理论。

算法学（Algorithms）在计算机科学理论中有着举足轻重的地位。是解决很多数值型，非数值型问题的基础。记得一次学校接收招标项目，很多中小型软件厂商都无法完成一个软件的功能模块，就是因为当时他们对一个具体问题的算法不能做出正确的抽象，最后由我们学校数理学院的一支软件团队承担了这项任务，他们的最终报告体现出来，问题的解决策略只有通过人工神经元网络的反向传播算法。可见在比较有深度的程序设计中，算法的重要性更为突出。学习算法学要有一个长期的理论和实践的过程。遇到一个具体算法问题时,首先要通过自己描述的数学抽象步骤，看看自己以前有没有处理过这种问题。如果没有，很可能这个问题是多个算法的综合，或者是需要我们自己去构造算法。这就需要我们有扎实的算法功底，为了打好这个功底，推荐两套圣经级的书籍首先是Thomas H.Cormen等著的《Introduction to Algorithms》。对算法学习而言，这一本内容相当的全面。再深一点的就是大家作为常识都知道的《The Art of Computer Programming》，目前已经出版3册。两本书的价值大家应当都是清楚的。

计算复杂性研究的内容很广，其中包括NP完全性理论，可计算性理论，自动机理论

，形式语言理论（包括广泛应用于编译原理领域的文法，还包括Petri网论的相关内容）以及大家熟知的复杂性度量。时间复杂度、空间复杂度的计算是度量算法非常重要的参数，也是我们衡量程序优劣程度的重要依据。

程序理论（Theory of programs）包含了形式语义学，程序验证和并发模型的研究。关于程序验证学习的重要性大家都很清楚，学习的方法自然也是多多结合具体的问题去分析。关于并发模型，主要研究的就是进程代数，通信系统演算，通信顺序进程。这部分是研究操作系统理论与实现的重要基础。

按照计算机科学数学理论的架构来谈了各方面的内容和一些应用，下面我们再单独来看一些上面没有涉及到的学科与这些理论的具体结合情况：设计方面的应用刚才谈的很多，我只再说说数据库原理与技术，这方面用到的重要数学基础主要包括：集合论，二元关系及其推理（尤其是研究关系数据库），研究数据分布与数据库结构又涉及相当多的图论知识。计算机科学的发展有赖于硬件技术和软件技术的综合。在设计硬件的时候应当充分融入软件的设计思想，才能使硬件在程序的指挥下发挥极致的性能。在软件设计的时候也要充分考虑硬件的特点，才能冲破软件效率的瓶颈。达到硬件和软件设计的统一，严格的说这并不轻松，一般的程序设计者很难将这样的思想贯穿在其程序设计当中。仅举个简单的例子：我们在写一些C语言的程序，必要的时候都会采取内嵌一段汇编指令，这

就是比较充分地考虑了硬件的工作情况，从而能够提高程序运行的效率。所以我们也有必要了解一些硬件的基础知识。关于学习硬件的时候常会用到的基本数学思想也是相当多的，拿电路基础与模拟电路来说，我们就经常要利用多元函数，不等式计算进行电流电压的计算。能量的计算还常常涉及微积分学的很多计算。在数字电子技术当中（有时也称数字逻辑学）数理逻辑，尤其是逻辑演算部分运用相当广泛，数制转换更是非常重要的基础，各种数字电路参数的计算则是多元函数，不等式的计算解决的问题。从事计算机硬件程序设计的程序员，则不可回避的就是数字信号处理。这门科学所用到的数学基础主要有：三角函数、微积分、高次方程求解、数值逼近，傅里叶变换。在滤波器的设计当中还会用到矩阵运算。笔者曾经研究过一个VC++环境下开发的滤波器的模拟软件，就是利用莱文逊-杜宾递推算法，在较大规模的矩阵运算基础上进行的。当然，开发的环境不一定是这个，你也可以选择MATLAB或者纯C语言编译器。如果我们不了解相关的数学基础，不要说程序设计，就算是建立运算模型都是相当困难的。

一些周围的同学和一些在职的程序员，大家经过一段时间的学习，普遍都觉得数学对学习计算机和研究计算机程序设计等问题来说非常重要，但是又苦于无从下手。上面比较全面地谈及了计算机科学数学理论的相关内容。需要特别指明的是，我们研究问题的精力是有限的，如果您是在校的计算机系学生，则可以对上面的方方面面都有所涉及，以尝试计算数学这个强大的理论工具。为今后的工作奠定一个坚实的基础。但是如果您研究的是比较具体的工作，我们并不推荐您研究所有的内容，最好的方法就是对上面的数学基础都有些了解，然后遇到具体工作，需要哪部分内容，再进行深入的学习与研究。这样针对性比较强的学习效果是会比较显著的。对于上面推荐的一些参考材料，除非你要花相当长的一段时间来提高你的计算机数学理论。否则也没必要每一页，每一本都字字精读，还是那个原则，按需索取其中的内容。学习的方法描述起来就一句话：结合具体的问题，深入的理解数学理论知识，将理论程序化，尝试用程序设计实现理论原理。达到这样的程度，问题基本上都可以解决的