简介

计算机是什么

• 计算机是工具，帮助人们提高效率；
• 作为工具，其本质作用就是帮助人们做一些机械性、重复性的工作，把人解 放出来，从事更多创新性的工作;
• 当你在手工的做一些机械性的工作时，你就要反思了，很能已经违背了计算 机的哲学，这本该由计算机完成。一个简单的例子：搜索／替换。

计算机科学

• 计算机科学是研究 solution 的科学，即研究怎样用计算机解决各种实际问 题;
• 从大面上看，计算机科学包括体系结构、算法理论和计算机应用三大块，前 两者是基础，第三块是 呈现，它有好多分支，如图形学、多媒体、人工智能、 信息系统、网络等等;

计算机科学本原

既然计算机科学是研究 solution 的科学，那么它的根本应该是解决问题的思路、 数据结构和算法。

思路是基础，数据结构和算法是思路的具体体现。

普遍认为计算机科学是“算法的科学”。美国计算机学会(ACM)对计算机科学有如 下定义：

Computer science as the "systematic study of algorithmic process that
describe and transform informatioi: their theory, analysis, design,
efficiency,implementation and application."

计算机科学有两个基础：可计算性和计算复杂性。可计算性研究问题是否可解， 不可解的问题称为 NP 问题；计算复杂性是在确认问题可解的前提下，研究解决 方法以及方法的时间、空间复杂度。

计算机科学本质上是研究做事效率和成本的“事理学”。所谓做事包括科学工程 计算、事务处理、信息服务等各种人类想做的事情。办事就要讲求章法、讲求系 统、讲求组织，不仅仅是算法。

信息技术发展的历史证明：信息技术发展遵循简单性法则，过于发杂的技术往往 被淘汰或变成脱离主流的技术等。如 Ada 语言，数据流计算机等。互联网的成 功的原因之一在于 KISS 原则 (Keep It Simple and Stupid)。

计算机科学需要强调与自然科学、社会科学的交叉，应该成为跨领域的二元或多 元科学。计算机科学要大大加强与物理学、生命科学及社会科学的交叉研究，形 成计算物理学、计算生物学、社会计算等新学科，还可以形成“计算机+生命+物 理”、“计算机+生命+社会”等三元交叉科学。这些交叉学科不仅仅是计算机的 应用扩展，而是我们需要高度重视的计算机科学的未来主流方向。今后计算机科 学的研究，不能完全像过去一样走越分越细的以归约还原为主的道路，应当考虑 走一条强调综合集成的新道路。

计算机算法

计算机算法大致上分为三类：

• 线性或几乎是线性发杂性的算法，如排序 (sorting)、商务出来等；
• 多项式或较低的指数复杂算法，如矩阵运算等；
• 指数复杂性算法，如各种模式转换，、规划 (planning) 等。

第一类算法一般可用微机或服务器实现。第二类算法和问题规模大或有实时要求 的第一类算法需要并行计算机，已知的第二类算法几乎都是科学计算。超级计算 对第三类算法帮助不大，加速 100 万倍也只能稍稍扩大求解问题规模，需要寻 找新的思路。

计算机的历史

Gospel of Tux unearthed. Tux福音

1937 年，图灵先生写的论文<论可计算数及其在判定问题中的应用>一文是阐明现 代电脑原理的开山之作，被永远载入计算机的发展史册。

1939 年数学家图灵（Turing）提出了著名的图灵机模型（Turing's machine）， 定义图灵机（图灵计算）是：在用户确定了输入（I）输出（O）需求之后，可以 用程序（P）和数据（D）表达出来的算法实现，即图灵机为（I，O；P，D）。

1945 年 6 月，冯诺依曼与戈德斯坦、勃克斯等人联名发表了一篇长达101页纸的报告，即计算机史上著名的"101页报告"，直到今天，仍然被认为是现代计算机科学发展里程碑式的文献。

1946年冯-络伊曼给出了支持图灵计算的硬件计算机系统。之后硬件就按照摩尔 定律一直发展着。

有了硬件计算机后，实现图灵计算的软件程序设计语言飞速发展，解决社会生活 各领域应用问题的数据结构与算法分析的实现方法被不断发明出来，计算技术日 益成熟。这些成果基本上都被”图灵奖“所覆盖。

1986年，图灵奖得主、人工智能领域专家Brooks给出著名论断：软件工程有怪兽 而没银弹，即实现图灵计算的软件工程肯定不能满足人们的计算需求且效率低下。

一些观点

不为原则

MIT 的“不为”原则：“不做只要努力一定能成功的课题”。即要做没有成功把握的 研究。

一味提高速度不是明智的选择

芯片和计算机性能的提高已遇到功耗、可靠性和成本三面高墙，计算机科学应重 点突破这些技术发展的限制。

虚拟化是化繁为简的关键技术

一部计算机发展的历史可看作计算机技术不断虚拟化的历史。上世纪70年代， IBM 370首先使用虚拟计算机概念。计算机产业的发展不可能完全做到先提出完 美的顶层设计再按既定的标准发展，标准往往是在竞争中形成的。为了解决发展 过程中互操作和兼容等问题，常常通过虚拟机的思路在更高的层次隐藏下一层的 技术细节。我们要把虚拟机的思想理论化，使之成为计算机科学的重要内容。

book list

Architecture

• Computer Organization and Design: The Hardware/Software Interface David A.Patterson, John L.Hennessy
• Computer Architecture: A Quantitative Approach

Programming

• Computer Systems A Programmer's Perspective Randal E.Bryant; David O'Hallaron

OS Principle

• 现代操作系统
• 操作系统概念 (龙书)
• Operating Systems: Internals and Design Principles 操作系统—精髓与 设计原理 William Stallings

Windows

• Jeffrey Richter，“Advanced Windows”，3e，Microsoft Press，1997
• Walter Oney，“Programming the Microsoft Windows Driver Model”，2e， Microsoft Press，2003
• Art Baker，“The Windows NT Device Driver Book”，Prentice Hall，1996
• Gary Nebbett，“Windows NT/2000 Native API Reference”，MTP, 2000
• Sven Schreiber，“Undocumented Windows 2000 Secrets”，Addison-Wesley，2001
• Parasad Dabak, “Undocumented Windows NT”，M&T Books, 1999
• Rajeev Nagar，“Windows NT File System Internals”，O’Reilly，1997
• Mark E.Russinovich, David A.Solomon "Microsoft Windows Internals" 深入解析Windows操作系统

compile

• 龙书：Compilers:Principles,Techniques,and Tools

这本书，前端讲的太多了，可以从第六章看起，内容有一些旧,适合初学者

• 虎书：Modern Compiler Implementation in C

适合初学者

• 鲸书：Advanced Compiler Design and Implementation

适合有一定基础的，完全侧重后端优化，但是也适合初学者

Network & TCP/IP

• The Linux Network Architecture
• Understanding Linux Network Internals 2005
• Advanced Linux Networking
• The Linux TCPIP Stack—Networking for Embedded Systems

File System

• linux文件系统
• UNIX Filesystems - Evolution, Design, & Implementation

See Also

• 微软 360 度
• 对计算机科学的反思 李国杰
• 赵维和 petri 网