[ZZ]胡侃学习(理论)计算机

作者是南大毕业的，现在美国某校做教授
看完以后我实在不好意思说自己是计算机科学与技术专业的毕业生。

发信人: sir (阿涩), 信区: Mathematics
标 题: 胡侃学习(理论)计算机(0)
发信站: 南京大学小百合站 (Mon Oct 8 03:57:41 2001), 站内信件

我也来冒充一回高手，谈谈学习计算机的一点个人体会。
由于我是做理论的，所以先着重谈谈理论。

记得当年大一，刚上本科的时候，每周六课时数学分析，
六课时高等代数，天天作业不断(那时是六日工作制)。
颇有些同学惊呼走错了门:咱们这到底念的是什么系？
不错，你没走错门，这就是(当时的)南大计算机系。系
里的传统是培养做学术研究，尤其是理论研究的人。而
计算机的理论研究，说到底了就是数学，虽然也许是
正统数学家眼里非主流的数学。

数学分析这个东东，咱们学计算机的人对它有很复杂
的感情。爱它在于它是第一门，也是学分最多的一门
数学课，又长期为考研课程--94以前可以选考数学分析
与高等代数，以后则并轨到著名的所谓“工科数学一”。
其重要性可见一斑。恨它则在于它好象难得有用到的
机会，而且思维跟咱们平常做的这些离散/有限的工作
截然不同。当年出现的怪现象是：计算机系学生的高中
数学基础在全校数一数二(希望没有冒犯其它系的同学)，
教学课时数也仅次于数学系，但学完之后的效果却几
乎是倒数第一。其中原因何在，发人深思。

我个人的浅见是：计算机类的学生，对数学的要求固然
跟数学系不同，跟物理类差别则更大。通常非数学专业
的所谓“高等数学”，无非是把数学分析中较困难的理论
部分删去，强调套用公式计算而已。而对计算机系来说，
数学分析里用处最大的恰恰是被删去的理论部分。说得
难听一点，对计算机系学生而言，追求算来算去的所谓
“工科数学一”已经彻底地走进了魔道。记上一堆曲面积分
的公式，难道就能算懂了数学分析？

中文的数学分析书，一般都认为以北大张筑生老师的
“数学分析新讲”为最好。我个人认为南大数学系的“数学
分析教程”也还不错，至少属于典型的南大风格，咱们
看着亲切。随便学通哪一本都行。万一你的数学实在
太好，这两本书都吃不饱，那就去看菲赫金哥尔茨的
“微积分学教程”好了--但我认为没什么必要，毕竟你
不想转到数学系去。

吉米多维奇的“数学分析习题集”也基本上是计算型的
东东。如果你打算去考那个什么“工科数学一”，可以
做一做。否则，不做也罢。

中国的所谓高等代数，就等于线性代数加上一点多项式
理论。我以为这有好的一面，因为可以让学生较早感觉
到代数是一种结构，而非一堆矩阵翻来覆去。当年我们
用林成森，盛松柏两位老师编的“高等代数”，感觉相当
舒服，我直到现在还保留着教材。此书相当全面地包含
了关于多项式和线性代数的基本初等结果，同时还提供
了一些有用的比较深的内容，如Sturm序列，Shermon
-Morrison公式，广义逆矩阵等等。可以说，作为本科
生如能吃透此书，就可以算高手。后来它得以在南大出
版社出版，可惜好象并轨以后就没有再用了。

国内较好的高等代数教材还有清华计算机系用的那本，
清华出版社出版，书店里多多，一看就知道。特点嘛，
跟南大那本差不太多。

但以上两本书也不能说完美无缺。从抽象代数的观点
来看，高等代数里的结果不过是代数系统性质的一些
例子而已。莫宗坚先生的“代数学”里，对此进行了深刻
的讨论。然而莫先生的书实在深得很，作为本科生恐
怕难以接受，不妨等到自己以后成熟了一些再读。

概率论与数理统计这门课很重要，可惜少了些东西。

