3.26在线视频

我们找那个数学模型以后

就要进行第二次映射

就是把问题从数学世界映射到机器世界

那么这个过程是经过算法和程序设计完成的

为什么需要这个映射过程呢

原因就在于机器是不能理解人的语言的

在机器世界里只有0和1这样的二进制数

机器能做的无非就是0和1的翻转

那么在这种情况下

我们必须要把我们自己做的事情

用机器能理解的方式告诉它

然后才能由机器来执行

这个过程就是是让计算机

理解已经形成的数学模型

这个过程

这个映射的过程

大部分的工作仍然是由人完成的

当然

最后的执行和计算过程是由机器完成的

那么怎么样才能让计算机理解数学模型呢

也要经过两个步骤

首先是把数学模型算法化

然后再把算法程序化

通过这两个步骤

我们就能把一个数学模型转化成

机器理解的程序

我们先来看看数学模型算法化的过程

算法是什么呢

从广义上来讲

算法实际上是解决问题的思路

和步骤的总和

举一个生活上的例子

在四川我们喜欢吃火锅

烫毛肚是非常受欢迎的

我们是这样教外地的朋友烫毛肚的

烫毛肚分成3个步骤

第一个步骤先把生毛肚

夹起来放入锅中

第二步

让毛肚完全浸在水里数秒

一般是15-20秒的时间

第三步

再把烫好的毛肚夹起来粘上作料放进嘴里

这个过程是吃毛肚的详细步骤

实际上就是在生活当中运用算法的过程

当然

这是广义的算法

我们在这里说的算法是狭义的算法

是数学函数的计算步骤的分解

也就是把数学模型计算步骤细分的过程

比如我们要计算两个数的算术平均

步骤应该怎么进行呢

第一步

先输入两个实数a和b

第二步把a和b加在一起并把这个结果告诉c

第三步就是把c除以2算出平均值并输出

这个过程的描述和刚才吃毛肚的过程描述

其实是类似的

都是通过一系列的方法和步骤

得到一个结果的过程

只不过一个是运用在生活里

一个运用在了数学里

我们再讲一个例子加深大家对算法的理解

这个是一个关于得到平均工资的问题

某个公司一共有十个员工

每个人的月薪工资都不一样

有的是5000

有的是1万

有的是两万

现在

需要得到这十个人的平均工资

但是问题是这十个人

都不想让其他人知道自己的

工资的实际数额

因为工资低的觉得没面子

工资高的怕别人人妒忌

在种情况下

我们怎么用一种方法

在不需要告诉其他人自己工资的情况下

得到这样一个平均工资呢

这就需要一种算法

其中一种算法是这样的

第一步

第一个人把自己的工资a1

加上一个其他人都不知道的随机数x

得到另一个数a2

那么这个数其实隐藏了第一个人的工资

第二步

第一个人把a2这个数交给第二个人

当然

第二个人是不知道第一个人的工资

然后再把这个a2加上自己的工资a3

这样依次加下去

直到所有人的工资都被加上去

得到一个总和

比如我们叫这个总和为b

在这个过程当中

因为那个加进去的随机数x

所以没有人知道其他人的工资

第三步

第一个人把最后的总数b

减去刚才的那个随机数x

这样就得到所有人的工资数的总和a

第四步

把工资数的总数再除以人数10

就得到了平均工资

这就是关于这个问题算法的描述

其实在抽象与建模的阶段

我们就已经找到了一个函数f(x)

当我们输入所有人的工资和随机数x

就会得到大家的平均工资

这个算法实际上

就是数学函数的具体实施步骤

其实这个算法就是最典型的加密算法的原型

加密过程就是这样完成的

在加密算法里最开始的信息叫明文

需要通过随机数的一次运算

转换成大家都猜不出意义的一个数

我们称这个随机数为密钥

这个转换的过程就是加密运算的过程

这样通过算法就把明文和密钥结合在一起

得到了加密信息

然后我们再把加密信息放到信道进行传输

这样一来

任何没有秘钥的人都

无法知道这些信息的含义

最后接到加密信息的人

通过秘钥进行逆运算

就会得到明文这种算法叫对称加密算法

当然加密算法还有非对称加密算法

在这个地方那就不展开讨论了

算法设计是第二次映射当中的核心问题

算法设计的方法有很多

我们在这里简单介绍三种主要的

第一种是穷举算法

第二种是分解算法

第三种是并行算法

穷举法就是尝试把所有

满足条件的可能解都找出来

然后挑选出符合题目目标的解

