※ [本文转录自 neoneon 信箱] 作者: [email protected] ("爱宕有机奈米负离子猫") 标题: [心得] 蔡锡钧 演算法 时间: Sun Jul 10 11:48:54 2016 作者: philo165 (老实种田人) 看板: NCTU-Teacher 标题: [心得] 蔡锡钧 演算法 时间: 2013/02/15 Fri 21:54:27 （按Ctrl+v 预览，稍微修一下版面，可让你这篇文章更专业喔^^） ⊕课名⊕ 演算法 ▲教授▲ 蔡锡钧 http://people.cs.nctu.edu.tw/~sctsai/ http://picasaweb.google.com/lh/photo/Wh742wxYBdNqV-tAZru5Kg ★修课年度★（请加注开课单位 如:大三通识、XX系选修、XX所） 101 学年度上学期，资科工硕必修四选二 http://www.cs.nctu.edu.tw/cht/academics/files/20080108_01.pdf http://www.cs.nctu.edu.tw/cht/academics/files/20080108_02.pdf ￡教了什麽￡（课程大概内容。或是额外学会了什麽东西。） 课程用书 Introduction to Algorithms, 3rd Ed, Cormen, Leiserson, Rivest and Stein 课程网页 http://people.cs.nctu.edu.tw/~sctsai/advalgo/ 课程内容 1. Probabilistic Analysis and Randomized Algorithms 2. Universal Hashing 3. Advanced Design and Analysis Techniques a) Dynamic Programming b) Greedy Algorithms c) Amortized Analysis 4. Advanced Data Structures a) Fibonacci Heaps b) Data Structure for Disjoint Sets. 5. Graph Algorithms a) Elementary Graph Algorithms （期中考到这边） i) Breadth-first search ii) Depth-first search iii) Topological sort iv) Strongly connected components b) Minimum Spanning Trees c) Single-Source Shortest Paths d) All-Pairs Shortest Paths e) Maximum Flow and related problems 6. Linear Programming （快速看过） 7. NP-Completeness （只讲简单概念） 详细请参考 http://people.cs.nctu.edu.tw/~sctsai/advalgo/notes/ ◆上课方式◆（投影片、团体讨论、老师教学风格） 投影片上课搭配蒙恬手写 ▼考试作业▼ 每一到两周出一份手写作业（要交的有5份，合计15%）、期中考（40%）、期末考（45%） 两次大考的满分都是120分（可带一张A4的note） 手写作业注重 correctness的证明 和 complexity的分析 手写作业的题目请参考 http://people.cs.nctu.edu.tw/~sctsai/advalgo/hw/ ￥其他￥（是否注重出席率or严禁迟到？需要的基础？） 不点名 建议需要的基础 1. 演算法概论 2. 离散数学 a) Number theory b) Bijection (or bijective function or one-to-one correspondence) 相关范围： Universal Hashing c) Fibonacci numbers 相关范围： Fibonacci Heaps 3. 图论 a) Path、Cycle b) Tree c) Handshaking lemma http://en.wikipedia.org/wiki/Handshaking_lemma 相关范围： Graph Algorithms 4. 微积分 a) Integral test http://en.wikipedia.org/wiki/Integral_test_for_convergence 相关范围： Probabilistic Analysis and Randomized Algorithms 5. 线性代数 a) Linear independence 相关范围： Greedy Algorithms 的 Matroids ￠最後想说的话￠ 先说说大家都会关心的成绩吧 因为学期总成绩是老师直接公告在注册组的 所以助教也不知道调分的方式 两次大考的成绩分布可以参考（满分是120分） http://people.cs.nctu.edu.tw/~sctsai/advalgo/2012mid.txt http://people.cs.nctu.edu.tw/~sctsai/advalgo/finaldist.txt 小弟个人是期中84、期末94 调分後95 预计老师调了大概20分左右 这门课的规划主要是让学生更深入理解演算法 实作的话可能就要修老师开的演算法概论了 然後老师上课偶而也会结合时事或者是讲故事 比如2012诺贝尔经济学奖得主发表时 http://www.ettoday.net/news/20121015/114950.htm http://www.nobelprize.org/nobel_prizes/economics/laureates/2012/ 老师便额外补充了 Stable Marriage Problem 而上到 Linear Programming 时则提到 Dantzig 和 Simplex algorithm 的轶事 http://0rz.tw/1e4P1 个人觉得这门课需要花一些时间准备 特别是手写作业常常需要连续想个三、四天才能完工（也可能是我不擅长演算法 Orz） 不过想通之後感觉自己对於演算法的了解会更深刻、应用起来会更灵活 也比较能够融入演算法怎麽被设计出来的过程 而不只是死背特定的问题与其解法 （比如 Kruskal's algorithm 和 Prim's algorithm 是两个不同的演算法 但背後有一个共同的设计蓝图 GENERIC-MST Floyd-Warshall algorithm 和 Johnson's algorithm 都是找 All-Pairs Shortest Paths 的演算法 但是他们想法的起源和适用的时机差别在哪里？ 更进一步的探讨会在这门课提到） ＆谁适合修这门课＆ 1. 需要相关学分的人 2. 想更深入了解演算法的人 3. 专注於过程、不太计较结果的人 4. 想知道该怎麽读 Introduction to Algorithms 这本书的人（误） -- ※ Origin: 交大次世代(bs2.to) ◆ From: 140-113-62-213.Dorm5.NCTU.edu.tw 推 dogsbear：感谢神人分享 02/15 22:04 推 gxlkhhc：推荐这篇文章 02/15 22:47 推 gn027759681：印象中大学部手写作业没这麽难,调分也调很少 02/15 23:12 推 androidsalsa：推荐这篇文章 02/15 23:44 推 allen79119：推荐这篇文章 02/16 14:09 推 freepluse：推荐这篇文章 02/17 17:31 推 yukuro：他上课解释的还不错,我喜欢 02/18 01:26 → philo165：他会抛出问题 让你思考为什麽可以得出那样的结论 还不错 02/18 10:52 推 amy780911：推荐这篇文章 02/18 22:57

※ 发信站: 批踢踢实业坊(ptt.cc) ※ 转录者: neoneon (106.105.175.48), 07/12/2016 03:10:22