少了的东西是随机过程。到毕业还没有听说过Markov
过程，此乃计算机系学生的耻辱。没有随机过程，
你怎么分析网络和分布式系统？怎么设计随机化算法
和协议？据说清华计算机系开有“随机数学”，早就是
必修课。人家可是工科学校，作为自以为“理科计算机
系”出身的人，我感到惭愧。

另外，离散概率对计算机系学生来说有特殊的重要性。
现在，美国已经有些学校开设了单纯的“离散概率论”
课程，干脆把连续概率删去，把离散概率讲深些。我们
不一定要这么做，但应该更加强调离散概率是没有疑
问的。

计算方法是最后一门由数学系给我们开的课。一般学生对
这门课的重视程度有限，以为没什么用。其实，做图形
图像可离不开它。而且，在很多科学工程中的应用计算，
都以数值的为主。

这门课有两个极端的讲法：一个是古典的“数值分析”，
完全讲数学原理和算法；另一个是现在日趋流行的“科学
与工程计算”，干脆教学生用软件包编程。南大数学系
的几位老师做了件大好事，把前者的一本极为经典的
教材翻译出版了：德国Stoer的“数值分析引论”。如果
你能学会此书中最浅显的三分之一，就算没有白上过
计算方法这门课！而后一种讲法似乎国内还没有跟上
潮流？不过，只要你有机会在自己的电脑上装个matlab
之类，完全可以无师自通。

本系里，通常开一门离散数学，包括集合论，图论，
和抽象代数，另外再单开一门数理逻辑。这样安排，
主要由于南大的逻辑传统：系里很多老师都算莫先生
的门人，就连孙先生都是逻辑专业出身(见孙先生自
述)。

不过，这么多内容挤在离散数学一门课里，是否
时间太紧了点？另外，计算机系学生不懂组合和
数论，也是巨大的缺陷。要做理论，不懂组合或
者数论吃亏可就太大了。

从理想的状态来看，最好分开六门课：集合，
逻辑,图论，组合，代数，数论。这个当然不现实，
因为没那么多课时。也许将来可以开三门课：集合
与逻辑，图论与组合，代数与数论。

不管课怎么开，学生总一样要学。下面分别谈
谈上面的三组内容。

古典集合论，北师大出过一本“基础集合论”不错。
南大出版朱梧(木贾)老师的“集合论导引”也许观点更
高些，但他的书形式化得太厉害，念起来吃力。

数理逻辑，莫先生的书自然是经典。然而我们也
不得不承认，此书年代久远，光读它恐怕不够。
尤其是命题/谓词演算本身有好多种不同的讲法，
多看几家能大大开阔自己的视野。例如陆钟万老师
的“面向计算机科学的数理逻辑”就不错。朱老师也
著有“数理逻辑教程”一书，但也同样读起来费力些。

总的来说，学集合/逻辑起手不难，但越往后越感觉
深不可测。建议有兴趣的同学读读朱老师的“数学
基础引论”--此书有点时间简史的风格，讲到精彩处，
所谓“天花乱坠，妙雨缤纷”，令人目不暇接。读完
以后，你对这些数学/哲学中最根本的问题有了个大概
了解，也知道了山有多高，海有多深。
学完以上各书之后，如果你还有精力兴趣进一步
深究，那么可以试一下GTM系列中的"Introduction
to Axiomatic Set Theory"和"A Course of Mathematical
Logic"。这两本都有世界图书的引进版。你如果
能搞定这两本，可以说在逻辑方面真正入了门，
也就不用再浪费时间听我瞎侃了。：)

据说全中国最多只有三十个人懂图论(当年上课时陈道蓄
老师转引张克民老师的话)。此言不虚。图论这东东，
技巧性太强，几乎每题都有一个独特的方法，让人头痛。
不过这也正是它魅力所在：只要你有创造性，它就能
给你成就感。所以学图论没什么好说的，做题吧。