渡河问题就是典型的运用穷举法的案例

比如在渡河算法里

首先把起始向量a1111

分别与运载向量b相异或

然后得到一个新的向量

接着判断这个新的向量是不是

渡河结束的向量a0000

那么如果是

表明渡河完成了

整个过程就结束了

如果不是

那么就要判断这个新的

状态向量是不是可取的状态向量

那么如果是的话

就把这个可取状态向量重新放在我们

初始值里面

继续使用它

然后再反复进行上面的过程

这样就可以把所有的渡河的状态全部都得到了

这实际上是一种暴力解法

暴力解法就是我们找到所有有可能的解

答案一定在这些解里

当深蓝

战胜人类的国际象棋冠军

也是用了这种算法

我们可以看到

穷举算法的计算量是非常大的

那么分解算法

是把一个复杂问题逐步分解简化的算法

比如在查找算法里

如果要查找的信息非常多怎么办呢

我们可以用二分法把问题逐步分解

也就是先查找所有信息里其中的一半

然后再找出另外一半

再一直以对半的方式分支下去

直到找到想要查找的信息为止

排序算法也是如此

怎么样把一堆数据进行排序呢

比如说从小到大进行排序

那么我们同样先把数据分成两半

然后再对分解的数据继续进行分解

直到不能分解为止

然后把这些数两两进行比较

按从小到大进行排序

然后我们把这个结果

合在一起再一次进比较和排序

这样我们就能得到这一堆数据的排序了

分解算法的实际上

是把一个复杂问题简单化的过程

那么并行算法呢

是把大的问题分解为多个独立的小的问题

这样

就可以同时处理这些小问题

这样做的目的是节约解决问题的时间

并行算法用的途径非常广

刚才提到的分解算法

其实已经用到了并行的概念

计算机体系结构和

机器学习里的神经网络

尤其是深度神经网络

大量的应用了这种并行算法

例如

在机器学习的运算当中

需要做大量的矩阵运算

那么这些矩阵运算

可以被分成多个独立的

小的矩阵运算

然后把这些独立的矩阵运算

放入GPU的多个独立运算器

通过这些独立矩阵单元的同时运算

来完成整个运算过程

这就是为什么在我们的机器

学习里大量的使用gpu的原因

那么GPU是由多个独立的

并行运算单元组成的

GPU的硬件设计

本身就非常适合进行并行运算

上面我们讨论了第二个映射的第一步

就是把数学模型算法化的过程

这个过程仍然是由人来完成的

接着我们要谈一谈第二次映射的第二步

就是把算法程序化的过程

其实就是把算法编写成程序

让计算机理解的过程

我们在以前的课程当中讲过

冯氏机是由组合逻辑电路实现的

那么核心就是对二进制数0和1进行各种操作

也就是说计算机只能理解0和1组成的机器语言

但是我们的算法

并不是用计算机

能够理解的0和1描述的

怎么办呢

只能通过对算法进行编程来进行转换

刚才我们看到

算法其实就是

实现数学模型的方法和步骤的集合

是靠一连串的逻辑判断来完成的

这些逻辑判断完全可以通过编程的方式来实现

比如if

then

else这样的逻辑编程语句

这样一来

我们就可以把算法

用编程语言的方式表达出来了

然后再经过编译

汇编等一系列变化

把这些程序转换成一堆

0和1组成的文件

我们称这样的文件格式为机器语言

那么这就是计算机可以理解的语音

这样

计算机终于理解了这些算法

并按算法的要求进行计算

最终可以得到结果

比如针对渡河问题

我们把刚才设计好的算法程序化

用c语言来实现

并且设计了四个功能函数

其中的主函数

也就是渡河函数通过用if

else这样的逻辑判断语言

以及对不同的功能函数的调用

把渡河算法用计算机编程的方式实现了

然后再通过把程序进行编译和汇编

把它变成一系列的0和1组成的机器语言文件

最后把这些可执行文件告诉计算机

这样计算机就能顺利的理解这些算法

并且执行了

好

我们来回顾刚才发生了什么

把现实问题

转换成计算机能理解的问题

是通过两次映射完成的

首先是通过抽象和建模

把问题转换成数学模型

然后

再通过把数学模型算法化

和程序化的方式的过程

转换成机器能够理解的信息

也就是机器语言

最后

由计算机来进行整个的运算执行

通过这样的方式

人们可以利用计算机高速运算的特点

来完成一系列的复杂而耗时的运算

这其中两次映射其实都很关键

尤其是把问题数学化的过程最为重要