专业导论05计算机学科核心概念.pptVIP

计算学科中的核心概念 掌握和应用学科的核心概念是成熟的计算机科学家和工程师的标志之一 算法——计算学科中最具方法论性质的核心概念 算法的历史、定义、表示方法 算法的分析等 数据结构、程序、软件、硬件。 CC1991提取的12个核心概念： (1)绑定 (2)大问题的复杂性 (3)概念模型和形式模型 (4)一致性和完备性 (5)效率 (6)演化 (7)抽象层次 (8)按空间排序 (9)按时间排序 (10)重用 (11)安全性 (12)折衷与结论 5.1 引 言 学科中的核心概念是学科中最关键、最重要的概念，它涉及学科研究的内涵、对象、本质、核心要素等内容，其基本特征有以下4点： （1）在学科中多处出现； （2）在各分支领域及抽象、理论和设计的各个层面上都有很多示例； （3）在技术上有高度的独立性； （4）一般都在数学、科学和工程中出现。 在计算学科的一般文献中，学科中的核心概念指的是CC1991报告提取的学科中反复出现的12个核心概念。为便于教学，本书将学科中最具方法论性质的概念——算法，以及数据结构、程序、软件、硬件、计算机中的数据等与CC1991报告提取的12个核心概念一起统称为学科中的核心概念。 5.2 算法 算法是计算学科中最具方法论性质的核心概念，也被誉为计算学科的灵魂。算法设计的优劣决定着软件系统的性能，对算法进行研究能使我们深刻地理解问题的本质以及可能的求解技术。 5.2.1 算法的历史简介 公元825年，阿拉伯数学家阿科瓦里茨米（AlKhowarizmi）撰写了著名的《波斯教科书》（Persian Textbook），书中概括了进行四则算术运算的法则。“算法（Algorithm）”一词就来源于这位数学家的名字。后来，《韦氏新世界词典》（Webster?s New World Dictionary）将其定义为“解某种问题的任何专门的方法”。而据考古学家发现，古巴比伦人在求解代数方程时，就已经采用了“算法”的思想。 在算法的研究中，人们不可避免的要提到丢番图方程，希尔伯特著名的23个数学问题中的第十个问题就是关于“丢番图方程的可解性问题”。 古希腊数学家丢番图（Diophantus）对代数学的发展有极其重要的贡献，并被后人称之为“代数学之父”。 他在《算术》（Arithmetica）一书中提出了有关两个或多个变量整数系数方程的有理数解问题。对于具有整数系数的不定方程，若只考虑其整数解，这类方程就叫丢番图方程。“丢番图方程可解性问题”的实质为：能否写出一个可以判定任意丢番图方程是否可解的算法？ 对于只有一个未知数的线性丢番图方程而言，求解很简单，如ax=b，只要a能整除b，就可判定其有整数解，该整数解即b/a。 对于有两个未知数的线性丢番图方程判定其是否有解的方法也很简单，如ax+by=c，先求出a和b的最大公因子d，若d能整除c，则该方程有整数解。 例5.1 问：方程13x+26y=52有无整数解？ 答：13和26的最大公因子是13，13又可整除52，故该方程有整数解（如x=2，y=1即方程的解）。 例5.2 问：方程2x+4y=15有无整数解？ 答：2和4的最大公因子是2，2不能整除15，故该方程无整数解。 因此可以看出，对于两个未知数的线性丢番图方程来说，求解的关键就是求最大公因子。公元前300年左右，欧几里德在其著作《几何原本》（Elements）第七卷中阐述了关于求解两个数最大公因子的过程，这就是著名的欧几里德算法：给定两个正整数m和n，求它们的最大公因子，即能同时整除m和n的最大正整数。 算法如下： （1）以n除m，并令所得余数为r（r必小于n）； （2）若r=0，算法结束，输出结果n；否则，继续步骤（3）； （3）将n置换为m，r置换为n，并返回步骤（1）继续进行。 例5.3 设m=56，n=32，求m、n的最大公因子。 算法的执行过程如下： （1）32除56余数为24； （2）24除32余数为8； （3）8除24余数为0，算法结束，输出结果8。 答：m、n的最大公因子为8。 欧几里德算法既表述了一个数的求解过程，同时，它又表述了一个判定过程，该过程可以判定“m和n是互质的”（即除1以外，m和n没有公因子）这个命题的真假。 5.2.2 算法的定义和特征 有关算法的定义不少，其内涵基本上是一致的，其中最为著名的是计算机科学家克努特在其经典巨著—《计算机程序设计的艺术》（The Art of Computer Programming）第一卷中对算法的定义和特性所作的有关描述。 1．算法的非形式化定义 一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型问题的运算序列。 2．算法的重要特性 （1）