大学计算机基础绪论

第1章绪论姚普选计算机教学实验中心课程内容网络通信|计算机Internet局域网生活、工作数据仓库联机分析处理数据挖掘信息利用管理决策计算机工作原理软件硬件数据管理数据库数据库DBMS数据结构线性表、树、图数据__数字、文字等的表示、存储、压缩程序设计__语言、算法网络局域网、Internet通信技术、设备数据仓库

OLAP数据挖掘软件文本、数据、讲稿、图处理声音、动画、视频播放操作系统数据__二进制数、ASCII码、汉字内码、图声视频数字化知识和技能硬件CPU、内存、外存、I/O设备数字电路；逻辑设计、制造工作原理__冯诺依曼计算机数据库数据库DBMS自动控制自控系统自控原理智能模拟专家系统推理、机器学习、模式识别Page4学习方法课堂VS课外

学时少，需看书、网上查询知识VS技能

如，OS_知原理可推知操作方法经验VS训练常用并不能自然成为高手统观VS局部认知：局部重要性—整体可行性广博VS精深相辅：方向正确—解决现实问题Page5学习方法_续现状VS将来如,Excel→数据处理→数据库Access→SQLServer|MySQL→数据仓库|OLAP|数据挖掘战略VS战术

严整的战略规划↔精细的战术实施

如：结构化设计——

数据流图→系统结构图（多个模块的层次结构）

