一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2572|回复: 5
收起左侧

关于CS103和离散数学

[复制链接] |试试Instant~ |关注本帖
EroicaCMCS 发表于 2014-1-10 22:18:53 | 显示全部楼层 |阅读模式

[其他]CS103: Mathematical Foundations of Computing #1 - 2014-01-06@Stanford

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 EroicaCMCS 于 2014-1-14 16:20 编辑

今天@rsun 版主私信问了我一些问题,我觉得这个问题还是很通性的,有些地方我也比较疑惑,放出来大家一起讨论讨论。

Question @rsun:
“请问一下,离散数学是不是学CS必修的课?不学的话学算法是不是就很吃力了?

我现在看到大S有一门CS103,貌似是讲离散数学的。。。
reference book: Chapter 1 only of "Discrete Mathematics and its Applications"
and "Introduction to the Theory of Computation"  

Course topics:
Basic propositional and first-order logic.
• Basic sets, functions, relations, graphs, etc.
• Proof techniques
• Regular languages and finite automata
• Context-free languages and push-down automata.
• Turing machines and undecidablity.
• NP-completeness

麻烦帮忙看看,或者有没有其他课程推荐。
谢谢!”

Reply:

我在学校上离散数学的时候就是用Rosen的Discrete Mathematics and its Applications这本书(机械工业出版社出版,影印版简版),这本书被称为经典。但当时我就觉得这本书的内容极其的简单,大部分的内容国内高中理科生都学过了(比如:组合数,排列数,集合,映射的类型等等),甚至很多是小学奥赛的内容;而有的内容(比如说:等价关系,级数,三大离散分布等),又在微积分、线性代数、概率论等课程中反复提过;图论的内容(比如:节点、边、连通图的概念,邻接矩阵等等)在数据结构这门课中也是全部讲过的(我上数据结构用的是严蔚敏的书);而且离散数学这门课和Rosen的这本书对这些内容都只是简单一提,没有在其他课学的深入,所以觉得我上的离散数学就是一门彻底的水课,完全没有必要开。

Rosen的这本书大概是美国CS本科标准教科书了,书的难度大概也反映美本这门课的难度了吧(有没有美本来证实或者证伪一下?),这本书我全本通读过,我觉得在国内接受小学中学教育并且大学是理工科(学过高数、线代和概率论)的人肯定会觉得这本书的内容很简单,顶多是一些定义要了解一下。

我一直不理解为什么把离散数学放在这么重要的位置。是因为美国的课程设置跟国内不同,上述内容只有在离散数学才能学到么?还是因为我学的太水,只是学了点皮毛?
我也不觉得学离散数学对学算法有什么特别的促进作用,两者有交集的地方,比如:算时间复杂度omega?这不是微积分的内容么(求高阶无穷小量)。树的遍历、求最短路径?这些不是数据结构的传统内容么。。

从CS103的syllabus看,前一半内容大概就是我上面说的了。后面讲automata的内容,国内一般在编译原理这门课学,这块倒是非常重要的内容,也非常有用。之前Coursera上有门stanford的教授开的Automata,课上第一个视频就说对于CS的学生,以后工作中第一有用的是编程课上学的东西,第二有用的就是automata课上学的东西(不知地里已经在美帝工作的同学是否同意这句话?)。从这个角度来说,这门CS103还是可以看一下的。”

不知我上面说法是否准确?求地里有经验的同学解答。
PS: 看了看CS103的syllabus,感觉和国内教学差别很大,有一些概念非常陌生,比如说什么叫Context-free Languages,我就第一次听。。


PPS:Context-free Languages其实是编译原理学过的,前后文无关文法(忘了对不起老师啊),看来这门CS103加了很多编译原理里面要用到的抽象的概念。








rsun 发表于 2014-1-10 22:31:45 | 显示全部楼层
其实类似的问题在地里有过讨论
1.http://www.1point3acres.com/bbs/ ... 46464&fromuid=67314
这个帖子里一边倒,转专业如果时间有限又不深入搞科研,不需要学离散数学
或者说,直接上数据结构和算分就行了
2.http://www.1point3acres.com/bbs/ ... 24771&fromuid=67314
然而更早些的这个帖子里,几乎又一边倒的提倡必须要学。

求有经验的朋友指导
谢谢!

回复 支持 反对

使用道具 举报

数字媒体技术 发表于 2014-1-10 22:42:54 | 显示全部楼层
同问啊,我离散是大一学的,只记得知识点很乱,不知道有什么,好多就是数据结构和高数的集合映射,美国的教授的比较好,偏向应用,那个板板,CS103老师没说什么在CS上的application吗?
回复 支持 反对

使用道具 举报

 楼主| EroicaCMCS 发表于 2014-1-10 22:49:39 | 显示全部楼层

没有看过CS103,对CS103的了解仅仅是syllabus..
现在发现美本CS的课程设置和国内很不一样啊,这门CS103和我学的离散数学很多内容无法对应起来。还有些很重要的课,比如programming language 或者 design of computer program 和 automata,要么内容分散在其他课程中,要么干脆没讲。。
回复 支持 反对

使用道具 举报

rsun 发表于 2014-1-10 22:51:28 | 显示全部楼层
本帖最后由 rsun 于 2014-1-10 22:53 编辑
数字媒体技术 发表于 2014-1-10 22:42
同问啊,我离散是大一学的,只记得知识点很乱,不知道有什么,好多就是数据结构和高数的集合映射,美国的教 ...

CS103说了这个是CS的foundations
S大说CS103的先修课是CS106A
然后S大把CS103列为CS161,也就是地里跟过的那个S大(coursearea上有的)algorithm的先修课。


回复 支持 反对

使用道具 举报

数字媒体技术 发表于 2014-1-10 22:52:58 | 显示全部楼层
EroicaCMCS 发表于 2014-1-10 22:49
没有看过CS103,对CS103的了解仅仅是syllabus..
现在发现美本CS的课程设置和国内很不一样啊,这门CS103和 ...

等个美本来介绍吧,我搬个凳子,good question!
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 22:44

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表