这是一门关于编程的课，主要目的：组织数据、处理数据、解决问题。

问题

问题：未知的事物，即各种What、Why、How。

尚未解决的问题的共性：表述含混、标准不一、结果不确定、涉及主观等。

解决之道：转换表述、明晰问题、建立数学命题与模型。

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

基于有穷观点的能行方法的计算模型：

有限数量的明确指令；
指令执行在有限步骤后中止；
指令每次执行都能得到唯一的结果；
可由人单独使用纸笔执行（机械式的执行）。

Turing Machine的计算模型

1936年Alan Turing提出一种抽象的计算模型，其基本思想为：用机器模拟人用纸笔进行数学运算的过程，但比数值计算简单。

基本概念：

在纸上写上或擦除某个符号；
注意力的转向；
在每个阶段，要决定下一步动作依赖于：此人当前关注位置、此人当前思维状态。

图灵机不是机器，只是思想上的计算模型。

基本定义：

1条无限长的分格纸带，每格可以记录1个符号；
1个读写头，可在纸上移动，能读出和擦写格子的字符；
1个状态寄存器，记录有限状态中的1个状态；
一系列有限的控制规则
- 某个状态，读入某个字符时：
- 要改写成什么字符？
- 读写头怎么移动？（左移 or 右移）
- 改变成什么状态？
构成了五元组：<当前状态，当前读入的字符，要改变成什么字符，如何移动读写头，要改变成什么状态>。

算法和计算的复杂性

对“问题”，可分为以下三类问题：

What：面向判断与分类的问题；
Why：面向求因与证明的问题；
How：面向过程与构建的问题。

用任何一个**“有限能行方法”的计算模型**可以解决的问题，都算是“可计算”的。

What：分类问题，可以通过树状的判定分支解决；
Why：证明问题，可以通过有限的公式序列解决（从不证自明的公理出发，一步步推理得到最后待证明的定理）；
How：过程问题，可以通过算法流程来解决（这门课的主要内容）。

“基于有穷观点的能行方法”的“可计算”概念：只关心问题的解决是否能在有限资源（时间/空间）内完成，并不关心具体要花费多少步骤或多少存储空间。

但资源（时间/空间）是有限的，因此解决问题还需要考虑可行性：

有些问题非常容易解决，如基本的数值计算等；
有些问题的解决程度尚可接受，如排序等；
有些问题的解决会爆炸性吞噬资源，没有什么可行性。

因此，有必要定义一些衡量指标，以对问题的难易程度（所需执行步骤数、所需存储空间大小）进行分类。

对于同一个问题，不同解法的解决效率也是不同的。

计算复杂性理论研究问题的本质：将问题按难易程度分类，研究各类问题的难度级别，不关心解决问题的具体方案。

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

不可计算问题

有些问题定义清晰，但无法解决。

并不是尚未找到解，而是在“基于有穷观点的能行方法“的条件下，已被证明并不存在解决方案。

不可计算数：大多数无理数都无法通过算法在有限时间内确定其任意一位是什么数。

如蔡廷常数：随机输入一段代码，该代码能成功运行并会在有限时间里终止的概率。

可计算数：可以通过算法在有限时间内确定这个数的任意一位数字。

如圆周率 $\pi$ ，自然对数 $e$ 。如果想知道第 $n$ 位是什么，总能在有限时间内计算出来。

这似乎说明解决问题的计算之道存在着边界和极限，而目前尝试突破计算极限的做法有：

超大规模分布式计算：机海战术；
光子计算：以超微透镜取代晶体管，以光信号代替电信号进行运算；
DNA计算：以DNA分子和酶的相互作用实现逻辑运算和数据存储；
量子计算：利用量子力学态叠加原理，使信息单元处于多种可能性的叠加状态，从而实现指数级别的并行计算；
分布式智慧：人海战术，聚集众多具有智慧的人脑来共同解决问题（如多人在线游戏预测蛋白质结构）。

抽象（Abstraction）

计算机科学：不仅仅是对计算机的研究，还研究问题、问题的解决过程、问题的解决方案。

抽象：为了更好地处理机器相关性或独立性而引入。从”逻辑“（logical）和”物理“（physical）的层次上看待问题及解决方案。

”抽象“的例子：

汽车
- 逻辑层次：汽车的操作使用。其操纵机构（油门、档位、方向盘等）称为“接口“（interface）。
- 物理层次：汽车的内部构造。其工作过程称为”实现“（implementation）。
计算机
- 逻辑层次：计算机的使用。
- 物理层次：计算机的内部原理。

对于程序员而言，编程时也会涉及到”抽象“，例如计算平方根，可以直接调用库函数，而不用从牛顿迭代法开始编程。

这种功能上的”黑盒子“称为”过程抽象“（procedural abstraction）。

无需关心内部是如何实现的。

编程

编程：通过一种程序设计语言，将抽象的算法实现为计算机可以执行的代码的过程。

编程就是对算法的一种实现。

图灵获奖者Niklaus Wirth提出了一个公式：

