哈工大大學(xué)計(jì)算機(jī)基礎(chǔ)課件2

大學(xué)計(jì)算機(jī)基礎(chǔ)

第三章問題求解哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院金野1Recap1.任何信息（數(shù)值、文字、多媒體）都可被表示成0，1串。2.圖靈將控制處理的規(guī)則用0和1表達(dá),將待處理的信息及處理結(jié)果也用0和1表達(dá),提出了圖靈機(jī)模型。3.馮諾依曼根據(jù)圖靈的設(shè)想構(gòu)建出了馮諾依曼體系計(jì)算機(jī)，包含輸入、輸出、存儲(chǔ)器、運(yùn)算器和控制器。4.計(jì)算機(jī)語言的發(fā)展：機(jī)器語言->匯編語言->高級(jí)語言->以構(gòu)造方式和事件驅(qū)動(dòng)程序?yàn)樘卣鞯牡谒拇绦蛟O(shè)計(jì)語言。人們使用計(jì)算機(jī)越來越方便，所能實(shí)現(xiàn)的功能也越來越多越來越強(qiáng)大。2第3章問題求解3.1算法類問題3.2系統(tǒng)類問題33.1算法類問題歐幾里德算法：求解兩個(gè)數(shù)的最大公因子的算法（公元前300年）表述了最大公因子的求解過程表述了一個(gè)判定過程，即判定“m和n是互質(zhì)的”（即除1以外，m和n沒有公因子）命題的真假。4歐幾里德算法語言描述：輸入：正整數(shù)M和正整數(shù)N輸出：M和N的最大公約數(shù)算法過程：Step1.將較大的數(shù)賦給M,較小的數(shù)賦給N;Step2.M除以N,記余數(shù)為RStep3.如果R不是0,將N的值賦給M,R的值賦給N,返回Step2;否則,最大公約數(shù)是N,輸出N,算法結(jié)束5例：歐幾里得算法的應(yīng)用設(shè)m=56,n=32,求m、n的最大公因子。32除56余數(shù)為24；

24除32余數(shù)為8；8除24余數(shù)為0，算法結(jié)束，輸出結(jié)果8。答：m、n的最大公因子為8。6歐幾里得算法的偽代碼描述7輸入：正整數(shù)m和正整數(shù)n輸出：m和n的最大公約數(shù)算法過程：Step1:M=max(m,n),n=min(m,n)Step2:R=MmodNStep3:IfR不等于0,那么M=N,N=R,GotoStep2;否則,最大公約數(shù)是N,輸出N,算法結(jié)束歐幾里德算法流程圖8開始m<nm與n交換r=mmodnr=0m=nn=r是否否是輸出n

結(jié)束控制流程圖:是人們對解決問題的方法、思路或算法的一種描述。9起止/結(jié)束框判斷框處理框輸入/輸出框連接點(diǎn)流向線控制結(jié)構(gòu)：順序結(jié)構(gòu)：“執(zhí)行A，然后執(zhí)行B”10//例：順序執(zhí)行，交換M,N{

tmp=M; M=N; N=tmp;}

控制結(jié)構(gòu)：分支結(jié)構(gòu)：“如果P成立，那么執(zhí)行A，否則執(zhí)行B”，P是某些邏輯條件11//例：根據(jù)M,N大小，選擇操作if(M>N){ Max=M;}else{ Max=N;}

控制結(jié)構(gòu)：循環(huán)結(jié)構(gòu)：控制指令的多次執(zhí)行——迭代（iteration）12//例：求平均分Sum=0;//總分Num=100;//人數(shù)i=0;do{ Sum+=Score[i];//累加 i++;}while(i<100)Avg=Sum/Num;//求平均

控制結(jié)構(gòu)：循環(huán)結(jié)構(gòu)：控制指令的多次執(zhí)行——迭代（iteration）13//例：求平均分Sum=0;//總分Num=100;//人數(shù)i=0;while(i<100){ Sum+=Score[i];//累加 i++;}Avg=Sum/Num;//求平均

控制結(jié)構(gòu)：循環(huán)結(jié)構(gòu)：控制指令的多次執(zhí)行——迭代（iteration）14//例：求平均分Sum=0;//總分Num=100;//人數(shù)for(i=0;i<Num;i++){ Sum+=Score[i];//累加}Avg=Sum/Num;//求平均

歐幾里得算法的C語言實(shí)現(xiàn)15int

