我所认识的编程与计算机

按照上面的算法的定义，算法设计在某种意义上就是程序的设计。但这里的所指的算法范围可能更小，集中于某些一般性问题的解决。

算法的设计是是运筹学（operation research）的许多解决方法理论的一部分，例如动态规划（dynamic programming）和分治法（divide-and-conquer）。算法的设计与实现技术也叫做算法设计模式。算法设计最重要的概念之一是运行时效率，它也被叫做大O（Big O）。

算法设计的一般步骤包括：

1. 定义问题
2. 建立一个模型
3. 指定算法
4. 设计算法
5. 检查算法的正确性
6. 分析算法
7. 实现算法
8. 程序测试
9. 编写文档

按照实现方式分类，算法可以分为：递归算法，逻辑算法，序列算法、并行算法和分布式算法，确定性和不确定性算法，精确和非精确算法。

按照设计范式分类，可以分为：暴力算法，分治算法，枚举算法，概率算法，规约算法，回溯算法。

按照优化问题分类，可以分为：现性规划算法，动态规划算法，贪婪算法，启发式算法。

按照复杂度分类，可疑分为：常数时间算法，线性时间算法，多项式时间算法，指数时间算法。

开头的名言是这么说的，程序 = 算法 + 数据结构。上文中我说过算法在某种意义上和程序是等价的，那么为什么还需要存在数据结构这个概念？如果你上过编程课的话，你大概率会学过叫做《算法与数据结构》或者类似的课程，课程名中算法与数据结构是并列关系。两者的区别和联系何在？参考资料【12】的回答中有着不同的理解和解释，经过整理和总结后的内容如下。

1. Konrad Garus 的观点：算法和数据结构是不同的。考虑一下对二叉树的前序中序后序遍历，这是三种算法，但是作用对象是一个数据结构。再考虑一下对二叉树，B 树，AVL 树的遍历操作，这是一种算法，但是对象是 3 个数据结构，算法有时是独立于数据结构的，有时又不是，某种算法对于不同的数据结构可能有不同的复杂度。
2. N 1.1 的观点：算法和数据结构关系非常紧密。算法依赖于数据结构，如果改变了两者中的任意一个，复杂度可能会发生显著的变化。特定的算法最好用于特定的数据结构，算法和数据结构是齐头并进的关系。
3. user287792 的观点：它们是不同的大学课程。一般而言，数据结构课程强调编程，而且它是先于算法课程的，而算法课程强调对算法的数学分析。

让我们来看看维基百科上的关于数据结构的定义：

在计算机科学中，数据结构是一种数据组织，管理和存储的格式，它允许高效的访问和修改。更准确地说，数据结构是数据值，它们之间的关系以及可以应用于数据的功能或操作的集合。

数据结构是抽象数据类型（ADT）的基础。ADT 定义数据类型的逻辑形式，数据结构负责实现数据类型的物理形式。不同类型的数据结构适用于不同类型的应用，其中的一些是高度特化于指定问题的。

在参考资料【14】中有这样一句话：

Algorithms are like verbs and Data Structures are like nouns. An Algorithm is just a method of doing something on a computer, while a Data Structure is a layout for memory that represents some sort of data. - Om Singh

它的大意是：算法和数据结构就像是动词和名词。算法就是在计算机上做事的方法，数据结构是表示某种数据的内存布局。

根据以上内容，我们可以得到算法与数据结构之间的关系：

1. 算法与数据结构是不同的东西
2. 算法与数据结构的关系相当紧密
3. 高效的算法和高效的数据结构有助于高效地解决问题

就我个人而言，算法和数据结构的提出都应该是基于需要解决的问题的。解决问题的第一步应该是对问题进行抽象，找出关键的影响因素并建立相应的模型，从而得到描述问题的数据结构抽象。接着，对问题的解决应该是基于得到模型展开的，从这里才开始算法的设计。算法是“一个定义了一系列操作的规则集合”，对数据结构的 操作 自然也属于这个操作集合。算法和数据结构，两者一动一静，共同组成了程序。数据结构在程序中的作用是不可忽视的，更准确的问题描述有助于更简单的解决问题。