国内的图论书中，王树禾老师的“图论及其算法”非常
成功。一方面，其内容在国内教材里算非常全面的。
另一方面，其对算法的强调非常适合计算机系(本来
就是科大计算机系教材)。有了这本书为主，再参考
几本翻译的，如Bondy&Murty的“图论及其应用”，
邮电出版社翻译的“图论和电路网络”等等，就马马
虎虎，对本科生足够了。

再进一步，世界图书引进有GTM系列的"Modern
Graph Theory"。此书确实经典！国内好象还有一
家出版了个翻译版。不过，学到这个层次，还是
读原版好。搞定这本书，也标志着图论入了门，呵呵。
组合感觉没有太适合的国产书。还是读Graham和Knuth
等人合著的经典“具体数学”吧，有翻译版，西电出的。

抽象代数，国内经典为莫宗坚先生的“代数学”。此书
是北大数学系教材，深得好评。然而对本科生来说，
此书未免太深。可以先学习一些其它的教材，然后
再回头来看“代数学”。国际上的经典可就多了，GTM
系列里就有一大堆。推荐一本谈不上经典，但却最简
单的，最容易学的：
http://www.math.miami.edu/...
这本“Introduction to Linear and Abstract Algebra"
非常通俗易懂，而且把抽象代数和线性代数结合起来，
对初学者来说非常理想。不过请注意版权问题，不要
违反法律噢。

数论方面，国内有经典而且以困难著称的”初等数论“
(潘氏兄弟著，北大版)。再追溯一点，还有更加经典
(可以算世界级)并且更加困难的”数论导引“(华罗庚先生
的名著，科学版，九章书店重印)。把基础的几章搞
定一个大概，对本科生来讲足够了。但这只是初等数
论。本科毕业后要学计算数论，你必须看英文的书，
如Bach的"Introduction to Algorithmic Number Theory"

理论计算机的根本，在于算法。现在系里给本科生
开设算法设计与分析，确实非常正确。环顾西方世界，
大约没有一个三流以上计算机系不把算法作为必修的。

算法教材目前公认以Corman等著的"Introduction to
Algorithms"为最优。对入门而言，这一本已经足够，
不需要再参考其它书。南大曾翻译出版此书，中文名
为”现代计算机常用数据结构与算法“。pie好象提供了
网上课程的link，我也就不用废话。

最后说说形式语言与自动机。我们用过北邮的教材，
应该说写的还清楚。但是，有一点要强调：形式语言
和自动机的作用主要在作为计算模型，而不是用来
做编译。事实上，编译前端已经是死领域，没有任何
open problem。如果为了这个，我们完全没必要去学
形式语言--用用yacc什么的就完了。北邮的那本，在深
度上，在跟可计算性的联系上都有较大的局限，现代
感也不足。所以建议有兴趣的同学去读英文书......不过
英文书中好的也不多，而且国内似乎没引进这方面的
教材。

入门以后，把形式语言与自动机中定义的模型，和
数理逻辑中用递归函数定义的模型比较一番，可以
说非常有趣。现在才知道，什么叫”宫室之美，百官
之富“！

发信人: sir (阿涩), 信区: Mathematics
标 题: 胡侃学习计算机--理论之外(0)
发信站: 南京大学小百合站 (Mon Oct 15 05:26:00 2001), 站内信件

如果计算机只有理论，那么它不过是数学的一个分支，而
不成为一门独立的科学。事实上，在理论之外，计算机
科学还有更广阔的天空。我一直认为，4年根本不够学习
计算机的基础知识，因为面太宽了......


一个一流计算机系的优秀学生决不该仅仅是一个编程高
手，但他一定首先是一个编程高手。

我上大学的时候，第一门专业课时程序设计，现在好象
改成了计算机科学导论？不管叫什么名字，总之，念计
算机的人就是靠程序吃饭。

