计算机程序设计艺术

前言：想要写出一篇令人眼前一亮的文章吗？我们特意为您整理了5篇计算机程序设计艺术范文，相信会为您的写作带来帮助，发现更多的写作思路和灵感。

计算机程序设计艺术范文第1篇

关键词：算法；程序结构；循环；递归

中图分类号：TP391文献标识码：B

文章编号：1672-5913(2007)12-0083-05

1问题的提出

结构化程序设计中，只有三种基本的结构：顺序、选择和循环。

顺序结构是程序设计过程中自然形成的，也是三种结构中最简单的一种。选择结构与我们日常中使用的自然语言“如果...则...否则...”十分相近，只是其嵌套时的二义性在形式上必须有一个明确的规定。

而循环结构是三者中最为复杂的，也是使用最多的。一个算法往往要用循环结构来描述，一个程序能否正确编写又往往取决于对循环结构的正确理解和使用。因此，有必要深入对循环结构做一个分析。本文从循环结构的三个要素、循环结构与程序的阅读、循环与递归的联系等三个方面进行分析与论述，而这些在目前的教学中往往很少提到，甚至是被忽略的。

2循环结构的三要素

初学程序设计的人，对于如何在程序中使用循环结构实现算法，总觉得不知从何入手，有时即使编出程序，也不尽人意。下面我们从一个简单的典型实例说起。为了说明问题，本文对有关编程的问题都以C语言函数的方式列出解答。

2.1一个典型实例及其两种解答

例2.1鸡兔同笼，有h个头，f只脚，求鸡兔各多少。这是我国古代一个典型的算术问题。现在要设计一个函数，求出兔子的数目(求出兔子的数目，自然就可以得到鸡的数目)。不妨设这个函数为：

int hab(int h, int f);

函数的定义如下：

int rabbit (int h, int f)// h为头数, f为脚数

{

int i;

i=h;

while (i＞=0 )

{

if (i*4+(h-i)*2==f) break;

i--;

}

return i; //-1表示该该问题无解。

}

这个程序的运行结果是正确的，但是很遗憾，这并不是一个完美的程序，尽管很多教科书也是这样写的。我们再来看看下面的另一种解法：

int rabbit (int h, int f)// h为头数, f为脚数

{

int i;

i=h

while((i＞=0)&& (i*4+(h-i)*2!=f ))

i--;

return i;//-1表示该问题无解。

}

以上两个程序都用到循环结构，第一个程序在循环结构中嵌套了一个选择结构，并且使用了break语句。而在第二个程序中，无需这样做。无论从程序的结构，还是从程序的可读性来说，后者显得比前者要好得多。那么问题出在哪里呢？

2.2深入分析

比较两个程序可以发现，关键是对条件表达式(i*4+(h-i)*2!=l)的运用。前者把条件表达式放在循环体中，后者把它作为循环条件。看来，有必要对循环结构做深入的分析。

不管一个循环结构有多复杂，都可以从以下三个方面来分析：

1) 初始状态：所有参与循环的变量在循环之前都必须有一个确定的值。

2) 循环条件：当条件满足时，循环继续，否则循环终止。循环条件应是一个逻辑表达式。

3) 循环体：每次循环要执行的语句。

这就是我们所讲的循环结构三要素。从这个角度再来分析上面的例子，就很容易找到问题的结症：(i*4+(h-i)*2!=l)是循环条件之一，因此不应放在循环体内使用。第一种方法虽然也能得到正确的结果，但并不是好的方法，甚至是不正确的方法。

2.3一个应用实例

例2.2 裴波那契序列数的递归表示如下：

f0=0

f1=1

fn=fn-2+fn-1(n＞=2)

对于任意给定的正整数x，判别其是否在裴波那契序列中。

现在要求判别一个给定的正整数x是否在裴波那契序列中，一个直观的判别方法是从f0和f1出发，不停地求后面的裴波那契序列数。每得到一个裴波那契序列数，就同这个待判别数进行比较，直到相等时输出“真”。或当得到一个裴波那契序列数大于这个待判别数时，输出“假”。

要实现这个算法，需用到循环结构。我们来分析一下这个循环结构的三个要素：

(1) 初始状态：f0=0; f1=1，x=?；

(2) 循环条件：当前求得的裴波那契序列数 < 待判别数x；

