论数学在计算机科学中的基础作用

论数学在计算机科学中的基础作用

课题引入
计算机基础与数学联系十分紧密。当今更为火爆的网络软件开发等信息界的精英，大部分是数学出身，数学在计算机中的应用是不言而喻的。

大部分高校的计算机系所开设的数学课程几乎和数学系不相上下，无论广度，深度都达到相当水准。从事计算机软件、硬件开发不仅需要高深的数学知识为基础，而且需要很强的逻辑思维能力、形象思维能力和空间想象能力，这些离开数学是不可能的。

计算机基础中所应用的数学知识主要有：数理逻辑、图论、数据处理、线性代数、概率分布、参数估计、群论、积分变换、微分方程、拓扑等。

(微观)从计算机角度看数学各学科的作用

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

    上图揭示了利用计算机解决科学计算的步骤，实际问题转换为程序，要经过一个对问题抽象的过程，建立起完善的数学模型，只有这样，我们才能建立一个设计良好的程序。从中我们不难看出计算数学理论对用计算机解决问题的重要性。下面我们将逐步展开对这个问题的讨论。

计算机科学的数学理论体系是相当庞杂的，笔者不敢随意划分，参考计算机科学理论的学科体系，我们谈及的问题主要涉及：数值计算，离散数学，数论，计算理论四大方向。

 
【一】数值计算（Numerical Computation）
主要包括数值分析学、数学分析学、线性代数、计算几何学、概率论与数理统计学。

数值分析学   又常被称为计算方法学，是计算理论数学非常重要的一个分支，主要研究数值型计算。研究的内容中首先要谈谈数值计算的误差分析，误差是衡量我们的计算有效与否的标准，我们的算法解决问题如果在误差允许的范围内，则算法是有效的，否则就是一个无效的问题求解。另外就是数值逼近，它研究关于如何使用容易数值计算的函数来近似地代替任意函数的方法与过程。感觉应用比较广的不得不提切雪比夫逼近和平方逼近了。笔者曾经尝试过的就是通过最佳平方逼近进行曲线的拟合，开发工具可以选择VC++或者MATLAB。插值函数是另外一个非常重要的方面，现代的计算机程序控制加工机械零件，根据设计可给出零件外形曲线的某些型值点，加工时走刀方向及步数，就要通过插值函数计算零件外形曲线及其他点函数值。至于方程求根、线性方程组求解，一般的计算性程序设计问题都会多多少少的涉及一些，我们这里就不赘述了。关于数值分析学的一个学习误区就是仅仅学习理论知识，而很难和程序设计结合起来，实际上通过上面的论述，大家已经能够初步地认识到这个学科是应当与程序设计紧密联系才能够体现它的重要性的。
 

    数学分析学 很多学校在近些年已经替代高等数学被安排到了本科教学当中。原因是很简单的，高等数学虽然也是非常有用的工程数学，介绍的问题方法也被广泛的应用，但是正如大家所知道的，高等数学不太严格的说，基本上就是偏向于计算的数学分析，当然省去了数学分析非常看重的推理证明，然而我们认为这一部分正是计算机人才最需要的。这对我们培养良好的分析能力和推理能力极有帮助。北工大数理学院的王仪华先生就曾经说过，数学系的学生到软件企业中大多作软件设计与分析工作，而计算机系的学生做初级程序员的居多，原因就在于数学系的学生分析推理能力，从所受训练的角度上要远远在我们平均水平之上。

    线性代数  是在工科本科学习的必修课程，似乎大家找不到到底这个有什么用，其实很明显，线性代数作为工程数学的重要分支，在计算机领域的研究有相当广泛的应用。最为突出的可以谈谈数组和矩阵的相关知识：
下面谈一个我经常和同学讨论的问题：四个城市之间的航线如图所示：

令=Aij,表示从i市到j市有1条航线
令Aij =0，表示从i市到j市没有单项航线
则图可用矩阵表示：                       
A= (Aij) =
   我们可以采用程序设计实现这个问题，如果辅以权值，可以转化为最短路径的问题，再复杂化一点还可以转化为具有障碍物的最短路径问题，这就会涉及一些如Dijkstra算法等高级程序设计算法话题。这些都依靠着数组、矩阵的基本知识。数组的应用主要在图像处理以及一些程序设计理论。矩阵的运算领域极为广泛，比如在计算机图形学当中曲线曲面的构造，图像的几何变换，包括平移、镜像、转置、缩放。在高级图像问题更有广泛应用，例如在图像增强技术，投影技术中的应用。

  计算几何学  研究的是几何外形信息的计算机表示。包括几何查找、多边形、凸包问题、交与并、几何体的排列、几何拓扑网络设计、随机几何算法与并行几何算法。它构成了计算机图形学中的基本算法，是动画设计，制造业计算机辅助设计的基础。

