以下内容来自中国大学慕课网的相关慕课（翁恺老师的程序设计入门、李戈老师的计算概论与程序设计基础、郭炜老师的程序设计与算法、陈斌老师的数据结构与算法Python版（除了这个其它的都是C或C++语言）、陈越老师的数据结构）以及C++ primer plus书籍，仅供个人学习参考使用，如有侵权请联系笔者删除。笔者水平有限，理解有错还望谅解指教。

目录

0. 前言

1. 计算机的基本原理

0）抽象的“计算”概念的提出

1）计算机的理论模型——图灵机

图灵机的构成

图灵机的工作步骤：

图灵机工作的例子

2）计算机为什么能计算？

数在计算机中如何表示？

逻辑上数是如何计算的？

物理上数的计算是如何实现的？

2. 程序设计语言

1）从汇编到C再到C++语言

2）计算机如何执行程序

3. 数据结构与算法

1）什么是数据结构（data structure）

2）如何描述数据结构

3）什么是算法

4）什么是好的算法

5) 为什么研究数据结构与算法

0. 前言

我们要让计算机做事情，就要找出算法，然后用编程语言写程序，然后让计算机去执行程序。

计算机——程序——算法

计算机科学不仅仅研究计算机硬件，还主要研究：问题（数据结构），问题解决的过程或步骤（算法）以及问题解决的方案（计算复杂度、算法分析）。为了更好地处理机器独立性和相关性，需要引入“抽象”和“具体”的概念，用以从“逻辑”或“物理”的不同层次上看待问题及解决方案。

什么是抽象？以汽车打比方：从司机角度看到的是一台带人去往目的地的代步工具，司机驾驶时看到汽车的逻辑功能层次，即操作各个机构来实现各个功能（换挡、转弯、刹车、点火等）这些操纵机构（档位、方向盘、脚刹、油门等）就称为接口（Interface）；从汽车修理工角度，还清楚汽车每项功能是如何实现的（发动机工作原理、档位操作的机械结构等），这些内部构造是汽车的物理层面，它们的工作过程称为实现（Implementation）。回到计算机：对于和我水平相当的计算机小白而言，看到的是计算机的逻辑层次，比如可以编辑文档、上网聊天、收发邮件等等，不用知道计算机内部如何处理；对于专业人士而言，看到的是计算机的物理层次，需要了解从硬件结构、操作系统原理到网络协议等各方面的低层次细节。当然，逻辑和物理是相对的。

下面简单讨论一下编程，后文还会详细展开。编程时也会涉及到“抽象”，实现一个功能时不用管这个功能是如何实现的，这种功能上的“黑盒子”称为“过程抽象”，比如调用库函数。但编程一般对应的是实现，指的是通过一种程序设计语言，将抽象的算法实现为计算机可执行的代码的过程。

程序设计语言 需要为 算法的实现 提供 实现“过程”和“数据”的机制，具体表现为“控制结构”和“数据类型”。其中，控制结构有顺序处理、分支选择、循环迭代。每种程序设计语言都有语句（像if，while，for）对应控制结构；也会提供基本数据类型来表示数据，但对于复杂问题而言，直接使用基本数据类型不利于算法的表达和问题的解决，比如C++的数据表示有多种类型——整数、小数、字符、字符串、用户定义的、由多种类型组成的复合结构。

讯享网

问题可以分为三类：

1. what：面向判断与分类的问题
2. why：面向求因与证明的问题
3. how：面向过程与构建的问题

用“有限能行方法”下的计算模型可以解决的问题都是可计算问题（后文有解释），问题的解决有三类：

1. what：利用有限的规则和有限次的判断，通过树状的判断分支解决
2. why：利用有限的推理规则和有限的公式序列，通过一步步推出公式解决
3. how：通过算法流程（顺序、条件分支、循环）解决

基于有穷观点的能行方法的“可计算”概念仅仅涉及到问题的解决是否能在有限的资源（时间、空间）完成，并不关心花费多少计算步骤或多少存储空间（即规模）。问题的解决还需要考虑其可行性，有些问题的解决会爆炸性地吞噬资源，虽有解法但没什么可行性，如哈密顿回路、货郎担问题。

因此我们需要计算复杂性理论：研究问题的本质，定义一些衡量指标，对问题的难易程度（步骤数、存储空间大小）分类，研究各类问题的难度级别，并不关心解决问题的具体方案。然而对于同一个问题，会有不同的解决方案，解决效率也是千差万别。这时我们需要算法分析：研究问题在不同现实资源约束下的不同解决方案，致力于找到效率最高的方案。比如：不同硬件配置（手机、PC、超级计算机）、运行环境（网络环境、单机/多机）、应用领域（工业控制、医疗系统）、使用状况（省电/正常）下具体的算法哪个好。计算复杂性理论是研究对于问题的分类，算法分析是研究对不同运行条件下最高效率的实现。

