推 alen332l:感謝分享 01/17 13:50
※ 引述《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