计算方法设计与分析

1、計算方法設計與分析Design and Analysis of AlgorithmsE-mail: 1什麼是 Algorithm ?A number of rules, which are to be followed in a prescribed order, for solving a specific type of problems.Computer Algorithm的額外考慮：Finiteness（有限個steps）Definiteness（每一個step做的事確定）Effectiveness（不只確定還要足夠的短能做完）Input/Output（O.S.永不terminate只

2、能稱是computational procedure）2Algorithm is everywhere !Operating SystemsSystem ProgrammingNumerical ApplicationsNon-numerical Applications：任何一field都要用Algorithm去解決該field所發生的問題。Algorithm Implement的方式：SoftwareHardwareFirmware3教科書：Introduction to the Design and Analysis of Algorithms A STRATEGIC APPROACH（

3、李家同）參考書：1. Cormen, Leiserson, Rivest: Introduction to Algorithms（開發）2. Horowitz and Sahni:Fundamentals of Computer3. Brassard & Bratley:Algorithmics（新月）4評估方式作業： 30%考試 x 2：70% (30%+40%)期末額外加分：10%（理解&創造）有創意的小報告找到書本上的錯不定時定額加分 -_-|5此次課程共有4次作業，每次作業占總成績7.5%，總共作業成績占總成績30%作業於上課前繳交給助教，若遲交(含課後)一次則分數折半作業將會於考試前

4、發還給同學，且考試內容與作業相關，所以請大家務必準時交以下為作業繳交日期3/23(二)、4/15(四)、5/18(二)、6/10(四)作業6考試內容與作業有相關，所以請好好寫作業如果老師上課有臨時出小題目給大家寫，有可能是考試的類題作答時請務必寫清楚自己的想法，助教會斟酌給分以下是考試日期（暫定）4/27(二)、6/22(二)考試7Office hour : Thu 13:1015:00Place :光復中學5F 5-12如果同學有問題想問，請同學先寄信告知問題課程網頁()，之後若有臨時事項將會公布於此 其他相關事項8Background for learning1. 一個清楚的頭腦2. Da

5、ta Structures3. Discrete Mathematics4. 用功Requirements for researching：1. 勤讀papers2. 一個叛逆的個性3. 藝術家似的創造慾望均可培養9為什麼要學Algorithm ?1. 如果不學，你可能用一個很花錢（Time, Space）的Algorithm去解決問題Life-time Job:永遠知道解某一問題最佳的Algorithm是什麼方法：對於自己的領域隨時要查paper，update最佳的algorithms或至少知道可以問誰。10為什麼要學Algorithm ?2. 如果不學，你可能去對NP-Complete的問

6、題去找efficient的解Life-time Job:去知道那些問題是NP-Complete的Real ApplicationAverage Performance好的找Approximating的解TSP：n = 20 771世紀N3log n in average (B & B)Planar Graph Coloring (Maximum # = 4 已被證明)11Outline1. Introduction2. Lower Bounds (Complexity)3. NP-Completeness4. Greedy Method5. Divide-&-Conquer Strategy6

7、. Prune-&-Search Strategy7. Dynamic Programming Strategy8. Branch-&-Bound Strategy9. Approximate Algorithms10. Randomized Algorithms11. Amortized Analysis12. On-line Algorithms12One can find good papers on algorithmsActa InformaticaAlgorithmicaAnnual Symposium on Foundations of Computer ScienceBITCo

8、mmunications of the ACMComputer JournalIEEE Transactions on ComputersInformation and ControlInformation Processing LettersInformation Science13One can find good papers on algorithms (Cont.)International Journal of Computer and System ScienceInternational Journal of Computer MathematicsJournal of AlgorithmsJournal of Parallel and Distributed ComputingJournal of the