===================個人想寫的公告=================== //↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ 有鑑於學校目前把很多科目的成績分布都不公開處理，導致選課資訊的流通被強力阻撓， 希望大家能夠多多發文寫每科的修課心得，讓後面要修課的人得到比較透明的資訊！希望 大家多多幫忙，不管是要發Dcard或臉書的通識平台都好，或者如果你願意發表到ptt上但 苦於沒有帳號，我可以協助代PO！ 需要我代PO的話，請登入google帳號後，填寫下列兩個表單其一: 一、 https://tg.pe/x3Ls (推薦版本，因為寫word檔可以存檔休息，不怕電腦突然中 斷) 二、 https://tg.pe/xQHL 我收到表單之後，應該會在一星期內貼出來。 希望大家多多參與！不管是通識課或專業科目都好，否則目前版上的文章看起來是快被電 資院的課程佔據了 //↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑ ===================個人想寫的公告=================== 課名： 隨機演算法 Randomized Algorithms 科號： 11020CS 531400 老師： 韓永楷 課本： 教授自製精美ppt。另可選購Probability and Computing: Randomized Algorithms and Probabilistic Analysis，作者Michael Mitzenmacher以及Eli Upfal 課別： 資工系碩班課程 學分： 3 涼度： ★x10 (滿分五分) 甜度： ★x5 (滿分五分) 建議先修課程： （1） 機率！！！（包含排列組合，以及集合的概念） （2） 演算法。 （3） 微積分會少量用到，尤其泰勒展開式的幾何概念 備註： 甲、 我覺得這堂課的機率成分比較重（尤其Discrete R.V. ，再尤以Binomial R.V. 以及更重要的Indicator R.V.為重中之重）。演算法反而非常還好，只要知道 AsysmptoticFunction以及NP-Complete即可（另外要有能夠理解PseudoCode的能力）。 乙、 我認為課名改成「高等機率：輔以演算法與資料結構的應用」的話，可能更貼切 。 課程內容\簡介： 前幾個禮拜會先複習集合的概念，順便複習Indicator、Binomial、Geometric這 三種Discrete R.V.的特性，並且會重新推導期望值的公式（在三個裡面重中之重的是 Indicator）。之後的一連串課程，就會奠基在這三個R.V.上去做介紹。 隨機演算法，顧名思義就是引入隨機性，所以並不著重在deterministic的 演算法的構思。具體來講的話，就是DP、greedy等等所構思出來的演算法可能是一個 M程度，那人類就會覺得是不是可以透過隨機性(白話文：可能會出錯)，來讓演算法的速 度達到N程度，同時讓演算法變得簡單。假設M是Polynomial程度，則我們會希望N程度 可以來到Linear。假設M程度是NP-Complete，則我們會希望N程度可以來到Polynomial 甚至是Linear。 而因為導入隨機性，所以結果可能會有錯誤。「隨機演算法」一門課，就是在 研究如果採用某種演算法，那錯誤率會是怎麼樣，而我們是否可以透過執行多次相同的 隨機演算法，來讓錯誤率下降到0.0000000000000001%。 所以比起deterministic的演算法而言，隨機演算法更著重在機率以及期望值的 計算。 課程大綱我認為可以大致分為以下甲、乙、丙，共三個階段： 甲、 Mid1：三種Discrete R.V. 的複習、UnionBounds、Markov Inequality、 Chebyshev Inequality 乙、 Mid2：Possion R.V.如何去做Binomial R.V.的近似（PossionCase v.s. ExactCase）、ChernoffBounds（會使用MomentGeneratingFunction）、BallsAndBins Model 丙、 Final：MarkovChain（這是高中數學）、ProbabilisticMethod（本課程我覺得 最困難的地方） 上課方式： 不點名。 疫情還沒升溫前，實體上課就是教授會寫板書。（英文授課，但不難理解） 疫情升溫後，採用遠距教學。因為往年已經有累積很多影片檔案，所以讓我們 自己回去看他的往年影片作為main course，而表訂的上課時間就是Youtube直播做為 QuickSummary。 考試作業型態： 總共有6次作業，但是完全不計分。教授會親自在課堂講解答案。 總共有三次期考。我記得本學期的滿分分別是110, 100, 105。 學期總成績 = Max(式[庚], 式[辛]) 式[庚] = 三次期考的平均 * 0.7 + 30 式[辛] = 較高的兩次期考的平均 * 0.8 + 較低的那次期考分數 * 0.2 大部分人應該都是用式[庚]會比較高分啦。 難易度問我不太準，因為我前兩次都考不好，期末考考得還不錯。有認真上課 寫作業的話絕對不會被當，因為每次都大概有一半的基本題吧。詳細成績分布可以參考 統計資料： Mid1: https://i.imgur.com/l844H4e.png Mid2: https://i.imgur.com/RBlopNs.png Final: https://i.imgur.com/GHnOOdR.png 老師的喜好、個性： 老師人超好！！！我超愛他！！！清大最愛的教授之一！！！而且也很可愛。 如果有誰說永楷的壞話，我一定跟他急！ 給加簽嗎? 不太清楚，這堂課似乎沒有《離散數學》或《高等離散結構》那麼熱門，所以 好像不太會滿。但其實滿推薦的。 補充: 因為炳豐是演算法大師而且他非常推薦韓永楷這位老師，所以我才來修的！ 炳豐教得很好所以可信度很高！而且我上過永楷的課之後真的覺得永楷是清大資工裡面 最好的老師之一了。 總成績/班上排名：A- 38/100 T分數：51.73 成績分布： https://i.imgur.com/24kbkg7.png --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.235.86.38 (臺灣) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTHU_Course/M.1656389742.A.829.html ※ 編輯: RhinoXiNiu (140.114.252.204 臺灣), 06/28/2022 22:01:09