算法 + 数据结构 = 程序

程序设计语言需要为算法的实现提供机制：计算与存储。即，提供实现过程和表示数据的机制。

提供实现过程的机制具体表现为提供控制结构，如：

顺序处理
条件分支
循环迭代

提供表示数据的机制具体表现为提供数据类型，如：

整数
字符

但对复杂的问题，直接使用这些基本数据类型不利于算法的表达。

数据抽象

为了控制问题和问题解决过程的复杂度，利用抽象来保持问题的整体感，而不会陷入到过多的细节中。这要求对现实问题建模时，算法所要处理的数据要与问题本身保持一致性，不要有太多与问题无关的细节。

过程抽象启发了我们进行数据抽象。

相对于程序设计语言中基本的数据类型，抽象数据类型（abstract data type，ADT）是对**数据及数据处理（运算）**的一种逻辑描述，并不涉及实现这些运算的具体操作。

ADT只有功能的描述和实现调用的接口，用户可以直接使用抽象数据类型的接口，而无需关心接口是如何实现的。即，用户 $\leftrightarrow$ 接口（实现原理）。
ADT建立了一种对数据的封装（encapsulation），将可能的实现细节隐藏了起来，能有效控制算法的复杂度。
同一ADT可以采用不同的数据结构来实现，可以使用程序设计语言的控制结构和基本数据类型来实现ADT的逻辑接口（因为是实现，所以这属于ADT的物理层次）。
ADT希望对数据实现逻辑层次和物理层次的分离，可定义复杂的数据模型来解决问题，之后再去考虑此模型如何实现。

说到底，就是分离使用规则（逻辑）与原理实现（物理）。

如汽车与电动车都是车，虽原理不同，但是操作逻辑是一致的。

在接口的两端，一端面对操作使用的人员，一端面对实现原理的人员（操作用户（抽象） $\leftrightarrow$ 接口 $\leftrightarrow$ （实现）开发）：

用户可专注于使用数据接口来解决问题，无需考虑接口的实现；
底层开发程序员可专注于实现和优化数据处理，又不改变数据的使用接口。

常见概念

数据元素：数据的基本单位
数据项：数据的最小不可分割单位
数据类型：
- 数据类型是一种在程序员和编译器两者之间传输的信息类型，使编译器了解所要存储的数据的类型，以及所需占据的内存空间的大小。
- 用来分类数据，描述具有相同属性的数据。
- 表示变量的类型，其定义了特定变量将被分配所给定的数据类型的值。
  
  基本例子就是程序中所使用的各种变量的类型，如int、char、string。
  
  也可自己定义数据类型，例如自己实现的数据结构就可以作为一种数据类型。
数据结构：
- 存在一种或多种特定关系的数据元素的集合。
  
  具有不同形式和不同类型的数据元素的集合，这些数据可以被某些操作所处理。
- 数据结构是数据项的结构化集合，其结构性表现为数据项之间的相互联系及作用，也可以理解为定义于数据项之间的某种逻辑次序。
- 数据结构具有可执行的特定的操作（如插入、删除和遍历），整个数据可以用一个对象（object）来表示，并且可以在整个程序中使用。
  
  例如，当需要存储大量个人数据（包括姓名、年龄、电话等信息）时，这种类型的数据需要复杂的数据管理，这意味着其需要多个基本（原始）数据类型所组成的数据结构来帮助数据管理，保证对数据的运算或操作能够高效实现。此时，可称这种数据结构是一种数据类型。
- 根据逻辑次序的复杂程度，可以将各种数据结构划分为线性结构、半线性结构与非线性结构三大类。
抽象数据类型：
- 一个数学模型以及定义在此数学模型上的一组操作，仅具有功能的描述和实现功能的接口。
- 数据结构可以实现一个或多个特定的抽象数据类型（ADT）。
- 数据结构是抽象数据类型（所提供的规范）的具体实现（concrete implementation）。
  
  例如，对栈、队列、图等概念的学习就是对某一种抽象数据类型的学习。
- 抽象数据类型的实现可以采用不同的方式。
  
  例如，可以使用数组或链表等数据结构来完成对ADT队列的实现。

算法

学习的意义：

有助于面对未知问题的时候，可根据类似问题的解决方案来帮助思考；
不同算法有不同之处，可通过算法分析技术来评判算法本身的特性，而不仅根据实现算法的程序在特定机器和特定数据上运行的表现来评判；

即使同一程序，在不同的运行环境和输入数据的情况下，其表现差异也可能很大。
帮助判断某些棘手问题是否存在算法，若存在，其是否耗费大量资源；
帮助选择适应当前条件要求的某些算法。

Python

这里取一个小例子与C语言进行对比：打印一个朴素的三角形。

n = int(input("Input a number: "))
for i in range(1,n+1):
    print("*" * i)

#include <stdio.h>

int main()
{
    int n, i, j;
    printf("Input a number: ");
    scanf("%d", &n);
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < i; j++)
            printf("*");
        printf("\n");
    }
}