计算机科学中的算法设计与数据结构的离散性

　　甄鹏华，于振梅

　　(山东女子学院 信息技术学院， 山东 济南 250300)

       摘要：数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型，以及如何将已用连续数量关系建立起来的数学模型离散化，从而由计算机加以处理的问题。实际上，可以将离散数学理解为对计算机问题的抽象，离散性可以在算法设计和数据结构中体现。计算机中也有其他的问题表现出了离散性，所以，计算机科学对离散数学的研究不应太过局限，这些表现都可以归结为计算机所采用的二进制。

　　关键词：离散数学；算法设计；数据结构；离散性；二进制

　　中图分类号：TP301文献标识码：ADOI： 10.19358/j.issn.16747720.2016.22.005

　　引用格式：甄鹏华,于振梅. 计算机科学中的算法设计与数据结构的离散性［J］.微型机与应用，2016,35（22）：18-21.

0引言

　　计算机科学(Computer Science)是一门日新月异的学科。计算机科学与技术专业的研究人员时刻站在国际先进科技的前沿，学习新知识，并向创造新知识而努力。

　　但是计算机科学中亦有许多基础科学中的理论支持，其与计算机的实际相结合，构成了计算机科学中最基础的理论。计算机问题归根结底是数学问题，将计算机问题抽象成数学问题，是一种合适的解决方式。

　　随着互联网行业的快速发展，作为其支柱的计算机行业越来越受到人们重视。然而，人们更加注重程序结果而不是算法，更疏于关心数据结构。

　　本文提出了对算法设计和数据结构的离散性体现的思路，给抽象解决计算机问题做一种具体化解释，以期给读者建立一种从连续性到离散性的思维。

1算法

　　本节主要以算法来表述计算机中的离散性问题。本节概括了算法的基本概念，并以两个算法设计的方法来表述离散性的表现。该节算法均以C语言描述。

　　1.1算法的基本概念

　　算法(algorithm)是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制［1］。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。

　　当然，对于流程型的程序确实对算法的要求不高，但对于人工智能、人机交互、图形图像识别、音视频识别、虚拟现实、现实增强、社会工程学、数据挖掘、大数据分析、大型网络拓扑、云计算等领域来说，算法是其关键。

　　现在流行于手机的各种美图软件中，亦存在较不错的算法设计。软件如何识别出人脸？如何分析眼睛、鼻子、嘴巴等的位置？如何对其进行一定的“美图”而不至于让人无法分辨？

　　由计算机科学之父、人工智能之父阿兰·图灵(Alan Turing)带领的小组，在二战中帮助盟军设计了破译德国的密码系统Enigma的机器。设计机器的过程，可以称作设计算法的过程。图灵实际是领导小组成员设计出一个快速解密德国纳粹密码系统的算法，并为这个算法设计了机器。

　　可见，算法其实是程序的根本。世界顶尖的科技企业和高等院校进行的各种科学性研究，只要涉及计算机或与程序相关，其中一大重点便是在研究算法。无论对于多么庞大的一个系统，设计其算法是最基础也是关键的第一步。

　　1.2算法体现的离散性

　　算法设计中可以体现出计算机科学中常见的不连续的特性，即离散性。

　　1.2.1算法设计常用的方法

　　算法设计的方法有很多，亦有很多相关文献。此处主要介绍最简单的两种方法［2］，并在后面以此为例。

　　（1）递推法：递推是序列计算机中的一种常用算法。它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。

　　（2）递归法：程序调用自身的编程技巧称为递归(recursion)。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

　　1.2.2两种方法的离散性体现

　　递推法中，计算机用一种比较“傻”的方法来进行一个复杂的运算。如算法1，以一个求最大值的算法来解释。

　　算法1求最大值

　　int max(int *array, int size)

　　{

　　int mval = *array;

　　int i;

　　for (i = 1; i < size; i++)

　　if (array［i］ > mval)

　　mval = array［i］;

　　return mval;

　　}

