軟件技術基礎（算法Algorithm程序設計語言Programminglanguage軟件工程SoftwareEngineering）,教學團隊：陽小華劉志明楚燕婷等nhdxlzmUniversityofSouthChinaSchoolofComputerScience&Software（,學習內容,1概述2算法3程序設計4軟件工程,1概述,什么是計算機軟件?,操作系統(tǒng)、QQ、360,計算機系統(tǒng)=硬件+軟件,程序以及相關的文檔的集合。,什么是文檔？,文檔：記錄軟件開發(fā)活動和階段性成果，理解軟件所必需的闡述性資料。需求分析文檔軟件設計文擋等編寫文檔目的促進對軟件的開發(fā)、管理和維護；便于各種人員(用戶、開發(fā)人員)的交流,什么是程序？,程序一詞源于生活。做任何一件事情，都是有程序的。例如，下面是某一個學校頒獎大會的程序：宣布大會開始校長講話宣布獲獎名單頒獎獲獎代表發(fā)言宣布大會結束按順序實施這些步驟就完成了該事情。,用計算機完成某事情，就把事先設計好的計算機處理信息的步驟，用計算機能夠識別的指令編寫出來，送入計算機。計算機按照指令執(zhí)行，就能完成指定的工作。,算法,程序設計語言,可以說程序就是用計算機語言表述的算法。,為解決一個問題而采取的方法和步驟，就稱為算法。,什么是算法？,一個農夫帶著一只狼、一只羊和一棵白菜，身處河南岸，要把東西全部運到北岸。約束條件是只有一條能容下他和一件物品的小船，只有農夫能撐船。不能單獨留下羊和白菜，也不能單獨留下羊和狼。,例如：,農夫過河算法,帶羊到對岸空手回本岸帶菜到對岸帶羊回本岸帶狼到對岸空手回本岸帶羊到對岸,帶羊到對岸空手回本岸帶狼到對岸帶羊回本岸帶菜到對岸空手回本岸帶羊到對岸,或,在使用計算機解題前，需要將解題方法轉換成一系列具體的在計算機上可執(zhí)行的步驟，這些步驟能夠清楚的反映解題方法一步步“怎么做”的過程，這個過程就是通常所說的算法。算法：解題過程的準確、完整的描述稱作解該問題的算法。,什么是計算機語言？,人們想和計算機交流，用符號來表達。計算機通過事先約定好的符號與意義的對應關系，把人用符號表達的內容讀懂，再按照這些符號的意思去執(zhí)行。,怎樣維護交通秩序？音樂是怎樣表示的？,用來表達這種關系的符號系統(tǒng)就是計算機語言，也叫“程序設計語言”。人與計算機交流使用的是“程序設計語言”。同人類語言一樣，程序設計語言也是由字、詞和語法規(guī)則構成的一個系統(tǒng)。,軟件的分類,系統(tǒng)軟件操作系統(tǒng)語言編譯和解釋系統(tǒng)網(wǎng)絡軟件數(shù)據(jù)庫管理系統(tǒng)（DBMS）各種服務程序,應用軟件業(yè)務軟件科技計算軟件個人計算機軟件人工智能軟件,軟件開發(fā)過程？,有一個工程：建一座橋梁。我們會怎么做？了解橋梁的要求、用途設計維護開發(fā)大型軟件：定義開發(fā)維護,2算法,算法的表示算法的要素算法的特點算法的復雜度常用算法,主要內容,算法的表示,算法一般可以使用下面幾種類型的工具描述算法：1.自然語言自然語言描述算法通俗易懂，但它有著難以克服的缺陷：(1)易產生歧義性武松打死老虎(2)語句繁瑣冗長，很難清楚地表達算法的邏輯流程(3)不便于直接轉換成程序,例：求12345。最原始方法：步驟1：先求12，得到結果2。步驟2：將步驟1得到的乘積2乘以3，得到結果6。步驟3：將6再乘以4，得24。步驟4：將24再乘以5，得120。這樣的算法雖然正確，但太繁。,改進的算法：S1:使t=1S2:使i=2S3:使ti,乘積仍然放在在變量t中，可表示為titS4:使i的值+1，即i+1iS5:如果i5,返回重新執(zhí)行步驟S3以及其后的S4和S5；否則，算法結束。如果計算100！只需將S5:若i5改成i100即可。,2.專用圖形工具常用的有流程圖、PAD圖和N-S圖等,流程圖描述,3.偽代碼為了便于轉換成某種編程語言，一般采用準程序設計語言作算法描述語言。,偽代碼描述：,BEGIN(算法開始)1=>t2=>iwhileiti+1=>iprinttEND(算法結束),算法兩要素,算法的兩要素算法由操作與控制結構兩要素組成。1.操作(1)邏輯運算：“與”、“或”、“非”；(2)算術運算：加、減、乘、除；(3)數(shù)據(jù)比較：大于、小于、等于、不等于；(4)數(shù)據(jù)傳送：輸入、輸出、賦值。,2.控制結構,1）算法的控制結構，決定了各操作的執(zhí)行次序。用流程圖可以形象地表示出算法的控制結構。2）任何復雜的算法都可以用順序、選擇、循環(huán)三種控制結構組合而成。,我們在構造一個算法的時候，也僅以這三種基本結構作為“建筑單元”，遵守三種基本結構的規(guī)范?；窘Y構之間可以并列、可以相互包含，但不允許交叉。正因為整個算法都由這三種基本結構構成，所以結構清晰，易于驗證，易于糾錯。這種方法就是結構化方法。,算法的特征,有窮性一個算法必須總是在執(zhí)行有窮步后結束，且每一步都可在有窮時間內完成；確定性算法中的每一個指令必須有明確的含義，不能有二義性；例：武松打死老虎歧義手舉過頭頂單手?雙手？舉多高？可行性(有效性)算法中描述的操作都是可通過已經實現(xiàn)的基本運算、執(zhí)行有限次實現(xiàn)的；例：a/b若b=0則無效,輸入一個算法應有0個或多個輸入；輸出一個算法應有1個或多個輸出。,算法的復雜度,求解一個問題可能有多種不同的算法，評價算法的標準主要有：執(zhí)行算法所耗費的時間，即時間復雜度；執(zhí)行算法所耗費的存貯空間，主要是輔助空間，即空間復雜度。,思考：給出一組數(shù)12、13、26、27、38、49、55、60、67、86，查找某一個數(shù)x是否在這組數(shù)中的算法？,的時間復雜度？,常用算法,枚舉法是一種比較笨但卻很有效的算法，他針對問題所有的可能一一查看是不是符合條件，一種情況他都不想落下，有寧可錯殺一千，不可放過一個的作風。,先依據(jù)題目的部分條件確定答案的大致范圍，在此范圍內對所有可能的情況逐一驗證，直到全部情況驗證完。若某個情況使驗證符合題目的條件，則為本題的一個答案；若全部情況驗證完后均不符合題目的條件，則問題無解。,1.枚舉法,例：公雞每只五元，母雞每只三元，小雞三只一元，問百元買百雞有幾種買法？,假設公雞數(shù)為x，母雞數(shù)為y，則小雞數(shù)是100-x-y，也就有了下面的方程式：3*x+5*y+(100-x-y)/3=100從方程式中看出：公雞最多有33只，最少是沒有，即x的范圍是0-33；母雞，即y的范圍是0-20；有了公雞母雞，小雞數(shù)自然就是100-x-y只。,可能的方案一共有34*21種，這些方案中，可能有一種或幾種正好符合相等的條件。我們就將上述34*21種方案全部過濾一遍，找出符合百錢買百雞條件的（也即上式），只要符合，這就是我們要的輸出結果。,2.遞推法,遞推法，就是找出和時間先后相聯(lián)系或和數(shù)的大小相聯(lián)系的步驟，上一步和下一步和數(shù)字的增大或減小有一定的聯(lián)系。我們要么從前向后（或從小到大）推導，也可從后向前（或從大到?。┩茖АＳ纱说贸鰞煞N推導方法：順推法和倒推法。,例：猴子分食桃子一天，一只猴子采得一堆桃子，當天它吃掉一半多一個，第二天又吃了一半多一個一直到第七天，它就剩一個桃子了。那么那天它共采了多少個桃子呢？,找一下天數(shù)和桃子數(shù)的關系。如果從第1天開始往第7天找，不好找，但如果從第7天到第1天去找，可得出下面的推導式：第N天桃子數(shù)目7s7=16s6=(s7+1)*25s5=(s6+1)*21s1=(s2+1)*2,算法：S1:使s=1S2:使t=7S3:使(s+1)2,結果仍然放在變量s中，可表示為(s+1)2sS4:使t的值-1，即t-1tS5:如果t>=1,返回重新執(zhí)行步驟S3以及其后的S4和S5；否則，算法結束。,3.遞歸法,如果一個過程直接或間接地調用它自身，則稱該過程是遞歸的。,遞歸就象我們講的那個故事：山上有座廟，廟里有個老和尚，老和尚在講故事，它講的故事是：山上有座廟，廟里有個老和尚，老和尚在講故事也就是直接或間接地調用了其自身。例：求階乘。,算法：,S1:如果n=1，返回結果1，結束。s2:保存當前階數(shù)n。S2:n-1n，遞歸調用自己，S3:取出當前階數(shù)，計算n*(n-1)!S4:返回計算結果，結束,例：有一個nm的棋盤(2<=n<=50，2<=m0theny=1elseifx=0theny=0elsey=-1endifPrintx,y,幾種高級程序語言,FORTRAN(FormulaTranslator)1954BASIC(BeginnerAllpurposeSymbolicInstructionCode)PascalPROLOG(ProgramminginLogic)C語言，70年代初期C+語言，80年代Java語言，1995年5月,EclipseC#，C#3.0,云計算時代最具潛力的12種編程語言,DART、Ceylon、GO、F#、OPA、Fantom、Zimbu、X10、Haxe、Chapel,2.常見的結構化程序控制,程序設計方法,面向過程(Process-oriented)的程序設計,面向過程的程序設計強調模塊化和結構化。采用自頂向下、逐步求精的程序設計方法；使用三種基本控制結構構造程序。遵循這種方法的程序設計就是面向過程的程序設計。,面向過程的程序設計，在數(shù)據(jù)處理過程中，采用自頂向下、分而治之的方法，將整個程序按功能劃分為幾個可獨立編程的子過程模塊，每一子模塊完成指定的子任務，并且提供一個清晰、嚴格的調用界面，主過程通過調用各子過程完來成全部處理工作。常用軟件：C，F(xiàn)ORTRAN，PASCAL等。,程序分解實例：,面向對象(Object-oriented)的程序設計,什么是對象？,現(xiàn)實世界中,比如書、人、車都是對象。我們怎么區(qū)分它們呢？從組成以及他們的動作行為。比如：人組成：一個腦袋,兩條腿,兩個胳臂動作行為：說話,吃飯,跑步,流淚,對象,對象是存在的具體實體，具有明確定義的狀態(tài)和行為。,類(Class),“類是具有相同屬性和行為的一組對象的集合”,在面向對象編程中，程序被看作是相互協(xié)作的對象集合，通過消息來實現(xiàn)對象間的通訊。,每個對象都是某個類的實例，所有的類構成一個通過繼承關系相聯(lián)系的層次結構。,常用語言：Java、c+、VB.Net等。,在結構化程序設計中可以用下面的式子表示程序：程序=數(shù)據(jù)結構+算法+程序設計語言+語言環(huán)境在面向對象程序設計中可以用下面的式子表示程序：程序=對象+對象+對象對象=算法+數(shù)據(jù)結構+程序設計語言+語言環(huán)境,面向過程：分析出解決問題所需要的步驟，用函數(shù)把這些步驟一步一步實現(xiàn)，使用的時候一個一個依次調用。面向對象：把構成問題事務分解成各個對象，建立對象的目的不是為了完成一個步驟，而是為了描敘某個事物在解決問題中的行為。,例1：有一臺如下流程的演出：主持人開場演員1表演演員2表演主持人總結。用面向過程的思想來分析，就是先完成主持人開場，再完成演員1的表演，再完成演員2的表演，最后完成主持人的總結。如果用面向對象的思想來分析，就是：這個演出由兩大部分組成：主持人、演員。與主持人相關的：開場、總結。與演員相關的：演員編號、所演的節(jié)目。然后這臺演出就可以這樣策劃：需要一個主持人a，需要兩個演員b、c。演出的事情可以表示為：a的開場>b、c的編號和節(jié)目>a的總結。,例2：下五子棋面向過程的設計思路就是首先分析問題的步驟：1、開始游戲，2、黑子先走，3、繪制畫面，4、判斷輸贏，5、輪到白子，6、繪制畫面，7、判斷輸贏，8、返回步驟2，9、輸出最后結果。把上面每個步驟用分別的函數(shù)來實現(xiàn)，問題就解決了。,面向對象的設計思路是，整個五子棋可以分為：1、黑白雙方，這兩方的行為是一模一樣的，2、棋盤系統(tǒng)，負責繪制畫面，3、規(guī)則系統(tǒng)，負責判定諸如犯規(guī)、輸贏等。第一類對象（玩家對象）負責接受用戶輸入，并告知第二類對象（棋盤對象）棋子布局的變化，棋盤對象接收到了棋子的變化就要負責在屏幕上面顯示出這種變化，同時利用第三類對象（規(guī)則系統(tǒng)）來對棋局進行判定。可以明顯地看出，面向對象是以功能來劃分問題，而不是步驟。,功能上的統(tǒng)一保證了面向對象設計的可擴展性。比如我要加入悔棋的功能，如果要改動面向過程的設計，那么從輸入到判斷到顯示這一連串的步驟都要改動，甚至步驟之間的順序都要進行大規(guī)模調整。如果是面向對象的話，只用改動棋盤對象就行了，棋盤系統(tǒng)保存了黑白雙方的棋譜，簡單回溯就可以了，而顯示和規(guī)則判斷則不用顧及，同時整個對對象功能的調用順序都沒有變化，改動只是局部的。,再比如：把五子棋游戲改為圍棋游戲，如果是面向對象的，只需要改寫規(guī)則對象就可以刻；如果是面向過程的，五子棋的規(guī)則分布在程序的每個角落，要改動還不如重寫。,面向過程方法的特點,優(yōu)點：這種程序設計方法算法描述準確。對每一子過程模塊容易進行程序正確性證明。缺點：程序代碼可重用性差。程序中除少數(shù)標準庫函數(shù)外，每設計一個程序時，程序員幾乎從零做起。即使重用代碼，通常也是通過拷貝或編輯重新生成一份。維護程序的一致性困難。前一步修改了導致以后步驟的修改。,OOP方法的特點,OOP以“對象”或“數(shù)據(jù)”為中心。由于對象自然地反映了應用領域的模塊性，因此具有相對穩(wěn)定性，可以被用作一個組件去構成更復雜的應用，又由于對象一般封裝的是某一實際需求的各種成分，因此，某一對象的改變對整個系統(tǒng)幾乎沒有影響。引入了“類”的概念。類與類以層次結構組織，屬于某個類的對象除具有該類所描述的特性外，還具有層次結構中該類上層所有類描述的全部性質，OOP中稱這種機制為繼承。OOP方法的模塊性與繼承性，保證了新的應用程序設計可在原有對象的數(shù)據(jù)類型和功能的基礎上通過重用、擴展和細化來進行，而不必從頭做起或復制原有代碼，這樣，大大減少了重新編寫新代碼的工作量。,面向對象的程序設計方法與面向過程的程序設計方法的比較,（1）以過程為中心構造應用程序，設計出的程序可重用代碼少，且當代碼量增加時維護數(shù)據(jù)和代碼的一致性困難。（2）面向對象程序設計方法中，對象所具有的封裝性和繼承性使得代碼重用成為可能，并大大減少了程序出錯的可能性。（3）面向對象方法吸收了結構化程序設計方法的優(yōu)點，同時引入了新概念、新機制并建立了比傳統(tǒng)方法更高層次的抽象。,4軟件工程,軟件工程是分析、設計、實現(xiàn)、與維護軟件系統(tǒng)的一組規(guī)范，它指導著軟件開發(fā)人員以工程化的手段規(guī)范地開發(fā)高質量的軟件。軟件工程源于軟件危機。,軟件危機-軟件危機的表現(xiàn),成本高美國空軍：1955年軟件占總費用(計算機系統(tǒng))的18%，70年60%，85年達到85。美國全球軍事指揮控制系統(tǒng)，硬件1億美元，軟件高達7.2億美元。軟件和硬件費用比不斷增加我國某軍艦計算機CPU運行850小時，故障120多次，其中軟件占70%。,軟件質量得不到保證軟件越來越多的應用于安全猶關(safetycritical)的系統(tǒng)，對軟件質量提出更高的要求80年代歐洲亞麗安娜火箭的發(fā)射失敗，原因是軟件錯誤美國阿托拉斯火箭的發(fā)射失敗，原因是軟件故障我國某型號導彈，由于軟件問題致使打靶失敗,進度難以控制項目延期比比皆是由于進度問題而取消的軟件項目較常見只有一小部分的項目能夠按期完成維護非常困難軟件維護的多樣性軟件維護的復雜性軟件維護的副作用,產生軟件危機的根源,復雜性高邏輯產品，邏輯復雜性遠高于硬件復雜性軟件的復雜性隨規(guī)模呈指數(shù)級上升規(guī)模大應用擴大，代碼量，1000萬行，仍在不斷膨脹影響軟件生產率和質量的因素比較復雜人員的能力和水平團隊合作缺乏有效、系統(tǒng)原理、原則、方法和工具的指導和輔助,SoftwareEngineeringvs.OtherEngineeringFields傳統(tǒng)工程,Buildingblocks(構件，組件）Roleoftolerances（誤差：傳統(tǒng)工程允許誤差范圍，軟件只有正確與不正確之分）Metrics（度量：傳統(tǒng)工程度量可通過故障的平均時間，而軟件不存在磨損）,對軟件開發(fā)的深層次認識,開發(fā)一個具有一定規(guī)模和復雜性的軟件系統(tǒng)與編寫一個簡單的程序不一樣。正如建設狗窩和高樓大廈大型、復雜軟件系統(tǒng)的開發(fā)是一項工程，必須按照工程化的方法組織軟件的生產和管理，必須經過分析、設計、實現(xiàn)、測試、維護等一系列軟件過程和活動。,軟件工程的目標,軟件工程目標：生產具有正確性、可用性以及開銷合宜的產品。正確性指軟件產品達到預期功能的程度?？捎眯灾杠浖窘Y構、實現(xiàn)及文檔為用戶可用的程度。開銷合宜是指軟件開發(fā)、運行的整個開銷滿足用戶要求的程度。,軟件工程強調使用生存周期方法學和各種結構分析及結構設計技術。,軟件工程方法,在完成生存周期每個階段的任務時，應該采用適合該階段任務特點的系統(tǒng)化的技術方法結構分析或結構設計技術。,生存周期方法學就指從時間角度對軟件開發(fā)和維護的復雜問題進行分解，把軟件生存的漫長周期依次劃分為若干個階段，每個階段有相對獨立的任務，然后逐步完成每個階段的任務。,在每個階段結束之前都從技術和管理兩個角度進行嚴格的審查，合格之后才開始下一階段的工作，這就使軟件開發(fā)工程的全過程以一種有條不紊的方式進行，保證了軟件的質量，特別是提高了軟件的可維護性。總之，采用軟件工程方法論可以大大提高軟件開發(fā)的成功率，軟件開發(fā)的生產率也能明顯提高。,軟件生命周期,某一軟件從被提出并著手開始實現(xiàn)，直到軟件完成其使命為止的全過程被劃分為一些階段，并稱這一全過程為軟件生命周期。通常，軟件生命周期分三個階段：軟件定義、軟件開發(fā)、運行維護。,(1)可行性研究與計劃制定：確定開發(fā)目標和總的要求，給出功能、可靠性等可能方案，制定實施計劃。(2)需求分析：對軟件需求進行分析并給出詳細定義，編寫軟件規(guī)格說明書及初步的用戶手冊，提交評審。,1軟件定義-軟件要“做什么”,(3)系統(tǒng)設計：概要設計和詳細設計，給出軟件的結構、模塊和功能的劃分等。編寫概要設計、詳細設計說明書和測試計劃初稿。(4)詳細設計：源程序編碼，把軟件設計轉換成計算機可以接受的程序代碼。編寫用戶手冊、操作手冊和單元測試計劃。(5)編碼：(6)測試：設計測試用例，檢驗軟件各個組成部分。編寫測試分析報告。,2軟件開發(fā)軟件要“怎么做”,3軟件運行和維護(7)軟件投入運行，維護(進行擴充和刪改)。,TraditionalDevelopmentPhase傳統(tǒng)開發(fā)階段,軟件生命周期的開發(fā)步驟,Analysis分析,AmajorgoalofanalysisistoidentifywhattheproposedsystemshouldaccomplishRequirements（需求）TheneedsofthepotentialusersStatedintermsoftheapplicationratherthaninthetechnicalterminologySpecifications（說明書）Technicaldescriptionsoftherequirements,Design設計,DesignconcentratesonhowthesystemwillaccomplishthegoalssetinanalysisSystemstructureisestablishedindesignThebeststructureisamodularoneModularity（模塊化）Divisionofasoftwareintomanageableunits,eachperformsonlypartoftheoveralltaskModulardecompositionMakestheimplementationoflargesystemspossibleAllowschangestobemadeonamodularbasis,ImplementationandTesting實現(xiàn)和測試,Implementationinvolvestheactualwritingofprograms,creationofdatafiles,anddevelopmentofdatabaseEachmoduleisnormallytestedasitisimplementedStubs（樁模塊）SimplifiedversionsofmodulesusedtotestacertainmoduleFeature（功能）testandloadtestReliabilitygrowthtestandcertificationtest,軟件DevelopmentModels開發(fā)模型RecentTrends趨勢,Waterfall（瀑布模型）Performsanalysis,design,implementation,andtestinginastrictlymannerIncremental（迭代模型）SoftwaresystemisconstructedinincrementsPrototyping（原型法）Incompleteversionsoftheproposedsystem(prototypes)arebuiltandevaluatedEvolutionaryprototyping（演化式原型）Earlyprototypingandthrowawayprototyping（拋棄式原型）,TestingMethodologyBasedonParetoPrinciple（基于Pareto法則的測試方法）,ParetoprincipleTheresultscanoftenbeincreasedmorerapidlybyapplyingeffortsinaconcentratedareaThusasmallnumberofmoduleswithinalargesoftwaresystemtendtobemoreproblematicthantherest,Testing方法,Glass-boxtesting（白盒測試）IdentifyproblematicmodulesBasispathtestingBlack-boxtesting（黑盒測試）Boundary（邊界）valueanalysisApplyredundancy（冗余：兩個公司開發(fā)同一套系統(tǒng)）Betatesting（初始版本）,ExtremeProgramming(XP極限編程),SuitableforateamoflessthanadozenindividualsAdisciplineofsoftwaredevelopmentbasedonvaluesofsimplicity（簡易）,communication（交流）,andcourage12practices,Computer-AidedSoftwareEngineering(CASE)計算機輔助軟件工程,ApplicationofcomputertechnologytothesoftwaredevelopmentprocessitselfProjectplanningtoolsProjectmanagementtools（MicrosoftProject2003、2008）DocumentationtoolsPrototypingandsimulationtoolsInterfacedesigntoolsProgrammingtools(e.g.codegenerator),Documentation文檔,UserdocumentationManualTutorial（指南）InstallationguideReferencemanualHelppackagesSystemdocumentationSourcecodesRecordofspecificationdevelopmentSystemspecifications（說明書）,SoftwareOwnership(所有權）andLiability（責任）,Copyrightlaws（版權法）Literary（文學）worksvs.softwareLookandfeelofasoftwaresystemLotusvs.MosaicPatents（專利）AlongstandingprincipleRSAalgorithm（一種加密算法）TradesecretlawsLiabilitylimitations（有限責任）DisclaimerLevelofcare,作業(yè),第5章：P167:7、12、42第6章：P210：2、21第7章：20、30,