大学数学(计算机专业)

计算机理论的一个核心问题——来自数学；

记得大一的时候，每周六上高数，每天做作业(当时是六天工作制)。不少同学惊呼走错门了:我们这里是学什么系的？是的，你没走错门。这是计算机科学与技术系。我国计算机系的传统是培养做学术研究，尤其是理论研究的人(方向不一定有问题，但工作不那么如意)。说到底，计算机的理论研究，比如网络安全、图形图像学、视音频处理，都和数学有很大的关系，虽然在正统数学家眼里可能是非主流数学。这里我也想澄清一下我的观点:众所周知，数学是从现实生活中抽象出来的理论。人们之所以把现实抽象成理论，是想用抽象出来的理论更好地指导实践。有些数学研究者喜欢用一些已有的理论知识推导出几个推论，却不知道一个是考虑问题不全面很可能是错误的推论，一个是他的推论在现实生活中找不到原型，无法指导实践。严格来说，我不是理想主义者，政治课理论联系实际一直是指引我学习科学文化知识的灯塔(至少我认为计算机科学与技术应该是这个方向)。

其实我们计算机系学数学和光学的高数是不够的(典型的工科院校一般都会开设高数)。我们应该像数学系一样学习数学分析(清华的计算机系好像开了数学分析)，我们计算机专业的学生对它的感情很复杂。就是偏向于证明型的数学课程，这对于我们培养良好的分析能力很有帮助。我的软件工程导师，北工大数理学院的王艺华老师曾经教过我们，数学系的学生大部分从事软件设计和分析工作，而计算机系的学生大部分从事程序员工作。原因是数学系学生的分析推理能力在培养上远在我们之上。当年出现的奇怪现象是，计算机系的学生高中数学成绩名列前茅(希望没有得罪其他同学)，授课时数仅次于数学系，但学了之后效果并不理想。是不是所有的学生都不努力？我没看到。不知道是不是方向错了。原因是什么？令人深思。

我的拙见是，计算机系的学生对数学的要求不一样，但和物理更不一样。通常所谓的非数学专业的《高等数学》，无非是把数学分析中比较难的理论部分删掉，强调公式的应用。对于计算机系来说，数学分析最有用的部分就是被删掉的理论部分。说白了，对于计算机专业的学生来说，追求计算的所谓“工程数学”完全走入了一个误区。记住一堆曲面积分的公式就能理解数学吗？还不如现在查，何必去记。或者直接用数学或者Matalab。

我在系里最喜欢做的事情就是给学弟学妹推荐参考书。在中国的数学分析书籍中，一般认为北京大学张竹生的《数学分析新讲》最好。万一你真的数学很好，可以去看看Fichkingolz的《微积分教程》——不过我觉得没必要。毕竟你不想转数学系。吉米·多维奇的《数学分析习题集》基本上是一个计算的东西。书很有名，但不一定适合我们。还是那句话，重要的是数学思想的建立。生活在信息社会，我们追求的是高效率。让我们把计算留给计算机吧。不过复旦大学的数学分析好像是本不错的教材。

中国所谓的高等代数等于线性代数加一点多项式理论。我觉得这有好的一面，因为可以让学生更早的感受到代数是一个结构，而不是一堆矩阵在折腾。不得不提南大林成森和盛编的《高等代数》，相当舒服。这本书相当全面地包含了多项式和线性代数的基本初等结果，还提供了一些有用而深刻的内容，如Sturm序列、Shermon-Morrison公式、广义逆矩阵等。可以说，作为一个本科生，如果你能把这本书理解透彻，那你也算是大师了。国内比较好的高等代数教材是清华计算机系用的那种，清华出版社出版，书店里也有很多。从抽象代数的角度来看，高等代数中的结果只是代数系统性质的一些例子。莫宗坚先生的《代数》对此有深刻的论述。但是，莫老师的书太深奥了，恐怕一个本科生很难接受。我还不如等自己成熟了再说。

如上所述，计算机系的学生学习高等数学:知道它是什么，更重要的是知道它为什么。你学习的目的应该是:把抽象的理论运用到实践中，不仅要掌握解题方法，还要掌握解题思路。对于定理的学习，不是简单的应用，而是掌握证明过程，也就是掌握定理的由来，训练你的推理能力。这样才能达到学习这门科学的目的，同时也能缩小我们和数学系同学的思维差距。