概率论与数理统计学  是这个领域最后一门关键的课程。概率论部分提供了很多问题的基本知识描述，比如模式识别当中的概率计算，参数估计等等。数理统计部分有很多非常经典的内容，比如伪随机数、蒙特卡罗法、回归分析、排队论、假设检验、以及经典的马科夫过程。尤其是随机过程部分，是分析网络和分布式系统，设计随机化算法和协议非常重要的基础。
【二】离散数学（Discrete Mathematics）
随着计算机科学的出现与广泛应用,人们发现利用计算机处理的数学对象与传统的分析有明显的区别：分析研究的问题解决方案是连续的，因而微分，积分成为基本的运算；而这些分支研究的对象是离散的，因而很少有机会进行此类的计算。人们从而称这些分支为"离散数学"。离散数学经过几十年发展，方向上基本上稳定下来。当然不同时期还有很多新内容补充进来。就学科方向而言，一般认为，离散数学包含：集合论、逻辑学、代数学、图论、组合学。

逻辑学（Logics）
我们主要指数理逻辑，形式逻辑在推理问题中也有比较广泛的应用。（比如我们学校还为此专门开设了选修课程）总的来说，学集合/逻辑一定要站在理解的高度上去思考相关的问题。集合论（Set Theory）和逻辑学构成了计算机科学最重要的数学问题描述方式。

代数学（Algebra）包括：抽象代数、布尔代数、关系代数、计算机代数
（1）抽象代数（Abstract Algebra）研究的主要内容涵盖群、环、域。抽象代表的是将研究对象的本质提炼出来，加以高度概括，来描述其形象。“欧式环”就是在将整数和多项式的一些相同的特点加以综合提炼引入的。抽象代数提供的一些结论为我们研究一些具体问题时所需使用的一些性质提供了依据。
（2）布尔代数（Boolean Algebra）是代数系统中最为基础的部分，也是最核心的基本理论。主要包括了集合的基本概念与运算，自对偶的公理系统。是数据表示的重要基础。相信大家都很清楚它的重要性。
（3）关系代数（Relational Algebra）应用也是极为广泛，比如数据库技术中的关系数据库的构建就要用到关系代数的相关理论。
（4）计算机代数（Computer Algebra）大家可能比较生疏，其实它研究的主要内容即是围绕符号计算与公式演算展开的。是研究代数算法的设计、分析、实现及其应用的学科。主要求解非数值计算，输入输出用代数符号表示。计算机代数的开发语言主要有：ALTRAN,CAMAL,FORMAL。主要应用于：射影几何，工业设计，机器人手臂运动设计。
     图论（Graph Theory）主要研究的内容包括：图的基本概念、基本运算、矩阵表示，路径、回路和连通性，二部图、平面图，树，以及网络流。图论的应用领域太过广泛，仅举两个例子：比如在计算机网络拓扑图的设计与结构描述中，就必须用到相当多的图的结构和基本概念。关于网络流更是在电流网络与信息网络的流量计算当中广泛应用。树的相关应用则无须多言了。
     组合学（Combinatorics）有两部分单独的研究领域：组合数学与组合算法。组合学问题的算法，计算对象是离散的、有限的数学结构。从方法学的角度，组合算法包括算法设计和算法分析两个方面。关于算法设计，历史上已经总结出了若干带有普遍意义的方法和技术，包括动态规划、回溯法、分支限界法、分治法、贪心法等。应用是相当广泛的,比如旅行商问题、图着色问题、整数规划问题。关于组合数学，主要研究的内容有：鸽巢原理、排列与组合、二项式系数容斥原理及应用，递推关系和生成函数、特殊计数序列、二分图中的匹配、组合设计。

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