回到标题”为什么会有算法和数据结构的区分“，现在我可以这样回答：数据结构在算法中的价值值得它被单独拎出来进行研究。

最普遍和最简单的数据结构估计就是这样几种：数组，链表，栈，队列，堆，二叉树，哈希表。

软件开发的方法论是一个用来设计、结构化和控制开发进程的框架。各种各样的框架已经演化了许多年，每种都有它自己的长处或弱点。软件开发的方式有很多种，有些方法使用更加结构化和基于工程的方法来开发软件，有些则采用更增量的方法，软件随着开发过程而不断进化。某种系统开发方法论不一定适用于整个项目。

大多数的方法论都有以下软件开发阶段的某种组合：

• 分析问题
• 市场研究
• 收集计划软件的需求
• 为软件开发制定计划
• 实现（编码（coding））软件
• 测试软件
• 分发软件
• 维护软件和修补 bug

这些阶段通常统称为软件开发生命周期或 SDLC（software development life-cycle）。不同的软件开发方法可能会以不同的顺序安排这些阶段，或是为不同的阶段分配不同的时间。不同方法有着不同的优缺点，解决问题的最佳方法是取决于问题的类型。

编程范式是计算机编程的一个基调（fundamental style），它一般不是由项目管理方法论来决定的。不同范式在用于表示程序元素的概念和抽象上（例如对象，函数，变量，约束），以及构成计算的步骤（例如赋值，求值，延续（continuation）和数据流）上表现为不同。有时，范式所主张的概念在高层系统体系（方法学）中被联合使用。在其他情况下，编程范式的范围限定于程序或模块的内部结果。

编程语言可以有多种范式。例如，C++ 写的程序可以是纯过程式的，或纯面向对象，或者是包含了两种范式元素。在面向对象编程中，程序员可以将程序看作一系列交互的对象，在函数式编程中则可被看作一系列无状态函数的求值。当在多系统或多处理器上编程时，面向进程编程（process-oriented programming）则允许程序员将应用程序看作一个对逻辑共享数据结果进行操作的并发进程集合。

就像软件工程中的不同群体提倡不同的方法论一样，不同的编程语言也提倡不同的编程范式。一些语言被设计为只支持一种范式（Smalltalk 支持面向对象编程，Haskell 支持函数式编程），其他的支持多范式（比如 Object Pascal，C++，C#，Visual Basic， Common Lisp，Scheme，Python，Ruby）

高阶的范式包括：

• Aspect-oriented software development 面向方向的软件开发
• Domain-specific modeling 特定领域建模
• Model-driven engineering 模式驱动工程
• Object-oriented programming 面向对象编程
• Search-based software engineering 基于搜索的软件工程
• Service-oriented modeling 面向服务建模
• Structured programming 结构化编程
• Top-down and bottom-up design 自顶向下和自底向上设计

编程语言是由提供各种输出的指令集组成的形式语言。编程语言被用在计算机编程中，来实现算法。编程语言是计算机程序的实现过程中必要的工具。

对编程语言的描述通常分为语法和语义两个部分。有些语言由 specification document 定义（例如， C 语言由 ISO 标准指定），而另一些语言有一个被当作标准的主导实现（比如 Perl）。一些语言同时具备两者，既有标准定义的基本语言，又有从主要实现中得到的通用扩展。

掌握一门编程语言，基本上就是掌握它的语法，它的标准库和一些语言特有的特性了。王垠在一篇文章【5】中写到”任何一种语言，都是各种“语言特性”的组合。“这里引用他文章里的几段话。

