关于CS103和离散数学

今天@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加了很多编译原理里面要用到的抽象的概念。

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

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

同问啊，我离散是大一学的，只记得知识点很乱，不知道有什么，好多就是数据结构和高数的集合映射，美国的教授的比较好，偏向应用，那个板板，CS103老师没说什么在CS上的application吗？

数字媒体技术 发表于 2014-1-10 22:42
同问啊，我离散是大一学的，只记得知识点很乱，不知道有什么，好多就是数据结构和高数的集合映射，美国的教 ...

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

数字媒体技术 发表于 2014-1-10 22:42
同问啊，我离散是大一学的，只记得知识点很乱，不知道有什么，好多就是数据结构和高数的集合映射，美国的教 ...

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

EroicaCMCS 发表于 2014-1-10 22:49
没有看过CS103，对CS103的了解仅仅是syllabus..
现在发现美本CS的课程设置和国内很不一样啊，这门CS103和 ...

等个美本来介绍吧，我搬个凳子，good question！