计算机科学数学理论浅谈 (转载)
【來源:TSTC文檔中心】
計算機自從其誕生之日起,它的主要任務就是進行各種各樣的科學計算。文檔處理,數(shù)據處理,圖像處理,硬件設計, 軟件設計等等,都可以抽象為兩大類:數(shù)值計算與非數(shù)值計算。作為研究計算機科學技術的人員,我們大都對計算數(shù)學對整個計算機科學的重要性有一些了解。但是 數(shù)學對我們這些專業(yè)的研究和應用人員究竟有多大的用處呢?我們先來看一下下面的一個流程圖:
????上圖揭示了利用計算機解決科學計算的步驟,實際問題轉換為程序,要經過一個對問題抽象的過 程,建立起完善的數(shù)學模型,只有這樣,我們才能建立一個設計良好的程序。從中我們不難看出計算數(shù)學理論對用計算機解決問題的重要性。下面我們將逐步展開對 這個問題的討論。
????計算機科學的數(shù)學理論體系是相當龐雜的,筆者不敢隨意劃分,參考計算機科學理論的學科體系,我們談及的問題 主要涉及:數(shù)值計算,離散數(shù)學,數(shù)論,計算理論四大方向。
[一]數(shù)值計算(Numerical Computation)主要包括數(shù)值分析學、數(shù)學分析學、線性代數(shù)、計算幾何學、概率論與數(shù)理統(tǒng)計學。
????數(shù)值分析學又常被稱為計算方法學,是計算理論數(shù)學非常重要的一個分支,主要研究數(shù)值型計算。 研究的內容中首先要談談數(shù)值計算的誤差分析,誤差是衡量我們的計算有效與否的標準,我們的算法解決問題如果在誤差允許的范圍內,則算法是有效的,否則就是 一個無效的問題求解。另外就是數(shù)值逼近,它研究關于如何使用容易數(shù)值計算的函數(shù)來近似地代替任意函數(shù)的方法與過程。感覺應用比較廣的不得不提切雪比夫逼近 和平方逼近了。筆者曾經嘗試過的就是通過最佳平方逼近進行曲線的擬合,開發(fā)工具可以選擇VC++或者Matlab。插值函數(shù)是另外一個非常重要的方面,現(xiàn) 代的計算機程序控制加工機械零件,根據設計可給出零件外形曲線的某些型值點,加工時走刀方向及步數(shù),就要通過插值函數(shù)計算零件外形曲線及其他點函數(shù)值。至 于方程求根、線性方程組求解,一般的計算性程序設計問題都會多多少少的涉及一些,我們這里就不贅述了。關于數(shù)值分析學的一個學習誤區(qū)就是僅僅學習理論知 識,而很難和程序設計結合起來,實際上通過上面的論述,大家已經能夠初步地認識到這個學科是應當與程序設計緊密聯(lián)系才能夠體現(xiàn)它的重要性的。關于理論的學 習,推薦華中科技大學李慶揚老師的《數(shù)值分析》。然而理論學習畢竟是個過程,最終的目標還是要用于程序設計解決實際的計算問題,向這個方向努力的書籍還是 挺多的,這里推薦大家高等教育出版社(CHEP)和施普林格出版社(Springer)聯(lián)合出版的《計算方法(Computational Methods)》,華中理工大學數(shù)學系寫的(現(xiàn)華中科技大學),這方面華科大做的工作在國內應算是比較多的,而個人認為以這本最好,至少程序設計方面涉 及了:任意數(shù)學函數(shù)的求值,方程求根,線性方程組求解,插值方法,數(shù)值積分,場微分方程數(shù)值求解。
????數(shù)學分析學很多學校在近些年已經替代高等數(shù)學被安排到了本科教學當中。原因是很簡單的,高等 數(shù)學雖然也是非常有用的工程數(shù)學,介紹的問題方法也被廣泛的應用,但是正如大家所知道的,高等數(shù)學不太嚴格的說,基本上就是偏向于計算的數(shù)學分析,當然省 去了數(shù)學分析非常看重的推理證明,然而我們認為這一部分正是我們最需要的。這對我們培養(yǎng)良好的分析能力和推理能力極有幫助。我的軟件工程學導師北工大數(shù)理 學院的王儀華先生就曾經教導過我們,數(shù)學系的學生到軟件企業(yè)中大多作軟件設計與分析工作,而計算機系的學生做初級程序員的居多,原因就在于數(shù)學系的學生分 析推理能力,從所受訓練的角度上要遠遠在我們平均水平之上。談到這方面的書籍,公認北京大學張筑生老師的《數(shù)學分析新講》為最好。張筑生教授一生寫的書并 不太多,但是只要是寫出來的每一本都是本領域內的杰作,這本當然更顯突出些。這種老書看起來不僅是在傳授你知識,而是在讓你體會科學的方法與對事物的認識 方法。現(xiàn)在多用的似乎是復旦大學的《數(shù)學分析》,高等教育出版社的,也是很好的教材。但關于如何去利用從中獲得的推理證明能力,我們在遇到具體問題的時 候,可以在今后的文章詳細討論。
????線性代數(shù)是我們在工科本科學習的必修課程,似乎大家找不到到底這個有什么用,其實很明顯,線 性代數(shù)作為工程數(shù)學的重要分支,在計算機領域的研究有相當廣泛的應用。最為突出的可以談談數(shù)組和矩陣的相關知識:
下面談一個我經常作為例 子和同學討論的問題:四個城市之間的航線如圖所示:
令aij=1,表示從i市到j市有1條航線
令aij=0,表示從i市到j市沒有單項航線
則 圖可用矩陣表示:????????????????????????
A= (aij) =
????我們可以采用程序設計實現(xiàn)這個問題,如果輔以 權值,可以轉化為最短路徑的問題,再復雜化一點還可以轉化為具有障礙物的最短路徑問題,這就會涉及一些如Dijkstra算法等高級程序設計算法話題。這 些都依靠著數(shù)組、矩陣的基本知識。數(shù)組的應用主要在圖像處理以及一些程序設計理論。矩陣的運算領域極為廣泛,比如在計算機圖形學當中曲線曲面的構造,圖像 的幾何變換,包括平移、鏡像、轉置、縮放。在高級圖像問題更有廣泛應用,例如在圖像增強技術,投影技術中的應用。
????計算幾何學研究的是幾何外形信息的計算機表示。包括幾何查找、多邊形、凸包問題、交與并、幾 何體的排列、幾何拓撲網絡設計、隨機幾何算法與并行幾何算法。它構成了計算機圖形學中的基本算法,是動畫設計,制造業(yè)計算機輔助設計的基礎。如果從事這方 面的深入研究,可以參考中國計算機學會周培德先生的《計算幾何——算法分析與設計》。
????概率論與數(shù)理統(tǒng)計學是這個領域最后一門關鍵的課程。概率論部分提供了很多問題的基本知識描 述,比如模式識別當中的概率計算,參數(shù)估計等等。數(shù)理統(tǒng)計部分有很多非常經典的內容,比如偽隨機數(shù)、蒙特卡羅法、回歸分析、排隊論、假設檢驗、以及經典的 馬科夫過程。尤其是隨機過程部分,是分析網絡和分布式系統(tǒng),設計隨機化算法和協(xié)議非常重要的基礎。
[二]離散數(shù)學(Discrete Mathematics)隨著計算機科學的出現(xiàn)與廣泛應用,人們發(fā)現(xiàn)利用計算機處理的數(shù)學對象與傳統(tǒng)的分析有明顯的區(qū)別:分析研究的問題解決方案是連續(xù) 的,因而微分,積分成為基本的運算;而這些分支研究的對象是離散的,因而很少有機會進行此類的計算。人們從而稱這些分支為"離散數(shù)學"。離散數(shù)學經過幾十 年發(fā)展,方向上基本上穩(wěn)定下來。當然不同時期還有很多新內容補充進來。就學科方向而言,一般認為,離散數(shù)學包含:集合論、邏輯學、代數(shù)學、圖論、組合學。
????邏輯學(Logics)我們主要指數(shù)理邏輯,形式邏輯在推理問題中也有比較廣泛的應用。(比 如我們學校還為此專門開設了選修課程)這方面的參考推薦中科院軟件所陸鐘萬教授的《面向計算機科學的數(shù)理邏輯》。現(xiàn)在可以找到陸鐘萬教授的講課錄像,http://www.cas.ac.cn/html/Dir/2001/11/06/3391.htm。總的來說,學集合/邏輯一定要站在理解的高度上去思考相關的問題。集合論(Set Theory)和邏輯學構成了計算機科學最重要的數(shù)學問題描述方式。
????代數(shù)學(Algebra)包括:抽象代數(shù)、布爾代數(shù)、關系代數(shù)、計算機代數(shù)
(1) 抽象代數(shù)(Abstract Algebra)研究的主要內容涵蓋群、環(huán)、域。抽象代表的是將研究對象的本質提煉出來,加以高度概括,來描述其形象。“歐式環(huán)”就是在將整數(shù)和多項式的 一些相同的特點加以綜合提煉引入的。抽象代數(shù)提供的一些結論為我們研究一些具體問題時所需使用的一些性質提供了依據。推薦一個最簡單的,最容易學的材料:http://www.math.miami.edu/~ec/book/這本《Introduction to Linear and Abstract Algebra》非常通俗易懂,而且把抽象代數(shù)和線性代數(shù)結合起來,對初學者來說非常理想。
(2)布爾代數(shù)(Boolean Algebra)是代數(shù)系統(tǒng)中最為基礎的部分,也是最核心的基本理論。主要包括了集合的基本概念與運算,自對偶的公理系統(tǒng)。是數(shù)據表示的重要基礎。相信大 家都很清楚它的重要性。
(3)關系代數(shù)(Relational Algebra)應用也是極為廣泛,比如數(shù)據庫技術中的關系數(shù)據庫的構建就要用到關系代數(shù)的相關理論。
(4)計算機代數(shù)(Computer Algebra)大家可能比較生疏,其實它研究的主要內容即是圍繞符號計算與公式演算展開的。是研究代數(shù)算法的設計、分析、實現(xiàn)及其應用的學科。主要求解 非數(shù)值計算,輸入輸出用代數(shù)符號表示。計算機代數(shù)的開發(fā)語言主要有:ALTRAN,CAMAL,FORMAL。主要應用于:射影幾何,工業(yè)設計,機器人手 臂運動設計。
????圖論(Graph Theory)主要研究的內容包括:圖的基本概念、基本運算、矩陣表示,路徑、回路和連通性,二部圖、平面圖,樹,以及網絡流。圖論的應用領域太過廣泛, 僅舉兩個例子:比如在計算機網絡拓撲圖的設計與結構描述中,就必須用到相當多的圖的結構和基本概念。關于網絡流更是在電流網絡與信息網絡的流量計算當中廣 泛應用。樹的相關應用則無須多言了。
????組合學(Combinatorics)有兩部分單獨的研究領域:組合數(shù)學與組合算法。組合學 問題的算法,計算對象是離散的、有限的數(shù)學結構。從方法學的角度,組合算法包括算法設計和算法分析兩個方面。關于算法設計,歷史上已經總結出了若干帶有普 遍意義的方法和技術,包括動態(tài)規(guī)劃、回溯法、分支限界法、分治法、貪心法等。應用是相當廣泛的,比如旅行商問題、圖著色問題、整數(shù)規(guī)劃問題。關于組合數(shù) 學,主要研究的內容有:鴿巢原理、排列與組合、二項式系數(shù)容斥原理及應用,遞推關系和生成函數(shù)、特殊計數(shù)序列、二分圖中的匹配、組合設計。推薦 Richard A.Brualdi的《Introductory Combinatorics》作為參考。
[三]數(shù)論(Number Theory)
?? 數(shù)論這門學科最初是從研究整數(shù)開始的,所以叫做整數(shù)論。后來更名為數(shù)論。它包括以下幾個分支:
?? 初等數(shù)論是不求助于其他數(shù)學學科的幫助,只依靠初等方法來研究整數(shù)性質的數(shù)論分支。比如在數(shù)論 界非常著名的“中國剩余定理”,就是初等數(shù)論中很重要的內容。對于程序設計來說這部分也是相當有價值的,如果你對中國剩余定理比較清楚,利用它,你可以將 一種表達式經過簡單的轉換后得出另一種表達式,從而完成對問題分析視角的轉換。
?? 解析數(shù)論是使用數(shù)學分析作為工具來解決數(shù)論問題的分支。是解決數(shù)論中比較深刻問題的強有力的工 具。我國數(shù)學家陳景潤在嘗試解決“哥德巴赫猜想”問題中使用的就是解析數(shù)論的方法。以素數(shù)定理為基礎解決計算素數(shù)的問題及其算法實現(xiàn)應是我們多多關注的。
????代數(shù)數(shù)論是把整數(shù)的概念推廣到一般代數(shù)數(shù)域上去,建立了素整數(shù)、可除性等概念。程序設計方面 涉及的比較多的是代數(shù)曲線的研究,比如說橢圓曲線理論的實現(xiàn)。
????幾何數(shù)論研究的基本對象是“空間格網”。空間格網就是指在給定的直角坐標系上,坐標全是整數(shù) 的點,叫做整點;全部整點構成的組就叫做空間格網。空間格網對計算幾何學的研究有著重大的意義。幾何數(shù)論涉及的問題比較復雜,必須具有相當?shù)臄?shù)學基礎才能 深入研究。
????總的說來,由于近代計算機科學的發(fā)展,數(shù)論得到了廣泛的應用。比如在計算方法、代數(shù)編碼、組合學理論等方面 都廣泛使用了初等數(shù)論范圍內的許多研究成果;現(xiàn)在有些國家應用“孫子定理”來進行測距,用原根和指數(shù)來計算離散傅里葉變換等。如果你曾經系統(tǒng)的學習過數(shù)論 算法,你會發(fā)現(xiàn)這個分支學科研究的一些基本問題對程序設計是相當有用的,比如說素數(shù)問題、素性測試、因子分解、最大公約數(shù)、模取冪運算、求解同余線性方 程。其中的很多問題都是程序設計的基本問題。但這些問題都不能小視,舉個例子來說吧,關于求最大公約數(shù)的程序,筆者曾經嘗試的就可以采用循環(huán)語句結構和遞 歸結構。另外,以大素數(shù)為基礎的密碼體系的建立是近些年數(shù)論算法廣泛應用的一個重要的原因。原理是大素數(shù)的乘積重新分解因數(shù)十分困難。RSA公鑰加密系統(tǒng) 的構建就是基于這個原理的(三位發(fā)明人因此也獲得了2002年美國計算機協(xié)會頒發(fā)的圖靈獎)。
[四]計算理論(Theory of Computation)
????涉及的內容是科學計算非常重要的一部分分支,也是大家研究相當多的一部分。主要包括:算法學,計算復雜性, 程序理論。
??算法學(Algorithms)在計算機科學理論中有著舉足輕重的地位。是解決很多數(shù)值型,非 數(shù)值型問題的基礎。記得一次學校接收招標項目,很多中小型軟件廠商都無法完成一個軟件的功能模塊,就是因為當時他們對一個具體問題的算法不能做出正確的抽 象,最后由我們學校數(shù)理學院的一支軟件團隊承擔了這項任務,他們的最終報告體現(xiàn)出來,問題的解決策略只有通過人工神經元網絡的反向傳播算法。可見在比較有 深度的程序設計中,算法的重要性更為突出。學習算法學要有一個長期的理論和實踐的過程。遇到一個具體算法問題時,首先要通過自己描述的數(shù)學抽象步驟,看看 自己以前有沒有處理過這種問題。如果沒有,很可能這個問題是多個算法的綜合,或者是需要我們自己去構造算法。這就需要我們有扎實的算法功底,為了打好這個 功底,推薦兩套圣經級的書籍首先是Thomas H.Cormen等著的《Introduction to Algorithms》。對算法學習而言,這一本內容相當?shù)娜妗T偕钜稽c的就是大家作為常識都知道的《The Art of Computer Programming》,目前已經出版3冊。兩本書的價值大家應當都是清楚的。
????計算復雜性研究的內容很廣,其中包括NP完全性理論,可計算性理論,自動機理論,形式語言理 論(包括廣泛應用于編譯原理領域的文法,還包括Petri網論的相關內容)以及大家熟知的復雜性度量。時間復雜度、空間復雜度的計算是度量算法非常重要的 參數(shù),也是我們衡量程序優(yōu)劣程度的重要依據。
????程序理論(Theory of programs)包含了形式語義學,程序驗證和并發(fā)模型的研究。關于程序驗證學習的重要性大家都很清楚,學習的方法自然也是多多結合具體的問題去分析。 關于并發(fā)模型,主要研究的就是進程代數(shù),通信系統(tǒng)演算,通信順序進程。這部分是研究操作系統(tǒng)理論與實現(xiàn)的重要基礎。
????按照計算機科學數(shù)學理論的架構來談了各方面的內容和一些應用,下面我們再單獨來看一些上面沒有涉及到的學科 與這些理論的具體結合情況:
????設計方面的應用剛才談的很多,我只再說說數(shù)據庫原理與技術,這方面用到的重要數(shù)學基礎主要包括:集合論,二 元關系及其推理(尤其是研究關系數(shù)據庫),研究數(shù)據分布與數(shù)據庫結構又涉及相當多的圖論知識。
????計算機科學的發(fā)展有賴于硬件技術和軟件技術的綜合。在設計硬件的時候應當充分融入軟件的設計思想,才能使硬 件在程序的指揮下發(fā)揮極致的性能。在軟件設計的時候也要充分考慮硬件的特點,才能沖破軟件效率的瓶頸。達到硬件和軟件設計的統(tǒng)一,嚴格的說這并不輕松,一 般的程序設計者很難將這樣的思想貫穿在其程序設計當中。僅舉個簡單的例子:我們在寫一些C語言的程序,必要的時候都會采取內嵌一段匯編指令,這就是比較充 分地考慮了硬件的工作情況,從而能夠提高程序運行的效率。所以我們也有必要了解一些硬件的基礎知識。關于學習硬件的時候常會用到的基本數(shù)學思想也是相當多 的,拿電路基礎與模擬電路來說,我們就經常要利用多元函數(shù),不等式計算進行電流電壓的計算。能量的計算還常常涉及微積分學的很多計算。在數(shù)字電子技術當中 (有時也稱數(shù)字邏輯學)數(shù)理邏輯,尤其是邏輯演算部分運用相當廣泛,數(shù)制轉換更是非常重要的基礎,各種數(shù)字電路參數(shù)的計算則是多元函數(shù),不等式的計算解決 的問題。
????從事計算機硬件程序設計的程序員,則不可回避的就是數(shù)字信號處理。這門科學所用到的數(shù)學基礎主要有:三角函 數(shù)、微積分、高次方程求解、數(shù)值逼近,傅里葉變換。在濾波器的設計當中還會用到矩陣運算。筆者曾經研究過一個VC++環(huán)境下開發(fā)的濾波器的模擬軟件,就是 利用萊文遜-杜賓遞推算法,在較大規(guī)模的矩陣運算基礎上進行的。當然,開發(fā)的環(huán)境不一定是這個,你也可以選擇MATLAB或者純C語言編譯器。如果我們不 了解相關的數(shù)學基礎,不要說程序設計,就算是建立運算模型都是相當困難的。
????一些周圍的同學和一些在職的程序員,大家經過一段時間的學習,普遍都覺得數(shù)學對學習計算機和研究計算機程序 設計等問題來說非常重要,但是又苦于無從下手。上面比較全面地談及了計算機科學數(shù)學理論的相關內容。需要特別指明的是,我們研究問題的精力是有限的,如果 您是在校的計算機系學生,則可以對上面的方方面面都有所涉及,以嘗試計算數(shù)學這個強大的理論工具。為今后的工作奠定一個堅實的基礎。但是如果您研究的是比 較具體的工作,我們并不推薦您研究所有的內容,最好的方法就是對上面的數(shù)學基礎都有些了解,然后遇到具體工作,需要哪部分內容,再進行深入的學習與研究。 這樣針對性比較強的學習效果是會比較顯著的。對于上面推薦的一些參考材料,除非你要花相當長的一段時間來提高你的計算機數(shù)學理論。否則也沒必要每一頁,每 一本都字字精讀,還是那個原則,按需索取其中的內容。學習的方法描述起來就一句話:結合具體的問題,深入的理解數(shù)學理論知識,將理論程序化,嘗試用程序設 計實現(xiàn)理論原理。達到這樣的程度,問題基本上都可以解決的。
參考文獻:
《計算機科學技術百科全書》中國計算機學會 清華大學出版社
《工程數(shù)學— 線性代數(shù)》同濟大學數(shù)學教研室 同濟大學出版社
《數(shù)值分析》李慶揚 華中科技大學出版社
轉載于:https://www.cnblogs.com/Henrya2/archive/2010/03/21/1690849.html
總結
以上是生活随笔為你收集整理的计算机科学数学理论浅谈 (转载)的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 微软白皮书发布:在IIS7.5中用Ser
- 下一篇: SQL server挂了之后