1.1 算法概念导入在线视频

同学们大家好

我是云南大学信息学院计算机科学与工程系的教师孔兵

这学期我们开始一起学习《数据结构》这门课程

这门课是计算机专业最重要的一门课程

先说一下这个课程的教材

我们选用的是清华大学严蔚敏老师

编写的数据结构教材

《数据结构C语言版》

这本教材是被广泛认可的

数据结构优秀教材

我们先从一个概念开始—

知识

这个概念应该是我们都听说过的

那么，什么是知识呢

这个概念并不容易说清楚

我给一个简单的说法

知识是人类对自然和社会的认知

记录传承下来

就是所谓的知识

根据知识的特征

我们可以大致分成两大类知识

陈述性知识和过程性知识

陈述性的知识

主要是回答是什么这样一个问题

下面大家看到的这个例子

是一个最大公约数的定义

这样的知识就是所谓陈述性知识

它给出了最大公约数的定义

换句话说

它回答了最大公约数是什么这样一个问题

第二类知识呢

我们称为过程性的知识

它回答怎么做的问题

比如说

我们看下面一小段描述

这段描述了利用辗转相除法求两个正整数

a 和 b 的最大公约数的过程

它描述了怎样求最大公约数

第一步怎么做

第二步又怎么做

按照这个步骤做下来

你就能求得两个正整数 a 和 b 的最大公约数

从这个例子可以看出

过程性知识描述了解决问题的步骤

在计算机领域

过程性的知识就被我们称为算法

为了加深对算法概念的理解

下面我们看一个例子

这个例子是烤蛋糕

我们看一下右边这个图

从图中我们可以看到

它分为三个部分

首先是配料

我们烤蛋糕肯定需要一些材料

比如面粉、鸡蛋、糖这类东西

我们的目标也是很清晰的

我们想要一个蛋糕

再看中间这部分

为了获得这个蛋糕

可能我们需要两个方面的东西

一个是硬件

如烤箱

锅碗瓢盆这样的器具

还有一个面包师

需要他来操作这些器具

在这儿我们做个假定

这个面包师不会烤蛋糕

有了配料

有了硬件

能烤蛋糕了吗

很明显

这是不够的

我们可以说他们的能力是有限的

他们不知道怎么做

那么我们还需要什么呢

我们还需要一个非常关键的东西

在这个问题当中

就是所谓的食谱

他告诉我们应该怎样来制作蛋糕

怎么做第一步

怎么做第二步

又怎么做第三步…等等

食谱是什么

它描述了什么

它是过程性的知识

是前人总结下来的知识

它描述烤蛋糕的步骤

告诉我们应该怎么做

只要照着做

就能获得一个蛋糕

哪怕像前面的假定

你以前并不会做蛋糕

我们就把这魔法般的指示叫做算法

下面我们观察一下红框中的三个部分

配料、食谱和蛋糕

这就是算法的三个部分

配料对应算法的输入

蛋糕对应算法的输出

食谱对应算法

上述例子是在烹饪领域

我们回到计算机科学领域

计算机科学领域中

我们的工具是有限的

也可以说是唯一的

我们的工具就是计算机

要把计算机用起来

让它按我们的要求工作

必须让计算机能够理解并执行算法

能够和计算机交流的东西是什么呢

大家应该已经学过

是程序设计语言

把算法用程序设计语言加以描述

就是我们所知道的程序

从上面的讨论中我们可以总结

所谓程序本质上就是

用程设计语言描述的算法

目的是为了能够

可以利用计算机这个工具执行我们的算法

从程序的角度来看

输入就是程序中要处理的数据

后面的课程中我们会看到

在很多问题中

数据并不是孤立的

数据之间是有关系的

也就是说数据是有结构的

这也就是《数据结构》名字的由来

至此

这门课讨论的内容也就大致清楚了

就是数据以及他们之间的关系

输出的是程序处理的结果

这样的结果有可能以数据的方式呈现

也可能利用人机交互技术

以更丰富的形式呈现

如图的形式

通过上面讨论

我们明确了算法和程序是什么

数据又是怎么回事

下面一节介绍一下数据结构这门课程的基本情况

好了，同学们

我们今天的课程就到这里

下节课再见