概率论与数理统计这门课很重要，但很遗憾的是，大部分高校都会少教这门课的东西。现在缺的至少是一个随机过程。毕业前都没听说过马尔可夫过程，对于计算机专业的学生来说是一种耻辱。没有随机过程，你如何分析网络和分布式系统？如何设计随机化算法和协议？据说“随机数学”是清华计算机系的必修课。此外，离散概率论对计算机专业的学生来说特别重要。而我们国家的工科数学都是连续概率。现在美国有些学校开设了简单的“离散概率论”课程，简单的把连续概率删掉，深入的讲离散概率。我们不一定要这样做，但我们应该更加重视离散概率。我认为最好尽快完成这项工作。

计算方法论(有些学校也叫数学分析)是数学与科学学院给我们上的最后一门课。一般学生对这门课的重视程度有限，认为没用。这只是一个公式！其实图形图像离不开它，密码学也离不开它。而且很多科学项目中的应用计算主要是数值。这门课有两个极端:一个是经典的“数值分析”，完全专注于数学原理和算法；另一种是越来越流行的“科学与工程计算”，简单地教学生用软件包编程。个人认为计算机系的同学一定要清楚我们计算机系的同学为什么要学这门课。我很倾向于把理论学好，然后用电脑实现。最好用C语言或者C++编程来实现。还有相当多的书在朝这个方向努力。在这里，我推荐《计算方法》，CHEP和斯普林格出版社联合出版，华中科技大学(现华中科技大学)数学系编写。在这方面，中国科大在国内做了很多工作，但个人认为这本书是最好的，至少在编程方面:任意数学函数的求值，方程求根。李清扬的书理论性太强，没有紧密结合实际应用。

每个学校都会开设离散数学课程，涉及到集合论，图论，抽象代数，数理逻辑。但是，把这么多内容挤到一门离散数学的课程里，是不是有点太紧了？另外，计算机专业的学生不懂组合和数论也是一个巨大的缺陷。想做理论，不懂组合，不懂数论，太吃亏了。从理想状态来说，最好把集合、逻辑、图论、组合、代数和数论六门课程分开。这当然不现实，因为没有那么多课时。也许以后可以开设三门课:集合与逻辑，图论与组合，代数与数论。(我们学校已经开始这么做了。)不管怎么上课，学生总是要学的。下面分别说一下以上三组。

经典集合论，北师大出了一本书《基础集合论》，不错。

数理逻辑，中科院软件所卢忠万教授的《计算机科学的数理逻辑》不错。现在可以找到卢忠万教授讲课的视频。/html/dir/2006 54 38+0/11/06/3391 . htm自己去看看吧。总的来说，学集合/逻辑不难，普通高中生也能看懂。但越往后，越觉得深不可测。

学完以上书籍，如果还有精力和兴趣进一步探索，可以试试《公理集合论导论》和GTM系列的一门数理逻辑课程。这两本书都有从世界图书出版社引进的版本。如果你能搞定这两本书，你在逻辑上就真的能进门了，就不用浪费时间听我讲了。

据说中国最多只有三十个人懂图论。这个说法是对的。图论太有技巧了，几乎每个问题都有独特的方法，让人头疼。但这就是它的魅力:只要你有创意，它就能给你成就感。我导师说在图论里随便抓个什么都可以写论文。你可以体会到里面内容的深度和广度！在国内的图论书籍中，王叔和老师的《图论及其算法》是非常成功的。一方面，其内容在国内教材中非常全面。另一方面，它对算法的强调非常适合计算机系(原本是HKUST计算机系的教材)。以这本书为主，参考几本翻译过来的书，比如Bondy &；穆尔蒂的《图论及其应用》，人民邮电出版社译的《图论与电路网络》等。都一般，对于本科生来说就够了。此外，GTM系列“现代图论”被引入世界书籍。这本书真的很经典！国内好像又有一家出了翻译版。不过，要学这个水平，还是读原著好。这本书的完成也标志着图论的进入。该书外文版的妙处就在这里。最新的科技成果都有讨论。不说别的，至少是“理论知识与时俱进”。

组合感觉没有合适的国产书。让我们来读读格雷厄姆和克努特合著的经典《具体数学》。西安电子科技大学出版社有翻译版。

抽象代数，国内的经典是莫宗坚先生的《代数》。这本书是北京大学数学系的教材，颇受好评。但是，对于本科生来说，这本书太深奥了。可以先学一些别的教材，再回头看代数。国际经典很多，包括GTM系列也很多。推荐一本不经典，但最简单易学的书:《计算机科学》(计算机科学的数学基础)，即理论计算机科学。原来我曾经在东方大学城的图书馆看过一本70年代的翻译(封面没了，但我很爱关注这类书)，大概叫计算机数学。那本书在当时会是一本好书，现在看来，覆盖面很广，但深度差很多。不过还是建议大一的同学看一看，至少能让你在计算数学方面入门。

