第5章計算學科中的數(shù)學和系統(tǒng)科學方法2015

內(nèi)容提要計算學科中的數(shù)學方法系統(tǒng)科學的基本方法信息系統(tǒng)結(jié)構(gòu)化方法和面向?qū)ο蟮姆椒ǖ?章計算學科中的

數(shù)學和系統(tǒng)科學方法1、計算學科中的數(shù)學方法在計算學科中，采用的數(shù)學方法主要是離散數(shù)學方法。集合論代數(shù)系統(tǒng)圖論數(shù)學有連續(xù)數(shù)學和離散數(shù)學之分，它們分別以離散型變量和連續(xù)型變量為研究對象。連續(xù)型變量是不可數(shù)的，如函數(shù)的連續(xù)性。連續(xù)數(shù)學源于幾何，以微積分為基礎，用連續(xù)的觀點對數(shù)學進行研究，如天氣分析與預報。離散型就是變量的變化是可數(shù)的，如自然數(shù)1,2,3,…。離散數(shù)學源于算術(shù)，所研究的對象都是離散型的，如整數(shù)、圖和數(shù)學邏輯中的命題。實例：銀行服務排隊服務問題。計算學科的根本問題是“能行性”問題。 “能行性”問題決定了計算機本身的結(jié)構(gòu)和它處理的對象都是離散型的。連續(xù)型的問題只有經(jīng)過“離散化”的處理后才能被計算機處理。凡是能用離散數(shù)學為代表的構(gòu)造性數(shù)學方法描述的問題，當該問題所涉及的論域為有窮，或雖為無窮但存在有窮表示時，這個問題一定能用計算機來處理。由于計算機的軟硬件都是形式化的產(chǎn)物，因此，凡是能被計算機處理的問題都可以轉(zhuǎn)換為一個數(shù)學問題。在對待數(shù)學的問題上，計算機科學家與數(shù)學家的側(cè)重點不一樣。數(shù)學家關(guān)心的是“是什么（Whatisit）”的問題，重點放在數(shù)學本身的性質(zhì)上；計算機科學家不僅要知道“是什么”的問題，更要解決“怎么做（Howtodoit）”的問題。數(shù)學家側(cè)重于幾何推理和關(guān)于無限問題的推理，計算機科學家側(cè)重于對變化的動態(tài)過程狀態(tài)的重點把握。計算機科學家傾向于將問題分解成若干狀態(tài)，并精確地定義事物處理的每一步驟。數(shù)學家則從本能上傾向于用一個單純的公式來描述一切事物所有的狀態(tài)。由于傳統(tǒng)數(shù)學研究的對象過于抽象，導致對具體問題（特別是有關(guān)計算的本質(zhì)）關(guān)心不夠。因此，在計算領域，人們又創(chuàng)造了基于離散數(shù)學的“具體”數(shù)學的大量概念和方法（如學科中的各種形式化方法）。計算學科中常用數(shù)學概念和術(shù)語集合：一組具有某種共同性質(zhì)的數(shù)學元素。函數(shù)（映射）：是指把輸入轉(zhuǎn)變成輸出的運算。函數(shù)是程序設計的基礎，函數(shù)以算法的形式來實現(xiàn)。關(guān)系：關(guān)系是一個謂詞，其定義域為k元組的集合。通常的關(guān)系為二元關(guān)系，其定義域為有序?qū)Φ募希硎居行驅(qū)Φ牡谝粋€元素和第二個元素有關(guān)系。（笛卡兒積D1xD2x…xDn的子集叫做在域D1，D2，…，Dn上的n元關(guān)系）代數(shù)系統(tǒng)：由集合A以及連同若干定義在該集合上的運算所組成的系統(tǒng)稱為代數(shù)系統(tǒng)。群、環(huán)、格、布爾代數(shù)是4種最基本的代數(shù)系統(tǒng)。計算學科中常用數(shù)學概念和術(shù)語字符串："abc1234"語言：語言是字符串的集合。計算機使用的語言是一種形式語言，語言由文法產(chǎn)生，而文法可看作是一種代數(shù)系統(tǒng)。定義、定理和證明：定義、定理和證明是數(shù)學的核心，也是計算學科理論形態(tài)的核心內(nèi)容。其中，定義是蘊含在公理系統(tǒng)之中的概念和命題；定理是被證明為真的數(shù)學命題；證明是為使人們確信一個命題為真，而作的一種邏輯論證。必要條件（necessarycondition）和充分條件（sufficientcondition）:p=>q數(shù)學方法概述證明方法：直接證明法和間接證明法，反證法，歸納法（不完全歸納法、完全歸納法、數(shù)學歸納法），構(gòu)造性證明。遞歸和迭代（構(gòu)造性數(shù)學方法）公理化方法：公理化方法是一種構(gòu)造理論體系的演繹方法，它是從盡可能少的基本概念、公理出發(fā)，運用演繹推理規(guī)則，推出一系列的命題，從而建立整個理論體系的思想方法。形式化方法：形式化方法是基于嚴密的、數(shù)學上的形式機制的開發(fā)方法。它包括形式規(guī)格，以及支持規(guī)格語言的語法檢查和規(guī)格屬性證明的方法和工具。形式規(guī)格是系統(tǒng)構(gòu)建的關(guān)鍵，它包括客戶需求的定義、程序?qū)嵤?、結(jié)果測試和程序文檔等內(nèi)容。計算機軟硬件系統(tǒng)都是形式化的產(chǎn)物，都可以用形式化的數(shù)學方法進行描述。遞歸：遞歸和迭代是最具代表性的構(gòu)造性