初等数论是不求助于其他数学学科的帮助，只依靠初等方法来研究整数性质的数论分支。比如在数论界非常著名的“中国剩余定理”，就是初等数论中很重要的内容。对于程序设计来说这部分也是相当有价值的，如果你对中国剩余定理比较清楚，利用它，你可以将一种表达式经过简单的转换后得出另一种表达式，从而完成对问题分析视角的转换。
   解析数论是使用数学分析作为工具来解决数论问题的分支。是解决数论中比较深刻问题的强有力的工具。我国数学家陈景润在尝试解决“哥德巴赫猜想”问题中使用的就是解析数论的方法。以素数定理为基础解决计算素数的问题及其算法实现应是我们多多关注的。
    代数数论是把整数的概念推广到一般代数数域上去，建立了素整数、可除性等概念。程序设计方面涉及的比较多的是代数曲线的研究，比如说椭圆曲线理论的实现。
    几何数论研究的基本对象是“空间格网”。空间格网就是指在给定的直角坐标系上，坐标全是整数的点，叫做整点；全部整点构成的组就叫做空间格网。空间格网对计算几何学的研究有着重大的意义。几何数论涉及的问题比较复杂，必须具有相当的数学基础才能深入研究。
    总的说来，由于近代计算机科学的发展，数论得到了广泛的应用。比如在计算方法、代数编码、组合学理论等方面都广泛使用了初等数论范围内的许多研究成果；现在有些国家应用“孙子定理”来进行测距，用原根和指数来计算离散傅里叶变换等。如果你曾经系统的学习过数论算法，你会发现这个分支学科研究的一些基本问题对程序设计是相当有用的，比如说素数问题、素性测试、因子分解、最大公约数、模取幂运算、求解同余线性方程。其中的很多问题都是程序设计的基本问题。但这些问题都不能小视，举个例子来说吧，关于求最大公约数的程序，笔者曾经尝试的就可以采用循环语句结构和递归结构。另外，以大素数为基础的密码体系的建立是近些年数论算法广泛应用的一个重要的原因。原理是大素数的乘积重新分解因数十分困难。RSA公钥加密系统的构建就是基于这个原理的（三位发明人因此也获得了2002年美国计算机协会颁发的图灵奖）。

[四]计算理论（Theory of Computation）
    涉及的内容是科学计算非常重要的一部分分支，也是大家研究相当多的一部分。主要包括：算法学，计算复杂性，程序理论。
　  算法学（Algorithms） 在计算机科学理论中有着举足轻重的地位。是解决很多数值型，非数值型问题的基础。例如有一个学校在接收招标项目，很多中小型软件厂商都无法完成一个软件的功能模块，就是因为当时他们对一个具体问题的算法不能做出正确的抽象，最后由学校数理学院的一支软件团队承担了这项任务，他们的最终报告体现出来，问题的解决策略只有通过人工神经元网络的反向传播算法。可见在比较有深度的程序设计中，算法的重要性更为突出。学习算法学要有一个长期的理论和实践的过程。遇到一个具体算法问题时,首先要通过自己描述的数学抽象步骤，看看自己以前有没有处理过这种问题。如果没有，很可能这个问题是多个算法的综合，或者是需要我们自己去构造算法。
     计算复杂性 研究的内容很广，其中包括NP完全性理论，可计算性理论，自动机理论，形式语言理论（包括广泛应用于编译原理领域的文法，还包括Petri网论的相关内容）以及大家熟知的复杂性度量。时间复杂度、空间复杂度的计算是度量算法非常重要的参数，也是我们衡量程序优劣程度的重要依据。
     程序理论 （Theory of programs）包含了形式语义学，程序验证和并发模型的研究。关于程序验证学习的重要性大家都很清楚，学习的方法自然也是多多结合具体的问题去分析。关于并发模型，主要研究的就是进程代数，通信系统演算，通信顺序进程。这部分是研究操作系统理论与实现的重要基础。
   

【五】其他 上面我们按照计算机科学数学理论的架构来谈了各方面的内容和一些应用，下面再单独来看一些上面没有涉及到的学科与这些理论的具体结合情况：
    设计方面的应用刚才谈的很多，我只再说说数据库原理与技术，这方面用到的重要数学基础主要包括：集合论，二元关系及其推理（尤其是研究关系数据库），研究数据分布与数据库结构又涉及相当多的图论知识。
    计算机科学的发展有赖于硬件技术和软件技术的综合。在设计硬件的时候应当充分融入软件的设计思想，才能使硬件在程序的指挥下发挥极致的性能。在软件设计的时候也要充分考虑硬件的特点，才能冲破软件效率的瓶颈。达到硬件和软件设计的统一，严格的说这并不轻松，一般的程序设计者很难将这样的思想贯穿在其程序设计当中。仅举个简单的例子：我们在写一些C语言的程序，必要的时候都会采取内嵌一段汇编指令，这就是比较充分地考虑了硬件的工作情况，从而能够提高程序运行的效率。所以我们也有必要了解一些硬件的基础知识。关于学习硬件的时候常会用到的基本数学思想也是相当多的，拿电路基础与模拟电路来说，我们就经常要利用多元函数，不等式计算进行电流电压的计算。能量的计算还常常涉及微积分学的很多计算。在数字电子技术当中（有时也称数字逻辑学）数理逻辑，尤其是逻辑演算部分运用相当广泛，数制转换更是非常重要的基础，各种数字电路参数的计算则是多元函数，不等式的计算解决的问题。
    从事计算机硬件程序设计的程序员，则不可回避的就是数字信号处理。这门科学所用到的数学基础主要有：三角函数、微积分、高次方程求解、数值逼近，傅里叶变换。在滤波器的设计当中还会用到矩阵运算。笔者曾经研究过一个VC++环境下开发的滤波器的模拟软件，就是利用莱文逊-杜宾递推算法，在较大规模的矩阵运算基础上进行的。当然，开发的环境不一定是这个，你也可以选择MATLAB或者纯C语言编译器。如果我们不了解相关的数学基础，不要说程序设计，就算是建立运算模型都是相当困难的。
   

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