Euclid(intm,intn){

intM=max(m,n);//被除數(shù)

intN=min(m,n);//除數(shù)

intR;//余數(shù)

do{ R=M%N;//求余數(shù)

if(R!=0)//余數(shù)不為0時(shí)設(shè)定被除數(shù)、除數(shù)。

{ M=N; N=R; } }while(R>0); returnN; }3.1算法類問題算法（Algorithm）源于數(shù)學(xué)家的名字：公元825年，阿拉伯?dāng)?shù)學(xué)家阿科瓦里茨米（AlKhowarizmi）寫了著名的《波斯教科書》（PersianTextbook），書中概括了進(jìn)行四則算術(shù)運(yùn)算的法則。163.1算法類問題算法的定義：一個(gè)有窮規(guī)則的集合，規(guī)則規(guī)定了一個(gè)解決某一特定類型問題的運(yùn)算序列。算法定義了任務(wù)執(zhí)行/問題求解的一系列步驟。算法的特征：有窮性：一個(gè)算法在執(zhí)行有窮步之后必須結(jié)束。確定性：算法的每一個(gè)步驟必須要確切地定義，不能有歧義。輸入：算法有零個(gè)或多個(gè)的輸入。輸出：算法有一個(gè)或多個(gè)的輸出/結(jié)果，即與輸入有某個(gè)特定關(guān)系的量可行性：算法中有待執(zhí)行的運(yùn)算和操作必須是相當(dāng)基本的,可實(shí)現(xiàn)的.173.1算法類問題哥尼斯堡七橋問題漢諾塔問題丟番圖方程可解性問題旅行商問題背包問題……183.1算法類問題算法類問題：由一個(gè)算法可以解決的問題193.1算法類問題旅行商問題（TravelingSalesmanProblem，TSP）威廉哈密爾頓爵士和英國數(shù)學(xué)家克克曼T.P.Kirkman于19世紀(jì)初提出有若干個(gè)城市，任何兩個(gè)城市之間的距離都是確定的，現(xiàn)要求一旅行商從某城市出發(fā)必須經(jīng)過每一個(gè)城市且只能在每個(gè)城市逗留一次，最后回到原出發(fā)城市，問如何事先確定好一條最短的路線使其旅行的費(fèi)用最少。20城市之間的距離3.1算法類問題旅行商問題TSP是最有代表性的優(yōu)化組合問題之一，在半導(dǎo)體制造、物流運(yùn)輸?shù)刃袠I(yè)有著廣泛的應(yīng)用TSP難于求解：2001年解決了德國15112個(gè)城市的TSP問題，使用了美國Rice大學(xué)和普林斯頓大學(xué)之間互連的、速度為500MHz

的CompaqEV6Alpha處理器組成的110臺(tái)計(jì)算機(jī)，所有計(jì)算機(jī)花費(fèi)的時(shí)間之和為22.6年。213.1算法類問題算法類問題求解的過程及思維方法22示例數(shù)學(xué)模型TSP問題的數(shù)學(xué)模型建立數(shù)學(xué)模型是求解算法類問題的第一步數(shù)學(xué)模型：數(shù)學(xué)模型就是為了某種目的，根據(jù)對研究對象所觀察到的現(xiàn)象及其實(shí)踐經(jīng)驗(yàn)，用字母、數(shù)字及其它數(shù)學(xué)符號(hào)建立起來的等式或不等式以及圖表、圖象、框圖等歸結(jié)成的一套反映對象某些主要數(shù)量關(guān)系的數(shù)學(xué)公式、邏輯準(zhǔn)則和具體算法，用來描述客觀事物的特征，其內(nèi)在聯(lián)系和運(yùn)動(dòng)規(guī)律。例如:如果訪問序列為ABCD，則下一個(gè)城市為A3.1算法類問題數(shù)學(xué)模型求解方法數(shù)學(xué)模型的求解可以理解為在狀態(tài)空間/解空間上尋找滿足約束并具有某些方面性能的特定解。求解方法：遍歷搜索分治動(dòng)態(tài)規(guī)劃……3.1算法類問題示例TSP問題求解中的數(shù)據(jù)操縱問題輸入：城市之間的距離輸出：訪問城市的路徑中間結(jié)果：路徑的距離之和、已經(jīng)訪問過的城市、當(dāng)前的最短路徑……確定數(shù)據(jù)結(jié)構(gòu)問題求解中的數(shù)據(jù)組織及操縱3.1算法類問題什么是數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)提供了問題求解/算法的數(shù)據(jù)操縱機(jī)制數(shù)據(jù)結(jié)構(gòu)：如何組織、存儲(chǔ)和操作數(shù)據(jù)的集合數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)之間的關(guān)系存儲(chǔ)結(jié)構(gòu)：在反映數(shù)據(jù)邏輯關(guān)系的原則下，數(shù)據(jù)在存儲(chǔ)器中的存儲(chǔ)方式，有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)?；具\(yùn)算：(1)建立數(shù)據(jù)結(jié)構(gòu)；(2)清除數(shù)據(jù)結(jié)構(gòu)；(3)插入數(shù)據(jù)元素；(4)刪除數(shù)據(jù)元素；(5)更新數(shù)據(jù)元素；(6)查找數(shù)據(jù)元素；(7)按序重新排列；(8)判定某個(gè)數(shù)據(jù)結(jié)構(gòu)是否為空，或是否已達(dá)到最大允許的容量；(9)統(tǒng)計(jì)數(shù)據(jù)元素的個(gè)數(shù)等。263.1算法類問題數(shù)據(jù)結(jié)構(gòu)基本數(shù)據(jù)結(jié)構(gòu)：變量向量/列表/數(shù)組矩陣/表27112522254539844212801003483751612341234行列M[2,3]向量實(shí)例表實(shí)例3.1算法類問題示例TSP問題求解的數(shù)據(jù)結(jié)構(gòu)城市間距離關(guān)系表D訪問路徑/解一維數(shù)組S路徑距離之和整數(shù)變量sum循環(huán)計(jì)數(shù)器i,j,k…1432{A->D->C->B->A}3.1算法類問題確定過程控制問題求解過程中需要組織并控制操作、指令的執(zhí)行的過程和順序。29示例TSP問題求解的流程控制求解TSP問題需要控制指令、基本操作的邏輯過程/流程遍歷所有的組合路徑判斷某條路徑的距離是不是比另外一條短，并據(jù)此作出不同的處理累加一條路徑的距離之和……3.1算法類問題確定算法策略求解方法：遍歷貪心搜索分治動(dòng)態(tài)規(guī)劃……30示例所有路徑組合及其長度城市之間的距離遍歷：列出每一條可供選擇的路線，計(jì)算出每條路線的總里程，最后從中選出一條最短的路線TSP問題的求解方法組合爆炸路徑組合數(shù)目：(n-1)!20個(gè)城市，總數(shù)1.216×1017