　　可见对于计算机来说，它会不断地用已知最大的数去和数组中下一个数字作比较，直到结束，即使有很多很多数字。而人类比较数字大小的方式就不同了，如果数字非常多，则可能会先看看数字都是几位的，挑出位数最高的，如果不止一个,则再去逐个比较。这是一种连续性的思维模式。这正是人类习惯的连续性思维，初等数学都是建立在连续的基础上，也亦有了几何的出现。然而对于计算机来说，要有这种连续的思维是很困难的，要设计出更加复杂的算法，才能“模拟”出人类的这种连续性思维。当然，亦有可能是因为人类的大脑这个“CPU”比较高级，自身的算法就足够复杂，所以人类才拥有连续性思维。对于设计出更复杂的算法和更快速的计算机来“模拟”人脑的思维模式，也有相关研究，亦有不少相关文献，这不是本文重点。

　　递归法有时可以简化算法，以求两个自然数的最大公约数为例，如算法2，其改用递归算法后如算法3。

　　算法2求最大公约数

　　void swapi(int *x, int *y)

　　{

　　int tmp = *x;

　　*x = *y;

　　*y = tmp;

　　}

　　int gcd(int m, int n)

　　{

　　int r;

　　do

　　{

　　if (m < n)

　　swapi(&m, &n);

　　r=m%n;

　　m=n;

　　n=r;

　　} while (r);

　　return m;

　　}

　　算法3递归法求最大公约数

　　int gcd(int a,int b)

　　{

　　if(a%b)

　　return gcd(b,a%b);

　　return b;

　　}

　　形象地说递归法就是“自己调用自己”。一种离散性的表现与之前的例子类似，这里不再重复。这里讲的是程序运行表现的离散性。计算机会在栈中运行程序，栈的特点就是“后进先出”。在运行这个递归的算法时，需要返回值时返回一个“自己”，只不过参数不同。直到返回一个确定的值，再层层返回，如图1所示。

　　可见，对于该算法，计算机每递归计算一次，就要向内存中Push一次，直到计算完成，再一次一次Pop出。这是一种计算的离散性体现，这亦不会是人类的连续性的思维方式。

2数据结构

　　本节主要以数据结构来表述计算机中的离散性问题。本节概括了数据结构的基本概念，并提出了数据结构的离散性的基本理解。

　　2.1数据结构的基本概念

　　数据结构是计算机科学的经典学科。字面上来说，就是研究数据元素之间的结构关系。根据数据元素之间关系的不同特性，一般来说可分为四类基本结构：集合、线性结构、树形结构、图状结构或网状结构［3］，如图2所示。这正是数据结构的元素具有的离散性特征。

　　Nicklaus Wirth凭借“算法+数据结构=程序”这一公式获得了计算机科学领域最高奖——图灵奖。这已足以可见数据结构的重要性。

　　数据结构主要讨论的是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称之为结构(structure)。而离散数学与数据结构有千丝万缕的联系，很多大学的计算机专业将离散数学作为数据结构的先导课程。

　　2.2数据结构的离散性

　　离散数学中的图论可以说就是对数据结构的抽象，这方面的学术文献相当丰富。这里仅对其做一个较为简单、通俗的理解说明。

　　对于集合结构，如图2所示，其元素本身就是离散的、无关的。

　　对于线性结构的离散性是显而易见的。前文在介绍算法的离散性时提到栈的应用，可见其离散性。其余线性结构类似。

　　树形结构和图形结构也很好理解，每个元素本来是独立存在，由于元素之间满足了某种关系使其变成了树形或图形结构，自然这种关系是离散的，不连续的。

　　实际上，离散数学与数据结构的关系是最为紧密的。离散数学中的图论实际就是研究一些复杂的数据元素之间的关系［4］。一些离散数学中的理论应用在计算机中，实现了一些难以解决的问题或优化了一些原本不恰当的方法，例如哈夫曼(Huffman)树解决了压缩编码的问题。

3离散数学与数字电子

　　本节将介绍离散数学的一些概念，并指出其与数字电子（主要是数字信号）的关系。

　　3.1离散数学的基本概念

　　离散数学是数学的几个分支的总称，是研究基于离散空间而不是连续的数学结构。与光滑变化的实数不同，离散数学的研究对象，例如整数、图和数学逻辑中的命题［5］，不是光滑变化的，而是拥有不等、分立的值［6］。因此离散数学不包含微积分和分析等“连续数学”的内容。离散对象经常可以用整数来枚举。更一般地，离散数学被视为处理可数集合（与整数子集基数相同的集合，包括有理数集但不包括实数集）的数学分支［7］。但是，“离散数学”不存在准确且普遍认可的定义［8］。实际上，离散数学经常被定义为不包含连续变化量及相关概念的数学，甚少被定义为包含什么内容的数学。