（宏观）数学和计算机技术的相互影响
摘  要
 

数学和计算机的关系非常密切。一直到二三十年以前，计算机科学本身还是数学学科的一个分支，最早研究计算机的专家也都是数学家。在计算机进行运算的基本原理中，处处渗透着数学的各种思想。而现在，计算机科学已经深受人们的关注，成为了一个独立的学术领域，这之间离不开数学理论的推动；反之，从数学的发展来看，不仅可以利用计算机解决大量人工无法实现的巨量计算问题，很多难以证明的定理还可以通过计算机完成证明；程序，作为数学与计算机之间的一座重要桥梁，在数学的发展，计算机的应用方面起着双重的推动作用。本文从数学原理与计算机技术的关系展开讨论。

引  言
数学是一门基础理论学科，数学在科学研究中的作用众所周知，甚至被称为“科学的皇后”。数学是所有学科的基础，统治着所有涉及到量的世界。每个想要搞理科研究的学者都必须有良好的数学基础。在计算机发明之前，数学的发展是靠无数科学家们代代相传的努力换来的。有了计算机，数学的发展的确变得更快更好。但是，具体地说，计算机技术是如何推动数学学科的发展的？数学作为计算机技术的基础又体现在哪些方面，下面从两者之间的相互影响展开讨论。

 

数学是计算机技术的基础
 

1、数学家对计算机理论和技术的贡献
提到计算机，不能不提到二十世纪的两位伟大的数学家——阿兰•图灵和冯•诺伊曼。阿兰•图灵是英国一位著名的数学家。他通过仔细研究，提出了“所有的数学运算过程都可以抽象成数学模型” 的观点，并于1936年开创性地提出了计算机的运算模型，奠定了现代计算机技术的理论基础，因此被誉为“计算机理论之父”。冯•诺伊曼是美籍匈牙利数学家。他的重要贡献是对由约翰·莫克利（John Mauchly）和普雷斯伯·埃克特（Presper Eckert）研制的世界上第一台数字式电子计算机进行了一次全新的改革。这项改革从此彻底改变了计算机技术的命运。原来，莫克利和埃克特发明的计算机虽然能大大提高运算速度，但它却存在着两个致命缺点：（1）没有储存器，无法将数据或指令存储到计算机中；（2）每次执行不同的任务，都要重新布置导线。这样，它运算速度快的优点被布线所需花费的大量时间所抵消。因此，他的应用也仅限于复杂的科学计算和军事应用。冯·诺伊曼运用数学中的“二进制”思想将其改进，发明了“离散变量自动电子计算机”EDVAC（electronic discrete variable automatic computer ）。这种计算机能够将数据或指令储存，更重要的是它由于采用了二进制的运算方式，大大方便了数据的传输。这样，计算机的应用面立刻扩大了，它不仅被用在军事与尖端技术上，同时也应用在工程设计、数据处理、事务管理等方面。可以说，我们现在使用的计算机还是建立在EDVAC基础之上的。由于冯•诺伊曼对计算机技术的巨大贡献，他被称为“计算机之父”。

2、数学思想在计算机技术中的运用
现代计算机之所以能够如此智能化，在很大程度上是由于受了数学思想的启发。数学逻辑结构的严谨，数学理论的严密，甚至许多数学方法本身，都直接被广泛地采用到计算机科学的众多领域。比如，数学中的二进制思想已成为现代计算机技术发展的坚实基础。广泛地说，只要进行数据的传输或整理时，就要用到这种思想。具体做法是将每一个字节的数据用八位二进制数保存，这样在通过导线传输时只需用导线的通与断来分别表示0和1，就可以表示整个字节。从一个文件的储存，到一幅千兆图片的存储，更甚网络中成千上万的各种格式的数据的运送，都是离不开二进制的。回想一下，如果没有二进制的思想作为基础，或者说没有数学的发展作基础，何来冯·诺伊曼的伟大创举，乃至EDVAC和当今计算机的诞生呢？从这个意义上说，没有数学原理的应用，就没有现代的计算机技术。