，計(jì)算機(jī)以每秒檢索1000萬條路線，需386年3.1算法類問題確定算法策略可行解與最優(yōu)解遍歷能夠獲得最優(yōu)解，然而，由于組合爆炸，對于較大規(guī)模的某些問題，無法在可接受的時(shí)間內(nèi)獲得最優(yōu)解退而求其次，在可接受的時(shí)間內(nèi)獲得足夠好的（可行）解31示例可行解最優(yōu)解TSP問題的可行解與最優(yōu)解3.1算法類問題城市之間的距離確定算法策略——貪心算法貪心算法“今朝有酒今朝醉”一定要做當(dāng)前情況下的最好選擇，否則將來可能會(huì)后悔，故名“貪心”32示例城市之間的距離TSP問題的貪心求解示例每次在選擇下一個(gè)城市的時(shí)候，只考慮當(dāng)前情況，保證迄今為止經(jīng)過的路徑總距離最短3.1算法類問題算法的表示方法自然語言；流程圖；偽代碼；計(jì)算機(jī)程序設(shè)計(jì)語言等。333.1算法類問題TSP問題的貪心求解偽代碼算法步驟4表示從第2個(gè)城市開始逐步選擇新的城市;步驟8表示用Sum記錄總路線的長度;步驟11輸出問題的解。算法的核心——“貪心策略尋找下一城市”體現(xiàn)在算法過程的步驟(5)中，即“從所有未訪問過的城市中查找距離S[i-1]最近的城市j”，然而，這一步驟如何執(zhí)行還有待進(jìn)一步明確。

