计算机科学与技术方法论ch05

计算学科中的数学方法数学的基本特征数学方法是指解决数学问题的策略、途径和步骤，它是计算学科中最根本的研究方法。理论上，凡能被计算机处理的问题均可以转换为一个数学问题，换言之，所有能被计算机处理的问题均可以用数学方法解决；反之，凡能以离散数学为代表的构造性数学方法描述的问题，当该问题所涉及的论域为有穷，或虽为无穷但存在有穷表示时，这个问题也一定能用计算机来处理。数学的基本特征高度的抽象性：量的关系和空间的形式逻辑的严密性：严格遵守形式逻辑的基本法则，充分保证逻辑的可靠性，才能保证结论的正确性。普遍的适用性：数学的高度抽象性决定了它的普遍适用性。数学方法的作用为科学技术研究提供简洁精确的形式化语言为科学技术研究提供数量分析和计算的方法为科学技术研究提供了逻辑推理的工具计算学科中的数学方法计算学科中常用的数学概念和术语集合集合的概念构造性数学方法的基础。集合就是一组无重复的对象的全体。集合中的对象称为集合的元素。如：计算机专业学生全部必修课程可以组成一个集合，其中的每门课程就是这一集合中的元素。集合的描述方法通常用大写字母表示集合，用小写字母表示元素集合的三种描述方法枚举法：列出所有元素的表示方法。如1至5的整数集合可表示为：=1，2，3，4，5；外延表示法：当集合中所列元素的一般形式很明显时，可只列出部分元素，其他则用省略号表示。如斐波那契数列可表示为：{0，1，1，2，3，5，8，13，21，34，…}；谓词表示法：用谓词来概括集合中元素的属性。如斐波那契数列可表示为：{Fn|Fn+2=Fn+1+Fn，F0=0，F1=1，n≥0}集合的运算集合的并设A、B为两个任意集合，所有属于A或属于B的元素构成的集合C，称为A和B的并集。可表示为：C＝A∪B＝｛x｜x∈A∨x∈B｝。求并集的运算称为并（运算）。例5.1若A={a，b，c，d}，B={b，d，e}，求集合A和B的并。解：A∪B＝｛a，b，c，d，e｝集合的差设A、B为两个任意集合，所有属于A而不属于B的一切元素构成的集合S，称为A和B的差集。可表示为：S=A－B=｛x｜x∈A∨x∈B｝。求差集的运算称为差（运算）。例5.2若A={a，b，c，d}，B={b，d，e}，求集合A和B的差。解：A－B={a，c}交集的交设A、B为两个任意集合，由和的所有相同元素构成的集合C，称为A和B的交集。可表示为：C＝A∩B＝｛x｜x∈A∧x∈B｝。求交集的运算称为交（运算）。例5.3若A={x|x-5}，B={x|x1}，求集合和B的交。解：A∩B＝｛x｜x﹣5｝∩｛x｜x1｝＝｛x｜–5x1｝集合的补设I为全集，A为I的任意一子集，I–A则为A的补集，记为。可表示为=I–A=｛x｜x∈I，｝求补集的运算称为补（运算）求补集的运算称为补（运算）例5.4若I=｛x｜–5﹤x﹤5｝，A=｛x｜0﹤x﹤1｝，求。解：=I–A=｛x｜–5﹤x﹤0∨1﹤x﹤5｝集合的乘积1集合A1，A2，…，An的乘积一般用法国数学家笛卡尔（ReneDescartes）的名字命名，即笛卡尔积。该乘积表示如下：A1×A2×…An={（a1，a2，…，an）｜ai∈Ai，i＝1，2，…，n}A1×A2×…An的结果是一个有序元组的集合。例5.5若A={1，2，3}，B={a，b}，求A×B。解：A×B={（1，a），（1，b），（2，a），（2，b），（3，a），（3，b）}函数函数又称映射，是指把输入转变成输出的运算，该运算也可理解为从某一“定义域”的对象到某一“值域”的对象的映射。函数是程序设计的基础，程序定义了计算函数的算法，而定义函数的方法又影响着程序语言的设计，好的程序设计语言一般都便于函数的计算。设f为一个函数，当输入值为a时输出值为b，则记作：baf)(关系关系是一个谓词，其定义域为k元组的集合。通常的关系为二元关系，其定义域为有序对的集合，在这个集合中，我们说有序对的第一个元素和第二个元素有关系。如学生选课学生课程成绩张三文学90张三哲学95李四数学80李四艺术85王五历史92王五文学88等价关系在关系中，有一种特殊的关系，即等价关系，它满足以下3个条件：自反性，即对集合中的每一个元素a，都有aRa；对称性，即对集合中的任意元素a，b，aRb成立当且仅当bRa成立；传递性，即对集合中的任意元素a，b，c，若aRb和bRc成立，则aRc一定成立。等价关系的一个重要性质是：集合A上的一个等价关系R可将A划分为若干个互不相交的子集，称为等价类。例5.6证明非负整数N上的模3的同余关系R为等价关系证明：首先将该关系形式化地表示为：R=｛(a，b)｜a，b∈N，amod3=bmod3｝自反性证明对集合中的任何一个元素a∈N，都有amod3=amod3；对称性证明对集合中的任意元素a，b∈N，若amod3=bmod3，则有bmod3=amod3；传递性证明对集合中的任意元素a，b，c∈N，若amod3=bmod3，bmod3=cmod3，则有amod3=cmod3。例5.7假设某人在唱歌（事件e1）的同时，还可以开车（事件e2）或者步行（事件e3），但一个人不能同时开车和步行。问：以上反映的并发现象，如用关系来表示时，是否是等价关系？答：以上反映的是一种并发（co）现象，如用关系来表示，则这种并发关系具有自反性和对称性，即可表示为：e1coe1，e2coe2，e3coe3；及e1coe2（或e2coe1），e1coe3（或e3coe1），不满足传递性，即（e2coe1）∧（e1coe3）不能推出e2coe3，即不能在开车的同时，又步行。因此，以上并发关系不是等价关系。计算学科中的数学方法计算学科中常用的数学概念和术语所有的计算机程序设计语言都是形式语言，其构成基础同一般自然语言一样，也是符号或字母。常用的符号有数字（09）、大小写字母（A～Z，a～z）、括号、运算符（+，-，*，/）等。有限字母表指的是由有限个任意符号组成的非空集合，简称为字母表，用表示。字母表上的元素称作字符或符号，用小写字母或数字表示，如a、b、c、1、2、3等。字母表可以理解为计算机输入键盘上符号的集合。字母可以理解为键盘上的每一个英文字母、数字、标点符号、运算符号等。字符串，也称为符号串，指的是由字符组成的有限序列，常用小写希腊字母表示。字母表上的字符串以下列方式生成：（1）ε为上的一个特殊串，称为空串，对任何a∈∑，aε=εa=a；（2）若σ是∑上的符号串，且a∈∑，则σa是∑上的符号串；（3）若α是∑上的符号串，当且仅当它由（1）和（2）导出。直观来说，∑上的符号串是由其上的符号以任意次序拼接起来构成的，任何符号都可以在串中重复出现。ε作为一个特殊的串，由零个符号组成。应当指出的是，空串ε不同于我们计算机键盘上的空格键。语言指的是给定字母表∑上的字符串的集合。例如，当∑={a，b}，则{ab，aabb，abab，bba}、｛ε｝、（anbn｜n≥1｝都是∑上的语言。不包含任何字符串的语言称作空语言，用Ф表示。注意：｛ε｝不同于Ф，前者表示由空串组成的语言，后者表示空语言。语言是字符串的集合，因此，传统的集合运算（如并、交、差、补、笛卡尔积）对语言都适用。除此之外，语言还有一种重要的专门的运算，即闭包运算。语言、文法以及自动机有着密切的关系。语言由文法产生。短语结构语言、上下文有关语言、上下文无关语言和正规语言分别由0型文法、1型文法、2型文法和3型文法产生。自动机是识别语言的数学模型，各类文法所对应的自动机分别是图灵机、线性有界自动机、下推自动机和有限状态自动机。需要指出的是，语言与数学模型不是一一对应的关系，一种语言可以由不同的文法产生，也可以由不同的自动机识别。定义、定理和证明是数学的核心，也是计算学科理论形态的核心内容。其中，定义是蕴含在公理系统之中的概念和命题；定理是被证明为真的数学命题；证明是为使人们确信一个命题是真的而作的一种逻辑论证。例5.8在欧氏几何中，平面角的定义为：平面角是在一平面内，但不在一直线上的两条相交线的相互倾斜度；等腰三角形的定理为：两边相等的三角形为等腰三角形。计算学科中的数学方法证明方法直接证明假定p为真，通过使用公理或已证明的定理以及正确的推理规则证明q也为真，以此证明蕴含式p→q为真。这种证明方法为直接证明法。例5.9用直接证明法证明“若p是偶数，则p2是偶数”。证明：假定p是偶数为真，设p=2k（k为整数）。由此可得，p2=2（2k2）。因此，p2是偶数（它是一个整数的2倍）。间接证明因为蕴含式p→q与其逆否命题¬q→¬p等价，因此可以通过证明¬q→¬p来证明蕴含式p→q为真。这种证明方法为间接证明法。例5.10用间接证明法证明“若p2是偶数，则p是偶数”。证明：假定此蕴含式后件为假，即假定p是奇数。则对某个整数k来说有p=2k+1。由此可得p2=4k2+4k+1=2（2k2+2k）+1，因此，p2是奇数（它是一个整数的2倍加1）。因为对这个蕴含式后件的否定蕴含着前件为假，因此该蕴含式为真。首先假定一个与原命题相反的命题成立，然后通过正确的推理得出与已知（或假设）条件、公理、已证过的定理等相互矛盾或自相矛盾的结果，以此证明原命题正确。这种证明方法就是反证法，也称归谬法，是一种常用的数学证明方法。例5.11证是无理数2归纳法的定义所谓归纳法，是指从特殊推理出一般的一种证明方法。归纳法可分为不完全归纳法、完全归纳法和数学归纳法。2．不完全归纳法不完全归纳法是根据部分特殊情况作出推理的一种方法，该方法多用于无穷对象的论证，然而，论证的结果不一定正确。因此，不完全归纳法不能作为严格的证明方法。3．完全归纳法完全归纳法也称穷举法，它是对命题中存在的所有特殊情况进行考虑的一种方法，用该方法论证的结果是正确的，然而，它只能用于“有限”对象的论证。数学归纳法的形式化定义根据数学归纳法的原理，可以对数学归纳法形式化地定义为：P(1)∧()(P(n)→P(n+1))→P(n)例5.12求证命题P(n)：“从1开始连续n个奇数之和是n的平方”，即公式1+3+5+…+（2n―1）=n2成立。证明归纳基础：当n=1时，等式成立，即1=12归纳步骤：设对任意k≥1，P(k)成立，即：1+3+5+…+（2K―1）=K2而1+3+5+…+(2K―1)+(2(K+1)―1)=K2+2K+1=(K+1)2则当P(k)成立时，P(K+1)也成立，根据数学归纳法，该命题得证。构造性证明构造性证明——通过找出一个使得命题P(a)为真的元素a，从而完成该函数值的存在性证明称为构造性证明。构造性证明方法是计算科学中广泛使用的一种证明方法，本章Armstrong公理系统的完备性证明就采用了构造性的证明方法。计算学科中的数学方法递归和迭代:很多序列项常常可以以这样的方式得到：由an–1得到an，按这样的法则，可以从一个已知的首项开始，有限次地重复做下去，最后产生一个序列，该序列是实现递归和迭代的基础。递归及其有关概念20世纪30年代，正是可计算的递归函数理论与图灵机、λ演算和POST规范系统等理论一起为计算理论的建立奠定了基础。递归关系指的是：一个数列的若干连续项之间的关系递归数列指的是：由递归关系所确定的数列。递归过程指的是：调用自身的过程。递归算法指的是：包含递归过程的算法。递归程序指的是：直接或间接调用自身的程序。递归方法（也称递推法），是一种在“有限”步骤内，根据特定的法则或公式对一个或多个前面的元素进行运算，以确定一系列元素（如数或函数）的方法。递归与数学归纳法例5.13计算56计算方法之一：6，6+6=12，12+6=18，18+6=24，24+6=30；计算方法之二：56，46，36，26，16；16+6=12，12+6=18，18+6=24，24+6=30；从56开始计算