算法分析與設計

AnalysisandDesignofComputerAlgorithms

楊春明YangChunming?西南科學技大學計算機學院?SchoolofComputerScienceandTechnology,SWUST

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