※ [本文轉錄自 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