演算法設計與分析|系統性的思維|楊昌彪

2月11日 16:48
一、簡介 ▎學校:國立中山大學 ▎課程:演算法設計與分析 (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表單,來線上隨堂問答。答錯不太會影響成績,因為主要是拿來點名用的。坦白說,有了線上問答,的確印象會比較深刻(◉3◉)。老師也說,上課睡覺的同學,好像也變少了。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)。 ▎相關文章 1. 演算法設計與分析|系統性的思維|楊昌彪
2. Voronoi Diagram 1:軟體使用說明
3. Voronoi Diagram 2:程式設計
4. Voronoi Diagram 3:實驗結果
5. Voronoi Diagram 4:結論與心得
6, VoronoiDiagram source code
11
留言 2
文章資訊
85 篇文章302 人追蹤
Logo
這裡是專屬於中山大學的版面。
共 2 則留言
匿名
此帳號疑似異常
官方正在進行身份確認
業配
b1 我也希望這是業配😥😥😥