3、数学原理对计算机软件系统的支持
上述提到的是计算机硬件技术的发展对数学的依赖，除此之外，计算机软件设计也离不开数学原理的支持。要掌握好计算机程序设计，数学功底非常重要。从我个人的体会来看，要设计任何一个计算机算法，其实质都是先将问题转化为一个（更多的情况下是多个）需要解决的子问题，然后再想办法逐一解决这些问题，最后使得整个程序连贯为一体。通俗的讲，就是先“审题” ，然后考虑解决的方法，一步一步深入，直到整个问题解决。这其中是一环紧扣一环，有着非常严密的逻辑性的。少一个步骤，跳一个步骤，或者有一个环节出了差错，整个程序就会瘫痪。另外，就从编程序的这个环节来说，利用任何一种语言编制程序都需要不断运用数学理论来帮助。同时，仍然要保持程序逻辑的严密性。一个具有数学修养的程序员在写代码时更有可能写出逻辑严密的最简化的高质量代码。尤其是对大型复杂的软件系统，如果没有良好的数学思维的训练，是很难编制出高质量的程序的。举例说，我们要操作或控制计算机，就必须有操作系统。操作系统至今已经有了几百种，个人计算机中最常用的有windows98 / me / 2 000 / 2003 / xp等。这些复杂的操作系统的产生，归根结底还是由不同的程序模块组合而成。这样大型的程序系统，离不开一个又一个的子程序，以及它们之间严密的优化组合，这样才能让用户放心使用，不会出现意想不到的漏洞与问题。有关研究表明，我们国家计算机软件水平的落后不是因为我们缺少程序员，而是因为缺乏懂数学的高质量的程序员。又比如微软公司总裁比尔·盖茨，他之所以能够在计算机软件方面取得成功，很大程度上是由于年青时对数学的痴迷，具有的极强的数学思维能力。归根结底，程序是计算机与数学之间最重要的一座连接的桥梁。有关程序的讨论放在下文中。

 

计算机技术对数学发展的贡献
 

1、计算机的高速运算能力
计算机之所以在数学上被广泛应用的一个因素是由数学计算的特有需要和计算机具有的独特优点所决定的，那就是：高速运算。粗略地说，计算机在数学学科的应用价值主要体现在快速穷举方面。我们知道，当面对一个很大的数据量时，靠人脑计算就十分困难了，不但进展很慢，而且计算的错误率很大。这时，我们就经常用到计算机的穷举法。既然计算机的运算速度可以达到每秒几千万次，靠这样的速度，即使算上编程序的时间（编穷举法程序比其它程序容易得多，程序员把大量的工作交给了计算机去完成，程序语言也比较简单），也会大大提高解决问题的效率。而且，计算机的准确率相当高，用这样的方法解决问题，自然要比人工优越得多。

2、程序是连接计算机和数学运算的桥梁
有了计算机，很多数学问题可以通过编写适当的程序解决，每个数学模型都可以写出对应的计算机程序。我们来看几个例子。

例1，“利用三角形三边长计算面积”，可以写出如下程序（用Pascal语言编写）。

Program square;

  Var

     a,b,c:real; {变量a,b,c表示三边的长}

     s,p:real;  {s表示面积，p表示半周长}

     begin

        readln(a,b,c); {从键盘读入a,b,c}

        p:=(a+b+c)/2;{计算半周长}

        s:=sqrt(p*(p-a)*(p-b)*(p-c)){用海伦公式计算s}

        writeln(‘s=’,s); {输出s}

End.

（说明：由用户输入一个已知三角形的三边长，程序会自动计算出其面积，遇到给定三边不能构成三角形时自动跳出程序并提示错误）

像这样一个程序是十分浅显易懂的，其中的重要步骤即海伦公式的运用。可见如果没有海伦公式这样的数学原理的话，这个程序的编写变成了空谈。需要说明的是，此程序能帮助运算的主要体现是使得运算速度大大提高。

例2：可以写出如下判断一个自然数是否是素数的程序（用Pascal语言编写）。

我们知道，判断素数的主要方法是将他除以每一个小于等于他的算术平方根的自然数。当数据很大时，一个一个地去试验是一种十分费时费力的方法，这时我们就可以让计算机帮我们去完成试验的工作。程序如下。

program prime;

  var

     p:longint; {要判断的自然数}

     q:longint; {每一个实验时用到的除数}

     f:Boolean;{是否是素数的标志}

  begin

     readln(p); {键盘读入p}

     f:=true; {假设p是素数}

     for q:=2 to trunc(sqrt(p)) do {将q分别赋值每一个小于等于p的算术平方根的自然数并重复执行如下语句：}

       if p mod q=0 then begin f:=false;break;end; {进行试验，若p是q的倍数，就将f赋值false并结束循环}

     if f=true then write(‘Yes.’) {根据情况打印出相应的判断}

          else write(‘No.’)

end.

（说明：用户只需输入一个自然数，程序便能自动判断其是否素数）

在一眨眼间，上述程序就能对十亿级的数字进行判断。此外，对于上面的程序，当p和q的变量类型都设定为longint（长整型）时，就可以表示十亿级的数字了，如果用一个一维数组来表示数的话（即假设有数列a，数列中的数分别为a[1],a[2],…a[n],那么用a[1]表示这个数字的第一位，a[2]表示第二位，依此类推），那么如果n仍以longint作为类型，这样就可以表示一个千兆位的数字了，可想而知他的“厉害”了。