→程序实现每个模块的功能（算法→程序）6S1：顶层设计存取款业务系统储户存取单、存折例0-1：存取款业务系统的设计存折(存折&存取单)|钱储户验(存折&存取单)(存款|取款)&记账存折|钱银行7S2：一层设计储户审查分类存款处理取款处理帐目文件现金帐存折、存取单存折、存款单存折存折、存款单存折、取款单8S2：二层设计9S3：转换成程序结构图实现：算法→程序10算法例0-2：求函数值例0-3：求解多项式y=9x5+10x4-5x3+8x2+3x-1数组p[1]~p[6]：-1,3,8,-5,10,9迭代式：y=p[k]+x∙yy=-1+x(3+x(8+x(-5+x(10+x(9)y=0y=9+x∙yy=10+x∙yy=-5+x∙yy=8+x∙yy=3+x∙yy=-1+x∙yy=p[k]+x*yp[1]~p[6]←

1,3,8,-5,10,9y=0k←1输出y的值开始输入X的值结束Tk<=6F例0-4：TowerofHonoi几个盘从一柱→另一柱方法：上组盘→辅助柱最大盘→目标柱辅助柱盘→目标柱例0-5：最短的编码欲传送电文：abaccda等长编码：abcd各为00、01、10、11等长码的电文：00010010101100共14位哈夫曼编码思想：字符出现频率越高→编码越短构造哈夫曼树：字符出现频率作权值、n个叶子本例字母频率：abcd各为3、1、2、12112437acbd010011abcd011010111abaccda011001010111014课时：40（课）+16（机）上课：中2-3223时间：上课_课表;上机_课堂通知

上机：计算机教学实验中心作业：学校统一制作的作业本——教材科购买实验报告：上传到_39用户名、密码——学号教材：《大学计算机基础》《大学计算机基础实验指导》清华大学出版社、2011年9月键盘功能键字母键光标键数字键计算机键盘定位：FJ基准键：ASDFJKL；食指：各两排中、无名指：

各一排左小指：

左侧其余右小指：

右侧其余右大指：

空格键Page17预备知识与技能1．操作系统的功能2．Windows系统的用户界面3．文件操作4．设置5．附件§1Windows操作系统Page181.Windows操作系统的功能计算机硬件：物质基础软件：管理计算机；为用户提供服务；扩充计算机系统的功能软件分类：系统软件（如Word）、应用软件操作系统：最重要的系统软件操作系统的功能：管理计算机的硬件、软件和数据资源；安排计算机工作流程，使各部件协同工作；提供用户与计算机之间的接口；常用操作系统：Unix、Linux、Windows、DOSPage192．Windows系统的用户界面桌面：开始菜单、图标、任务栏开始菜单：程序、设置、搜索、帮助、关机等桌面上的图标：

文件夹图标：我的电脑、网上邻居、我的文档等；文件；快捷方式任务栏：按钮、指示器等文件夹窗口：我的电脑、网上邻居、资源管理器等剪贴板：剪_Ctrl+X、复制_Ctrl+C、粘贴_Ctrl+V拖放操作：移动、复制_按住Ctrl键3.文件操作Page204.设置开始｜设置｜控制面板｜显示

→“显示属性”对话框开始｜设置｜控制面板｜管理工具｜计算机管理→“计算机管理”对话框开始｜设置｜打印机

→“打印机”对话框｜添加打印机５.附件开始｜程序｜附件｜写字板开始｜程序｜附件｜画图开始｜程序｜附件｜娱乐｜录音机Page21§2Word内容1.Office用户界面

主窗口、文档窗口：菜单、工具栏、定制；2．文档操作

打开、创建、保存、关闭3．录入输入法工具条、插入符号、自动图文集、自动更正4．格式编排

字样、段落、页面、分栏、页眉、页脚、模板、样式（标题等）Page225．表格制作

插入表格、表格与边框工具栏、文字与表格转换、自动套用格式6．作图

绘图工具条、微调、组合、环绕方式等7．数学公式

上标、下标、插入公式、插入域8．图文混排

插入图片、图片格式、图片工具栏、裁剪缩放Word内容_续Page23实验报告格式1．题目

例：文档操作与格式编排

实验报告2．暑名学号姓名班级3．任务

课堂布置4．实验条件

计算机硬件、软件配置等5．实验过程

详细说明操作步骤及解决问题的过程6．总结第一次实验24微机总线结构CPU和内存外存储器总线和I／O设备软件分类与功能计算机的应用上网查询、编辑Word文档并上传：第一章绪论√

什么是计算

计算、图灵机、可计算性√

计算工具的发展和电子计算机算筹、算盘、机械计算机、计算尺、电子数字计算机√

计算科学学科形态、基本概念√

计算科学的应用例：人工智能；云计算、网格计算、普适计算26本章内容什么是计算—执行算法哪些问题是可计算的？ 哪些是不可计算的？如何衡量问题的复杂性？历史上的计算工具与 计算机有哪些共同的思想?计算科学的根本问题是什么？

算法、可计算性、软硬件实现了解计算科学的应用范围

数值计算、数据处理、实时控制、 智能模拟；CAD（计算机辅助设计）姚普选271.1什么是计算思考：求解x2+2x-3=0？求解ax2+bx+c=0？有4个嫌疑人：a说："我不是小偷。"b说："c是小偷。"c说："小偷肯定是d。"d说："c冤枉人！"4人中3人说的是真话，问到底谁是小偷？总结：什么是计算？281.1.1计算计算_

computation：算法的执行，从包含算法和输入数据的初始状态开始，经过一系列中间状态直到最终的目标状态的过程算法_algorithm：若干条指令组成的有穷序列姚普选29计算

VS产品的加工/生产过程，可比之处？函数_function：一组可能的输入值和一组可能的输出值之间的映射关系函数为每个可能的输入赋予单一的输出函数的计算：对于一个给定的输入，确定其具体输出的值的过程

通过对函数的计算来解决问题计算机科学的一个基本问题__找到一种技术，并用之于计算哪些解决问题的函数，即

y=f(x)能否确定，如何确定加工过程，如何实现加工过程?30思考：实现下列函数的计算，有什么特点和问题？去年每天的平均气温投资额P，利率r，投资n年后的金额=P(1+r)n计算sin(x)的值计算22，23，24，210，2100函数越复杂，需要的技术支持越强结论：问题：任意复杂的函数，总能找到系统来计算它吗？姚普选201131函数的可计算与不可计算可计算：如果一个函数可依据输入值和一定的计算步骤来确定输出值，则称其为可计算的（computable）不可计算：如果根据输入找不到定义好的、一步一步的过程来确定输出值，这样的函数称为不可计算的(uncomputable)如果一个问题是可计算的，不管它有多复杂，总能制造出一种机器对其进行求解而如果问题是不可计算的，意味着它超出了机器的能力范围姚普选201132（计算机解题）例1：求解ax2+bx+c=0⑴变量a、b、c←输入各次项系数⑵变量delta←计算b*b-4*a*c⑶判断（delta>=0？）,是则

变量sdelta←计算sqrt(delta);

否则，变量sdelta←计算sqrt(-delta)⑷变量real←计算-b/(2*a);

变量imag←计算sdelta/(2*a)⑸判断（delta>=0？），是则x1←real+imag; x2←real-imag否则， x1←real+jimag; x2←real-jimag⑹输出变量x1和x2的值姚普选201133（计算机解题）例2：求n!⑴变量n←终值10变量mul←初值1

变量I←初值1⑵判断（i<=10？）,是则mul←计算mul*i

否则，转到⑷⑶i←计算i+1

转到⑵⑷输出变量mul的值⑸算法结束34计算设备模型——图灵机

依程序命令及内部状态移动、读写阅读35图灵机组成纸带，两端无限长，划为一个个格子_存储单元读写头_大盒子，可左/右移，读/改写当前格符号状态寄存器_盒子上的方块0、1、8、9等，保存有限个状态（可能的内部状态、初始状态、停机状态）控制规则_程序，按当前机器状态及格子上符号确定读写头下一步动作，改变状态寄存器值，令机器进入新状态图灵机计算：

预存的程序依据机器当前状态和当前格内容确定控制单元动作，控制单元一步步执行每一步：观察当前格的符号，必要时写入符号、左移/右移一格，然后改变状态阅读36例：本步操作

现状态操作新状态

当前状态为q4，A

改写为E左移一格，进入q3状态指令：q4

A

E

L

q3工作方式读写头_读出当前格符号依据_当前状态及读取的符号查表(一连串指令)确定_是否改写符号、如何移动读写头、是否停机机器_进入程序指定的新状态阅读37图灵机：输入信息变换→输出信息最简信息形式、运算：0、1、布尔运算_与或非构造图灵机：信息可0、1编码；变换可分解为0、1编码的变换；0、1编码的运算可分解为_与/或/非

→布尔电路可组成任意图灵机阅读姚普选201138预先输入指令阅读姚普选201139图灵可计算：将二进制形式输入值放在纸带上，运行机器直至停止，即可从带上读取输出值。由图灵机这样计算的函数称为图灵可计算的。即，存在一个图灵机，给它一个空纸带，可打印出任意逼近该函数的结果

丘奇—图灵论题（图灵猜想）：图灵可计算函数与可计算函数是一样的，即，图灵机的计算能力囊括了任何算法系统的能力还可以说，图灵机概念提供了一个环境，在此环境下，所有可计算函数的解都可表示出来图灵猜想的意义：可将图灵机的能力作为一种标准，若一个计算系统能够计算所有的图灵可计算函数，即可认为其能力相当于任何计算系统的能力阅读40元胞自动机_冯诺依曼研究可自我复制的自动机时提出空间分成元胞（方、∆、六边形等离散的格子）。元胞处于若干可能状态之一、可随时间演化且其演化受临近元胞状态影响。传统元胞自动机中，每个元胞的变化都同时进行例:J.H.Conway_生命游戏二维空间划为方格_元胞，元胞仅死/活二态，记为0/1，姚普选2011冯诺依曼邻居Moore邻居邻居，可考虑上下左右，或四周，或其他类型整个空间初始状态可人为设计，也可随机设定。随时间推移，每个元胞或死或生，然而空间整体却出现了非常复杂的状态演化阅读41生命游戏J.H.Conway_60年代末设计，单人玩计算机游戏

产生动态图案和动态结构能力的元胞自动机模型给定初始状态分布。经若干步运算：有的图案很快消失有的图案固定不动，有的周而复始重复两个或几个图案有的婉蜒而行有的保持图案定向移动，形似阅兵阵……等价于通用图灵机，选择不同初始条件，可完成一切计算机可完成的算法演算/complex/models/gameoflife.htm姚普选2011阅读42生命游戏的构成及规则(1)元胞分布在规则划分的网格上；(2)元胞具有0，1两种状态，0代表“死”，l代表“生”；(3)元胞以相邻8个元胞为邻居。即Moore邻居形式；(4)一个元胞的生死由该时刻本身生死状态和周围8个邻居的状态(确切讲是状态的和)决定:当前时刻，若一元胞状态为“生”，且8个相邻元胞中有2或3个的状态为“生”，则下一时刻该元胞继续保持“生”，否则“死”；当前时刻，若一元胞为“死”。且8个相邻元胞中正好有3个为“生”。则该元胞下一时刻“复活”。否则保持为“死”演示阅读姚普选2011431.1.2可计算性自终止（self-terminating）

：若程序中所有变量都用程序自身的编码形式进行初始化，且该程序的执行可导致一个终止的过程，则该程序是自终止的x=0;whilexnot0dox=x+1;endwhilestop一个自终止的程序阅读44假设：停机函数是可计算的，→可找到一个程序，其输入是程序，若输入的程序是自终止的，则结果为x=1，若输入的程序不是自终止的，则结果为x=0。设该程序为“停机函数判定程序”。问题：所有函数都是可计算的吗？答案是否定的函数值为1输入的程序是自终止的0输入的程序不是自终止的例：停机函数：其输入为一个程序问：停机函数是可计算的吗？阅读45构造另一个新程序“停机函数判定扩展程序”：假设：新程序是自终止的，则“停机函数判定程序”的结果是x=1，由于x不等于0，导致x不停地加1，而且永远不会为0，从而程序不终止，矛盾；假设：新程序不是自终止的，则“停机函数判定程序”的结果为x=0，由于x=0，while的循环不会执行而使程序停止，仍矛盾→停机函数在图灵机模型下是不可计算的以新程序作为新程序自身的输入“停机函数判定程序”whilexnot0dox=x+1;endwhile阅读461.1.3问题的复杂性求解两个问题将{5,2,8,1,6,3,10,7,4,9}从小到大排序计算3.1x2+6.2x+8.9=0的根哪个简单？（求解同一个问题可找到多种不同的算法）如果要排序的不是数字，而是装在相同容器中的不同重量的物质47时间复杂性：

计算机求解所花的时间——问题求解关键算法的时间复杂度：主要看算法中需要的主要运算的次数和问题规模的关系同一个问题可以有不同的算法，用其中时间复杂度最小的作为问题的时间复杂性若算法在最坏情况下的时间复杂度是O(nk)，其中n为问题的规模，k为一确定常数，则称该算法的时间复杂性为多项式时间一般地，将可由多项式时间算法求解的问题看作易处理的问题，称为P问题

超出多项式时间才能求解的问题看做难处理问题48例如，n个人的群体，列出所有可能的小组组合：2n-1时间复杂度至少O(2n-1)_指数时间复杂性问题有一类问题，已有时间复杂性为指数阶的算法，且已证明不存在多项式阶算法，如梵塔问题__称之为顽型问题另一类问题，目前已有的算法的时间复杂性为指数阶，但不能肯定它有或没有多项式阶算法，

如当m＞2时任意图的m-可着色问题

__称之为NP（NondeterministicPolynomial）问题，即“非确定的多项式”问题西安交通大学计算机教学实验中心201149空间复杂性计算机内存资源有限，问题较大时需考虑节省内存的算法通过度量程序所需的存储空间来衡量复杂性称为空间复杂性空间复杂性也是用问题规模的数量级来表示的空间复杂性和时间复杂性可能常常是矛盾的，在设计算法时需要做出折中501.2计算工具发展__电子计算机诞生1.手工计算工具算筹记数加法线性方程组51算盘、计算尺、手摇计算机523.电子计算机的诞生电子数值积分机和计算机（ElectronicNumericalIntegratorandComputer）,简称ENIAC1945年，冯•诺依曼“EDVAC报告的第一份草案”

，确定新机器有五个构成部分：运算器、控制器、存储器、输入和输出装置这一结构被称为冯•诺依曼结构，有此结构的计算机统称为冯•诺依曼计算机EDVAC的方案有两个重大改进：发挥电子元件高速度而采用了二进制；实现了存储程序,可自动从一个指令进入下一指令,作业顺序可通过“条件转移”指令而自动完成53冯.诺依曼结构西安交通大学计算机教学实验中心201154计算机的发展随着组成逻辑电路的电子元件的发展，将电子计算机的发展划分为：第一代电子管时代，第二代晶体管时代，第三代集成电路时代，第四代超大规模集成电路时代。如今，计算机从体积上趋于小型化，性能上趋于巨型化，功能上趋于网络化、智能化和综合化西安交通大学计算机教学实验中心2011551.3计算科学1985年，ACM（美国计算机协会）和IEEE－CS（国际电子电气工程师学会计算机分会）组成联合攻关小组，开始了对“计算作为一门学科”的存在性证明1989年1月，该小组提交了《计算作为一门学科》（Computingasadiscipline）的报告第一次给出了计算学科一个透彻的定义，回答了计算学科中长期以来一直争论的一些问题，完成了计算学科的“存在性”证明561.3.1计算学科计算学科(thedisciplineofcomputing）是对描述和变换信息的算法过程，包括对其理论、分析、设计、效率、实现和应用等进行的系统研究它来源于对算法理论、数理逻辑、计算模型和自动计算机器的研究并与存储式电子计算机的发明一起形成于20世纪40年代初期计算学科，即计算机科学与工程及计算机科学技术计算学科的研究：从算法与可计算性的研究到硬件和软件实现问题的研究计算学科，总体上对算法和信息处理过程进行研究的内容，满足给定规格要求的有效而可靠的软硬件设计——它包括所有科目的理论研究、实验方法和工程设计西安交通大学计算机教学实验中心201157报告认为，计算的根本问题是：什么能被（有效地）自动化，讨论能行性的有关内容包括：什么是（实际）可计算的、什么是（实际）不可计算的、如何保证计算的自动性、有效性及正确性等1.3.2计算科学的三个学科形态理论、抽象和设计581.理论

理论源于数学，其主要要素：定义、公理、定理、证明和结果用定义和公理来表达所研究对象的特征；用定理来假设对象之间的基本性质和对象之间可能存在