(1)S[I]=1;(2)Sum=0;(3)初始化距離數(shù)組D[N,N];(4)I=2;(5)從所有未訪問過的城市中查找距離S[I-1]最近的城市j;(6)S[I]=j;(7)I=I+1;(8)Sum=Sum+D[S[I-2],j];(9)如果I<=N，轉(zhuǎn)步驟(5)，否則，轉(zhuǎn)步驟(10);(10)Sum=Sum+D[1,j]；(11)逐個(gè)輸出S[N]中的全部元素;(12)輸出Sum。3.1算法類問題將步驟(5)進(jìn)一步細(xì)化，得到如下的過程：從所有未訪問過的城市中查找距離S[I-1]最近的城市jDtemp用于在遍歷時(shí)，保存當(dāng)前最小的距離。而j存儲(chǔ)該城市。K遍歷每一個(gè)即將可能要訪問到的城市，因此，其初始值為2.（A是始點(diǎn)，已被訪問了）。L表示訪問過的城市。在K確定的前提下，利用L的變化，考察每個(gè)已經(jīng)訪問過的S[L]，是否與K相同，即K是否被訪問過。一旦確定K被訪問過，即S[L]=K，則將K更新為下一個(gè)，如果K+1>n，則意味著處理完畢，否則利用更新過的K重新處理。外循環(huán)，K變化內(nèi)循環(huán)，L變化TSP問題的貪心求解偽代碼3.1算法類問題算法的流程圖描述36示例TSP問題貪心算法的流程圖3.1算法類問題算法的程序描述——算法的實(shí)現(xiàn)程序是算法的一種機(jī)器相容（Compatible）的表示程序是利用計(jì)算機(jī)程序設(shè)計(jì)語言對算法描述的結(jié)果程序可在計(jì)算機(jī)上執(zhí)行程序設(shè)計(jì)語言：C、Java、…程序設(shè)計(jì)過程：編輯編譯鏈接執(zhí)行373.1算法類問題算法的程序描述38示例TSP問題貪心算法程序算法的模擬與分析算法的正確性：問題求解的過程、方法——算法是正確的嗎？算法的輸出是問題的解嗎？20世紀(jì)60年代，美國一架發(fā)往金星的航天飛機(jī)由于控制程序出錯(cuò)而永久丟失在太空中算法的效果評(píng)價(jià)：算法的輸出是最優(yōu)解還是可行解？如果是可行解，與最優(yōu)解的偏差多大？兩種方法：理論分析方法：利用數(shù)學(xué)方法證明。嚴(yán)格有效但困難。仿真分析方法：產(chǎn)生或選取大量的、具有代表性的問題實(shí)例，利用該算法對這些問題實(shí)例進(jìn)行求解，并對算法產(chǎn)生的結(jié)果進(jìn)行統(tǒng)計(jì)分析。易實(shí)現(xiàn)但不能保證永遠(yuǎn)正確。393.1算法類問題TSP問題貪心算法的模擬與分析TSP問題貪心算法的正確性：直觀上只需檢查算法的輸出結(jié)果中，每個(gè)城市出現(xiàn)且僅出現(xiàn)一次，該結(jié)果即是TSP問題的可行解，說明算法正確的求解了這些問題實(shí)例TSP問題貪心算法的效果評(píng)價(jià)：如果實(shí)例的最優(yōu)解已知（問題規(guī)模小或問題已被成功求解），利用統(tǒng)計(jì)方法對若干問題實(shí)例的算法結(jié)果與最優(yōu)解進(jìn)行對比分析，即可對其進(jìn)行效果評(píng)價(jià)，對于較大規(guī)模的問題實(shí)例，其最優(yōu)解往往是未知的，因此，算法的效果評(píng)價(jià)只能借助于與前人算法結(jié)果的比較。403.1算法類問題算法的復(fù)雜度算法的復(fù)雜度：時(shí)間復(fù)雜度和空間復(fù)雜度時(shí)間復(fù)雜度：在問題規(guī)模增大時(shí)，算法的執(zhí)行時(shí)間的增長?！按驩記法”：算法處理的數(shù)據(jù)規(guī)模為n。算法的復(fù)雜度表示為n的函數(shù)。例：O(1),O(n),O(n^2),O(a^n)等等.算法的空間復(fù)雜度：算法在執(zhí)行過程中所占存儲(chǔ)空間隨問題規(guī)模的增長。413.1算法類問題42示例TSP問題算法的復(fù)雜性TSP問題遍歷算法：列出每一條可供選擇的路線，計(jì)算出每條路線的總里程，最后從中選出一條最短的路線組合爆炸：路徑組合數(shù)目為(n-1)!時(shí)間復(fù)雜度是O((n-1)!)TSP問題貪心算法：時(shí)間復(fù)雜度是O(n3)。3.1算法類問題算法的復(fù)雜性當(dāng)算法的時(shí)間復(fù)雜度的表示函數(shù)是一個(gè)多項(xiàng)式，如O(n2)時(shí)，計(jì)算機(jī)對于大規(guī)模問題可以處理。例如，TSP問題的貪心算法算法的時(shí)間復(fù)雜度用一個(gè)指數(shù)函數(shù)表示，如O(2n)，當(dāng)n很大（如10000）時(shí)計(jì)算機(jī)是無法處理的，在計(jì)算復(fù)雜性中將這一類問題稱為難解型問題或NP問題。例如，TSP問題的遍歷算法433.1算法類問題計(jì)算復(fù)雜性理論：所有可以在多項(xiàng)式時(shí)間內(nèi)求解的問題稱為P類問題所有在多項(xiàng)式時(shí)間內(nèi)能夠用不確定的算法解決的問題稱為NP類問題，P?NP。Openproblem:P=NP?美國克雷數(shù)學(xué)研究所百萬大獎(jiǎng)難題443.1算法類問題3.1算法類問題小結(jié)453.2系統(tǒng)類問題*系統(tǒng)類問題是指那些不能由單一算法解決的，而必須構(gòu)建一個(gè)系統(tǒng)來解決的問題。例如：衛(wèi)星導(dǎo)航系統(tǒng)、機(jī)器人系統(tǒng)、企業(yè)生產(chǎn)管理系統(tǒng)、計(jì)算機(jī)操作系統(tǒng)等。463.2系統(tǒng)類問題*系統(tǒng)的概念：系統(tǒng)是指由相互聯(lián)系、相互作用的若干元素構(gòu)成的，具有特定功能的統(tǒng)一整體。一個(gè)大系統(tǒng)往往是復(fù)雜的，通常可劃分為一系列較小的系統(tǒng)，稱為子系統(tǒng)。系統(tǒng)的特性：系統(tǒng)是有結(jié)構(gòu)的：系統(tǒng)內(nèi)各組成部分（元素和子系統(tǒng)）之間相互聯(lián)系、相互作用的框架。系統(tǒng)是處于環(huán)境之中的：所謂環(huán)境是指一個(gè)系統(tǒng)之外的一切與它有聯(lián)系的事物組成的集合。系統(tǒng)要發(fā)揮它應(yīng)有的作用，達(dá)到應(yīng)有的目標(biāo)，系統(tǒng)自身一定要適應(yīng)環(huán)境的要求。473.2系統(tǒng)類問題系統(tǒng)的特性：系統(tǒng)是有功能的：所謂功能是指系統(tǒng)行為所引起的、有利于環(huán)境中某些事物乃至整個(gè)環(huán)境存在與發(fā)展的作用。系統(tǒng)是有行為的：所謂行為是指系統(tǒng)相對于它的環(huán)境所表現(xiàn)出來的一切變化，行為屬于系統(tǒng)自身的變化，同時(shí)又反映環(huán)境對系統(tǒng)的影響和作用。系統(tǒng)是有狀態(tài)的：所謂狀態(tài)是指系統(tǒng)的那些可以觀察和識(shí)別的形態(tài)特征。狀態(tài)一般可以用系統(tǒng)的定量特征來表示，如溫度T、體積V等。483.2系統(tǒng)類問題49衛(wèi)星導(dǎo)航系統(tǒng)操作系統(tǒng)機(jī)器人系統(tǒng)系統(tǒng)類問題與系統(tǒng)科學(xué)50物料需求管理問題系統(tǒng)類問題與系統(tǒng)科學(xué)解決系統(tǒng)類問題需要采用系統(tǒng)科學(xué)方法：系統(tǒng)科學(xué)是以系統(tǒng)為研究和應(yīng)用對象的一門科學(xué)，誕生于20世紀(jì)40年代。系統(tǒng)科學(xué)的崛起被認(rèn)為是20世紀(jì)現(xiàn)代科學(xué)的兩個(gè)重大突破性成就之一。系統(tǒng)科學(xué)是探索系統(tǒng)的存在方式和運(yùn)動(dòng)變化規(guī)律的學(xué)問，是對系統(tǒng)本質(zhì)的理性認(rèn)識(shí)，是人們認(rèn)識(shí)客觀世界的一個(gè)知識(shí)體系。系統(tǒng)科學(xué)方法是用系統(tǒng)的觀點(diǎn)來認(rèn)識(shí)和處理問題的各種方法的總稱。計(jì)算學(xué)科中的結(jié)構(gòu)化方法、面向?qū)ο蠓椒ǘ佳赜昧讼到y(tǒng)科學(xué)的思想方法。51系統(tǒng)類問題與系統(tǒng)科學(xué)（系統(tǒng)科學(xué)）解決系統(tǒng)類問題遵循的原則：整體性原則：非還原性是指系統(tǒng)的整體具有但還原為部分便不存在的特性——“涌現(xiàn)性”非加和性是指整體不能完全等于各部分之和——“貝塔朗菲定律”研究系統(tǒng)時(shí)，應(yīng)從整體出發(fā)，立足于整體來分析其部分以及部分之間的關(guān)系，進(jìn)而達(dá)到對系統(tǒng)整體的更深刻的理解。整體優(yōu)化原則：運(yùn)用各種有效方法，從系統(tǒng)多種目標(biāo)或多種可能的途徑中選擇最優(yōu)系統(tǒng)、最優(yōu)方案、最優(yōu)功能、最優(yōu)運(yùn)動(dòng)狀態(tài)，達(dá)到整體優(yōu)化的目的。52系統(tǒng)類問題與系統(tǒng)科學(xué)（系統(tǒng)科學(xué)）解決系統(tǒng)類問題遵循的原則：動(dòng)態(tài)原則：系統(tǒng)總是動(dòng)態(tài)的，永遠(yuǎn)處于運(yùn)動(dòng)變化之中。研究系統(tǒng)時(shí)，應(yīng)從動(dòng)態(tài)的角度去研究系統(tǒng)發(fā)展的各個(gè)階段，以準(zhǔn)確把握其發(fā)展過程及未來趨勢。模型化原則根據(jù)系統(tǒng)模型說明的原因和真實(shí)系統(tǒng)提供的依據(jù)，提出以模型代替真實(shí)系統(tǒng)進(jìn)行模擬實(shí)驗(yàn)，達(dá)到認(rèn)識(shí)真實(shí)系統(tǒng)特性和規(guī)律性的方法。模型化方法是系統(tǒng)科學(xué)的基本方法，主要采用符號(hào)模型，包括概念模型、邏輯模型、數(shù)學(xué)模型等。基于計(jì)算機(jī)的模型（Computer-BasedModel），計(jì)算思維（Computationalthinking），建立基于計(jì)算機(jī)的模型，利用計(jì)算手段研究和解決系統(tǒng)類問題。53系統(tǒng)類問題求解過程及思維方法54業(yè)務(wù)模型與業(yè)務(wù)建模系統(tǒng)類問題求解的第一步——業(yè)務(wù)建模/問題域建模系統(tǒng)類問題是復(fù)雜問題，解決該問題的前提是正確的理解問題，把握系統(tǒng)的目標(biāo)、結(jié)構(gòu)、行為等，并將其描述出來運(yùn)用系統(tǒng)科學(xué)的模型化原則這一過程稱為——業(yè)務(wù)建模/問題域建模獲得的結(jié)果——業(yè)務(wù)模型55業(yè)務(wù)模型與業(yè)務(wù)建模模型與建模的概念模型是對某一真實(shí)系統(tǒng)（如衛(wèi)星導(dǎo)航系統(tǒng)、企業(yè)）的目標(biāo)、結(jié)構(gòu)、行為的抽象描述。模型的內(nèi)容：識(shí)別概念識(shí)別概念間的關(guān)系…表達(dá)（可視化/形式化）建模的根本原則——抽象：把握系統(tǒng)的本質(zhì)內(nèi)容，而忽略與系統(tǒng)當(dāng)前目標(biāo)無關(guān)的內(nèi)容，它是一種基本的認(rèn)知過程和思維方式。56業(yè)務(wù)模型與業(yè)務(wù)建模業(yè)務(wù)建模/問題域建模的內(nèi)容業(yè)務(wù)過程模型組織模型信息模型….業(yè)務(wù)模型的作用：理解區(qū)分命名表達(dá)57業(yè)務(wù)模型與業(yè)務(wù)建模58示例物料需求管理問題的業(yè)務(wù)模型概念及關(guān)系：產(chǎn)品結(jié)構(gòu)：描述了產(chǎn)品的構(gòu)成關(guān)系，即產(chǎn)品各零部件之間的父子構(gòu)成關(guān)系，一個(gè)父件由多少單位的子件構(gòu)成。提前期和期量標(biāo)準(zhǔn)：提前期描述了由零件制造、產(chǎn)品裝配或材料采購所需的時(shí)間，當(dāng)所有構(gòu)成子件完成后制造出父件的周期即為提前期。期量標(biāo)準(zhǔn)是依據(jù)產(chǎn)品結(jié)構(gòu)模型和提前期信息，為產(chǎn)品建立時(shí)間坐標(biāo)上的產(chǎn)品結(jié)構(gòu)。業(yè)務(wù)模型與業(yè)務(wù)建模59示例物料需求管理問題的業(yè)務(wù)模型概念：獨(dú)立需求物項(xiàng)：企業(yè)可以獨(dú)立對外銷售的物料，其需求數(shù)量一般由市場決定，不依賴于其他物料的需求。相關(guān)需求物項(xiàng)：為了制造獨(dú)立需求物項(xiàng)而制造或采購的物項(xiàng)，例如木板是為了制造桌子而采購的，其需求數(shù)量是依賴于其他(獨(dú)立或相關(guān))物料需求數(shù)量而計(jì)算出來的。庫存：為了某些目的存儲(chǔ)在倉庫中的物項(xiàng)，庫存量因入庫而增加，因出庫而減少。在途：物項(xiàng)已經(jīng)投產(chǎn)尚未完工或已經(jīng)采購尚未到貨的數(shù)量，將在未來某一時(shí)間完工可用或到貨。計(jì)劃產(chǎn)出量：預(yù)計(jì)將于某一時(shí)段產(chǎn)出某種物項(xiàng)的數(shù)量。計(jì)劃投入量：預(yù)計(jì)將于某一時(shí)段投入某種物項(xiàng)的數(shù)量。業(yè)務(wù)模型與業(yè)務(wù)建模60示例物料需求計(jì)算過程的實(shí)例：物料需求管理問題的業(yè)務(wù)模型業(yè)務(wù)模型與業(yè)務(wù)建模61示例問題的核心模型----物料需求計(jì)算模型物料需求管理問題的業(yè)務(wù)模型業(yè)務(wù)模型與業(yè)務(wù)建模62示例物料需求管理問題的求解：核心算法及軟件系統(tǒng)算法系統(tǒng)軟件模型系統(tǒng)類問題求解第二步：軟件模型系統(tǒng)類問題的求解需要構(gòu)建一個(gè)系統(tǒng)人：用戶/使用者硬件：計(jì)算機(jī)、網(wǎng)絡(luò)軟件：基礎(chǔ)軟件：操作系統(tǒng)、數(shù)據(jù)庫管理系統(tǒng)應(yīng)用軟件：面向特定系統(tǒng)類問題求解的軟件應(yīng)用軟件的構(gòu)建是系統(tǒng)類問題求解的核心軟件是復(fù)雜的智力產(chǎn)品，需運(yùn)用系統(tǒng)科學(xué)方法、工程方法獲取——軟件工程業(yè)務(wù)模型（問題域模型）→軟件模型→軟件系統(tǒng)（解）63軟件模型64軟件模型與軟件開發(fā)過程軟件模型軟件系統(tǒng)系統(tǒng)模塊類函數(shù)變量調(diào)用/事件對象/實(shí)例數(shù)據(jù)庫表…65軟件模型軟件模型/軟件建模用例模型功能模型結(jié)構(gòu)模型行為模型數(shù)據(jù)模型…66軟件模型67示例物料需求管理系統(tǒng)的軟件模型模塊劃分及功能分解模型分解原則：先總體、后局部的思想原則，自頂向下、分層解決。模塊化原則：將系統(tǒng)分解成具有特定功能的若干模塊，從而完成系統(tǒng)指定的各項(xiàng)功能。軟件模型68示例物料需求管理系統(tǒng)的軟件模型結(jié)構(gòu)模型（類圖）基本構(gòu)造法則：區(qū)分對象及其屬性；區(qū)分整體對象及其組成部分；形成并區(qū)分不同對象的類。抽象：強(qiáng)調(diào)一個(gè)對象和其他對象相區(qū)別的本質(zhì)特性。封裝：封裝是對抽象元素的劃分過程，抽象由結(jié)構(gòu)和行為組成，封裝用來分離抽象的原始接口和它的執(zhí)行。類之間的靜態(tài)聯(lián)系：繼承，聚合，關(guān)聯(lián)物料類數(shù)據(jù)方法類圖表示法軟件模型69示例物料需求管理系統(tǒng)的軟件模型結(jié)構(gòu)模型（類圖）軟件模型70示例物料需求管理系統(tǒng)的軟件模型動(dòng)態(tài)/行為模型：表征運(yùn)行時(shí)的對象交互/消息傳遞/接口調(diào)用軟件實(shí)現(xiàn)系統(tǒng)類問題求解第三步：軟件實(shí)現(xiàn)軟件模型必須被實(shí)現(xiàn)為軟件系統(tǒng)，才能夠?qū)嶋H被用戶使用，解決系統(tǒng)類問題軟件實(shí)現(xiàn)：利用程序設(shè)計(jì)語言將軟件模型轉(zhuǎn)換為可運(yùn)行的軟件模塊/系統(tǒng)模塊→系統(tǒng)模塊實(shí)現(xiàn)的內(nèi)容用戶界面程序業(yè)務(wù)處理程序數(shù)據(jù)的持久化存儲(chǔ)程序模塊實(shí)現(xiàn)程序必須進(jìn)行測試—模塊/單元測試：模塊接口測試，局部數(shù)據(jù)結(jié)構(gòu)測試，路徑測試，錯(cuò)誤處理測試，邊界測試71軟件實(shí)現(xiàn)系統(tǒng)實(shí)現(xiàn)的概念：將多個(gè)模塊組裝成一個(gè)完整的系統(tǒng)系統(tǒng)實(shí)現(xiàn)的內(nèi)容：選擇合適的體系結(jié)構(gòu)并建立系統(tǒng)底層框架；

