※ 引述《fakewen (fakewen)》之銘言： : 請問這堂課的內容大概是偏向什麼 : 會跟資工系大二的演算法有密切關係嗎 : 還有課程的難度跟負載 謝謝 咦!!! 這個敝人剛好修過... 課本是 Graham, Knuth, Patashnik 的 "Concrete Mathematics: A Foundation for Computer Science" 第二版, 當時敝人 修的時候是每周有超過十個作業, 屬萬年作業, 沒有考試或報告, 作業題目是老師自己 出的題目 + 課本習題. 課程內容大約就是: 計算一些 recurrence; 計算一些級數和; 計算一些組合數; 計算 一些演算法 (如 quicksort) 的 expected running time 和 running time 的 variance 和 (hashing 的) expected number of probing 等. 和一般演算法課程不同的是, 這邊算的量都不是 asymptotic, 而是算到剛剛好, 這會 導致一些東西變得很難算... 像是 quicksort 的 expected running time, 如果要算 出 asymptotically O(n log n) 這個經典的結果, 是有很簡單的方法來求; 但是要 算到剛剛好, 甚至把 running time 的 variance 這些量也都算到剛好, 就會需要很多 很多技巧, 而這門課正好會提供這類技巧... 整體而言, 這門課和資訊工程系大二的演算法課程幾乎完全無關 (純屬敝人淺見)... 整個課對敝人來說, 就是不斷看到一些求解 recurrence 的方法, 求級數和的方法, 求組合數的方法等等, 每個方法都是互相獨立的, 學一招是一招. 負載的話, 敝人是覺得因人而異, 大概一周作業六題左右吧, 其中會有些簡單的, 也 有些需要嘗試熟悉一陣子的, 也有些可能需要查查課本公式來套的... 至於真正需要 發明新方法, 不能靠經驗和手動嘗試來解決的題目, 大概不會出在作業裡... 如果不想要修課, 只想一賭其中各種技巧, 我以前從總圖借過一本 Greene 和 Knuth 的 "Mathematics for the Analysis of Algorithms", 這是一本薄薄的書, 裡面可以說是 含有各種巧妙又華麗的技巧, 可以拿來算很多乍看之下不知道怎麼算的 recurrences... 讀起來感覺就像是課本的精簡版... 推薦給喜歡不斷地看各種新奇技巧的人們... --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.217.116.103