一、簡介
- 學校：國立中山大學
- 課程：演算法設計與分析 (Algorithm Design and Analysis)
- 教授：楊昌彪
- 系所：資訊工程所
- 學分：3學分
- 學期：110-1
- 宗宗的學期總成績：A+(94)
二、評分
- 作業：25%
- 程式實作：25%
- 期末考：40%
- 其他(含上課表現、出席狀況等)：10%
- 修課必要條件：CPE一次二題或UVA Online Judge題目庫二星以上至少五題於開學二週內完成
作業是手寫習題，以證明題居多，一章節有2~8小題，習題題目在楊老師網頁中可以下載，每交完一章的兩週後要交出來。程式實作的部分使用分治法 (Divide and conquer)實作Voronoi Diagram，實做的要求與評分標準都在楊老師的網頁中。Voronoi Diagram會有兩次驗收，分別為初測與完測，初測佔20分，完測佔60分。初測直接用暴力法解三點，即可輕鬆拿20分。完測如果能夠正確解公開測資，基本上可以拿40~50分，我程式這部分就拿70分 (20+50)。
最後只有期末考，老師網頁上有期末考考古與參考答案，基本上把老師上課中的必考演算法與證明題練熟，並寫完近五年的考古題，應該可以拿到60基本分。至少我寫了五年以上的考古，最後拿了78分，不過證明要全拿不容易，因為要寫完整，不完整老師會斟酌給分。
三、老師評價
 |
| 楊昌彪老師 |
楊老師評價我在中山資工所找教授這篇文章有寫過，這邊我會講一下上課的情形。整體教課步調是慢的，畢竟是教演算法，如果教太快，學生應該很難吸收。然後老師上課第一句是向大家問早٩(◦`꒳´◦)۶，接下來會快速複習上週教的內容，最後才是進入進度。
老師會希望能和學生互動，所以這學期嘗試使用Google表單，來線上隨堂問答。答錯不太會影響成績，因為主要是拿來點名用的。坦白說，有了線上問答，的確印象會比較深刻(◉３◉)。老師也說，上課睡覺的同學，好像也變少了。PPT整理的很精簡，圖文並茂，然後也可以搭配參考書一起看。
然後老師會講一些笑話！？像是：數學家與科學家的差別，數學家比較重視理論，科學家比較重視實作，所以我們要當科學家(́=◞౪◟=‵)。還有第九章bin packing problem時，應該會講到曬衣竿，如果曬衣竿上的衣服滿了怎麼辦？嘿嘿，我就不爆雷了～
四、課程分析
課程大綱
The Complexity of Algorithms and the Lower Bounds of Problems、Greedy Method、Divide-and-Conquer Strategy、Tree Searching Strategies、Prune-and-Search、Dynamic Programming、Theory of NP-completeness Approximation Algorithms、Amortized Analysis、Randomized Algorithms
楊老師的網頁上有放上課的PPT與影片，所以可以直接看到課程的內容。這門課主要是設計與分析演算法，所以是偏理論的課程。如何計算時間複雜度？是一個重要的議題，因為我們經常會用時間複雜度來評估演算法的效能（好壞），尤其是遞迴的時間複雜度，是經典考題。
還會介紹數個常見的演算法類型：貪婪 (Greedy)、分治 (Divide-and-Conquer)、樹狀搜索 (Tree Searching)、剪枝 (Prune)、動態規劃 (Dynamic Programming)。
最後少不了大家都很害怕的NP-C、近似率 (approximation rate)、分攤時間 (amortized time)的證明，NP-C和近似率幾乎是期末必考。NP-C為NP和NP-Hard的交集，所以如果能證明此問題既是NP也是NP-Hard，就能說此問題是NP-C。證明為NP不難，所以證明為NP-Hard就是關鍵。令B問題為NP-C，如果我們能證明B可以還原成 (reduce)A，則可以說A是NP-Hard，因為A比B困難。
然後再證明B reduce A時，我們會寫出B和A的實例以及證明若B有解則A有解，和若A有解則B有解。證明時，我們是以是非題 (decision problem)的角度去證明的，也就是以實例的角度去證明的，所以會看到B decision problem reduce A decision problem的形式。
隨機化算法（randomized algorithm）這學期沒有時間教到，不過也是以證明最壞事件機率為主，並非是介紹這類的演算法。很多超啟發式演算法 (metaheuristic algorithm)都是這類的演算法，且解決的問題是是非題 (decision problem)，如：基因演算法 (genetic algorithm, GA)。
留言
張貼留言