任何一种“语言”，都是各种“语言特性”的组合。打个比方吧，一个程序语言就像一台电脑。它的牌子可能叫“联想”，或者“IBM”，或者“Dell”，或者“苹果”。那么，你可以说苹果一定比 IBM 好吗？你不能。你得看看它里面装的是什么型号的处理器，有多少个核，主频多少，有多少 L1 cache，L2 cache……，有多少内存和硬盘，显示器分辨率有多大，显卡是什么 GPU，网卡速度，等等各种“配置”。有时候你还得看各个组件之间的兼容性。

这些语言特性，就像你在选择一台电脑的时候，看它里面是什么配置。选电脑的时候，没有人会说 Dell 一定是最好的，他们只会说这个型号里面装的是 Intel 的 i7 处理器，这个比 i5 的好，DDR3 的内存 比 DDR2 的快这么多，SSD 比磁盘快很多，ATI 的显卡是垃圾…… 如此等等。

按照王垠的观点，语言是语言特性的巧妙组合。语言特性相对于语言，正如骨骼之于人体，把握好语言的骨架知识有助于对不同语言的学习掌握，毕竟万变不离其宗。

编程语言与上文提到的编程范式有着十分紧密的联系，编程语言体现着语言作者对于编程风格的见解，作者钦定的”一等公民“以及支持的语法就决定了在语言中使用某种编程范式的难易程度。试想在面向过程的 C 语言中编写面向对象风格的代码，虽然这样是可行的（比如 GObject），但是这样做相对于支持面向对象范式的语言显得十分别扭（可能需要各种变态的宏）。在 Scheme 中过量使用赋值也会使代码的可读性显著下降，远远不如函数式简洁。语言想要引入多范式就需要考虑到各个范式之间的相互影响，这种影响通常并不是什么好事，各范式之间的相容性可能并不怎么好。

编程的过程是在纯文本上进行的，想要编辑文本，自然是需要编辑器。完成代码的编写后，下一步是将它丢到解释器或编译器中观察输出结果。如果出现了错误，则需要根据错误提示对程序进行调试，如此反复得到满足要求的程序。

当未被处理的数据在输入设备的帮助下被发送到计算机时，数据会被处理并发送到输出设备。输入设备可以是手动的也可以是自动的。数据的处理过程由 CPU 负责。常见的输入设备包括：

• 计算机键盘，Computer keyboard
• 鼠标，Mouse
• 触摸板，Touchscreen
• 数字相机，Digital camera
• 扫描仪，Image scanner

计算机给出输出的设备即为输出设备，常见的输出设备包括：

• 计算机显示器，Computer monitor
• 打印机，Printer
• 声卡，Sound card
• 显卡，Video card

控制单元（通常叫做控制系统或中央控制器）管理着计算机的各个组件；它读取并解释程序指令，将它们转化成控制信号来激活计算机的其他部分。某些高级计算机的控制单元可能会打乱某些指令的执行顺序来提高性能。

所有 CPU 共有的关键组件是程序计数器（program counter），它是一种特殊的存储单元（寄存器），用于追踪下一条要读取的指令在存储器中的哪个位置。

控制系统的功能如下所示 —— 需要注意的是，这是一个简化后的版本。

1. 从程序计数器指定的单元读取下一条指令
2. 对数字指令码进行解码得到一个命令或信号集
3. 增加程序计数器，使它指向下一条指令
4. 从存储（或其他输入设备）中读取指令要求的数据。数据的位置一般存储在指令码中
5. 为 ALU 或寄存器提供必要的数据
6. 如果指令需要使用 ALU 或专用硬件来完成，则指示（instruct）硬件执行所需操作
7. 将 ALU 中的结果写回到存储区域，或写入到寄存器，或是一个输出设备
8. 回到第一步

因为程序计数器不过是另一种存储单元，它可以通过 ALU 的计算进行改变。对程序计数器加上 100 会导致下一条指令从距离当前指令 100 个单位的地方被读取。修改程序计数器的指令一般叫做”跳跃“（jumps），它允许循环和条件执行的实现。

控制单元处理指令序列的操作本身就像一个简单的计算机程序（一个简单的解释器），实际上，在更复杂的 CPU 设计中，还有一个被叫做微序列器（microsequencer）的小计算机，它运行一个微代码程序来控制这一切的发生。

