浅谈数学与计算机的关系

2022-09-10

现如今数学和计算机科学的关系有点奇怪。20, 30年以前, 计算机科学基本上还是数学的一个分支, 而现在, 计算机科学拥有广泛的研究领域和众多的研究人员, 在很多方面反过来很好的推动了数学发展, 从某种意义上可以说是孩子长得比妈妈还高了。但不管怎么样, 这个孩子身上始终流着母亲的血液, 这血液是the mathematical underpinning of computer science (计算机科学的数学基础) , ——也就是理论计算机科学。

现代计算机科学和数学的另一个交叉是计算数学/数值分析/科学计算, 随着计算机科学的出现, 一些以前不太受到重视的数学分支突然重要起来。人们发现, 这些分支处理的数学对象与传统的分析有明显的区别:分析研究的对象是连续的, 因而微分, 积分成为基本的运算;而这些分支研究的对象是离散的, 因而很少有机会进行此类的计算, 人们从而称这些分支为“离散数学”。“离散数学”的名字越来越响亮, 最后导致以分析为中心的传统数学分支被相对称为“连续数学”。

我们知道, 学计算机的, 其数学修养很重要, 计算机专业课程中最难的几门课程莫过于离散数学、编译原理、数据结构等, 很多自认为数据库学得很好的学生在范式、函数依赖、传递依赖等数学性比较强的概念面前感到力不从心, 这些都是因为数学基础或者说数学知识的缺乏所造成的。

数学是计算机的基础, 这也是为什么考计算机专业研究生数学都采用最难试题 (数学一) 的原因。许多天才程序员本身就是数学尖子, 很多数学基础很好的人, 一旦熟悉了某种计算机语言, 他可以很快地理解一些算法的精髓, 使之能够运用自如, 并可能写出时间与空间复杂度都有明显改善的算法。

因此计算机科学作为数学的一个分支, 其内容其实是很多数学知识的融合, 软件工程需要图论, 密码学需要数论, 软件测试需要组合数学, 计算机程序的编制更需要很多的数学知识, 如集合论、排队论、离散数学、统计学, 当然还有微积分。

1 数学在编程中的应用

首先我们来看一个使用数学方法可以大大提高效率的例子。

实例一:给定一个自然数a, 判断它是不是质数。

普通的想法:若a是合数, 那么必然有一个因数不大于a1/2, 建立一个a1/2以内的质数表, 逐一检索。显然, 这样速度太慢!

下面介绍一种基于费马小定理的Miller-Rabin测试算法:

首先是引理:费马小定理, 相信大家都有耳闻, 这里我也不嫌累赘, 仍旧列出。

若n是质数, (a, n) =1, 则an-1mod n=1。

同样, 若我们选取若干个a, 都满足以上等式的话, 几乎可以肯定n是素数。 (尽管不能完全确认, 但在实际操作中是可行的)

下面给出算法:

事实上, 数学在计算机当中最为重要的还是递推关系的应用:许多看似棘手的题目, 在有了这一层的关系后便显得柳暗花明了。

实例二:方格取数。

在一个n*m的方格中, m为奇数, 放置有n*m个数, 方格中间的下方有一人, 此人可按照正前方相临的五个方向 (方格) 前进但不能越出方格。人每走过一个方格必须取此方格中的数。要求找到一条从底到顶的路径, 使其数相加之和为最大。输出和的最大值。

解:这题在本质上类似于递推, 是从一个点可以到达的点计算可以到达一个点的所有可能点, 然后从中发掘它们的关系。我们用坐标 (x, y) 唯一确定一个点, 其中 (m, n) 表示图的右上角, 而人的出发点是 ([m/2], 0) , 受人前进方向的限制, 能直接到达点 (x, y) 的点只有 (x+2, y-1) , (x+1, y-1) , (x, y-1) , (x-1, y-1) , (x-2, y-1) 。到达 (x, y) 的路径中和最大的路径必然要从到 (x+2, y-1) , (x+1, y-1) , (x, y-1) , (x-1, y-1) , (x-2, y-1) 的几条路径中产生, 既然要求最优方案, 当然要挑一条和最大的路径。