(3) 循环体：计算一个新的裴波那契序列数。

根据以上的分析，判别一个给定的正整数x是否在求裴波那契序列中的C函数如下：

int in_fib(int x)

{

int f0=0, f1=1;

while (f1＜x)

{

t=f1+f0;

f0=f1;

f1=t;

}

return (x==f1|| x==f0);

}

3循环结构与程序的阅读

3.1阅读的意义

对于计算机程序的阅读，著名的计算机科学家克努特曾说过：阅读他人的计算机程序获得技巧是极其重要的，但在许许多多的计算机课程中这样一种训练却可悲地被忽视了，因此导致计算机极其低效率的使用。

学习一种计算机程序设计语言，不管是汇编语言还是高级语言，一个重要而又常用的方法就是阅读：阅读书中的例题，阅读别人写的程序，更多的是阅读自已写的程序。在某种意义上来说，一个程序是“被阅读”的。首先是被计算机阅读，这是毫无疑义的，但更多时候是被人阅读。

3.2阅读的方法

阅读的目的是为了分析程序中的语句是如何实现算法的。对于一些较为复杂的程序，如果一开始就去分析每一个语句的功能，就很容易掉进“迷宫”。因此在分析一个程序时应该先分析程序的结构，然后再对每个结构中的语句逐一进行跟踪阅读。

1. 程序结构的分析

程序结构的分析过程分为两个步骤：第一是找出组成程序的各种结构，第二是找出这些结构之间的连接方式。

程序结构的分析应符合结构化程序设计的原则。一种结构化程序设计语言(如C语言，Pascal)，只包含三种基本结构：顺序、选择和循环。每种结构只有一个入口和一个出口。而各个结构之间的连接方式有两种：积木式和嵌套式。积木式的连接是一个结构的出口与另一个结构的入口的连接，而嵌套式的连接是在一个结构的内部嵌套另一个结构。一般来说，我们应先分析出程序中积木式连接的各个结构，然后再找出这些结构中的嵌套式连接的结构。分析程序结构时可以借用一些工具，如N-S图、伪代码等，即根据源程序画出能反映程序结构的N-S图或写出等效的伪代码。这是一个与编程过程刚好相反的过程。

2. 语句的跟踪阅读

对于顺序结构的语句，阅读是不成问题的。而对于选择结构的语句，由于与我们平时所用的自然语言比较一致，也不是太大的困难。关键在于，当有两个选择结构连接时，采用积木式的连接与采用嵌套式连接的差别是很大，有时甚至使得程序运行的结果截然相反。

循环结构是三种结构中最为复杂的一种，对这种结构的跟踪阅读可以用列表的方法，将循环过程中各语句执行的结果一一列出。这个表包含了循环结构的三个要素。

我们还是从著名的欧几里德算法说起。

例3.1求两个正整数的最大公约数。

【欧几里德算法】

E1.[求余数] 以n除m并令r为所得余数(0＜=r＜n)。

E2.[余数为0?] 若r=0, 算法结束, n即为答案。

E3.[互换] 置mn, nr, 并返回步骤E1。

为了使计算过程更为紧凑，也考虑到当n=0时，算法仍然有效，可将以上算法稍作改动如下：

E'1.[n为0?] 若n=0, 算法结束, m即为答案。

E'2.[求余数] 以n除m并令r为所得余数(0＜=n＜n)。

E'3.[互换] 置mn, nr, 并返回步骤E'1。

根据以上所描述的算法，我们可以用C语言写出相应的函数：

int gcd(int m,int n)

{

int r;

while (n!=0)

{

r=m%n;

m=n;

n=r;

}

return m;

}

我们通过一组真实的数据(例如：m=20, n=12)分析循环结构的执行过程，即对循环体内的语句逐一进行跟踪阅读，直至循环条件不成立。分析程序执行的过程如下：

阅读的过程是艰苦的，初学者对此可能不十分习惯。但是这是学习一种计算机程序设计语言所必须掌握的方法，也是必须经历的过程。企图绕开这个过程，寻找别的捷径是不可能的。

4循环与递归

递归是计算科学中一个很重要的核心概念，它出现在计算科学的各门分支学科中，如计算理论基础、数据结构、程序设计方法、程序设计语言等等。那么，递归与循环有什么联系和区别呢？