　　3.2数字电子的基本概念与离散性

　　数字电子是一门学科，与计算机学科相互交叉。此处仅以其数字信号的基本概念解释其离散性。

　　数字信号同模拟信号相对，模拟信号是指时间和数值都连续的一组信号，而数字信号是指时间和数值都是离散的一组信号，如图3所示。从图3可以看出，这种连续性与离散性是非常明显的。从数学上来说，连续，意味着其微积分有意义。显然，对离散的信号这是没有意义的。这里不再深究。

4计算机中的离散性问题

　　本节主要介绍二进制体现出来的离散性问题，并归结出计算机中的离散性问题基本都与计算机采用的二进制的性质有关。

　　4.1二进制

　　计算机中以二进制进行存储和运算，这涉及逻辑数学的一些概念。实际上，逻辑运算亦能体现离散性。这与计算机的运算是有映射关系的。

　　4.1.1基本概念

　　二进制是逢2进位的进位制。“0”、“1”是基本算符。现代的电子计算机技术全部采用的是二进制，因为它只使用“0”、“1”这两个数字符号，非常简单方便，易于用电子方式实现［9］。

　　由于人类习惯使用十进制，可以这样表述二进制：二进制数的每一位数的位权（理解为“1”能有多“大”）为2n-1（n为位数）。这样可以充分理解二进制数的“大小”。

　　4.1.2体现

　　计算机是一个只认识“0”、“1”的机器，对于人类来说很容易理解的信息（如图片、音视频）对于计算机来说却不能直接理解。所以计算机本身就要通过离散的数据来“认识世界”。

　　计算机所处理的对象都是离散的数据。所谓离散的数据，可以理解为从本质上说计算机只能处理“0”、“1”组成的二进制的数据。计算机要进行图像、文字、声音等数据的处理，必须将其转换成二进制的数据表示，

　　也就是说进行离散化处理。只如音频处理，只有将连续变化的声音转换成二进制的数据来表示，这样计算机才能进行处理。

　　图4所示就是计算机将音频信息离散化的方法。离散化得越“细”，就越能还原声音的原来面貌。　　

　　4.2简要分析

　　计算机采用的二进制使得计算机处理问题具有离散性的特征。前面所述的算法设计与数据结构的离散性体现，都可以通过二进制来解释。这涉及一些比较靠近计算机底层的理论，这里不再深究。

5结论

　　本文以探究离散数学的方式浅析了计算机的离散性问题，特别是在算法设计与数据结构上，并最终说明计算机采用的二进制是计算机离散性问题的一个关键。

　　随着计算机科学的发展和实际需求的日益增长，计算机的离散性越来越受到相关领域的关注和重视，相信这是一个极具价值的研究领域，值得更深一步的探索。

　　参考文献

　　［1］ 谭浩强. C程序设计［M］. 北京: 清华大学出版社,2005.

　　［2］ ROGERS H. Theory of recursive functions and effective computability［M］. Cambridge: The MIT Press, 1987.

　　［3］ 严蔚敏,吴伟民. 数据结构: C语言版［M］. 北京: 清华大学出版社,2007.

　　［4］ 屈婉玲,耿素云,张立昂. 离散数学［M］. 北京: 清华大学出版社,2008.

　　［5］ JOHSONBAUGH R. Discrete mathematics ［M］. Upper Saddle River： Prentice Hall, 2008.

　　［6］ WEISSTEIN E. Discrete mathematics ［EB/OL］. (2016-06-19)［2016-07-16］ http://mathworld.wolfram.com/DiscreteMathematics.html.

　　［7］ BIGGS N. Discrete mathematics ［M］. Oxford: Oxford University Press,2002.

　　［8］ HOPKINS B. Resources for teaching discrete mathematics ［M］. Washington D.C.: Mathematical Association of America,2008.

　　［9］ 康华光. 电子技术基础: 数字部分（第6版）［M］. 北京: 高等教育出版社,2014.