數(shù)學方法，廣泛地應用于計算學科各個領域。與遞歸有關(guān)的概念有：遞歸關(guān)系、遞歸數(shù)列、遞歸過程、遞歸算法、遞歸程序、遞歸方法。遞歸與數(shù)學歸納法：數(shù)學歸納法是一種論證方法，遞歸是算法和程序設計的一種實現(xiàn)技術(shù)。涉及遞歸定義的證明通常采用數(shù)學歸納法。遞歸的定義功能：遞歸不僅應用于算法和程序設計之中，還應用于定義序列、函數(shù)和集合。例如，階乘F(n)=n!的遞歸定義：F(n)=n×F(n–1)迭代所謂迭代，就是反復替換的意思。在程序

設計中，為了處理重復性計算的問題，最

常用的方法就是迭代方法，主要是循環(huán)迭代。迭代與遞歸有著密切的聯(lián)系，一類如X0=a，Xn+1=f(n)的遞歸關(guān)系就可以看作是數(shù)列的一個迭代關(guān)系?？梢宰C明，迭代程序都可以轉(zhuǎn)換為與它等價的遞歸程序；反之，則不然。遞歸程序比迭代程序要耗費更多的時間和空間（需要額外開銷）。因此，在具體實現(xiàn)時，盡可能將遞歸程序轉(zhuǎn)化為等價的迭代程序。但有些算法就不能用迭代方法，如梵天塔問題，只能用遞歸方法。理論上，利用?？梢詫⑦f歸程序轉(zhuǎn)換為非遞歸程序。例如，梵天塔問題，二叉樹的遍歷算法。數(shù)學的基本特征高度的抽象性：數(shù)學的抽象程度大大超過自然科學中一般的抽象，它最大的特點在于拋開現(xiàn)實事物的物理、化學和生物學等特性，而僅保留其量的關(guān)系和空間的形式。邏輯的嚴密性：數(shù)學高度的抽象性和邏輯的嚴密性是緊密相關(guān)的。若沒有邏輯的嚴密性，那么用數(shù)學方法對現(xiàn)實世界進行抽象就失去了意義。只有遵守形式邏輯的基本法則，充分保證邏輯的可靠性，才能保證結(jié)論的正確性。普遍的適用性：數(shù)學的高度抽象性決定了它的普遍適用性。數(shù)學廣泛地應用于其他科學與技術(shù)，甚至人們的日常生活之中。計算學科中的數(shù)學方法：總結(jié)數(shù)學方法的作用為科學技術(shù)研究提供：簡潔精確的形式化語言：簡明的數(shù)學公式、抽象的數(shù)學模型就是運用數(shù)學的形式化語言。數(shù)量分析和計算的方法：一門科學要從定性分析發(fā)展到定量分析，數(shù)學方法從中起了杠桿的作用。邏輯推理的工具：數(shù)學的邏輯嚴密性這一特點使它成為建立一種理論體系的手段——公理化方法：數(shù)學邏輯用數(shù)學方法研究推理過程，把邏輯推理形式加以公理化、符號化，為建立和發(fā)展科學的理論體系提供有效的工具。計算學科中的數(shù)學方法：總結(jié)2、計算機科學中的系統(tǒng)科學方法