有的问题需要我们突破计算的极限。

一种方法是超大规模分布式计算即机海战术，利用闲置计算力（公众利用全球联网计算机共同计算搜寻，如地外文明、蛋白质分子结构、气象）；或者众包学术研究即人海战术，利用空闲智力，如通过多人在线游戏预测蛋白质结构。

另一种方法是研究新型计算技术：

1. 光子计算：用纳米级的超微透镜取代晶体管，用光信号代替电信号进行运算。光芯片无需改变二进制计算机的软件原理，但可以轻易实现极高的运算频率，而且能耗低，不需要复杂的散热装置
2. DNA计算：以DNA分子和酶的相互作用实现逻辑运算和数据存储（剪切、复制、粘贴映射为逻辑运算），计算并行度和存储能力高。
3. 量子计算：利用量子力学态叠加原理，让每个信息单元处于多种可能的叠加状态（0，1，同时是0和1），从而实现指数级别的并行计算，根本上解决最高复杂度计算问题。

1. 计算机的基本原理

计算机做的所有事情都是“计算”。

0）抽象的“计算”概念的提出

20世纪20年代，为了解决数学本身的可检验性问题，大数学家希尔伯特提出“能否找到一种基于有穷观点的能行方法，来判定任何一个数学命题的真假“，这种基于有穷观点的能行方法：由有限数量的明确有限指令构成； 指令执行在有限步骤后终止； 指令每次执行都总能得到唯一结果； 原则上可以由人单独采用纸笔完成，而不依靠其它辅助； 每条指令可以机械地被精确执行，而不需智慧和灵感。

20世纪30年代，几位逻辑学家各自独立提出了几个关于“计算”的数学模型：哥德尔和克莱尼的递归函数模型 丘奇的Lambda演算模型 波斯特的Post机模型 图灵的图灵机模型（这几个计算模型后来被证明是等价的）。虽然希尔伯特的计划最终被哥德尔证明无法实现，但“能行可计算”概念成为计算理论的基础，其中的一些数学模型（如图灵机）也成为现代计算机的理论基础。

1）计算机的理论模型——图灵机

根据哥德尔不完备性定理，任何一个数学系统，只要它是从有限的公理和基本概念中推导出来，并且从中能推证出自然数系统，就可以在其中找到一个命题，对于它我们既没有办法证明，又没有办法推翻。那么，可以或不可以被证真、证伪的边界在哪里？也就是说，怎么判断一个未解的问题能不能有解？

在计算机中，我们称有解的问题为可计算问题，而无解的问题为不可计算问题。

被证明的 不可计算问题 有 停机问题：判定任何一个程序在任何一个输入情况下是否能停机。还有不可计算数：除了圆周率pi和自然对数的底e，几乎所有的无理数都无法通过算法确定任意一位是什么数字。

如何判断可计算还是不可计算？研究思路有：为计算建立数学模型，称为计算模型；然后证明：凡是这个模型能计算的任务，就是可计算的问题。

图灵在《论可计算数在判定问题中的应用》提出了一种数学模型——图灵机。

图灵机的构成

1. 一条存储带：双向无限延长，上有一个个小方格，每个小方格可存储一个数字或字母
2. 一个控制器：含一个读写头（可以读、写、更改小方格），可以接受设定好的程序语句，可以存储当前自身的状态，可以变换自身的状态，可以沿着存储带一格格左移或右移

图灵机的工作步骤：

1. 准备： （1）存储带上符号初始化； （2）控制器设置好自身当前状态； （3）读写头置于起始位置； （4）准备好工作程序；

2. 反复执行以下工作直到停机： （1）读写头读出存储带上当前方格中 的字母/数字； （2）根据 自身当前状态 和 所读到的 字符，找到相应的程序语句； （3）根据 相应程序语句，做三个动作： ① 在当前存储带方格上写入一个相 应的字母/数字； ② 变更自身状态至新状态； ③ 读写头向左或向右移一步

b表示空白。每一行表示一个程序语句，每个语句包含5个符号，前两个是条件，后三个是动作。

 图灵机停机表示计算完毕，意味着得出计算结果

图灵机工作的例子

B表示空白

2）计算机为什么能计算？

数在计算机中如何表示？