計算機程序設計藝術

前言：想要寫出一篇令人眼前一亮的文章嗎？我們特意為您整理了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算法求解。了解了這些知識后，學生在把問題抽象成特定的算法模型時，就可以正確地使用合適的算法了。其他問題包括使用矩陣胚理論來證明貪心算法的正確性以及靈活應用動態規劃來求解離散結構上的最優化問題等等。