系統(tǒng)科學方法廣泛地應用于社會、經(jīng)濟和科學技術(shù)等各個領域。在計算學科中，采用的系統(tǒng)科學方法主要是模型方法，包括建模、驗證和實現(xiàn)。建模屬于學科抽象方面的內(nèi)容，模型的驗證屬于學科理論方面的內(nèi)容，模型的實現(xiàn)屬于學科設計形態(tài)方面的內(nèi)容。系統(tǒng)科學的基本方法信息系統(tǒng)結(jié)構(gòu)化方法和面向?qū)ο蟮姆椒?.1系統(tǒng)科學的基本方法系統(tǒng)科學方法是指用系統(tǒng)的觀點來認識和處理問題的各種方法的總稱，是一般科學方法論中的重要內(nèi)容。模型方法是系統(tǒng)科學的基本方法，研究系統(tǒng)具體來說就是研究它的模型。模型是對系統(tǒng)原型的抽象，是科學認識的基礎。系統(tǒng)科學是探索系統(tǒng)的存在方式和運動變化規(guī)律的學問。建立在系統(tǒng)科學基礎之上的系統(tǒng)科學方法是認識、改造和設計復雜系統(tǒng)的有效手段，它為系統(tǒng)形式化模型的構(gòu)建提供了有效的中間過渡模式。計算學科中一些重要的系統(tǒng)方法，如結(jié)構(gòu)化方法、面向?qū)ο蠓椒ǘ佳赜昧讼到y(tǒng)科學的思想方法。系統(tǒng)的定義系統(tǒng)是由相互聯(lián)系和相互制約的若干組成部分結(jié)合而成的、具有特定功能的有機整體。系統(tǒng)可以形式化地定義為：S=<A，R>

其中：A表示系統(tǒng)S中所有元素的集合；R表示系統(tǒng)S中所有元素之間關(guān)系的集合。 一個大的系統(tǒng)往往是復雜的，它通?？梢詣澐譃橐幌盗休^小的系統(tǒng)，這些系統(tǒng)稱為子系統(tǒng)。系統(tǒng)的基本模型（圖）處理處理反饋輸入輸出一個簡單的系統(tǒng)模型有反饋控制的系統(tǒng)模型輸入輸出系統(tǒng)的基本要素：六個要素系統(tǒng)（功能）、輸入、輸出、邊界、組織、環(huán)境系統(tǒng)的例子

生命系統(tǒng)化學元素周期表計算機網(wǎng)絡軟件系統(tǒng)數(shù)據(jù)庫管理系統(tǒng)系統(tǒng)和子系統(tǒng)（圖）結(jié)構(gòu)和結(jié)構(gòu)分析： 指系統(tǒng)內(nèi)各組成部分（元素和子系統(tǒng)）之間相互聯(lián)系、相互作用的框架。層次和層次分析(圖)環(huán)境、行為和功能系統(tǒng)的環(huán)境是指一個系統(tǒng)之外的一切與它有聯(lián)系的事物組成的集合。系統(tǒng)要適應環(huán)境的要求。 系統(tǒng)的行為是指系統(tǒng)相對于它的環(huán)境所表現(xiàn)出來的一切變化。行為反映環(huán)境對系統(tǒng)的影響和作用。 系統(tǒng)的功能是指系統(tǒng)行為所引起的、有利于環(huán)境中某些事物乃至整個環(huán)境存在與發(fā)展的作用。狀態(tài)、演化和過程狀態(tài)：系統(tǒng)的形態(tài)特征。演化：系統(tǒng)的結(jié)構(gòu)、狀態(tài)、行為等變化。過程：系統(tǒng)演化的發(fā)展階段。

