1、計(jì)算方法設(shè)計(jì)與分析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（有限個(gè)steps）Definiteness（每一個(gè)step做的事確定）Effectiveness（不只確定還要足夠的短能做完）Input/Output（O.S.永不terminate只

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

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

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

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

6、題去找efficient的解Life-time Job:去知道那些問題是NP-Complete的Real ApplicationAverage Performance好的找Approximating的解TSP：n = 20 771世紀(jì)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