※ [本文转录自 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)其实也一样没用...
随着考虑的问题越来越复杂，会有越来越多需要妥协的部分，
巧妙地做出一些妥协，容许一些误差，让整个问题变得能被解决，
这点在人生中处处受用。惨了我觉得我越来越像业配
最后，一句话总结这门课
“既不凉亦不甜，但保证有让人不在意凉甜的收获。”