系統(tǒng)與子系統(tǒng)：一種系統(tǒng)復雜性的分解方法子系統(tǒng)3-1子系統(tǒng)3-3子系統(tǒng)3-2子系統(tǒng)1-1子系統(tǒng)2-1子系統(tǒng)2-2輸入輸出系統(tǒng)0000主功能2100子系統(tǒng)3000子系統(tǒng)2000子系統(tǒng)1000主功能2200主功能3100主功能3200子模塊3111子模塊1112子模塊1111子模塊3112主功能1200主功能1100子功能3110子功能3120子功能1120子功能1110層次結(jié)構(gòu)圖系統(tǒng)科學遵循的一般原則整體性原則 這一原則要求人們在研究系統(tǒng)時，應從整體出發(fā)，立足于整體來分析其部分以及部分之間的關(guān)系，進而達到對系統(tǒng)整體的更深刻的理解。動態(tài)原則 系統(tǒng)總是處于運動變化之中，我們在研究系統(tǒng)時，應從動態(tài)的角度去研究系統(tǒng)發(fā)展的各個階段，以準確把握其發(fā)展過程及未來趨勢。最優(yōu)化原則 從系統(tǒng)多種途徑中選擇最優(yōu)系統(tǒng)、最優(yōu)方案、最優(yōu)功能、最優(yōu)運動狀態(tài)，達到整體優(yōu)化的目的。模型化原則 根據(jù)真實系統(tǒng)提供的依據(jù)，以模型代替真實系統(tǒng)進行模擬實驗，達到認識真實系統(tǒng)特性和規(guī)律性的方法。模型化方法是系統(tǒng)科學的基本方法。主要采用符號模型，而非實物模型。符號模型包括概念模型、邏輯模型、數(shù)學模型。數(shù)學模型是系統(tǒng)定性和定量分析的主要方法，通常是指通過建立和分析系統(tǒng)的數(shù)學模型來解決問題的方法和程序。數(shù)學模型是指描述元素之間、子系統(tǒng)之間、層次之間以及系統(tǒng)與環(huán)境之間相互作用的數(shù)學表達式，如樹結(jié)構(gòu)、圖、代數(shù)結(jié)構(gòu)等。用計算機程序定義的模型稱為基于計算機的模型。所有數(shù)學模型均可轉(zhuǎn)化為基于計算機的模型。一些復雜的、無法建立數(shù)學模型的系統(tǒng)，如生物、社會和行為過程等，也可建立基于計算機的模型。2.2信息系統(tǒng)信息系統(tǒng)的定義以計算機和各種信息技術(shù)為基礎，為實現(xiàn)某個系統(tǒng)目標，由信息資源處理模型支持的，由計算機軟硬件、通訊和網(wǎng)絡設備、信息資源、用戶、規(guī)章制度等所組成的信息處理的統(tǒng)一體。信息系統(tǒng)的功能對信息的采集、處理、存儲、管理、檢索和傳輸并能向有關(guān)人員提供有用信息。信息系統(tǒng)的類型低層信息系統(tǒng)：事務處理系統(tǒng)中層信息系統(tǒng)：業(yè)務信息系統(tǒng)、辦公自動化系統(tǒng)，管理信息系統(tǒng)高層信息系統(tǒng)：決策支持系統(tǒng)，知識工作系統(tǒng)，專家系統(tǒng)2.3結(jié)構(gòu)化方法（StructuredMethodology)軟件系統(tǒng)的狀態(tài)數(shù)量巨大，其擴展不像硬件系統(tǒng)那樣，可以由相同元素重復添加，從而使軟件的復雜度呈非線性增長。布魯克斯從復雜度、一致性、可變性、不可見性等方面作了系統(tǒng)地分析，揭示了軟件所固有的困難。軟件概念結(jié)構(gòu)的特點決定了這種結(jié)構(gòu)的設計很難采用形式化的方法。采用非形式化的系統(tǒng)化方法，如結(jié)構(gòu)化方法、面向?qū)ο蠓椒ǖ?，可以有效地控制和降低概念結(jié)構(gòu)設計的復雜性。軟件開發(fā)的系統(tǒng)化方法遵循的基本原則：