ALU 负责两类操作：算数和逻辑。某个 ALU 支持的算数操作可能被限制在加法和减法，其他的可能包括乘除法，三角函数以及开平方。某些 ALU 只能计算整数，而其他的一些可以计算有限精度的浮点数。然而，所有只能进行简单计算的计算机可以通过编程来进行更复杂的运算。因此，通过编程，所有的计算机都可以进行任意的算数运算 —— 即使因为 ALU 不直接支持运算而需要更多的运算时间。逻辑运算包括与运算，或运算，异或运算和非运算。这些运算可以用来创建复杂的条件语句和处理布尔逻辑。

超标量（Superscalar）计算机可能包含多个 ALU，这允许它们能同时执行多个指令。图形处理器以及使用 SIMD 和 MIMD 特性的计算机通常包含能够处理向量和矩阵的 ALU。

控制单元，ALU，和寄存器被统称为中央处理单元。早期的 CPU 由许多分立组件组成。从 1970 年代开始，CPU 一般被构建在一片叫做微处理器的 MOS 集成电路芯片（MOS integrated circuit）上。

计算机存储可以看作一系列的单元，可以从单元中读取和写入数字。每个单元有一个数字”地址“。计算机可以使用使用像是”把数字 123 放入编号为 1357 的单元中“或”把在编号为 1357 单元中的数字和编号为 2468 单元中的数字相加并把结果放到编号为 1595 单元中“的指令。存储在计算机存储中的信息可以表示任何的东西，比如数字，字母，甚至是计算机指令。

在几乎所有的现代计算机中，每个存储单元被设置为存储 8 个比特位（叫做字节）。每个字节可以表示 256 个不同的数字（2^8 = 256）；可以是从 0 到 255，也可以是从 -128 到 +127。要想存储更大的数字，可以将几个连续的字节连在一起用（一般是两个，四个或八个）。当需要表示负数时，数字一般使用 2 的补码形式存储。

CPU 包含一个叫做寄存器的特殊存储单元集合，它可以以远快于主存的速度进行读写。寄存器的数量在 2 个到 100 个之间，具体的数量取决于 CPU 的类型。寄存器用来存储使用最频繁的数据项，以此避免每当需要数据时主存中读取。

计算机主存有两个主要种类：

• 随机访问存储或者叫 RAM，random-access memory
• 只读存储或者叫 ROM，read-only memory

RAM 可以在 CPU 命令下达的任何时间进行读写，而 ROM 则预装载了不可改变的数据和软件，因此 CPU 只能对它进行读取。ROM 一般用来存储计算机的初始化指令。一般来说，RAM 的内容会在计算机关机后被擦除，但是 ROM 会保持数据不变。在 PC 上，ROM 包含着一种叫做 BIOS 的程序的信息，它被用来在计算机开机或重启时从硬盘中引导操作系统进入 RAM。在嵌入式计算机中，计算机可能没有硬盘驱动，所有需要的软件都放在 ROM 中。存储在 ROM 中的软件一般叫做固件（firmware），因为它比起软件更像是硬件。闪存（Flash memory）模糊了 ROM 和 RAM 的区别，它可以在关机时保存信息，但它同时也是可写入的。它的速度一般比传统 ROM 和 RAM 慢很多，因此它应用在对速度要求不高的地方。

计算理论科学从本质上讲是数学和抽象的，但它也是用实践和日常的计算中获得驱动力的。它的目的是理解计算的本质，并以此理解和提供更高效的算法。所有和数学，逻辑以及形式概念和方法有关的研究都可以视作计算理论科学，只要它的动机明显来自计算领域即可。

软件工程对设计，实现和修改软件的研究，以确保软件的高质量，合适的价格，可维护性和可构建性。它是软件设计的系统方法，设计将工程实践应用于软件。软件工程涉及软件的组织和分析 —— 它不仅涉及新软件的创建或制造，还涉及其内部的组织与维护。