第4章计算学科中的核心概念

第4章计算学科中的核心概念内容摘要：

限制了与他人的交流 ， 不利于问题的解决；  要花费大量的时间去熟悉和掌握某种特定的程序设计语言；  要求描述计算步骤的细节 ， 而忽视算法的本质。 例 （ C语言）的算法描述： main() { int X,Y。 X=1。 Y=2。 while(Y=100) { X=X+Y。 Y=Y+1。 }。 printf(%d,X)。 } 例 （ C语言）的算法描述 main() { int n。 float X,I。 printf(Please input n:)。 scanf(%d,amp。 n)。 X=0。 I=1。 do { X=X+1/I。 I=I+1。 }while(I=n)。 printf(\n%f,X)。 } 算法 算法分析 （ 1）算法的时间复杂度； 用 T(n)表示 ， n表示问题规模的大小。 使用一个记号   Order（ 数量级 ） 的第一个字母 ，  允许使用 “ =” 代替 “ ≈”。 如 n2+n+1=(n2) 设 f(n)是一个关于正整数 n的函数 ， 若存在一个正 整 数 n0 和 一 个 常 数 C， 当 n≥n0 时 ，∣ T(n)∣ ≤∣ C f(n)∣ 均成立 ， 则称 f(n)为 T(n)的同数量级的函数。  算法时间复杂度 T(n)可表示为： T(n)= (f(n)) 常见的大 表示形式有： (1) ： 称为常数级； (logn)： 称为对数级； (n) ：称为线性级； (nc) ：称为多项式级； () ：称为指数级； (n!) ：称为阶乘级。 算法的空间复杂度 指算法在执行过程中所占存储空间的大小， 用 S(n)表示， S为英文单词 Space的第一个字母。 与算法的时间复杂度相同 算法的空间复杂度 S(n)也可表示为： S(n)= (g(n))。 算法 算法的研究 算法 算法：定义一向工作如何完成的步骤的集合  在一台机器可以完成一个任务之前，必须找到完成这个任务的算法并且用与机器兼容的方式来描述  一个与机器兼容的算法的描述 —— 程序 算法的研究开始是作为数学的一个学科  目标：找到描述特定类型问题是如何被解决的指令的集合，如 Euclidean算法  一旦一个完成任务的算法被找到，任务的实现就不再需要对算法原理的理解，任务的实现仅仅是遵循算法的只是过程  现有的解决问题需要的智慧被编码进了算法 算法转化为智慧 通过使用算法来得到并转化智慧，我们才可以构建起可以表现 智慧行为的机器。  机器表现的智能等级受到通过算法转化的智慧所限制  如果没有解决问题的算法，意味着问题的解决方案超出了机器的能力范围 算法的开发就成了计算机领域的一个主要目标  如何找到算法 —— 一个十分接近于寻找通用问题解决方案  描述这个算法 —— 转变为一个清晰的指令的集合（程序设计语言描述） 计算机技术别用于复杂问题（大型软件系统） 不仅仅包括实现任务的单个算法的开发  还要求对组件之间的交互进行设计  软件工程：借鉴了工程领域、项目管理领域、人力资源管理以及程序语言设计领域的经验 执行算法的机器的设计和实现 数据的存储 数据的操作 体系结构中涵盖了对现今技术的讨论  我们的目标不是去熟知类似当今体系结构是如何用电路来实现这样的细节问题，那将会导致过分陷入电子工程学科  正如昨天的齿轮驱动的计算机让位于电子设备一样，今天的电子技术也许很快也被其它的技术所取代 理想情况下 希望计算机的体系结构是我们的有关算法过程知识的延续，并且不应该被技术能力酸限制  使我们的算法知识在当代机器体系结构的发展背后起推动作用，而不仅仅是从技术的要求触发来解顶机器的设计 构建允许使用多个指令序列来代替算法的机器是可能的  这些指令被同时执行或者作为 机器于外部世界的接口的设计于计算机的设计紧密相连 算法是如何机器中的。 机器是如何被告知执行的是哪一个算法。 计算理论 对解决越来越复杂问题的算法的研究  导致了算法过程的最终限制问题  如果没有算法可以解决这个问题，那么算法是不能被机器所解决的，机器仅仅可以解决在算法上可解的问题  Godel的不完全定理阐述了  在任何传统算术领域的数学理论中，有些是既不能证明有不能被推翻的  任何对算术系统的彻底研究都超出了算法的能力  对算法的限制的研究欲望似的数学家们设计抽象的机器来执行算法，并在理论上研究这些假想机器的能力。 数据结构 ： 一类定性数学模型 数据结构的基本概念 数据结构的基本概念 组成：数据结构是一类定性的数学模型，它由以下 3部分组成  逻辑结构  存储结构（或称。