大学计算机基础绪论剖析.ppt

1.3.3 计算学科的基本概念 反映对象的本质属性的思维形式，在人的头脑中形成概念 计算机科学家总结出计算学科的12个基本概念： 绑定、 抽象层次、大问题的复杂性、 按空间排序、 概念与形式模型、 按时间排序、 一般性和完备性、重用、效率、安全性、演化、折衷与结论 它们在计算学科的各领域中反复出现，描述了该学科具有普遍性、持久性的重要思想、原则和方法 * 西安交通大学 计算机教学实验中心 2011 * 1.4 计算科学的研究与应用 人工智能 网格计算 云计算 普适计算 姚普选 2011 * 本章要点 计算、算法、函数 可计算的、不可计算的 图灵机的组成和工作过程 图灵可计算的、丘奇——图灵论题 是否有不可计算的函数 停机函数 程序自终止的，举例 停机判定函数 时间复杂性/度（算法、问题） 空间复杂性/度 多项式时间复杂度、指数阶时间复杂度 * 要点_续 计算工具 算筹、算盘、纳皮尔筹、计算尺 盘式计算机、莱布尼茨计算机、巴贝奇差分机和分析机 ENIAC、EDVAC、区别？ 计算科学的概念、形态、基本概念 计算科学的研究与应用 人工智能、网格计算、云计算、普适计算 应掌握的技能： 通过网络获取有价值的知识 西安交通大学 计算机教学实验中心 2011 * 本章作业 1. 掌握本章介绍的基本概念 2. 了解计算机的应用 3. 写出在N个数中查找最大数的计算步骤 4. 在习题1的3、4、6、7、8中任选一题，进行论述。 * 计算（computation）是算法的执行，从包含算法和输入数据的初始状态开始，经过一系列的中间状态，直到达到最终的目标状态的过程。而算法（algorithm）是由若干条指令组成的有穷序列。 一组可能的输入值和一组可能的输出值之间的映射关系称为函数（function），它使每个可能的输入被赋予单一的输出。对于一个给定的输入，确定其具体输出的值，这一过程称为函数的计算。对函数进行计算的能力非常重要，这是因为正是通过对函数的计算，问题才能得到解决。计算机科学的一个基本问题就是找到一种技术，并用其来计算用于求解问题的函数。 * 计算和产品的生产： 相同：输入—加工—输出 不同计算加工的是数据、信息或符号。产品加工的是实物。 * 可计算和不可计算的概念，见[美]J.Glenn Brookshear著.刘艺,等译. 计算机科学概论（第9版）. 人民邮电出版社,2007. p329 * 可计算和不可计算的概念，见[美]J.Glenn Brookshear著.刘艺,等译. 计算机科学概论（第9版）. 人民邮电出版社,2007. p329 * 可计算和不可计算的概念，见[美]J.Glenn Brookshear著.刘艺,等译. 计算机科学概论（第9版）. 人民邮电出版社,2007. p329 * 生命游戏，元细胞自动机 /complex/models/ca/ca2.htm /complex/models/gameoflife.htm 释放比特自由——Wolfram的“一种新科学”介绍 /vm/articles/freebits.htm * 资料：不插电的排序视频 选择排序的比较次数：n（n-1）/2，与n有关 求根：10次，与系数无关 纳皮尔筹 纳皮尔的筹是一种用来计算乘法与除法，类似算盘的工具。由一个底座及九根圆柱（方柱）组成，可以把乘法运算转为加法，也可以把除法运算转为减法，甚至可以开平方根。 计算尺 利用对数运算把乘法变为加法，把除法变为减法。 还可以计算平方根，指数，对数，和三角函数。 启示？ 可以把一种运算通过某种变换，转换为另一种运算从而使运算变得简单、快速 纳皮尔筹 纳皮尔的筹是一种用来计算乘法与除法，类似算盘的工具。由一个底座及九根圆柱（方柱）组成，可以把乘法运算转为加法，也可以把除法运算转为减法，甚至可以开平方根。 计算尺 利用对数运算把乘法变为加法，把除法变为减法。 还可以计算平方根，指数，对数，和三角函数。 启示？ 可以把一种运算通过某种变换，转换为另一种运算从而使运算变得简单、快速 程序结构的主要语法语义模型的分类（过程结构、函数组织、抽象数据类型、通信并行处理等） 以及解析、编译、解释和代码优化的方法等是程序设计语言中的抽象 * 姚普选 * 计算 VS 产品的加工/生产过程，可比之处？ 函数_function：一组可能的输入值和一组可能的输出值之间的映射关系 函数为每个可能的输入赋予单一的输出 函数的计算：对于一个给定的输入，确定其具体输出的值的过程 通过对函数的计算来解决问题 计算机科学的一个基本问题__找到一种技术，并用之于计算哪些解决问题的函数，即 y=f(x) 能否确定，如何确定加工过程，如何实现加工过程?