甄鵬華,，于振梅
(山東女子學院 信息技術學院,， 山東 濟南 250300)
摘要：數(shù)字電子計算機是一個離散結構，它只能處理離散的或離散化了的數(shù)量關系,，因此,，無論計算機科學本身，還是與計算機科學及其應用密切相關的現(xiàn)代科學研究領域,，都面臨著如何對離散結構建立相應的數(shù)學模型,，以及如何將已用連續(xù)數(shù)量關系建立起來的數(shù)學模型離散化，從而由計算機加以處理的問題,。實際上,，可以將離散數(shù)學理解為對計算機問題的抽象，離散性可以在算法設計和數(shù)據(jù)結構中體現(xiàn),。計算機中也有其他的問題表現(xiàn)出了離散性,，所以，計算機科學對離散數(shù)學的研究不應太過局限,，這些表現(xiàn)都可以歸結為計算機所采用的二進制,。
關鍵詞：離散數(shù)學；算法設計,；數(shù)據(jù)結構,；離散性；二進制
中圖分類號：TP301文獻標識碼：ADOI： 10.19358/j.issn.16747720.2016.22.005
引用格式：甄鵬華,于振梅. 計算機科學中的算法設計與數(shù)據(jù)結構的離散性［J］.微型機與應用,，2016,35（22）：18-21.
0引言
計算機科學(Computer Science)是一門日新月異的學科,。計算機科學與技術專業(yè)的研究人員時刻站在國際先進科技的前沿，學習新知識,，并向創(chuàng)造新知識而努力,。
但是計算機科學中亦有許多基礎科學中的理論支持，其與計算機的實際相結合,，構成了計算機科學中最基礎的理論,。計算機問題歸根結底是數(shù)學問題，將計算機問題抽象成數(shù)學問題,，是一種合適的解決方式,。
隨著互聯(lián)網(wǎng)行業(yè)的快速發(fā)展，作為其支柱的計算機行業(yè)越來越受到人們重視,。然而,，人們更加注重程序結果而不是算法,，更疏于關心數(shù)據(jù)結構。
本文提出了對算法設計和數(shù)據(jù)結構的離散性體現(xiàn)的思路,，給抽象解決計算機問題做一種具體化解釋,，以期給讀者建立一種從連續(xù)性到離散性的思維。
1算法
本節(jié)主要以算法來表述計算機中的離散性問題,。本節(jié)概括了算法的基本概念,，并以兩個算法設計的方法來表述離散性的表現(xiàn)。該節(jié)算法均以C語言描述,。
1.1算法的基本概念
算法(algorithm)是指解題方案的準確而完整的描述,，是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機制［1］,。也就是說,，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時間內(nèi)獲得所要求的輸出,。
當然，對于流程型的程序確實對算法的要求不高,，但對于人工智能,、人機交互、圖形圖像識別,、音視頻識別,、虛擬現(xiàn)實、現(xiàn)實增強,、社會工程學,、數(shù)據(jù)挖掘、大數(shù)據(jù)分析,、大型網(wǎng)絡拓撲,、云計算等領域來說，算法是其關鍵,。
現(xiàn)在流行于手機的各種美圖軟件中,，亦存在較不錯的算法設計。軟件如何識別出人臉,？如何分析眼睛,、鼻子、嘴巴等的位置,？如何對其進行一定的“美圖”而不至于讓人無法分辨,？
由計算機科學之父、人工智能之父阿蘭·圖靈(Alan Turing)帶領的小組,，在二戰(zhàn)中幫助盟軍設計了破譯德國的密碼系統(tǒng)Enigma的機器,。設計機器的過程,，可以稱作設計算法的過程。圖靈實際是領導小組成員設計出一個快速解密德國納粹密碼系統(tǒng)的算法,，并為這個算法設計了機器,。
可見，算法其實是程序的根本,。世界頂尖的科技企業(yè)和高等院校進行的各種科學性研究,，只要涉及計算機或與程序相關，其中一大重點便是在研究算法,。無論對于多么龐大的一個系統(tǒng),，設計其算法是最基礎也是關鍵的第一步。
1.2算法體現(xiàn)的離散性
算法設計中可以體現(xiàn)出計算機科學中常見的不連續(xù)的特性,，即離散性,。
1.2.1算法設計常用的方法
算法設計的方法有很多，亦有很多相關文獻,。此處主要介紹最簡單的兩種方法［2］,，并在后面以此為例。
?。?）遞推法：遞推是序列計算機中的一種常用算法,。它是按照一定的規(guī)律來計算序列中的每個項，通常是通過計算機前面的一些項來得出序列中的指定項的值,。其思想是把一個復雜的龐大的計算過程轉(zhuǎn)化為簡單過程的多次重復,，該算法利用了計算機速度快和不知疲倦的機器特點。
?。?）遞歸法：程序調(diào)用自身的編程技巧稱為遞歸(recursion),。一個過程或函數(shù)在其定義或說明中有直接或間接調(diào)用自身的一種方法，它通常把一個大型復雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解,，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算,，大大地減少了程序的代碼量。遞歸的能力在于用有限的語句來定義對象的無限集合,。一般來說,，遞歸需要有邊界條件、遞歸前進段和遞歸返回段,。當邊界條件不滿足時,，遞歸前進；當邊界條件滿足時,，遞歸返回,。
1.2.2兩種方法的離散性體現(xiàn)
遞推法中，計算機用一種比較“傻”的方法來進行一個復雜的運算,。如算法1,，以一個求最大值的算法來解釋,。
算法1求最大值
int max(int *array, int size)
{
int mval = *array;
int i;
for (i = 1; i < size; i++)
if (array［i］ > mval)
mval = array［i］;
return mval;
}
可見對于計算機來說，它會不斷地用已知最大的數(shù)去和數(shù)組中下一個數(shù)字作比較,，直到結束,，即使有很多很多數(shù)字。而人類比較數(shù)字大小的方式就不同了,，如果數(shù)字非常多,，則可能會先看看數(shù)字都是幾位的，挑出位數(shù)最高的,，如果不止一個,則再去逐個比較,。這是一種連續(xù)性的思維模式。這正是人類習慣的連續(xù)性思維,，初等數(shù)學都是建立在連續(xù)的基礎上,，也亦有了幾何的出現(xiàn)。然而對于計算機來說,，要有這種連續(xù)的思維是很困難的,，要設計出更加復雜的算法，才能“模擬”出人類的這種連續(xù)性思維,。當然,，亦有可能是因為人類的大腦這個“CPU”比較高級，自身的算法就足夠復雜,，所以人類才擁有連續(xù)性思維。對于設計出更復雜的算法和更快速的計算機來“模擬”人腦的思維模式,，也有相關研究,，亦有不少相關文獻，這不是本文重點,。
遞歸法有時可以簡化算法,，以求兩個自然數(shù)的最大公約數(shù)為例，如算法2,，其改用遞歸算法后如算法3,。
算法2求最大公約數(shù)
void swapi(int *x, int *y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
int gcd(int m, int n)
{
int r;
do
{
if (m < n)
swapi(&m, &n);
r=m%n;
m=n;
n=r;
} while (r);
return m;
}
算法3遞歸法求最大公約數(shù)
int gcd(int a,int b)
{
if(a%b)
return gcd(b,a%b);
return b;
}
形象地說遞歸法就是“自己調(diào)用自己”。一種離散性的表現(xiàn)與之前的例子類似,，這里不再重復,。這里講的是程序運行表現(xiàn)的離散性。計算機會在棧中運行程序,，棧的特點就是“后進先出”,。在運行這個遞歸的算法時，需要返回值時返回一個“自己”,，只不過參數(shù)不同,。直到返回一個確定的值,，再層層返回，如圖1所示,。
可見,，對于該算法，計算機每遞歸計算一次,，就要向內(nèi)存中Push一次,，直到計算完成，再一次一次Pop出,。這是一種計算的離散性體現(xiàn),，這亦不會是人類的連續(xù)性的思維方式。
2數(shù)據(jù)結構
本節(jié)主要以數(shù)據(jù)結構來表述計算機中的離散性問題,。本節(jié)概括了數(shù)據(jù)結構的基本概念,，并提出了數(shù)據(jù)結構的離散性的基本理解。
2.1數(shù)據(jù)結構的基本概念
數(shù)據(jù)結構是計算機科學的經(jīng)典學科,。字面上來說,，就是研究數(shù)據(jù)元素之間的結構關系。根據(jù)數(shù)據(jù)元素之間關系的不同特性,，一般來說可分為四類基本結構：集合,、線性結構、樹形結構,、圖狀結構或網(wǎng)狀結構［3］,，如圖2所示。這正是數(shù)據(jù)結構的元素具有的離散性特征,。
Nicklaus Wirth憑借“算法+數(shù)據(jù)結構=程序”這一公式獲得了計算機科學領域最高獎——圖靈獎,。這已足以可見數(shù)據(jù)結構的重要性。
數(shù)據(jù)結構主要討論的是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合,。在任何問題中,，數(shù)據(jù)元素都不是孤立存在的，而是在它們之間存在著某種關系,，這種數(shù)據(jù)元素相互之間的關系稱之為結構(structure),。而離散數(shù)學與數(shù)據(jù)結構有千絲萬縷的聯(lián)系，很多大學的計算機專業(yè)將離散數(shù)學作為數(shù)據(jù)結構的先導課程,。
2.2數(shù)據(jù)結構的離散性
離散數(shù)學中的圖論可以說就是對數(shù)據(jù)結構的抽象,，這方面的學術文獻相當豐富。這里僅對其做一個較為簡單,、通俗的理解說明,。
對于集合結構，如圖2所示，其元素本身就是離散的,、無關的,。
對于線性結構的離散性是顯而易見的。前文在介紹算法的離散性時提到棧的應用,，可見其離散性,。其余線性結構類似。
樹形結構和圖形結構也很好理解,，每個元素本來是獨立存在,，由于元素之間滿足了某種關系使其變成了樹形或圖形結構，自然這種關系是離散的,，不連續(xù)的,。
實際上，離散數(shù)學與數(shù)據(jù)結構的關系是最為緊密的,。離散數(shù)學中的圖論實際就是研究一些復雜的數(shù)據(jù)元素之間的關系［4］,。一些離散數(shù)學中的理論應用在計算機中，實現(xiàn)了一些難以解決的問題或優(yōu)化了一些原本不恰當?shù)姆椒?，例如哈夫?Huffman)樹解決了壓縮編碼的問題,。
3離散數(shù)學與數(shù)字電子
本節(jié)將介紹離散數(shù)學的一些概念，并指出其與數(shù)字電子（主要是數(shù)字信號）的關系,。
3.1離散數(shù)學的基本概念
離散數(shù)學是數(shù)學的幾個分支的總稱,，是研究基于離散空間而不是連續(xù)的數(shù)學結構。與光滑變化的實數(shù)不同,，離散數(shù)學的研究對象,，例如整數(shù)、圖和數(shù)學邏輯中的命題［5］,，不是光滑變化的,，而是擁有不等、分立的值［6］,。因此離散數(shù)學不包含微積分和分析等“連續(xù)數(shù)學”的內(nèi)容。離散對象經(jīng)?？梢杂谜麛?shù)來枚舉,。更一般地，離散數(shù)學被視為處理可數(shù)集合（與整數(shù)子集基數(shù)相同的集合,，包括有理數(shù)集但不包括實數(shù)集）的數(shù)學分支［7］,。但是，“離散數(shù)學”不存在準確且普遍認可的定義［8］,。實際上,，離散數(shù)學經(jīng)常被定義為不包含連續(xù)變化量及相關概念的數(shù)學，甚少被定義為包含什么內(nèi)容的數(shù)學,。
3.2數(shù)字電子的基本概念與離散性
數(shù)字電子是一門學科,，與計算機學科相互交叉,。此處僅以其數(shù)字信號的基本概念解釋其離散性。
數(shù)字信號同模擬信號相對,，模擬信號是指時間和數(shù)值都連續(xù)的一組信號,，而數(shù)字信號是指時間和數(shù)值都是離散的一組信號，如圖3所示,。從圖3可以看出,，這種連續(xù)性與離散性是非常明顯的。從數(shù)學上來說,，連續(xù),，意味著其微積分有意義。顯然,，對離散的信號這是沒有意義的,。這里不再深究。
4計算機中的離散性問題
本節(jié)主要介紹二進制體現(xiàn)出來的離散性問題,，并歸結出計算機中的離散性問題基本都與計算機采用的二進制的性質(zhì)有關,。
4.1二進制
計算機中以二進制進行存儲和運算，這涉及邏輯數(shù)學的一些概念,。實際上,，邏輯運算亦能體現(xiàn)離散性。這與計算機的運算是有映射關系的,。
4.1.1基本概念
二進制是逢2進位的進位制,。“0”,、“1”是基本算符?，F(xiàn)代的電子計算機技術全部采用的是二進制，因為它只使用“0”,、“1”這兩個數(shù)字符號,，非常簡單方便，易于用電子方式實現(xiàn)［9］,。
由于人類習慣使用十進制,，可以這樣表述二進制：二進制數(shù)的每一位數(shù)的位權（理解為“1”能有多“大”）為2n-1（n為位數(shù)）。這樣可以充分理解二進制數(shù)的“大小”,。
4.1.2體現(xiàn)
計算機是一個只認識“0”,、“1”的機器，對于人類來說很容易理解的信息（如圖片,、音視頻）對于計算機來說卻不能直接理解,。所以計算機本身就要通過離散的數(shù)據(jù)來“認識世界”。
計算機所處理的對象都是離散的數(shù)據(jù)。所謂離散的數(shù)據(jù),，可以理解為從本質(zhì)上說計算機只能處理“0”,、“1”組成的二進制的數(shù)據(jù)。計算機要進行圖像,、文字,、聲音等數(shù)據(jù)的處理，必須將其轉(zhuǎn)換成二進制的數(shù)據(jù)表示,，
也就是說進行離散化處理,。只如音頻處理，只有將連續(xù)變化的聲音轉(zhuǎn)換成二進制的數(shù)據(jù)來表示,，這樣計算機才能進行處理,。
圖4所示就是計算機將音頻信息離散化的方法。離散化得越“細”,，就越能還原聲音的原來面貌,。
4.2簡要分析
計算機采用的二進制使得計算機處理問題具有離散性的特征,。前面所述的算法設計與數(shù)據(jù)結構的離散性體現(xiàn),，都可以通過二進制來解釋。這涉及一些比較靠近計算機底層的理論,，這里不再深究,。
5結論
本文以探究離散數(shù)學的方式淺析了計算機的離散性問題，特別是在算法設計與數(shù)據(jù)結構上,，并最終說明計算機采用的二進制是計算機離散性問題的一個關鍵,。
隨著計算機科學的發(fā)展和實際需求的日益增長，計算機的離散性越來越受到相關領域的關注和重視,，相信這是一個極具價值的研究領域,，值得更深一步的探索。
參考文獻
?。?］ 譚浩強. C程序設計［M］. 北京: 清華大學出版社,2005.
?。?］ ROGERS H. Theory of recursive functions and effective computability［M］. Cambridge: The MIT Press, 1987.
［3］ 嚴蔚敏,吳偉民. 數(shù)據(jù)結構: C語言版［M］. 北京: 清華大學出版社,2007.
?。?］ 屈婉玲,耿素云,張立昂. 離散數(shù)學［M］. 北京: 清華大學出版社,2008.
?。?］ JOHSONBAUGH R. Discrete mathematics ［M］. Upper Saddle River： Prentice Hall, 2008.
［6］ WEISSTEIN E. Discrete mathematics ［EB/OL］. (2016-06-19)［2016-07-16］ http://mathworld.wolfram.com/DiscreteMathematics.html.
?。?］ BIGGS N. Discrete mathematics ［M］. Oxford: Oxford University Press,2002.
［8］ HOPKINS B. Resources for teaching discrete mathematics ［M］. Washington D.C.: Mathematical Association of America,2008.
?。?］ 康華光. 電子技術基礎: 數(shù)字部分（第6版）［M］. 北京: 高等教育出版社,2014.