作者Hatred (yo)
看板NTUcourse
标题Re: [问题] 文进老师 "演算法的数学解析"
时间Mon Jul 28 01:53:36 2008
※ 引述《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
1F:推 alen332l:感谢分享 01/17 13:50