关系式如下:F (x, y) =Max{F (x+2, y-1) , F (x+1, y-1) , F (x, y-1) , F (x-1, y-1) , F (x-2, y-1) }+Num (x, y) , 其中Num (x, y) 表示 (x, y) 点上的数字。 (边界条件为:F ([m/2], 0) =0, F (x, 0) =-0 (1<=x<=m且x<>[m/2]) ) 。

这种问题, 涉及到最值, 采用的递推手法被称为“动态规划”, 简称DP。程序设计中可采用多种数学方法, 恰如其分的数学方法可以大大减少程序运行的时间和所需空间, 起到优化程序的作用。遇到一道题目时, 如进制运算、多项式运算等, 应不急于马上用递归, 回溯等搜索算法, 特别是测试数据的范围很大的时候。不妨先用笔算, 从中发现一些规律。但是也不是每一道题都可以用数学方法完成, 数学方法只能用于一些求总数, 最值之类的题目上。

数学方法的合理运用, 可以给编程带来很大方便, 不仅是在编程方面, 在计算机的其他领域中, 数学也有广泛的应用。

2 数学在计算机图形中的应用

(1) 代数和三角学。

对于计算机图形学的初学者来说, 高中的代数和三角学可能是最重要的数学。日复一日, 我们从简单的方程解出一个或更多的根, 并且时常还要解决类似求一些几何图形边长的简单三角学问题。那么代数和三角学是计算机图形学的最基础的知识。

(2) 线性代数。

线性代数的思想贯穿于计算机图形学。事实上, 只要牵涉到几何数值表示法, 就常常抽象出例如x, y, z坐标之类的数值, 我们称之为矢量, 图形学自始至终离不开矢量和矩阵。用矢量和矩阵来描述旋转, 平移, 或者缩放是再好不过了。高中和大学都有线性代数的课程, 只要想在计算机图形学领域工作, 就应该打下坚实的线性代数基础。

(3) 微积分学。

微积分学是高级计算机图形学的重要成分。如果打算研究图形学, 我强烈建议你应该对微积分学有初步认识, 理由不仅仅是微积分学是一种很有用的工具, 还有许多研究员用微积分学的术语来描述他们的问题和解决办法。另外, 在许多重要的数学领域, 微积分学被作为进一步学习的前提。

(4) 微分几何学。

微分几何学研究支配光滑曲线, 曲面的方程组。如果你要计算出经过某个远离曲面的点并垂直于曲面的矢量 (法向矢量) 就会用到微分几何学。让一辆汽车以特定速度在曲线上行驶也牵涉到微分几何学。有一种通用的绘制光滑曲面的图形学技术, 叫做“凹凸帖图”, 这个技术用到了微分几何学。如果要着手于用曲线和曲面来创造形体 (在图形学里称之为建模) 你至少应该学习微分几何学的基础。

(5) 矩阵方程组。

计算机图形学的许多问题要用到矩阵方程组的数值解法。一些涉及矩阵的问题包括:找出最好的位置与方向以使对象们互相匹配 (一个最小二乘法的例子) , 创建一个覆盖所给点集的曲面, 并使皱折程度最小 (薄板样条算法) , 还有材质模拟, 例如水和衣服等。在图形学里矩阵表述相当流行因此在用于图形学的数学中我对矩阵方程组的评价是很高的。

(6) 概率论与统计学。

计算机图形学的许多领域都要用到概率论与统计学。当研究员涉及人类学科时他们当然需要统计学来分析数据, 图形学相关领域涉及人类学科, 例如虚拟现实和人机交互 (HCI) 。另外, 许多用计算机描绘真实世界的问题牵涉到各种未知事件的概率。两个例子:一棵成长期的树, 它的树枝分杈的概率;虚拟的动物如何决定它的行走路线。最后, 一些解高难度方程组的技巧用了随机数来估计他们的解。以上仅是部分一些在计算机图形学里使用概率论和统计学的方法。

数学方法的合理运用, 可以使计算机学习带来很多方便.越来越多的计算机程序需要应用数学推导、归纳, 因此想要学习好计算机, 就必须学习好数学这门基础课程。