在关于循环结构三要素中，我们说循环结构中的第一个要素是循环的初始状态，那么每循环一次，参与循环的变量中至少有一个会发生变化(否则就会出现“死循环”)。因此，循环的过程就是从一种状态转移到另一种状态，在经历了若干个状态之后，到达终结状态，循环就结束。因此可以把一个循环结构看成是一个有穷状态机。在计算理论上，有穷状态机能计算的问题，图灵机必能计算，而图灵机与递归函数是等价的。从这个意义上讲，一个可以用循环结构解决的问题必然也可以用递归方法来解决。对现在一般在大学一、二年级学习程序设计的学生来说，还不可能深入讨论这个问题。但我们可以用一些典型的实例，通过循环与递归的对比，使得低年级的学生们对递归有一个初步的认识。

4.1递归的意义与递归函数

我们来看一个简单的例子。

例4.1求一个正整数n的阶乘。

根据正整数阶乘的定义n！＝1×2×3×......×n，用一个循环结构即可很容易编写出计算阶乘的程序。如果用一个函数f(n)来表示n的阶乘，也可以这样来定义f(n)：

1 n=0

f(n)={

n・f(n-1)n＞0

在定义f(n)时又用到f这个函数，这就是递归。注意，在定义式中用到函数f，但它的自变量是n-1，计算n-1的阶乘要比计算n的阶乘容易一些。而且当n=0时，可以直接得到答案f(0)=1。

例4.2求两个正整数的最小公倍数。

欧几里德算法(见例3.1)与以下的递归函数是等价的：

m n=0

gcd(m,n)= {

gcd(n,m%n)n＞0

在这里，当n>0时，计算的是n和m%n的最小公倍数。显然，这时的两个正整数要比原来的两个正整数(m, n)要小，计算也变得容易一些。

通过以上的例子，我们可以这样来理解递归的意义：把一个复杂的、规模较大的问题转化为简单的、规模较小的同一个问题，直至可以直接得到问题的解。

4.2用递归函数取代循环结构

一个程序如果可以用循环结构来实现，那么也可以用一个递归函数来实现。我们先来看一个简单的例子。

例4.3求一个有n个元素的数组中的最大元素。

用循环结构的方法如下：

int max(int a[])

{

int i, m;

m=a[0]

for (i=1; i＜10,i++)

if(max＜a[i])m=a[i];

return m;

}

用递归函数。设一递归函数max(a,k)是求a数组中第k个元素及其后所有元素的最大者：

a[k]k=n-1;

max(a,k)= {

a[k]＞max(a,k+1)?a[k]：max(a,k+1) k＜n-1

用C语言编写的函数如下：

int max(int a[], int k, int n)

{ int m;

if (k==n-1)return ( a[k] )

else {m=max(a,k+1);

return ( a[k]＞m?a[k]：m ); }

}

这是一个简单的例子，下面再看一个较为复杂性的例子。

例4.4用递归函数求解例2.1。

用递归函数来求解例2.1，应如何考虑呢？正如以上所说，递归的意义是把一个复杂的、规模较大的问题转化为简单的、规模较小的同一个问题，直至可以直接得到问题的解。因此我们可以这样来考虑：把笼中的一只鸡抓走，笼中的兔子的数目是不变的，显然这仍然是鸡兔同笼的问题，但少了一只鸡，问题就变得简单了一点。当所有的鸡都被抓走时，剩下的都是兔，这时就可以直接得到答案――腿数除以头数就是兔子的数目。

我们用robb(h,g)这样一个函数表示求兔子的数目，参数h、g分别表示头数和腿数，因此有：

robb(x,y)=robb(x-1,y-2)

但在什么情况下能直接得到结果呢？显然，当鸡全部抓走只留下兔子时，就可以直接得到答案，这时腿数应是头的4倍：

roob(x,y)=x当4*x=y

另外还要考虑在什么情况下问题没有解。显然，当4*h＜g时，这个问题无解。

x

4*x=y

robb(x,y)={ robb(x-1,y-2)　4*x＞y

-1

4*x＜y(-1表示问题无解)

在求得兔子的数目之后，只要用总数减去兔子的数目，就能求出鸡的数目。

结束语

程序设计作为一门学科，经历了子程序、高级语言、结构化程序设计三个里程碑[2]。近十几年兴起的面向对象程序设计可以说是第四个里程碑。程序设计在计算科学这门年轻的学科中，是一门“古老”的分支学科，又是一门久经不衰的学科。计算科学中的许多新思想、新方法、新技术都首先体现在程序设计上。这种现象使我们不得不领悟到，这门课程中的许多知识反映了计算科学深刻的内涵，程序设计的教学应体现这一点。例如上述的循环结构，就很值得我们去探讨。本文提出的一些观点，确实很肤浅，希望能起到一个抛砖引玉的作用。

参考文献：

[1] 苏运霖译. 计算机程序设计艺术 第1卷 基本算法［M］. 北京：国防工业出版社，2002.

[2] 王选. 王选文集［M］.北京大学出版社，1997.

[3] 赵致琢. 计算科学导论(第二版)［M］. 北京：科学出版社，1998.

收稿日期：2006-5-27

通信地址：广东省广州市 华南师范大学计算机学院， 510631

计算机程序设计艺术范文第2篇

关键词:算法;复杂认知技能;4C/ID

尼克劳斯•威茨,结构化程序设计的首创者和图灵奖获得者,提出了一个著名论断:程序=算法+数据结构。这说明了算法的重要地位。什么是算法?算法和程序设计技术的先驱者高德纳把算法比喻成菜谱。他认为“算法是一组有穷的规则,这些规则给出求解特定类型问题的运算序列”,他强调“我们不仅要算法,而且还要在某种不明确定义的意义下的好算法”[1]――算法分析。《高等学校计算机科学与技术专业实践教学体系与规范》把算法设计与分析能力界定为计算机专业高级人才的基本学科能力之一[2]。可见,“算法设计与分析”课程的重要性。然而,学生普遍觉得该课程难学。为了解决这个问题,应用四要素教学设计模型(以下简称4C/ID)进行教学改革。4C/ID是提高复杂认知技能的方法,在国外,4C/ID的研究已有30年的历史,曾经成功地将4C/ID应用与计算机编程。在国内,4C/ID的研究还处于起步阶段。本文主要研究了4C/ID在“算法设计与分析”课程教学中的实践。

1课程教学中存在的问题

1.1学生学习有畏难情绪

算法是问题的程序化解决方案[3]。首先,要理解问题,确定问题的条件和应用范围。然后,建立数学模型。最后,证明算法的正确性和分析算法的效率。这需要微积分、线性代数、离散数学等数学知识。所以,对于这门复杂、抽象的课程,学生自然感到难学。

1.2算法实现有难度

算法实现指编制与调试算法。算法实现有助于加深对算法的理解,是不可缺少的环节。算法的实现取决于:(1)丰富的程序设计语言和数据结构实践经验。如学生在程序调试时经常出的错是缺少函数声明;在进行“分支限界”实训时,很多学生由于没有掌握队列而无法实现装载问题算法。这是程序设计语言和数据结构基础不扎实造成的。过多的出错会严重影响上机实践的质量,造成学生不愿动手。(2)对算法的理解。算法通常是由伪代码来描述的,如果不理解算法,很难准确地将算法转换成可以运行的程序。如果这两个问题不能很好地解决,算法设计与分析能力的培养就成为一句空话。

2 “4C/ID”是解决问题的途径

算法设计与分析是复杂的认知技能,其构成见图1。复杂的认知技能是由一系列的技能所构成,其中一部分构成技能体现为自动的处理过程,其它多数的构成技能涉及认知的领域[4]。从图1可以看出,这是一个复杂的学习过程。如果从头到尾地讲解给学生听,然后再让学生上机实践,这就不能了解学生哪些技能掌握了,哪些没有掌握,从而影响了上机实践的质量。而且,直线式讲解不符合问题求解的规律,有些过程需要反复实践,有些过程需要思考和补充相关信息。4C/ID是面向复杂认知技能培训的教学设计模型,由约伦•范麦里恩伯尔基于学习和信息加工的认知心理学理论创造。该模型之所以能提高复杂认知技能的原因是它将复杂认知技能分成再用性构成技能和非再用性构成技能,并对它们分别进行实际练习设计和信息呈现设计。再用性构成技能是指在不同问题情境中以极为类似的方式而操作的技能,非再用性构成技能是指在不同的问题情境中进行不同操作的技能[5]。再用性构成技能的熟练掌握可以解决问题中熟悉的方面,非再用性构成技能通过图式建构可以运用于问题情境中新的、不熟悉的方面。两者相互促进,能提高解决问题的整体水平。所以,将4C/ID应用于“算法设计与分析”教学中会比传统的教学方法更能提高算法设计与分析的能力。

3 “4C/ID”的教学实践

4C/ID分成教学分析和教学设计两个部分。这两个部分又各分成两层,共4层。它们是:(1)原理性技能的分解;(2)构成技能及相关知识的分析;(3)教学方法的选择;(4)训练策略的合成。

3.1原理性技能的分解

4C/ID的第一步是将复杂认知技能分成不同类型的构成技能。分解的过程依据一定的原则,因此称为“原理性”分解。原理性技能的分解遵循以下的原则:(1)识别。识别组成复杂认知技能的构成技能,产生一个技能分层结构。这个分层结构包含了确定的构成技能及它们之间的关系。(2)描述。清晰描述每个构成技能。(3)分类。将构成技能分成用于培训和不用于培训的技能。对于用于培训的构成技能将进一步分成再用性构成技能和非再用性构成技能。(4)排序。将被选择用于培训的构成技能排序。这里重点讲一下如何区别再用性构成技能和非再用性构成技能。它们的区别主要反映在执行时表现不同。再用性构成技能的表现特征为:(1)执行很快;(2)显示错误很少或没有;(3)能和其他构成技能同时执行;(4)只能在特定的问题情境中产生上述特点,不易迁移到新的、不熟悉的情境中。再用性构成技能的执行过程可以被制定成一套执行程序,只要配以必备的知识,总能成功的执行。非再用性构成技能的表现特点:(1)执行缓慢;(2)执行过程容易出错;(3)不适合与其他的非再用性构成技能同时执行。如,深度优先搜索算法就是再用性构成技能,在求解动态规划问题时分析最优子结构是非再用性构成技能。

3.2构成技能及相关知识的分析

构成技能的分析方法有程序分析法和基于规则的分析法。程序分析法用于可以观察的、具有先后执行顺序的再用性构成技能,基于规则的分析法用于不可观察的、不具有明显先后执行顺序的非再用性构成技能。

3.2.1再用性构成技能

深度优先搜索可以表示成固定的“算法”,如图2。再用性构成技能的成功执行往往需要必备知识。必备知识包括事实、概念、原则等,见图2中的注释。

3.2.2非再用性构成技能

非再用性构成技能的执行过程不能表示成固定的“程序”,它的执行依赖于支撑性知识和策略性知识。其实,非再用性构成技能的分析就是对支撑性知识和策略性知识的分析。支撑性知识的分析涉及到复杂的认知图式。复杂的认知图式由不同的、有相互关系的认知单元所组成,这些认知单元可以是陈述、概念、原理等。支撑性知识的分析是建立在对关系分析的基础上,再从相关的关系中找出所有有用的认知单元。主要的关系包括种类关系、部分关系、方位关系、原因―结果关系、相似关系。确定关系和认知单元后,用概念模型、目标―方案层次结构、原理功能模型、心智模型组织和显示认知单元及它们之间的关系。策略性知识的分析主要采用解决问题的系统方法。该方法的目的是要建立一个描述解决问题的模型。为了建立这个模型,让专家和教师解决他们领域内和该问题相似的经典问题,并且要求他们在思考问题的同时把思路讲出来,这些话便被整理成描述解决问题的模型。如,在求解动态规划问题时可以选择矩阵链相乘、求最长公共子序列、最优二叉搜索树、装配线调度等例子,通过分析经典教材来建立描述解决问题的模型。

3.3教学方法选择和训练策略合成

教学方法通过现则支持再用性、非再用性构成技能获得的实际练习设计和信息呈现设计。学习者通过反复训练都能掌握再用性构成技能,相应的信息呈现可以采用分割、示范和搭建脚手架的方法。分割的作用是避免认知负荷,在同一时间内仅提供直接的、可利用的信息。专家示范可以形象地说明规则和程序的运作。搭建脚手架就像帮助系统一样,能因人而异地

提供及时的、直接有效的信息。非再用性构成技能的获得取决于图式建构。图式建构是指把低水平的图式整合到高水平图式中,逐渐形成更加复杂的图式。复杂的图式有助于非再用性构成技能的获得。图式建构取决于归纳的程度。归纳的作用为:(1)创建新的图式;(2)调整已有图式,使之适合更广泛的事件。相应的信息呈现方式必须能为归纳所用。因此,必须要对知识精制化。精制化是指将新的知识整合到记忆中已有的认知结构。这个过程通过类比来实现。

复杂认知技能的获得是建立在整体任务实践的基础上。因此,训练策略的合成是形成复杂认知技能的关键。这个过程必须遵循以下原则:(1)在实践开始阶段,为再用性和非再用性构成技能提供需要的必备知识和支撑知识;(2)随着专长的提高,相应地减少知识的呈现,直至学习者能够独立地、在不需要帮助的情况下面对真实的问题。这时,学习者获得了复杂认知技能。

4结论

经过实践检验,4C/ID能有效提高复杂认知技能。应用4C/ID于“算法设计与分析”课程,效果体现在两方面:(1)解决问题的能力提高了。以前,答题是把算法从头到尾背过来的,算法常有缺漏或搞乱算法语句顺序。现在,答题内容以实践的经验体会居多,答对率提高了16%。(2)考证通过率提高了。“算法设计与分析”是一门综合性的课程,算法设计与分析能力的提高深化了学生对“程序设计语言”、“数据结构”等课程的学习,考证通过率也增加了。4C/ID不尽人意之处在于要费很多时间去分析。所以,4C/ID一般和教学设计系统一起使用。

参考文献:

[1] DONALD E.KNUTH. 计算机程序设计艺术:基本算法[M]. 苏运霖,译.北京:国防工业出版社,2007.

[2] 教育部高等学校计算机科学与技术教学指导委员会. 高等学校计算机科学与技术专业实践教学体系与规范[M]. 北京:清华大学出版社,2008.

[3] Anany Levitin. 算法设计与分析基础[M]. 潘彦,译. 北京:清华大学出版社,2007.

[4] Jeroen J.G.Van Merrienboer,Paul A. Kirschner.Ten Steps to Complex Learning:A Systematic Approach to Four-component Instructional Design[M]. New Jersey:LAWRENCE ERLBAUM ASSOCIATES,2007.

[5] 罗伯特D.坦尼森,弗兰兹•肖特,诺伯特M.西尔,等. 教学设计的国际观:理论•研究•模型[M]. 任友群,裴新宁,译. 北京:教育科学出版社,2007.

Improve Complex Cognitive Skills on "Algorithms Design and Analysis" Course

LUO Yi-sheng

(Department of Technology Education, Guangdong Polytechnic Normal University, Guangzhou 510630,China)

计算机程序设计艺术范文第3篇

数学在人类文明的发展历史中发挥着重要的作用，推动了重大的科学技术进步。尤其是到了二十世纪中叶以后，数学的理论研究与实际应用之间的时间差已大大缩短。当前，随着计算机应用的普及，信息的数字化和信息通道的大规模联网，依据数学所作的创造设想已经达到可即时试验、即时实施的地步。数学技术一直是一种应用最广泛、最直接、最及时、最富创造力的实用技术。数学为计算机的发明和发展壮大提供了坚实的理论基础。早在1936年，英国数学家图灵(Turing)发表了对计算机具有奠基意义的论文《论可计算数及其在判定问题上的应用》，里面提出了计算的图灵机模型，该模型即为现代计算机模型的原型。为纪念数学家图灵，美国计算机学会于1966年设立了计算机界最负盛名的“图灵”奖，以表彰那些对计算机事业做出重要贡献的个人。数学是所有工科的基础，其中离散数学已经成为计算机科学发展的理论基础。图灵奖的获得者中有不少是学数学或者数学家出身。1974年获奖的DonaldE.Knuth被称为现代计算机之父，之前在加州理工获得数学博士学位，著有经典著作《计算机程序设计艺术》4卷。RichardM.Karp于1985年获奖，之前在哈佛大学获应用数学博士学位。1986获奖的RobertE.Tarjan在斯坦福大学同时获得数学和计算机的博士学位，主要研究图论、算法和数据结构。当前计算机理论及应用的壮大和发展更是离不开近代数学的发展，将计算机与数学的发展分割开来既不合理也不现实，和所有学科一样，计算机领域也有自己的问题，比如什么是可计算的，什么是实际可计算的，这些计算模型本质上是数学的应用。离散结构上的算法研究无疑是计算机科学中的重要领域，研究算法需有扎实的数学功底，就机器学习领域的研究而言，通常要对所处理的数据建立不同的数学模型如分类模型、回归模型和排序模型。一般地，先针对这些问题建立特定的模型，然后采用有效的优化算法来求解这些模型。应用数学如矩阵论、多元统计分析和最优化理论可以为深入地研究机器学习领域提供理论基础。在实际的工作中，会经常看到数学基础好、具有一定数学素养的人解决问题会游刃有余且后劲足，学习新事物和新东西会比较快，会表现出一定的创造性。但是当前大学的课程安排普遍存在对学生的数学学习的掌握程度不是很重视，导致学生对数学课的态度停留在学习时仅了解，一学完就全忘，到用时就迷惑的一知半解状态。教师在教授专业课和专业基础课的过程中，没有引导学生深入地发掘理论背后的数学本质，导致学生对计算机科学理论的理解只能停留在表面，凭机械性记忆而没有彻底理解。鉴于上述数学在计算机的发明发展和实际工作中的重要作用，因此，在计算机教育的过程中，迫切地需要培养学生的数学素养以满足现实工作和学习中解决实际问题的需要。

二、数学素养的培养

《算法设计与分析》是计算机专业的一门重要的专业课，有利于培养学生分析问题和解决问题的能力，为学生学习后续课程打下坚实的基础。下面结合这门课程来谈谈在计算机课程中如何提高学生的数学素养。

(一)结合算法的发明史来讲解算法

深入学习计算机科学需要有良好的数学基础，对于算法的学习更是如此。研究算法的图灵奖获得者中有很多是数学家或者学数学出身，如图论中有很多算法是以前面提到的RobertE.Tarjan的名字命名的，著名的Dijkstra最短路径算法由EdsgerW.Dijkstra发明，而他2000年退休前一直是美国Taxas大学的计算机科学和数学教授。前面提到的DonaldE.Knuth则是字符串匹配算法KMP算法的发明人。给学生讲解算法的发明历史一方面帮助学生了解发明算法的背景和发明过程，激发学生的创新欲望；另一方面让学生认识到数学的重要性和其在该课程所涉及的领域中发挥的重要作用。

(二)结合学生所掌握的数学知识来讲解算法

修读该门课程的对象一般为大学高年级学生，他们之前应该修过其他的数学课程，如高等数学(数学分析)、线性代数和离散数学。通常教师在讲授该课程的过程中会认识到离散数学在其中发挥的作用，会有意识地提及离散数学的知识，但实际上学生学习的高等数学或线性代数的知识对理解该门课程也是有帮助的。下面通过一个例子来说明数学知识对理解算法正确性的重要作用。设计完算法如何证明算法的正确性呢？对于顺序结构和选择结构比较好验证，而对于循环结构就使用循环不变量(LoopInvariant)来证明。而循环不变量的证明实际上借鉴了数学归纳法的思想：循环发生前某个循环不变量为真，循环进行的过程中保持为真，那么循环结束时，该循环不变量仍然为真。因此可以断定：无论循环体循环多少次，该循环不变量总为真。其他的例子，包括：比较算法的时间复杂度时可以引入高等数学中的无穷小量来讲解；计算时间复杂度也会涉及到利用无穷级数的估计等等。

(三)结合数学工具来可视化算法

理论的发明通常是从简单直观的例子中归纳得来的，数学工具可以帮助我们理解和可视化算法。

(四)结合数学抽象思维来帮助学生理解算法

数学的抽象思维可以帮助学生站在更高的角度来看待问题和算法之间的联系。算法通常是针对某一类问题的，而如何对问题进行归类，如何选择合适的算法解决是值得学生去探究的问题。讲解算法时，应该帮助学生抽象出问题的本质，同时注意算法之间的联系与区别。计算点对之间的距离是算法设计中一个经典问题，如果源点单一，可采用Dijkstra最短路径算法，而计算图中任意点之间的最短路径，使用Floyd-Warshall最短路径算法会合适一些，但是如果图上的权重存在负值，那就要用带松弛操作的Bellman-Ford算法求解。了解了这些知识后，学生在把问题抽象成特定的算法模型时，就可以正确地使用合适的算法了。其他问题包括使用矩阵胚理论来证明贪心算法的正确性以及灵活应用动态规划来求解离散结构上的最优化问题等等。