抽象第一的原則：對實際事物進行人為處理，抽取所關(guān)心的、共同的、本質(zhì)特征的屬性，并對這些事物及其特征屬性進行描述。由于抽取的是共同的、本質(zhì)特征的屬性，大大降低了系統(tǒng)元素的數(shù)量。層次劃分的原則：遵循等價類劃分的基本原則。如計算機網(wǎng)絡層次結(jié)構(gòu)、計算機體系結(jié)構(gòu)等。模塊化原則：模型化原則就是根據(jù)系統(tǒng)模型說明的原因和真實系統(tǒng)提供的依據(jù)，以模型代替真實系統(tǒng)進行模擬實驗，達到認識真實系統(tǒng)特性和規(guī)律性。模型化方法是系統(tǒng)科學的基本方法。結(jié)構(gòu)化方法采用了系統(tǒng)科學的思想方法，從層次的角度，自頂向下分析和設計系統(tǒng)。結(jié)構(gòu)化方法包括：結(jié)構(gòu)化分析（StructuredAnalysis，SA）結(jié)構(gòu)化設計（StructuredDesign，SD）結(jié)構(gòu)化程序設計（StructuredProgramDesign，SP）結(jié)構(gòu)化方法的產(chǎn)生和發(fā)展1966年，提出“程序結(jié)構(gòu)”理論：任何程序的邏輯結(jié)構(gòu)都可以用順序結(jié)構(gòu)、選擇結(jié)構(gòu)和循環(huán)結(jié)構(gòu)表示。1968年，爭論：“goto語句是有害的”SP逐漸形成，并成為軟件領域的重要方法，出現(xiàn)了Modula-2、C、Ada等結(jié)構(gòu)化程序設計語言。1974年，《結(jié)構(gòu)化設計》論文為結(jié)構(gòu)化設計方法奠定了思想基礎。結(jié)構(gòu)化分析方法產(chǎn)生于20世紀70年代中期，在20世紀80年代又得到了進一步的發(fā)展。結(jié)構(gòu)化方法實例：高校信息管理系統(tǒng)模型問題是結(jié)構(gòu)化方法的核心問題，建模是從系統(tǒng)的需求分析開始。首先使用SA方法構(gòu)建系統(tǒng)的環(huán)境模型，然后使用SD方法確定系統(tǒng)的行為和功能模型，最后使用SP方法進行系統(tǒng)設計，確定用戶的現(xiàn)實模型。在信息系統(tǒng)的結(jié)構(gòu)化設計中，一般采用自頂向下，逐步細化的分解原則。首先將系統(tǒng)分解為若干子系統(tǒng)；然后再將子系統(tǒng)繼續(xù)分解，一直到每一個子系統(tǒng)都足夠基礎，不需要再分為止。這祥就可以將一個復雜的大系統(tǒng)劃分為若干具有特定功能的子系統(tǒng)，從而使系統(tǒng)的復雜性下降，同時，又使待解決的問題具體化。結(jié)構(gòu)化方法實例：高校信息管理結(jié)構(gòu)圖課堂測驗：編寫一個函數(shù)，將一個大寫字母轉(zhuǎn)換為小寫字母。作業(yè)：P1795.322.4面向?qū)ο蠓椒ǎ∣bject-Oriented)面向?qū)ο蠓椒ㄊ且詫ο鬄橹行?，以類和繼承為構(gòu)造機制來抽象現(xiàn)實世界，并構(gòu)建相應的軟件系統(tǒng)。面向?qū)ο蟮姆椒ǖ漠a(chǎn)生和發(fā)展起源于面向?qū)ο笳Z言：Simula、Smalltalk、ObjectiveC、C++20世紀90年代，面向?qū)ο蠓治龊兔嫦驅(qū)ο笤O計開始成熟，一些實用的面向?qū)ο箝_發(fā)方法、技術(shù)、工具相繼出現(xiàn)面向?qū)ο蟮姆椒ǖ幕舅悸贰胺诸悓W理論”的構(gòu)造法則區(qū)分對象及其屬性區(qū)分整體對象及其組成部分形成并區(qū)分不同對象的類面向?qū)ο蠓椒ㄖ凶罨镜母拍顚ο螅合到y(tǒng)運行時的基本單位，是類的具體實例。類：是對具有相同屬性和操作（或稱方法、服務）的對象進行的抽象描述。對象與類的關(guān)系猶如變量與數(shù)據(jù)類型的關(guān)系。類的形式化定義：

Class=<ID，INH，ATT，OPE，ITF>

其中：

ID——類名；

INH——類的繼承性集；

ATT——屬性集；

OPE——操作集；

ITF——接口消息集。面向?qū)ο蟪绦蛟O計的四個基本特征抽象：是指對一類對象進行概括，抽出它們共同的性質(zhì)并加以描述的過程。封裝：封裝是把對象的數(shù)據(jù)(屬性)和操作(行為)包裝在一個類中。通過封裝，可以決定對象的哪些屬性作為內(nèi)部細節(jié)被隱藏起來，哪些行為是作為對象與外部的接口。封裝是實現(xiàn)抽象的基本手