(山东女子学院信息技术学院，山东济南250300)
关键词：离散数学；算法设计；数据结构；离散性；二进制
中图分类号：TP301文献标识码：ADOI：10.19358/j.issn.16747720.2016.22.005
引用格式：甄鹏华,于振梅.计算机科学中的算法设计与数据结构的离散性［J］.微型机与应用，2016,35（22）：18-21.
0引言
计算机科学(ComputerScience)是一门日新月异的学科。计算机科学与技术专业的研究人员时刻站在国际先进科技的前沿，学习新知识，并向创造新知识而努力。
但是计算机科学中亦有许多基础科学中的理论支持，其与计算机的实际相结合，构成了计算机科学中最基础的理论。计算机问题归根结底是数学问题，将计算机问题抽象成数学问题，是一种合适的解决方式。
随着互联网行业的快速发展，作为其支柱的计算机行业越来越受到人们重视。然而，人们更加注重程序结果而不是算法，更疏于关心数据结构。
本文提出了对算法设计和数据结构的离散性体现的思路，给抽象解决计算机问题做一种具体化解释，以期给读者建立一种从连续性到离散性的思维。
1算法
本节主要以算法来表述计算机中的离散性问题。本节概括了算法的基本概念，并以两个算法设计的方法来表述离散性的表现。该节算法均以C语言描述。
1.1算法的基本概念
当然，对于流程型的程序确实对算法的要求不高，但对于人工智能、人机交互、图形图像识别、音视频识别、虚拟现实、现实增强、社会工程学、数据挖掘、大数据分析、大型网络拓扑、云计算等领域来说，算法是其关键。
现在流行于手机的各种美图软件中，亦存在较不错的算法设计。软件如何识别出人脸？如何分析眼睛、鼻子、嘴巴等的位置？如何对其进行一定的“美图”而不至于让人无法分辨？
由计算机科学之父、人工智能之父阿兰·图灵(AlanTuring)带领的小组，在二战中帮助盟军设计了破译德国的密码系统Enigma的机器。设计机器的过程，可以称作设计算法的过程。图灵实际是领导小组成员设计出一个快速解密德国纳粹密码系统的算法，并为这个算法设计了机器。
1.2算法体现的离散性
算法设计中可以体现出计算机科学中常见的不连续的特性，即离散性。
1.2.1算法设计常用的方法
（1）递推法：递推是序列计算机中的一种常用算法。它是按照一定的规律来计算序列中的每个项，通常是通过计算机前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。
（2）递归法：程序调用自身的编程技巧称为递归(recursion)。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。
1.2.2两种方法的离散性体现
递推法中，计算机用一种比较“傻”的方法来进行一个复杂的运算。如算法1，以一个求最大值的算法来解释。
算法1求最大值
intmax(int*array,intsize)
{
intmval=*array;
inti;
for(i=1;i if(array［i］>mval) mval=array［i］; returnmval; } 递归法有时可以简化算法，以求两个自然数的最大公约数为例，如算法2，其改用递归算法后如算法3。 算法2求最大公约数 voidswapi(int*x,int*y) inttmp=*x; *x=*y; *y=tmp; intgcd(intm,intn) intr; do if(m swapi(&m,&n); r=m%n; m=n; n=r; }while(r); returnm; 算法3递归法求最大公约数 intgcd(inta,intb) if(a%b) returngcd(b,a%b); returnb; 形象地说递归法就是“自己调用自己”。一种离散性的表现与之前的例子类似，这里不再重复。这里讲的是程序运行表现的离散性。计算机会在栈中运行程序，栈的特点就是“后进先出”。在运行这个递归的算法时，需要返回值时返回一个“自己”，只不过参数不同。直到返回一个确定的值，再层层返回，如图1所示。 可见，对于该算法，计算机每递归计算一次，就要向内存中Push一次，直到计算完成，再一次一次Pop出。这是一种计算的离散性体现，这亦不会是人类的连续性的思维方式。 2数据结构 本节主要以数据结构来表述计算机中的离散性问题。本节概括了数据结构的基本概念，并提出了数据结构的离散性的基本理解。 2.1数据结构的基本概念 数据结构是计算机科学的经典学科。字面上来说，就是研究数据元素之间的结构关系。根据数据元素之间关系的不同特性，一般来说可分为四类基本结构：集合、线性结构、树形结构、图状结构或网状结构［3］，如图2所示。这正是数据结构的元素具有的离散性特征。 NicklausWirth凭借“算法+数据结构=程序”这一公式获得了计算机科学领域最高奖——图灵奖。这已足以可见数据结构的重要性。 数据结构主要讨论的是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称之为结构(structure)。而离散数学与数据结构有千丝万缕的联系，很多大学的计算机专业将离散数学作为数据结构的先导课程。 2.2数据结构的离散性 离散数学中的图论可以说就是对数据结构的抽象，这方面的学术文献相当丰富。这里仅对其做一个较为简单、通俗的理解说明。 对于集合结构，如图2所示，其元素本身就是离散的、无关的。 对于线性结构的离散性是显而易见的。前文在介绍算法的离散性时提到栈的应用，可见其离散性。其余线性结构类似。 树形结构和图形结构也很好理解，每个元素本来是独立存在，由于元素之间满足了某种关系使其变成了树形或图形结构，自然这种关系是离散的，不连续的。 实际上，离散数学与数据结构的关系是最为紧密的。离散数学中的图论实际就是研究一些复杂的数据元素之间的关系［4］。一些离散数学中的理论应用在计算机中，实现了一些难以解决的问题或优化了一些原本不恰当的方法，例如哈夫曼(Huffman)树解决了压缩编码的问题。 3离散数学与数字电子 本节将介绍离散数学的一些概念，并指出其与数字电子（主要是数字信号）的关系。 3.1离散数学的基本概念 3.2数字电子的基本概念与离散性 数字电子是一门学科，与计算机学科相互交叉。此处仅以其数字信号的基本概念解释其离散性。 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］ROGERSH.Theoryofrecursivefunctionsandeffectivecomputability［M］.Cambridge:TheMITPress,1987. ［3］严蔚敏,吴伟民.数据结构:C语言版［M］.北京:清华大学出版社,2007. ［4］屈婉玲,耿素云,张立昂.离散数学［M］.北京:清华大学出版社,2008. ［5］JOHSONBAUGHR.Discretemathematics［M］.UpperSaddleRiver：PrenticeHall,2008. ［7］BIGGSN.Discretemathematics［M］.Oxford:OxfordUniversityPress,2002. ［8］HOPKINSB.Resourcesforteachingdiscretemathematics［M］.WashingtonD.C.:MathematicalAssociationofAmerica,2008. ［9］康华光.电子技术基础:数字部分（第6版）［M］.北京:高等教育出版社,2014.