去年在计算机系版有过一场争论，关于第一程序设计语言
该用哪一种。我个人认为，用哪种语言属于末节，关键在
养成良好的编程习惯。当年老师对我们说，打好基础后
学一门新语言只要一个星期。现在我觉得根本不用一个
星期--前提是先把基础打好。

数据结构有两种不同的上法：一种把它当成降低要求的
初级算法课，另一种把它当成高级的程序设计课。现在
国内的课程好象介乎两者之间，而稍偏向前者。我个人
认为，假如已经另有必修的算法课，恐怕后一个目的更
重要些。

国内流行的数据结构书也有两种：北大的红皮书(许卓
群等著，高教版)和清华的绿皮书(严蔚敏等著，清华版)。
两书差距不大。红皮书在理论上稍深一些，当然离严格
的算法书还差好远。绿皮书更易接受些，而且佩有一本
不错的习题集，但我觉得它让学生用伪代码写作业恐怕
不见得太好。最好还是把算法都code以后debug一番，
才能锻炼编程能力。

汇编预言和微机原理是两门特烦人的课。你的数学/理论
基础再好，也占不到什么便宜。这两门课之间的次序也
好比先有鸡还是先有蛋，无论你先学哪门，都会牵扯另
一门课里的东西。所以，只能静下来慢慢琢磨。这就是
典型的工程课，不需要太多的聪明和顿悟，却需要水滴
石穿的渐悟。

有关这两门课的书，电脑书店里不难找到。弄几本最新
的，对照着看吧。

模拟电路这东东，如今不仅计算机系学生搞不定，
电子系学生也多半害怕。如果你真想软硬件通吃，那么
建议你先看看邱关源的“电路原理”，也许此后再看模拟
电路底气会足些。

教材：康华光的“电子技术基础”还是不错的。有兴趣也
可以参考童诗白的书。

数字电路比模拟电路要好懂得多。阎石的书也算一本好
教材，遗憾的一点是集成电路讲少了些。真有兴趣，到
东南无线电系去旁听他们的课。

计算机系统结构该怎么教，国际上还在争论。国内能找
到的较好教材为Stallings的"Computer Organization
and Architecture:Designing for Performance"(清华影印
本)。国际上最流行的则是“Computer architecture: a
quantitative approach", by Patterson & Hennessy。

操作系统可以随便选用Tanenbaum的"Operating System
Design and Implementation"和"Modern Operating
System"两书之一。这两部都可以算经典，唯一缺点
就是理论上不够严格。不过这领域属于Hardcore System,
所以在理论上马虎一点也情有可原。

如果先把形式语言学好了，则编译原理中的前端我看只要
学四个算法：最容易实现的递归下降；最好的自顶向下
算法LL(k)；最好的自底向上算法LR(k)；LR(1)的简
化SLR(也许还有另一简化LALR?)。后端完全属于工程
性质，自然又是another story。

推荐教材：
Aho等人的著名的Dragon Book: "Compilers: Principles,
Techniques and Tools".
或者Appel的"Modern Compiler Implementation in C".

学数据库的第一意义是告诉你，会用VFP编程不等于懂
数据库。(这世界上自以为懂数据库的人太多了！)数据库
设计既是科学又是艺术，数据库实现则是典型的工程。
所以从某种意义上讲，数据库是最典型的一门计算机课
--理工结合，互相渗透。

推荐教材：Silberschatz, et al., "Database System
Concepts".

网络的标准教材还是来自Tanenbaum:”Computer
Networks"(清华影印本)。不过，网络也属于Hardcore
System，所以光看书是不够的。建议多读RFC，从
IP的读起。等到能掌握10种左右常用协议，就没有几个
人敢小看你了。

必须结束这篇“胡侃”了，再侃下去非我力所能及。其实
计算机还有很多基础课都值得一侃，如程序设计语言原
理，图形图像处理，人工智能等等。怎奈我造诣有限，
不敢再让内行耻笑。

最后声明：前后的两篇“胡侃”只针对本科阶段的学习。
即使把这些全弄通了，前面的路还长......