一、概述¶

数据时代¶

问题求解的计算之道¶

20世纪20年代，为了解决数学本身的可检验性问题，数学家希尔伯特提出——能否找到一种基于有穷观点的能行方法，来判断任何一个数学命题的真假。

20世纪30年代，几位逻辑学家格子提出了几个关于“计算”的数学模型。

哥德尔和克莱尼的递归函数

丘奇的 Lambda 演算模型

波斯特的 Post 机模型

图灵的图灵机模型

研究证明，这几个“基于有穷观点的能行方法”的计算模型，全都是等价的。

希尔伯特的计划最终被证明无法实现——不存在“能行方法”可判定所有数学命题的真假，总有数学命题，其真假是无法证明的。但是——“能行可计算”概念成为计算理论的基础。其中一些数学模型（如图灵机）也成为现代计算机的理论基础。

图灵机计算模型¶

图灵机模拟器软件 Visual Turing

算法和计算复杂性¶

问题的分类¶

What: 面向判断与分类的问题 —— 通过树状的判定分支解决；
Why：面向求因与证明的问题 —— 通过有限的公式序列解决，如数学定理的证明；
How：面向过程与构建的问题 —— 通过算法流程解决：即算法和相应数据结构的研究。

计算复杂性¶

计算复杂性理论研究问题的本质，将各种问题按照其难易程度分类，研究各类问题的难度级别（如容易解决、解决程度尚可接受、解法没什么可行性等），并不关心解决问题的具体方案。

算法¶

算法研究问题在不同现实资源约束情况下的不同解决方案，致力于找到效率更高的方案。

突破计算极限¶

超大规模分布式计算 - SETI@home：利用全球联网计算机共同搜寻地外文明的科学实验计划 - BONIC 平台

新型计算技术 - 光子计算 - DNA 计算 - 量子计算

分布式智慧 - Foldit：游戏化众包蛋白质结构分析 —— 相比分布式计算的闲置计算力，革命性地利用了空闲智力。 - Eyewire、phylo DNA puzzles 等

什么是抽象和实现¶

计算机科学主要研究的是问题、问题解决过程、以及问题的解决方案。

抽象（Abstraction）¶

为了更好地处理及其相关性或独立性，引入了“抽象”的概念。
用以从”逻辑 Logical“ 或 ”物理 Physical“ 的不同层次上看待问题或解决方案。
一般大众视角上，计算机可以用来编辑文档、收发文件、聊天娱乐等；
对于计算机科学家、程序员、系统管理员等来说，必须了解从硬件结构、操作系统原理、网络协议等各方面低层次细节，

利用既有功能只是计算机的“逻辑”层次。其内部如何实现，是计算机的“物理”层次。

抽象发生在各个不同层次上¶

抽象与实现：编程¶

图灵奖获得者 Niklaus Wirth 的著名公式，Pascal语言设计者。

Attention

算法＋数据结构＝程序

程序设计语言，需要未算法的实现提供实现过程和数据的机制，具体表现为控制结构和数据类型。

控制结构：顺序、分支选择、循环迭代
数据类型：基本的有整数、字符等，但对于复杂问题，直接利用这些基本类型，不利于算法表达。

为什么研究数据结构与算法？¶

数据抽象：ADT抽象数据类型¶

过程抽象，启发我们进行数据抽象
ADT（Abstract Data Type）相对于程序设计语言中的基本数据类型，ADT是对数据进行处理的一种逻辑描述，并不涉及如何实现这些处理。
抽象数据类型ADT，建立了一种对数据的封装，即 Encapsulation。
封装技术将可能的处理实现细节，隐蔽起来，能有效控制算法的复杂度。

数据结构是对 ADT 的具体实现¶

同一个 ADT，可以采用不同的数据结构来实现
采用程序设计语言的控制结构和基本数据类型来实现 ADT 所提供的逻辑接口。

这种实现，属于 ADT 的物理层次。

ADT 实现：数据结构 DS（Data Structure）¶

对数据实现逻辑层次和物理层次的分离，可以定义复杂的数据模型，来解决问题，而不需要立即考虑此模型如何实现。

接口的两端：抽象与实现¶

类似于电动车 vs 汽油车

底层动力、能源不同

但是开车的操作接口（方向盘、油门、刹车、档位等）基本相同

由于对抽象数据类型可以有多种实现方案，且独立于实现的数据模型，则可以通过层层抽象，降低问题解决过程的复杂度。

底层开发程序员，专注于实现和优化数据处理，而不改变数据的使用接口。
用户专注于用数据接口来进行问题的解决，而无需考虑如何具体实现这些接口。

为什么要研究和学习算法？¶

面对未知问题，有助于根据类比方法，找到相似的解决方案。
各种算法的差异通常比较大，可以通过算法分析技术，来评判算法本身的特性。
对于棘手问题，判断是否存在相应算法，或者是有算法，但是需要耗费大量资源。
某些问题的解决，需要一些折衷的处理方式。

拓展阅读¶

《未来简史》
《超时空接触 Contact 1997
《模仿游戏 The Imitation Game 2014》