例三：用哈夫曼树原理编制哈夫曼编码：

 

program huffman_tree;

  type

      node=record

          w,llink,rlink,parent:integer;

      end;

      element=record

             symbol:char;

             code:string;

      end;

  var

     tree:array[1..100] of node;

     table:array[1..100] of element;

     n,i:integer;

  procedure putin;

    var

       ch:char;

       i:integer;

    begin

       for i:=1 to n do

         begin

           read(ch);

           table[i].symbol:=ch;

         end;

    end;

 

  procedure select(s:integer;var x1,x2:integer);

    var

       i,min1,min2:integer;

    begin

       min1:=maxint;min2:=min1;

       x1:=0;x2:=0;

       for i:=1 to s do

         begin

           if tree[i].parent=0 then

             if tree[i].w<min1 then begin

                       x2:=x1;x1:=i;

                       min2:=min1;min1:=tree[i].w;

                  end

               else if tree[i].w<min2 then begin

                        x2:=i;min2:=tree[i].w;end;

         end;

    end;

  procedure settree;

    var

       i,x1,x2:integer;

    begin

       for i:=1 to n do

         begin

           with tree[i] do

             begin

               read(w);

               llink:=0;rlink:=0;

               parent:=0;

             end;

         end;

       for i:=n+1 to 2*n-1 do

          begin

            select(i-1,tree[i].llink,tree[i].rlink);

            tree[tree[i].llink].parent:=i;

            tree[tree[i].rlink].parent:=i;

          end;

    end;

  procedure getcode;

    var

       i,i1,s:integer;

    begin

       for i:=1 to n do

         begin

           i1:=i;

           table[i1].code:='';

           repeat

             s:=tree[i1].parent;

             if tree[s].llink=i1 then table[i].code:='0'+table[i].code

               else table[i].code:='1'+table[i].code;

             i1:=s;

           until tree[s].parent=0;

         end;

    end;

  procedure translate_into;

    var

       ch:char;

       i:integer;

    begin

       read(ch);

       while ch<>'#' do

         begin

           i:=1;

           while table[i].symbol<>ch do i:=i+1;

           write(table[i].code);

           read(ch);

         end;

       end;

  procedure translate_oufo;

    var

       st:string;

       ch:char;

       i:integer;

    begin

       st:='';

       read(ch);

       while ch<>'#' do

         begin

           i:=1;

           while (table[i].code<>st)and(i<=10) do i:=i+1;

           if table[i].code=st then begin write(table[i].symbol);st:='';end;

           st:=st+ch;

           read(ch);

         end;

       i:=1;

       while (table[i].code<>st)and(i<=10) do i:=i+1;

       write(table[i].symbol);

    end;

  begin

    readln(n);

    settree;

    readln;

    putin;

    readln;

    getcode;

    for i:=1 to n do

      writeln(table[i].symbol:4,table[i].code);

    readln;

    translate_into;

    readln;readln;

    translate_oufo;

    readln;

end

（使用说明：哈夫曼编码主要运用于数据加密与方便传输，用哈夫曼树可以方便地根据数据串中每种字符出现的频率（由用户输入，即每种字符的权重）来合理编排编码。具体原理复杂，在此不详细介绍。

使用方法：1、输入字符种数并换行；依次输入各种字符的权重，换行；

2、依上述顺序输入各种字符，换行；

3、屏幕上自动打印出所编排好的每种字符的编码，需用户手动换行，并输入要进行翻译的字符串，以#结束并换行；

4、屏幕自动打印出所转换而来的编码串；

若要继续进行编码串到字符串的转换，则

5、换行，并输入所要进行转换得编码串，以#结束并换行）

上述程序融入了较多的数学逻辑思维方式以及数学方法，故可以完成的任务也更加复杂，有一定的应用价值。程序中不难看到许多个子模块，这正是为了帮助设计者进行结构化程序设计。

计算机技术的发展让数学科学变得更加实用，计算机出现之前，很多现实问题所要求的计算难以被解决，有了计算机，数值计算不再是障碍，只要问题能被描述成数学模型，就能通过计算机进行求解。

实际上，单纯就数学计算而言，现代的微型计算器已经可以解决从小学到大学的几乎所有运算问题。这种进步能减少从事数学学习和研究的人们花费在数值计算上的时间和精力，使他们有更多的时间进行数学推理和数学证明过程，促进数学科学的发展。

但是，这里再提到一点：计算机的“穷举法”只限于在有限的数据量中进行，当把范围扩大到全体自然数（或实数）并要求进行证明时，计算机也无能为力。不过，不管怎样，计算机还是能够给人们提供一些思路或规律，帮助人们解答遇到的难题。

