※ 引述《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