建立菜單管理器，即建立系統(tǒng)的功能菜單，給用戶以功能入口；提供系統(tǒng)級(jí)的功能和基礎(chǔ)設(shè)施，如安全和權(quán)限控制、統(tǒng)一的界面風(fēng)格控制、統(tǒng)一的數(shù)據(jù)訪問等；模塊/構(gòu)件的裝載，包括將模塊/構(gòu)件裝載到框架上，與菜單關(guān)聯(lián)起來等；將模塊/構(gòu)件組裝為完整的過程以支持完整的問題求解等。模塊組裝成系統(tǒng)后要進(jìn)行整體測試——系統(tǒng)測試72軟件實(shí)現(xiàn)73示例物料需求管理系統(tǒng)的軟件實(shí)現(xiàn)庫存管理模塊業(yè)務(wù)處理程序庫存管理模塊用戶界面軟件實(shí)現(xiàn)74示例物料需求管理系統(tǒng)的功能菜單和框架物料需求管理系統(tǒng)的軟件實(shí)現(xiàn)系統(tǒng)的部署與運(yùn)行75系統(tǒng)類問題求解的第四步：系統(tǒng)的部署與運(yùn)行系統(tǒng)的部署與運(yùn)行系統(tǒng)部署與運(yùn)行：數(shù)據(jù)+軟件系統(tǒng)+使用在企業(yè)構(gòu)建系統(tǒng)運(yùn)行的必要環(huán)境，鋪設(shè)網(wǎng)絡(luò)、搭建硬件、軟件平臺(tái)。部署軟件系統(tǒng)到企業(yè)：在數(shù)據(jù)庫中建立數(shù)據(jù)庫、表、視圖等；在客戶機(jī)、應(yīng)用服務(wù)器上安裝（物料需求管理）系統(tǒng)的客戶機(jī)部分或服務(wù)器部分，取決于軟件系統(tǒng)的體系結(jié)構(gòu)選擇；對系統(tǒng)進(jìn)行測試。系統(tǒng)配置：設(shè)置系統(tǒng)的用戶（計(jì)劃員、庫管員等）、設(shè)置用戶的權(quán)限（即可以使用的軟件功能和數(shù)據(jù)）等。對系統(tǒng)進(jìn)行必要的初始化：將企業(yè)中的所有物項(xiàng)編碼、清查庫房中的物項(xiàng)數(shù)量，并將這些數(shù)據(jù)輸入到系統(tǒng)中，作為系統(tǒng)運(yùn)行的起點(diǎn)。76系統(tǒng)的部署與運(yùn)行系統(tǒng)部署與運(yùn)行：數(shù)據(jù)+軟件系統(tǒng)+使用系統(tǒng)的試運(yùn)行/試應(yīng)用：嘗試性的利用系統(tǒng)來解決問題，支持業(yè)務(wù)工作，例如計(jì)算物項(xiàng)的需求、對物項(xiàng)計(jì)劃作出安排等，在此過程中，系統(tǒng)的運(yùn)行、系統(tǒng)所產(chǎn)生的輸出需要由用戶檢驗(yàn)其正確性，必要時(shí)對系統(tǒng)進(jìn)行調(diào)整。系統(tǒng)的運(yùn)行和應(yīng)用：如系統(tǒng)通過了試運(yùn)行/試應(yīng)用，則系統(tǒng)開始正式應(yīng)用，企業(yè)信任該系統(tǒng)的解決問題的能力，并依賴系統(tǒng)支持其業(yè)務(wù)工作和問題求解。當(dāng)然，某些錯(cuò)誤可能會(huì)在運(yùn)行期出現(xiàn)，此時(shí)再進(jìn)行系統(tǒng)的維護(hù)和完善。77系統(tǒng)的部署與運(yùn)行78示例物料需求管理系統(tǒng)的部署與運(yùn)行系統(tǒng)角色與權(quán)限配置系統(tǒng)的部署與運(yùn)行79示例物料需求管理系統(tǒng)的體系結(jié)構(gòu)選擇客戶機(jī)/服務(wù)器結(jié)構(gòu)瀏覽器/服務(wù)器結(jié)構(gòu)用戶界面+業(yè)務(wù)邏輯數(shù)據(jù)用戶界面+業(yè)務(wù)邏輯數(shù)據(jù)3.2系統(tǒng)類問題高級(jí)話題：系統(tǒng)的結(jié)構(gòu)性與演化為什么系統(tǒng)的結(jié)構(gòu)會(huì)變化，會(huì)演化？早期的軟件實(shí)現(xiàn)技術(shù)是從零開始，利用某種程序設(shè)計(jì)語言實(shí)現(xiàn)模塊或系統(tǒng)的所有部分，如用戶界面、業(yè)務(wù)處理、數(shù)據(jù)的持久化存儲(chǔ)等。缺點(diǎn)：程序員需要考慮硬件平臺(tái)、操作系統(tǒng)平臺(tái)的特性等諸多因素。實(shí)現(xiàn)難度大，對程序員的要求高，實(shí)現(xiàn)周期長，成本高。隨著技術(shù)的發(fā)展和反復(fù)的開發(fā)，逐漸形成了對某類問題的有效解決方案，并形成了支持該問題的系統(tǒng)和工具問題逐漸分離為與特定應(yīng)用有關(guān)的部分和與特定應(yīng)用無關(guān)的共性技術(shù)及工具，導(dǎo)致了軟件實(shí)現(xiàn)模式和體系結(jié)構(gòu)的發(fā)展和演化。803.2系統(tǒng)類問題81示例早期的程序員在實(shí)現(xiàn)時(shí)需要自己設(shè)計(jì)、定義數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)形式/結(jié)構(gòu)，還需要考慮硬件平臺(tái)、操作系統(tǒng)平臺(tái)的特性等。隨著技術(shù)的發(fā)展和反復(fù)的開發(fā)，逐漸形成了關(guān)系數(shù)據(jù)庫理論，并形成了關(guān)系數(shù)據(jù)庫管理系統(tǒng)等工具數(shù)據(jù)持久化存儲(chǔ)問題逐漸分離為與特定應(yīng)用有關(guān)的部分（如物料需求管理系統(tǒng)中的特定數(shù)據(jù)內(nèi)容及格式）和與特定應(yīng)用無關(guān)的共性技術(shù)及工具（如關(guān)系數(shù)據(jù)庫及關(guān)系數(shù)據(jù)庫管理系統(tǒng)），導(dǎo)致了軟件實(shí)現(xiàn)模式和體系結(jié)構(gòu)的發(fā)展和演化。系統(tǒng)結(jié)構(gòu)演化舉例——數(shù)據(jù)持久化存儲(chǔ)問題系統(tǒng)的結(jié)構(gòu)性與演化軟件模式的概念：“每個(gè)模式描述了那些在我們的環(huán)境中反復(fù)發(fā)生的問題，然后描述了該問題的解決方案的核心，從而使得你可以重復(fù)利用該方案”。模式關(guān)注于某種特定的解決方案，這種方案在處理一個(gè)或多個(gè)反復(fù)發(fā)生的問題時(shí)是通用而有效的。模式的一個(gè)關(guān)鍵特征是他們根植于實(shí)踐，你可以通過觀察人如何做事、事物如何工作而獲得“解決方案的核心”。模式廣泛存在于軟件的分析、設(shè)計(jì)、實(shí)現(xiàn)等過程和領(lǐng)域中，應(yīng)該有針對性的選擇軟件模式，以更好、更快地解決軟件系統(tǒng)問題。軟件模式影響了軟件的結(jié)構(gòu)，促進(jìn)了軟件結(jié)構(gòu)的演化。82系統(tǒng)的結(jié)構(gòu)性與演化軟件體系結(jié)構(gòu)：問題：隨著軟件系統(tǒng)的規(guī)模和復(fù)雜性不斷增加，系統(tǒng)的全局結(jié)構(gòu)的設(shè)計(jì)和規(guī)劃變得比算法的選擇以及數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)更加重要。全局組織結(jié)構(gòu)、全局控制結(jié)構(gòu)、通信和同步、數(shù)據(jù)存取的協(xié)議、設(shè)計(jì)元素的功能、設(shè)計(jì)元素的組合、物理分布、規(guī)模和性能、設(shè)計(jì)方案的選擇等。軟件體系結(jié)構(gòu)的概念：包括構(gòu)成系統(tǒng)的設(shè)計(jì)元素的描述、設(shè)計(jì)元素的交互、設(shè)計(jì)元素組合的模式，以及在這些模式中的約束。軟件體系結(jié)構(gòu)的重要性：為系統(tǒng)設(shè)計(jì)一個(gè)合適的體系結(jié)構(gòu)是系統(tǒng)取得長遠(yuǎn)的成功的關(guān)鍵因素。83系統(tǒng)的結(jié)構(gòu)性與演化