※ [本文轉錄自 NTUcourse 看板 #1OYGflQB ]
作者: arsenefrog (柯蛙) 看板: NTUcourse
標題: [評價] 102-1 104-1 105-1 陳和麟 演算法
時間: Thu Jan 26 04:28:25 2017
※ 本文是否可提供臺大同學轉作其他非營利用途？（須保留原作者 ID）
（是／否／其他條件）：是
哪一學年度修課：102-1 104-1 105-1
我自己接觸了這堂課三次，後面兩次是以TA的身分。
雖然這門課其實沒什麼變，也已經有幾篇現有的評價文，
但有感這兩年課堂中外系學生人數明顯增加，
以及觀察到修課的同學通常會遇到什麼問題，
覺得可以以不同的角度來寫一篇不設限對象的評價文。
ψ 授課教師 (若為多人合授請寫開課教師，以方便收錄)：陳和麟 大神
λ 開課系所與授課對象 (是否為必修或通識課 / 內容是否與某些背景相關)
電機系/所選修(可能將變為必修)、電子所EDA組二選一必修
δ 課程大概內容
以下是老師提供的syllabus，每年都99%像
‧Mathematic Tools：
Asymptotic Notations、Recurrence Relations
這一段就是必要的數學工具，大約會占兩到三週的內容。
雖然演算法嚴格來說並不是很數學的一門學問，
但在這裡可能會帶來這種錯覺，因為相關的定義和證明都相當嚴謹。
這一段的數學其實不是很需要基礎，
懂一般程度的微積分會有幫助，但相較之下邏輯概念更為重要。
對抽象數學苦手的話，前面就會過得有點痛苦，
但在接下來的課程中，這段的東西雖然非常重要，
但都只會用到概念，相關的細節沒學通倒不至於造成太大問題。
對有志修這門課的同學來說，這一段是個人認為很適合先預習的部分。
這兩個關鍵詞在一般的離散數學教科書裡面都會詳細介紹，
網路上也有極多的參考資料。
這一段先預習過的話，至少前幾週的課程會比較不容易迷失方向。
‧Algorithm Design Techniques：
Divide and Conquer、Sorting and Order Statistics、
Greedy Algorithms、Dynamic Programming
這一段是一些經典的演算法設計技巧，每個標題大概都是一週左右。
對每種技巧，都會舉出幾個應用的範例，
會把演算法講得較為詳細，包括效率分析和正確性的部分。
前幾週的數學會在這邊每個演算法的效率分析派上用場。
從這裡開始課程就會變得更為有趣一點，
因為會認識到各種有效解決問題的精妙方法。
從這邊老師上課的描述，也會大略認知到怎樣完整的定義一個演算法，
以及為什麼需要發展這些演算法。
前兩個標題大概對應作業一，後兩個大概對應作業二。
以上為期中考的範圍。
‧Data Structures：
Basic Data Structures、Heaps、Hash Tables
這一段大概會是期中考前一兩週開始到期中考後一兩週結束。
和學期初一開始的數學工具很像，教資料結構是因為後面會用到。
因為教的時候接近期中考(而且不考)，加上內容有點繁雜，
可能在這一段會突然有茫然不知頭緒之感，會有點驚慌。
不過也跟前面的數學工具一樣，之後用到的時候並不會那麼複雜，
其實助教每年也都會把Fibonacci Heap的細節忘得一乾二淨(遮臉)。
‧Graph Algorithms：
Search、Minimum Spanning Tree、Shortest Path、Max Flow/Min Cut
下半學期的重頭戲就是各種定義在圖(graph)上面的問題和演算法。
這裡因為會用到圖的概念，修過離散數學會有一些幫助。
這裡的每個部分都會先定義問題，然後講解幾種相關的演算法。
個人覺得這裡釐清問題本身也很重要，
釐清各問題間的差異，有助於避免迷失在各種奇怪名字的演算法中。
大約也是一週就會講完一個問題+兩三個相關的演算法，
且因為這些演算法相較於期中考前，顯得更為精妙複雜一些，
這一段非常建議要以良好狀態認真聽課。
大約也是對應到作業三/四的內容。
‧Advanced Topics：
NP-Completeness、Approximate Algorithms、Randomized Algorithms
NP完全性質可以說是這門課的大魔王，
如果沒有在前一個部分失去戰鬥能力的話，會發現這部分相當有趣。
後面兩個主題則是比較接近補充的進階教材，
在這門課中只會簡略提到，甚至進度太趕會來不及上到。
(但今年老師又開了高等演算法這門在學校已經失傳好多年的課，
裡面應該會有不少相關內容)
Ω 私心推薦指數(以五分計) ★★★★★
第一次修完課的時候覺得是五分，現在覺得是十分。客觀來說的話，
覺得解決問題很有趣 ★★★★★★★★★★
想學各種演算法的概念 ★★★★★
比起理論，只喜歡實作 ★★★
討厭被要求寫嚴謹的數學證明 ★
老師在每學期的第一堂課都會說明，學演算法絕對包含為了樂趣！
這門課最大的特色就是它是純理論課，完全不含實作成分，
即使要設計演算法也只需要紙上談兵即可。
但卻是一點都不馬虎的紙上談兵，特別是牽涉到數學的時候。
個人覺得這門課還是極佳的思考訓練，能讓頭腦變得更清楚，
是少數電機系課程中有如同數學系的理論課一樣效果的。
η 上課用書(影印講義或是指定教科書)
其實沒有。指定閱讀是那本演算法聖經，但幾乎不會用到。
用到的時機1：連老師都不想講的細節，通常在書裡面找得到。
用到的時機2：助教被問倒的時候會翻書找答案。
μ 上課方式(投影片、團體討論、老師教學風格)
老師會將累積好幾年的筆記以板書的方式反芻給同學，英文授課。
因此，每年的內容都是架構幾乎相同、細節上則有增減，
每位修課同學要負責抄寫一週的共筆，提供複習用。
由於修課人數穩定破百，每週都會有許多份的筆記，
其中不乏字美圖美甚至latex排版之傑作。
然而看筆記完全無法取代聽老師講課，
不單是因為複雜的演算法很難光從較為簡略的筆記看懂，
而是因為老師在解釋概念的部分真的非常厲害。
除了英語幾乎沒有口音、口條也很清楚之外，
老師擁有3分鐘讓人理解自己要花3小時搞懂的概念的能力。
此外老師每堂課都留下來回答同學的問題到很晚，
與學生互動也非常親切，幾乎不會有距離感，
有心的話真的可以從老師身上學到非常多。
σ 評分方式(給分甜嗎？是紮實分？)
ρ 考題型式、作業方式
如同前述，這門課有四次主要的手寫作業。
手寫作業方面，允許討論並且鼓勵討論(相較於放棄而言)
交作業時必須註明和討論的對象。
題目都相當有深度，特別是後期的演算法設計，
基本上想到關鍵之後都會非常簡單，但想到關鍵點本身則是相對困難的。
非常建議即使是參考他人的想法，也要搞懂想法之後全部自己寫，
雖然老師有要求這點，但還是不少人註明了大神後就照抄大神的作業內容。
如果作業一直都是照抄的話，雖然作業拿得到分數，但考試的下場就會非常慘。
考試的題型和作業相仿，基本上期中期末考就類似一份作業的量。
雖然題型和難度都和作業差不多，但考試不能討論，
而且應該很少人可以三小時解決一份作業，所以還是很有挑戰性。
作業不調分但是給分非常大方，雖然不能詳細說但是反正真的很大方，
老師希望大家都能花時間思考這些有趣的問題，沒想出來也沒關係。
相對之下考試就是嚴格把關，方向搞錯很容易會失去整題的分數。
隨著老師不斷想出有挑戰性的題目，
考試的原始分數平均從幾年前曾有到60左右，到最近剩不到40，
不過所有人的考試成績會統一調到平均70幾。
作業占40%，兩次考試占30%(直接以調分後的分數計)，
此外有時還有加分用的小作業、以及一些額外的補救機制，
故只有要付出努力，其實要通過是相當容易的。
但只想得到學分的話仍然不推薦，
因為與其什麼都沒學會、考試寫不出來、最後被老師大方的調過
不如去修更涼更甜的課，這樣助教可以少改一點擺爛的作業跟考卷XD
對認真跟上全部進度的同學來說，
收穫和成就感應該會超過所有原始分數上的不如意，
最後等第出來可能還會再獲得驚喜。
ω 其它(是否注重出席率？如果為外系選修，需先有什麼基礎較好嗎？老師個性？
加簽習慣？嚴禁遲到等…)
來者不拒，也完全不點名，但是沒上到課除了比較沒效率之外，還很可惜。
知道我身分的話，其實我是非常不愛聽課的人，
但認真覺得老師的課堂是電機系最值得出席的幾門之一。
提到基礎，如同課程內容那邊有講過，
基礎微積分概念、離散數學、資料結構 都會有幫助。
但完全沒有也是可行的，碰到的時候老師還是會再提，
只是也許需要多一點摸索和自學的時間。
值得一提的是，雖然這門課不寫程式，但是有學過程式設計還是會比較適當，
完全沒接觸過迴圈、遞迴、函式這種基本概念的話，
也會需要更多摸索和消化的時間。
這門課即使以上基礎全部缺乏還是能學到很多，
但每多具備一些，能夠更領略到的部分(或機會)就越大。
雖然沒有任何一定必須組隊的活動，
找隊友一起討論、或在課堂上認識隊友應該比單打獨鬥收穫更多。
Ψ 總結
雖然我的立場是嚴重偏好評(XD)，
但據我的了解，還沒有人真的負評過這門課，
老師也剛拿到教學傑出獎，代表大家對這門課應該是頗為肯定的。
最常聽到的抱怨是上課內容/作業好難，聽不懂/想不出來。
雖然演算法這門學問有時候真的蠻玄的，
但也曾遇過一些同學是因為誤會了一些關鍵概念，或沒有抓到重點，
稍微澄清之後就一切順利。
相當建議在遇到瓶頸時找助教討論，想不出來的題目可能會獲得提示，
另外也有用中文解釋上課內容的功能，雖然品質絕對有差。
反正我應該不會再當這門課的助教了所以做這個建議無壓力XD
100個人對演算法的內容可能會有100種不同的解讀，
後兩年從和同學們的討論中，我也獲益非常多。
不乏一些細節是第一次學覺得懂了、第二次解釋時又有完全不同的體會。
最後想提的一點是，
「如果不是為了要學演算法，還可以從這門課獲得什麼？」
- For Fun!
相信老師希望課程內容能夠引發同學的興趣，
而在聽課的過程中，就很容易可以發現老師本人真的覺得這些內容很有趣。
就算往後的人生真的用不到好了，
思考怎麼解決問題，本身就是一件非常好玩的事。
- Get Creative
老師設計的題目，都沒有困難到要學生憑空造出新的演算法概念。
絕大多數的情形下，是透過一些有創意的修改，
讓上課教過的演算法能應用在更難、或不一樣的問題之上。
有時候，發揮創意的方法不只一種，
偶爾也會有同學想到了老師沒預料過的做法。
即使天馬行空的想法最後不一定正確，但是透過這個激盪過程，
思考可以變得更為靈活。
- Get realistic
雖然老師其實是個大理論派，但演算法終究是一門解決實際問題的學問
很多時候都必須跟現實妥協
Ex: 雖然polynomial time很棒，但O(n^8)其實也一樣沒用...
隨著考慮的問題越來越複雜，會有越來越多需要妥協的部分，
巧妙地做出一些妥協，容許一些誤差，讓整個問題變得能被解決，
這點在人生中處處受用。慘了我覺得我越來越像業配
最後，一句話總結這門課
「既不涼亦不甜，但保證有讓人不在意涼甜的收穫。」