最常与理论计算机科学放在一起的词是什么？答:离散数学。两者关系如此密切，在很多场合都成了同义词。(这在之前的书里也有体现)传统上，数学是以分析为中心的。数学系的学生要学三四个学期的数学分析，然后是复变函数，实变函数，泛函数等等。实变量和泛函被很多人认为是现代数学的入门。在物理、化学、工程方面的应用主要以分析为主。

随着计算机科学的出现，一些以前被忽视的数学分支突然变得重要起来。发现这些分支所处理的数学对象明显不同于传统的分析:分析和研究的解题方案是连续的，因此微分和积分成为基本运算；但是这些分支的对象是离散的，所以这种计算的机会很少。人们因此称这些分支为“离散数学”。“离散数学”的名号越来越响，最后以分析为中心的传统数学分支相对称之为“连续数学”。

离散数学经过几十年的发展，已经基本趋于稳定。一般认为，离散数学包括以下学科:

1)集合论，数理逻辑，元数学。这是数学和计算机科学的基础。

2)图论，算法图论；组合数学，组合算法。计算机科学，尤其是理论计算机科学的核心是

算法，而且大量的算法都是基于图和组合的。

3)抽象代数。代数无处不在，在数学中非常重要。在计算机科学中，人们惊讶地发现代数有如此多的应用。

然而，理论计算机科学仅仅是给数学加一顶“离散”的帽子那么简单吗？直到大约十年前，一位大师终于告诉我们:No. D.E.Knuth(他有多伟大，我觉得不用我废话)在斯坦福开了一门全新的课程《混凝土数学》(Concrete Mathematics)。混凝土这个词在这里有两个意思:

首先:对于抽象。Knuth认为传统数学研究的对象过于抽象，导致对具体问题关注不够。他抱怨说，他所需要的数学往往在他的研究中并不存在，所以他不得不自己创造一些数学。为了直接满足应用的需要，他应该提倡“具体的”数学。我在这里简单说明一下。比如集合论，数学家关心的是最根本的问题——公理系统的各种性质等等。数学家认为一些特定集合、公共集合、关系和映射的性质是什么样的并不重要。然而，正是这些具体的东西被应用在计算机科学中。克努特能最先看到这一点，不愧为世界计算机第一人。其次，混凝土是连续加离散的。连续数学和离散数学都是有用的数学！

理论与实践的结合——计算机科学研究的范畴

前面主要是从数学的角度。从计算机的角度来看，目前理论计算机科学的主要研究领域包括:可计算性理论、算法设计与复杂性分析、密码学与信息安全、分布式计算理论、并行计算理论、网络理论、生物信息学计算、计算几何、程序设计语言理论等。这些领域相互交叉，不断有新的课题提出，很难理出一个头绪。如果你想做这个工作，我推荐你看中国计算机联合会的系列书籍，至少代表了我们国家的权威。这里有一些随机的例子。

由于应用需求的推动，密码学现在已经成为一个热门的研究课题。密码学的基础是数论(尤其是计算数论)、代数、信息论、概率论和随机过程，有时也会用到图论和组合学。很多人认为密码学就是加密解密，而加密就是用一个函数对数据进行加扰。这种理解太简单了。

现代密码学至少包括以下几个层次:

第一，密码学的基础。比如分解一个大数真的很难吗？有没有通用的工具证明协议的正确性？

第二，密码学的基础学科。比如更好的单向函数，签名协议等。

第三，密码学的高级问题。比如零知识证明的长度，秘密共享的方法。

第四，密码学的新应用。比如数字现金，叛徒追踪等。

在分布式系统中，也有许多重要的理论问题。例如，进程之间的同步、互斥协议。一个经典的结果是，当通信信道不可靠时，没有确定性的算法来实现进程间的协作。所以改进TCP三次握手几乎没有意义。比如时间问题。常见的秩序是因果秩序，但因果秩序直到最近才有一个理论结果...例如，没有实用的方法可以完美地处理死锁。举个例子，.....如果操作系统学过，自己提！

如果计算机只有理论，那么它只是数学的一个分支，而不是一门独立的科学。其实除了理论，计算机科学还有更广阔的天空。

我一直觉得学计算机基础知识四年是不够的，因为太宽了，八年应该差不多够了。......