3、计算机技术推动数学机器证明的发展
计算机对数学科学发展的另一个重要贡献在于自动推理，这个在科学史上曾经被众多数学家研究、猜想、苦苦思索的研究方向，由于计算机技术的发展和数学家的不懈努力，已经取得重大突破。其中，关于几何定理的机器证明的研究，属于数学机械化领域的研究范畴。比如：著名的四色猜想就是用计算机成功证明的。我国著名数学家吴文俊教授在此领域也进行了创造性的突破，为该研究领域的发展带来勃勃生机。数学机械化的实质就是利用计算机程序证明数学问题，这不仅需要计算机软硬件技术的支持，还需要建立适当的数学理论来适应计算机运算模式。这个过程，又为数学科学提出了更高的发展要求。   

总  结
 

总结上面的论述，其中数学是计算机的基础重点表现在以下几个方面：

许多计算机研究者都是从数学家中脱颖而出；

数学思想在计算机中的应用——具体实例：“二进制”思想；

数学原理、方法及思维方式的应用——具体实例：程序。

而计算机对于数学的推动在于：

计算机的高速运算能力以及大量数据范围；

程序的帮助及数学定理机器证明。

数学理论以及数学思维方式在现代计算机科技中的应用举足轻重，无论是计算机工作原理的设计还是计算机系统与软件的不断完善都与数学家的贡献密不可分。没有数学作为基础，就不会有现代的计算机技术。建立在数学原理之上的计算机技术又反过来促进了数学科学本身的发展，数学也得到了更多的应用。现在，科学家们正在努力研究供理论研究和定理证明使用的F.P.语言。随着数学理论的不断进步，计算机的技术也会不断更新，两者的结合也会更加密切。

国内外对比中看中国的误区

可能我天生就是要注定学Computer的，因为从小学到现在，只有两堂课是可以的——数学，英语。我那股凡事都要问个为什么的牛脾气，更在学数学中体现得淋漓尽致。整天地查书，追问着同学，老师每一条算式，定理的推算和证明，直到最后得知那是一条公理，才心有不甘地停止了穷追猛打，甚至还想弄一些鬼点子来推翻公理。以至同学、老师一见到我就觉得烦。可惜我学艺不精，小中大学都被选拔参加过不少数学竞赛，却没有拿过一次理想的成绩。我那牛脾气也延续都到写program中，几乎什么都喜欢自己implementation。所以我不太喜欢VB，DELPHI，CBC，什么都用别人的Component。觉得有一种压抑感，由于是从SDK学起的，所以Windows的机理也比较清晰，以前还打算把MFC source codes改写成为自己的classes，可惜MFC实在庞大，而且还在不断updated,以我一个人的能力完成了约1/3，已经筋疲力尽了。以前在国内一直梦想着能到Symantec 这样的公司做developer，因为很想弄清楚为什么Norton能把Windows control 起来。

以前总觉得国外的programmer很厉害，若不是的话，为什么能开发出这么多改变人类生活Software，但出来见识过了，才知道在技术上，他们也不过如此，反而觉得国内的高手还多一些。也许这与教育制度有关，国内普遍都认为只要数学学好了，计算机也就没问题了，君不见国产的教科书都是以那些枯燥的数学问题来教导初学者。诚然，数学思维对写code有莫大的帮助，我也是受益者，所以中国人写程序在同等外界条件下（硬件，资料等）绝对比鬼佬强。但同时也带来了严重的错误观念——“编程研究到一定程度，归根结底是数学问题”。 刚出来的时候，我也是这样认为。

我哥也是Master of Computer Science出身，由于他自己的努力，还没到30岁，已经在3com总部担任Project manager了。他以前在silicon valley 多间公司做过，包括Symantec。兄弟俩经常就computer的问题进行讨论，他为了我能尽快适应silicon valley的文化，不断把不少经验告诉我，使我收益非浅。发现其实是观念上的不同。这里认为“编程研究到一定程度，归根结底是管理和人类发展的问题”。

一、管理问题: 其实写code在一个software product生产过程中只占一小部分，关键在于如何使product占有market和有效管理整个pro- duct的开发过程。这学期在Project Management Course学习中，有两点很有感受。

(1) At some point in the development, Better becomes the enemy of Good. 

(2) Engineers are very good at taking more time and sp- ending  more money to make "better" than what the customer  ever wanted or has the time or money to pay for. 

(3)一群水平一般的Engineers + 一个优秀，经验丰富的Manager >> 一群拔尖的Engineers。

