計算方法設計與分析 Design and Analysis of Algorithms 唐傳義 E-mail: cytang@cs.nthu.edu.tw http://algorithm.cs.nthu.edu.tw/~course/

什麼是 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只能稱是 computational procedure）

Algorithm is everywhere ! Operating Systems System Programming Numerical Applications Non-numerical Applications ： 任何一field都要用Algorithm去解決該field 所發生的問題。 Algorithm Implement的方式： Software Hardware Firmware

教科書： Introduction to the Design and Analysis of Algorithms – A STRATEGIC APPROACH（李家同…） 參考書： 1. Cormen, Leiserson, Rivest: Introduction to Algorithms（開發） 2. Horowitz and Sahni: Fundamentals of Computer 3. Brassard & Bratley: Algorithmics（新月）

評估方式 作業： 30% 考試 x 2：70% (30%+40%) 期末額外加分：10% （理解&創造） 有創意的小報告 作業： 30% 考試 x 2：70% (30%+40%) 期末額外加分：10% （理解&創造） 有創意的小報告 找到書本上的錯—不定時定額加分 -__-||

作業 此次課程共有4次作業，每次作業占總成績7.5%，總共作業成績占總成績30% 作業於上課前繳交給助教，若遲交(含課後)一次則分數折半 作業將會於考試前發還給同學，且考試內容與作業相關，所以請大家務必準時交 以下為作業繳交日期 3/23(二)、4/15(四)、5/18(二)、6/10(四)

考試 考試內容與作業有相關，所以請好好寫作業 如果老師上課有臨時出小題目給大家寫，有可能是考試的類題 作答時請務必寫清楚自己的想法，助教會斟酌給分 以下是考試日期（暫定） 4/27(二)、6/22(二)

其他相關事項 Office hour : Thu 13:10~15:00 Place :光復中學5F 5-12 如果同學有問題想問，請同學先寄信告知問題 課程網頁(http://algorithm.cs.nthu.edu.tw/~course/)，之後若有臨時事項將會公布於此

Background for learning 1. 一個清楚的頭腦 2. Data Structures 3. Discrete Mathematics 4. 用功 Requirements for researching： 1. 勤讀papers 2. 一個叛逆的個性 3. 藝術家似的創造慾望 ★均可培養

為什麼要學Algorithm ? 1. 如果不學，你可能用一個很花錢（Time, Space）的Algorithm 去解決問題 Life-time Job: 永遠知道解某一問題最佳的Algorithm是什麼 方法：對於自己的領域隨時要查paper，update最佳的algorithms或至少知道可以 問誰。

為什麼要學Algorithm ? 2. 如果不學，你可能去對NP-Complete的問題去找efficient的解 Life-time Job: 去知道那些問題是NP-Complete的 Real Application Average Performance好的 找Approximating的解 TSP： n = 20 771世紀 N3log n in average (B & B) Planar Graph Coloring (Maximum # = 4 已被證明)

Outline 1. Introduction 2. Lower Bounds (Complexity) 3. NP-Completeness 4. Greedy Method 5. Divide-&-Conquer Strategy 6. Prune-&-Search Strategy 7. Dynamic Programming Strategy 8. Branch-&-Bound Strategy 9. Approximate Algorithms 10. Randomized Algorithms 11. Amortized Analysis 12. On-line Algorithms

One can find good papers on algorithms Acta Informatica Algorithmica Annual Symposium on Foundations of Computer Science BIT Communications of the ACM Computer Journal IEEE Transactions on Computers Information and Control Information Processing Letters Information Science

One can find good papers on algorithms (Cont.) International Journal of Computer and System Science International Journal of Computer Mathematics Journal of Algorithms Journal of Parallel and Distributed Computing Journal of the ACM Networks Parallel Computing SIAM Journal on Computing Theoretical Computer Science International Journal of Parallel Programming