在这方面，我想谈谈我们系各个学校普遍开设的“计算机基础”。高校开设计算机基础课程是我国高等教育部门规定的所有专业的必修课要求。主要内容是使学生掌握计算机发展史，学会简单使用操作系统、文字处理、表格处理和初步的网络应用功能。但是计算机系教这门课的目标一定不能和这个一致。计算机科学课程的目标应该是:让学生充分了解计算机科学的发展，明确把握计算机科学的研究方向，发展的前沿是各门课程在整个学科体系中的地位。搞清楚每门学科的学习目的，学习内容，应用领域。使学生在学科学习初期对整个学科有一个整体的了解，从而明确知道以后要学什么，怎么学。计算机应用基础技能的位置应该放在第二位甚至更靠后，因为这个系的学生应该有这个探索能力。这一点非常重要。推荐一本书:机械工业出版社的《计算机科学新视角》。看完这本书，我深深地意识到，我还是一个计算机科学的初学者，我对什么是计算机科学已经有了透彻的了解。

一个一流计算机系的优秀学生，绝不应该只是一个编程高手，而首先必须是一个编程高手。大学的时候，第一门专业课是C语言编程。从某种角度来说，相当一部分读计算机的人是靠写程序过日子的。关于哪一种应该作为第一编程语言。个人认为，最后一节属于哪种语言，关键在于养成良好的编程习惯。当时老师告诉我们，打好基础后只需要一个星期就能学会一门新的语言。现在我觉得根本用不了一周，前提是先打好基础。不要犹豫，学吧，等你做出选择的时候，别人已经会几种语言了。

汇编语言和微机原理是两门特别讨厌的课程。你的数学/理论基础再好，也不能占便宜。这两道菜之间的顺序也是先有鸡还是先有蛋。不管你先学哪门课，都会涉及到另一门课的东西。所以，只能静下心来慢慢想。这是典型的工科类，不需要太多的聪明和顿悟，需要循序渐进的开悟。关于这两门课的书在电脑书店里不难找到。拿几本最新的书比较一下。《组成原理》推荐清华大学王爱英教授写的《计算机组成与结构》。汇编语言每个人都把8086/8088带进一个门，然后你必须学习80x86汇编语言。很有实用价值，不落后，结构很好。写高效的病毒，用高级语言嵌入一点点汇编，进行低级开发，总是离不开他。推荐清华大学沈梅梅的IBM-PC汇编语言编程。有人说，不想了解计算机架构，不想做计算机，没必要学计算机原理、汇编语言、接口等课程。这合理吗？明显不合理，这些东西迟早要掌握，必须接触。而且这些都是计算机专业相对于其他专业为数不多的优势。做项目的时候，了解这些很重要。不能说技术只是为了技术。只懂技术的人最多只能做个编码工，永远无法完全理解整个系统的设计。编码工作者年龄越大，价值越低。关于构图原理还有一个教学问题。我在学这门课的时候，老师省略了CPU工作原理和微程序设计这一块。原因是我们国家的CPU技术不如其他国家，而且经过这么长时间，我们终于出了一个比英特尔差十万八千里的龙芯，建议不要学。我不认为这是所有学校的问题。如果真如他所说，中国可以在任何方向阻止计算机科学。美国有几样东西是可以做的，比如软件、硬件、应用，其他的都做不到，那我们为什么坐在这里？教学观念需要改变。

现在不仅计算机专业的学生不会处理模拟电路，电子专业的学生也大多害怕。如果你真的想同时吃软件和硬件，那么我建议你先看看邱关源的“电路原理”，也许再看看模拟电路。教材:康的《电子技术基础》(高等教育出版社)还是不错的(我校电子系用)。如果你有兴趣，也可以参考童的书。

数字电路比模拟电路好得多。清华大学阎石的书是一本很好的教材，但遗憾的是其中对集成电路的论述较少。我很感兴趣。再来看看大型数字系统的设计(北航的还是用的比较多)。

如何教授计算机系统结构在国际上仍有争议。国内能找到的比较好的教材是Stallings的《计算机组织与架构:为性能而设计》(清华影印)

本)。世界上最流行的一本是《计算机架构:水生途径》，作者帕特森&；轩尼诗.

