1算法分析與設(shè)計

算法分析與設(shè)計

AnalysisandDesignofComputerAlgorithms

楊春明YangChunming?西南科學(xué)技大學(xué)計算機(jī)學(xué)院?SchoolofComputerScienceandTechnology,SWUST

2009年8月/algorithm/?SchoolofComputerScienceandTechnology,SWUST2WhoisYangChunming?InstructorofSWUSTTel:608935713881194177Office:東6E401 QQ:4879687Email:mryangforstu@教學(xué)主頁：/index.php?blogId=3課程網(wǎng)站：/algorithm/課程練習(xí)及考核：:8080/JudgeOnline網(wǎng)絡(luò)答疑：/modules/newbb/viewforum.php?forum=12課程教學(xué)方案注重實踐和過程課程考核方案：考核由算法設(shè)計與實現(xiàn)（程序設(shè)計）、課程報告和出勤三部分構(gòu)成，分別占70%、20%和10%。算法設(shè)計與實現(xiàn)：平時課程教學(xué)過程中在JudgeOnline平臺完成。課程報告：課程結(jié)束后開始。出勤：上課的出勤情況，缺席一次扣2分，扣完為止。/algorithm/?SchoolofComputerScienceandTechnology,SWUST3課程教學(xué)方案（續(xù)）課程考核——算法設(shè)計與實現(xiàn)每次時間為一周到兩周，完成后判斷代碼雷同，如果雷同率超過85%，則視為抄襲，作0分處理。/algorithm/?SchoolofComputerScienceandTechnology,SWUST4順序時間覆蓋內(nèi)容分值題目難度第一次第二~三周第一至三章中的經(jīng)典算法15分3~5容易第二次第五~六周分治策略、減治法、變治法20分5~8容易，中等第三次第八~九周時空權(quán)衡、動態(tài)規(guī)劃15分3~5中等，難第四次第十~十一周貪心策略、回溯20分4~6中等，難/algorithm/?SchoolofComputerScienceandTechnology,SWUST5課程教學(xué)方案（續(xù)）:8080/JudgeOnline/登陸OnlineJudge注冊/algorithm/?SchoolofComputerScienceandTechnology,SWUST6程序雷同判斷/algorithm/?SchoolofComputerScienceandTechnology,SWUST7執(zhí)行效果2007年：實踐考核40%，分5次進(jìn)行，期末考試60%，共計93人作業(yè)一作業(yè)二作業(yè)三作業(yè)四作業(yè)五提交人數(shù)6653554339完成總數(shù)3371961997172平均/人5.113.703.621.651.852008年：課程考核由過程（70%）、課程報告（20%）、出勤（10%）三部分組成。過程考核共計4次，共計20題，其中11題選做。51人。提交比例雷同滿分比列考核14384.31%223466.67%考核24588.24%63262.75%考核33976.47%303670.59%考核43874.51%63160.78%執(zhí)行情況2009年：考核方式與2008年相同，82人。過程考核統(tǒng)計表/algorithm/?SchoolofComputerScienceandTechnology,SWUST8提交比例雷同比例滿分比列考核17793.90%22.60%7192.21%考核27692.68%56.58%6686.84%考核37793.90%1012.99%6483.12%考核47895.12%56.41%6076.92%分?jǐn)?shù)段<6060~6970~7980~8990~100人數(shù)3771550比例3.66%8.54%8.54%18.29%60.98%/algorithm/?SchoolofComputerScienceandTechnology,SWUST9AboutAlgorithm課程主要介紹計算機(jī)算法分析、算法設(shè)計及復(fù)雜性理論的基本概念、基本的算法分析方法和常用的算法設(shè)計方法。目標(biāo)：掌握計算機(jī)算法分析的基本方法及常見算法設(shè)計方法訓(xùn)練邏輯思維利用常見的算法設(shè)計方法解決軟件開發(fā)中的實際問題先修課程：離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)、高級程序設(shè)計語言。/algorithm/?SchoolofComputerScienceandTechnology,SWUST10為什么要學(xué)習(xí)算法？算法不僅是計算機(jī)科學(xué)的一個分支，它更是計算機(jī)科學(xué)的核心，而且，可以毫不夸張地說，它和絕大多數(shù)的科學(xué)、商業(yè)和技術(shù)都是相關(guān)的?！狣avidHarel《算法：計算的靈魂》程序=數(shù)據(jù)結(jié)構(gòu)+算法開發(fā)人們的分析能力作為一種技術(shù)的算法一個人只有把知識教給“計算機(jī)”，才能“真正”掌握它。算法可以解決哪些問題找出人類DNA中所有100000中基因，確定構(gòu)成人類DNA的30億種化學(xué)基對的各種序列?？焖俚卦L問和檢索互聯(lián)網(wǎng)數(shù)據(jù)電子商務(wù)活動中各種信息的加密及簽名制造業(yè)中各種資源的有效分配確定地圖中兩地之間的最短路徑各種數(shù)學(xué)、幾何計算（矩陣、方程、集合）/algorithm/?SchoolofComputerScienceandTechnology,SWUST11/algorithm/?SchoolofComputerScienceandTechnology,SWUST12ContentsofAlgorithm算法基礎(chǔ)(Foundations)算法基本概念算法效率分析基礎(chǔ)算法設(shè)計及分析技巧蠻力法分治法(DivideandConquer)減治法變治法時空權(quán)衡動態(tài)規(guī)劃(DynamicProgramming)貪婪技術(shù)(GreedyAlgorithm)回溯法(BackTracking)/algorithm/?SchoolofComputerScienceandTechnology,SWUST13References[1]算法設(shè)計與分析基礎(chǔ)(第2版).（美）AnanyLevitin著，潘彥譯.北京：清華大學(xué)出版社.2007年1月[2]ThomasH.Cormen等著，潘金貴等譯.算法導(dǎo)論（第二版）.機(jī)械工業(yè)出版社.2006年9月[3]C算法（第二卷圖算法）（第三版）（中文版）人民郵電出版社2004年4月[4]盧開澄（2000），《計算機(jī)算法導(dǎo)引》，清華大學(xué)出版社[5]算法設(shè)計與分析.王曉東.清華大學(xué)出版社.2003年1月/algorithm/?SchoolofComputerScienceandTechnology,SWUST14HowtoStudyAlgorithm？“Sometimeswehaveexperiences,andsometimesnot.Therefore,thebetterwayistolearnmore."/algorithm/?SchoolofComputerScienceandTechnology,SWUST15Chapter1IntroductiontoAlgorithmsWhat’sanAlgorithm?算法是一系列解決問題的清晰指令，也就是說，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時間內(nèi)獲得所要求的輸出。AlgorithmQuestion/algorithm/?SchoolofComputerScienceandTechnology,SWUST16算法的幾個要點(diǎn)算法的每一個步驟都必須清晰、明確。算法所處理的輸入的值域必須仔細(xì)定義。同樣的一個算法可以用幾種不同的形式來描述?？赡艽嬖趲追N解決相同問題的算法。針對同一個問題的算法可能會基于完全不同的解題思路，而且解題的速度也會有明顯區(qū)別。/algorithm/?SchoolofComputerScienceandTechnology,SWUST17Example求兩個正整數(shù)m,n的最大公約數(shù)gcd(m,n)歐幾里得算法基于的方法是重復(fù)應(yīng)用下列式子，直到mmodn=0gcd(m,n)=gcd(n,mmodn)gcd(m,n)的歐幾里得算法第一步：如果n=0，返回m的值作為結(jié)果，結(jié)束；否則進(jìn)入第二步第二步：用n去除m，將余數(shù)賦給r。第三步：將n的值賦給m，將r的值賦給n，回第一步。算法Euclid(m,n)//使用歐幾里得算法計算gcd(m,n)//輸入：兩個不全為0的非負(fù)整數(shù)m,n//輸出：m，n的最大公約數(shù)Whilen!=0dormmodnmnnrReturnm同一個算法有不同的表達(dá)方式/algorithm/?SchoolofComputerScienceandTechnology,SWUST18Examplegcd(m,n)的連續(xù)整數(shù)檢測算法第一步：將min{m,n}的值賦給t。第二步：m除以t，如果余數(shù)為0，則進(jìn)入第三步；否則，進(jìn)入第四步。第三步：n除以t，如果余數(shù)為0，則返回t值作為結(jié)果；否則，進(jìn)入第四步。第四步：把t的值減1。返回第二步。gcd(m,n)的中學(xué)計算算法第一步：找到m的所有質(zhì)因數(shù)。第二步：找到n的所有質(zhì)因數(shù)第三步：從第一步和第二步中求得的質(zhì)因數(shù)分解式找出所有的公因數(shù)第四步：將第三步中找的質(zhì)因數(shù)相乘，其結(jié)果作為給定數(shù)字的最大公因數(shù)。同一個問題有不同的解決方法/algorithm/?SchoolofComputerScienceandTechnology,SWUST19算法問題求解基礎(chǔ)算法是問題的程序化解決方案。理解問題決定：計算方法；精確和近似的解法；數(shù)據(jù)結(jié)構(gòu)；算法設(shè)計技術(shù)；設(shè)計算法正確性證明分析算法根據(jù)算法寫代碼/algorithm/?SchoolofComputerScienceandTechnology,SWUST20算法問題求解基礎(chǔ)理解問題設(shè)計算法前做的第一件事情仔細(xì)閱讀問題的描述提出疑問手工處理一些實例考慮特殊情況確定輸入抽象出問題，用數(shù)學(xué)表達(dá)式描述/algorithm/?SchoolofComputerScienceandTechnology,SWUST21算法問題求解基礎(chǔ)了解計算設(shè)備的性能確定計算方法RAM結(jié)構(gòu)下的順序算法并行算法選擇精確解和近似解某些重要的問題無法求得精確解某些問題利用精確解速度慢，無法接受/algorithm/?SchoolofComputerScienceandTechnology,SWUST22算法問題求解基礎(chǔ)確定適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)算法+數(shù)據(jù)結(jié)構(gòu)=程序算法設(shè)計技術(shù)使用算法解題的一般性方法，用于解決計算領(lǐng)域的多種問題。詳細(xì)表述算法的方法自然語言偽代碼流程圖/algorithm/?SchoolofComputerScienceandTechnology,SWUST23算法問題求解基礎(chǔ)證明算法的正確性證明對于每一個合法的輸入，該算法都會在有限的時間內(nèi)輸出一個滿足要求的結(jié)果。一般方法：數(shù)學(xué)歸納法證明算法的正確性與不正確哪一個更容易？分析算法算法有兩種效率：時間效率和空間效率算法的另外兩個特性：簡單性和一般性/algorithm/?SchoolofComputerScienceandTechnology,SWUST24算法問題求解基礎(chǔ)為算法寫代碼用計算機(jī)程序?qū)崿F(xiàn)算法在把算法轉(zhuǎn)變?yōu)槌绦虻倪^程中，可能會發(fā)生錯誤或者效率非常低作為一種規(guī)律，一個好的算法是反復(fù)努力和重新修正的結(jié)果算法是一個最優(yōu)性問題：對于給定的問題需要花費(fèi)多少力氣（資源）？是不是每個問題都能夠用算法的方法來解決？發(fā)明或者發(fā)現(xiàn)算法是一個非常有創(chuàng)造性和非常