而中国恰好在管理上缺乏优秀人才，制度和观念更是与silicon valley 的不能同日而语。因此，尽管国内优秀的programmer相当多，但是只是一盘散沙，白白浪费掉。可叹的是有不少国人还白日做梦地期盼着中关村能取代硅谷。若制度和观念不改变的话，即使把全国最优秀的程序员聚积在中关村，也别想追上硅谷。另一个典型的例子，Linux 如今高唱入云，而且聚积了世界上许多优秀程序员的成果，但是若它的开发和维护仍停留在以个人或小群体的基础上，没有系统性，规范化。即使它的性能比Windows 要好许多，也只能成为那些发烧友桌上的宠物，永远不能登大雅之堂！如今不少大公司加入其中，对它开发和维护的管理有很大帮助，才有可能向Microsoft叫板！

二、人类发展从计算机技术的发展历史来看，计算机最终解决的是人类发展问题，而不是数学问题。很简单的例子就是，Programming Language的发展，asm-> c-> c++-> java-> CORBA（注意：CORBA不是一种语言）

可以看到这样的发展，主要是为了方便一个Software，一个Pro-duct 的更有效的开发和应用。简单地说，c使程序员摆脱了机器语言的苦涩，c++(也可以说Object-oriented Languages)使产品的组成、开发、维护更符合人类的思维方式，java在Internet流行的这个年代，顺理成章地成为了宠儿，CORBA更是进了一大步，承诺Language-inde-pendence,  Platform-independence,  Location-independence。已经是相当成熟的Distributed Object Computing。看了许多CORBA 的书，颇有感叹，CORBA应该说是人类思维的发展的一个体现。同时，为中国计算机的研究无奈！这里的研究可以说是以人为本，为的是在整体上运用计算机促进人类发展，而国内的研究更多的是在于算法等局部，微观的研究，这方面虽然是必要，但在观念上可以看得出人家已经高一个层次了。不夸张地说，silicon valley，它有自己独特的文化，在这里，不但可以看到到计算机技术的飞速发展，同时也从中感受到人类思维的发展。这也是为什么要独立开办一个Computer science  department的缘故。毕竟，数学与计算机有紧密联系，但同时也有许多本质的不同。

以上是我出国后感觉到的不同，归根到底就是两个字：“观念”。这也是我一家之言，盼能与大伙讨论一下，为中国的计算机发展出一分绵力。

数学人努力的方向

　　想想自己以前的迷茫和看过的那些书，的确想拿出来分享。就慢慢写慢慢加吧 :)
　  (我为什么推荐了这么多英文书？ 1, 原版比翻译的好；2,这些英文都不难; 3, 如果你想出国，看完这些书，可以不背红宝，因为你连这些词的用法都记得)

  计算机程序设计艺术 / Art of Computer Programming, Volume 1-3

（美）Donald E.Knuth / 2002-09-01 / 国防工业出版社 / 第1卷 基本算法（第3版） / 98.0 / 精装 / 苏运霖

TAOCP（The Art of Computer Programming的简写）第一卷是学数学的人走向计算机的捷径(s数学学不好的不建议看)
 

 

  具体数学：计算机科学基础（英文版.第2版） / Concrete Mathematics A Foundation for Computer Science(Second Edition)

Ronald Graham / Donald Knuth / Oren Patashnik / 2002-08-01 / 机械工业出版社 / 49.0 / 平装

CM与TAOCP是一体的， 同时看可以相得益彰，而且对数学水平大有好处
 

 

  设计模式：可复用面向对象软件的基础（英文版） / Design Patterns Elements of Reusable Object-Oriented Software

（美）伽玛 / 2003-1-1 / 机械工业出版社 / 38.0 / 平装

很多学数学的人往往认为软件就是民工活，看看这个对于自己的设计和对软件的理解豆油帮助
 

 

  TeXbook

Donald E. Knuth / 1984-01-01 / Addison-Wesley Professional / $44.99 / Spiral-bound

这个书是为了你排版毕业论文准备的，这也会让你喜欢上Knuth这个人和他的幽默
 

 

  人工智能：英文 / Artificial Intelligence A New Synthesis

（美）尼尔松 / 1999-9-1 / 机械工业出版社 / 38.0 / 平装

AI是数学和计算机结合的一个美妙领域，现在一切的工作，从垃圾邮件过滤到豆瓣推荐，都是AI. 看完了这本书，你就不会后悔你学的那些实变函数和数理统计
 

 

  The Art of UNIX Programming / The Art of UNIX Programming

Eric S. Raymond / 17 September, 2003 / Addison-Wesley Professional / $39.99 / Paperback

很多学计算机的人认为windows用的好就是高手了，实际上学习计算机的“捷径”是*NIX系统。绝对是捷径，因为一个系统让你从编程到设计，从理论到应用都变成大师级别。不会类UNIX系统的人都不能算真正的计算机科学家
 

 

本文来自CSDN博客，转载请标明出处：http://blog.csdn.net/sdfgh2046/archive/2009/06/12/4264745.aspx