操作系统可以选择《操作系统内核的设计与实现》和《现代操作系统》两本书中的一本。两者都算得上经典，唯一的缺点就是理论上不够严谨。但是这个领域属于硬核系统，理论上马虎可以理解。如果想看理论，请推荐清华大学出版社的《操作系统》，高教部主任张尧学著，是我们用的教材。另外推荐一本机械工业出版社出版的《Windows操作系统原理》。这本书是中国操作系统专家在微软零距离考察半年后写的，写作历时一年多。几乎所有教操作系统的专家都参与了，除了清华大学的张尧学(现高教部主任)。比尔·盖茨亲自写了序言。不仅结合windows2000、xp、XP详细介绍了操作系统的内核，后面还讲了一些windows编程基础，很有一种洋版书的味道，而且上面的一些内容可以说国内外只有那本书对windows内核有详细的介绍。

如果先学好形式语言，我觉得只需要学习编译原理前端的四个算法:递归下降，最容易实现；最佳自顶向下算法LL(k)；最佳自底向上算法LR(k)；LR(1)的简化单反(也许还有另一个简化的LALR)。后端完全是工程，自然是后话。

推荐教材:Kenneth C.Louden写的《编译原理与实践》是《编译原理与实践》(机械工业出版社译)。

学习数据库要提醒大家，会用VFP、VB、PowerBuilder不等于会数据库。世界上自以为懂数据库的人太多了！数据库设计是科学也是艺术，数据库实现是典型的项目。所以从某种意义上说，数据库是最典型的计算机课程——理工科结合，相互渗透。另外，我推荐你学完软件工程再去翻一翻数据库技术，会是一种新的感受。推荐教材:《数据库系统概念》亚伯拉罕·西尔伯沙茨等。作为知识的完备性，我也推荐大家看一下机械工业出版社的《数据仓库》翻译。

计算机网络的标准教材来自Tanenbaum的《计算机网络》(清华大学译)。还有谢希仁的《计算机网络教程》(人民邮电出版社)的推荐，比较清晰，参考文献也比较权威。但是网络也属于硬核体系，光看书是不够的。建议多看RFC。你可以在http://www.ietf.org/rfc.htm.从IP阅读按编号下载RFC文档。当你能掌握10左右的常用协议，就没几个人敢小看你了。我认为做网络设计的工作会更好。

数据结构的重要性不言而喻。学完数据结构，你的编程思路会有一次革命性的洗礼，对如何建立合理高效的算法有一个清晰的认识。我觉得大家对于算法的建立要注意以下几点:

当你遇到一个算法问题的时候，首先要知道你之前有没有处理过这个问题。如果有，通常会顺利解决。如果没有，请考虑以下问题:

1.问题是否基于某种已知的、熟悉的数据结构(比如二叉树)？如果没有，你应该设计你自己的数据结构。

2.问题需要以下哪种类型的算法？(建立数据结构，修改数据结构，遍历，查找，排序...)

3.分析问题所需的算法的数学本质。是递归的吗？对于递归编程，只要设计出合理的参数表和递归结束的条件，基本就搞定了。

4.继续分析问题的数学本质。根据你之前的编程经验，设想一个可能的解决方案，并证明这个方案的正确性。如果题目对算法有时间和空间的要求，证明你的想法符合它的要求。一般时间效率和空间效率很难兼顾。有时需要通过建立辅助存储来节省时间。

5.经过一段时间的分析，你有了自己解决这个问题的思路。或者，你可以简单地用自然语言描述你的算法。继续验证其正确性，努力找出错误，找出解决方法。必要时(如果发现无法解决的矛盾)，推翻自己的想法，从头开始。

6.确认你的想法可行后，开始写程序。在编写代码的过程中，把各种问题考虑得尽可能详细透彻。该计划应该有一个良好的结构，并在关键地方提供评论。

7.举个例子，然后用笔在纸上执行你的程序，进一步验证它的正确性。当你遇到与你想法不符的情况时，分析问题是编程问题还是算法想法本身的问题。

8.如果程序通过了上述正确性验证，将进一步优化或简化。

9.写思路分析和评论。

具体的算法思路只能靠自己通过自己的知识和经验获得，没有具体的规律(否则可以裁掉所有程序员，代码由机器自动生成)。你要有丰富的想象力，就是当一条路走不通的时候，不要陷入困境，要敢于推翻自己的想法。我只是一个初学者，我把上面的一些经验讲给大家，供大家参考和讨论。

关于人工智能，我觉得也是非常值得我们认真研究的。虽然不是新兴学科，但绝对是很有前途的学科。中国人工智能的奠基人之一，北京科技大学的涂徐焰教授(这位老先生是我的导师李小健博士)是这样定义人工智能的:人工智能是一个模型。