哈尔滨工业大学《计算机导论》课程复习提纲 …
任课教师:战德臣,聂兰顺
1.1 基本概念清单 1. 计算思维
第 1 章 引论
计算思维是计算机的思维和利用计算机的思维的统称,计算机的思维是关于“计算机是 如何工作的? 计算机的功能是如何越来越强大的?”的思维,利用计算机的思维是关于“现 实世界的各种事物如何利用计算机来进行控制和处理?”的思维。 2. 集成电路
集成电路是指将基本的元器件封装与集成在一起的芯片,它实现了数量众多元器件的封 装与集成,可有效地缩小电子电路的体积、提高电子电路的可靠性。 3. 主频与字长
主频是指 CPU 每秒钟所能完成操作的次数,以 MHz 或 GHz 为单位来度量, 1GHz=210MHz。字长是指 CPU 每一次操作所能处理数据的位数。 4. 典型的计算机术语
冯.诺依曼计算机、巨型机、小型机、微型机、个人计算机、兼容机等; 微处理器、硬件、软件、输入设备、输出设备、磁芯/磁鼓、内存与外存 操作系统、计算机网络、局域网、广域网、因特网、WWW
5. 典型的计算机语言与典型的操作系统 典型的计算机语言:FORTRAN、COBOL、BASIC、Pascal、C、C++、Visual C++、Visual
BASIC、Java。 典型的操作系统:Unix、MS DOS、Netware、Windows、Liunx。
1.2 基本思想与基本过程 1. 自动计算首先要解决的几个问题?
自动计算首先要解决的几个问题是数的表示及其存储、计算规则及执行和数及规则的输 入输出。
2. 算盘与机械计算机的异同点? 典型的机械计算机及其思想和意义; 算盘与机械计算机的异同点是:相同点是:二者都能实现数的表示及存储,也都有一套
计算规则;差异是:前者是人执行计算规则,后者是机械自动执行计算规则。 典型的机械计算机用纯机械装置来代替人的思维(规则及执行)和记忆(存储),开辟了自
动计算的道路。 3. 输入手段的变迁;输出手段的变迁;存储手段的变迁。
输入手段的变迁:打孔卡键盘鼠标扫描仪数码产品;
输出手段的变迁:阴极射线管向量式模拟显示器字符发生器基于内存的数字光 栅扫描显示器
存储手段的变迁:磁芯、磁鼓半导体存储器(内存)软盘硬盘光盘 4. 从元器件看计算机的发展过程与特点
电子管(真空二极管)晶体管集成电路大规模集成电路 体积越来越小、可靠性越来越高、规模越来越大、性能越来越高。
5. 微处理器的发展过程;微处理器的性能指标。 字长:8 位16 位32 位64 位 主频:几 MHz几十 MHZ几百 MHz几 GHz几十 GHz 晶体管数量:几万几十万几百万几千万几亿颗 功能:微处理器微处理器+协处理器(浮点运算)微处理器+多媒体处理器微处理器
+3D 多媒体处理器多微处理器 6. Unix、DOS、Netware、Windows、Linux 等操作系统引发的计算技术的变化
Unix—-操作系统,硬件功能的扩展 DOS—-微机操作系统,个人计算机的普及 NetWare—-网络操作系统,计算机网络应用的普及 Windows—-图形界面操作系统,多媒体应用的普及 Linux—-开放源代码运动
7.计算机网络的发展过程与特点;分组交换网、以太网、互联网等引发的计算技术的变化 远距离控制的实现分组交换技术与广域网以太网技术与局域网个人微机的网卡
WWW 与 Internet。 局域网(LAN)是指在一个有限地理范围内的各种计算机及外部设备通过高速传输媒介
连接起来的通信网络,可以包含一个或多个子网,通常局限在几千米的范围之内。典型的局 域网为以太网(Ethernet)。
广域网(WAN)是指由相距较远的计算机通过公共通信线路互联而成的网络,范围可覆盖 整个城市、国家,甚至整个世界,广域网有时也称为远程网,通常除了计算机设备以外,还 要使用电信部门提供的传输装置和媒介进行连接。常见的广域网如。
互联网(internet)是通过专用设备而连接在一起的若干个网络的集合。通过专用互联设 备,可以进行局域网与局域网之间的互联、局域网与广域网之间的互联以及若干局域网通过 广域网的互联。
因特网(Internet), 又称国际互联网,是世界最大的互联网,是由广域网连接的局域网 的最大集合。Internet不是一种新的物理网络,而是把多个物理网络互联起来的一种方法和 使用网络的一套规则。
8.典型的计算机应用—利用计算机的思维 科学计算:数值计算,如求解复杂高阶方程、工程分析与仿真模拟等 CAx:如过程控制、数字控制、机器人 信息管理:非数值计算,如数据库、管理与协同等 人工智能:智能化,使机器具有人的智能 嵌入式系统:使各种电器内嵌入计算机芯片接受自动控制
9.典型的计算机发展趋势: 高性能计算–无所不能的思维; 移动计算–无处不在的思维; 服务计算(Software As A Service)–提供软件转为提供服务,未来互联网的思维; 生物计算–生物器件与生物芯片及生物信息处理;
智能计算–智能化的思维; 全球信息化–信息技术与信息系统等。
哈尔滨工业大学《计算机导论》课程复习提纲 任课教师:战德臣,聂兰顺
2.1 基本概念清单 1. 语义符号化
第2章 计算原理
语义符号化是指将现实世界的语义用符号表达,进而进行基于符号的计算的一种思维, 将符号赋予不同语义,则能计算不同的问题。 2. 基本逻辑运算
基本逻辑运算有“与”运算、“或”运算、“非”运算、“异或”运算和“同或”运算等。 用1表示“真”,0表示“假”,则: “与”运算为“有0则0,全1则1”(语义是:参与运算的两个命题如有一个为假,
则结果为假;否则为真。下略)。 “或”运算为“有1则1,全0则0”;“非”运算为“0 的非则1,1的非则0”;“异或”运算为“相同则0,不同则1”。 3. 进位制、编码、ASCII 码、BCD 码
进位制是用数码和带有权值的数位来表示有大小关系的数值型信息的表示方法。常用的 进位制为十进制、二进制和十六进制。
编码是以若干位数码或符号的不同组合来表示非数值性信息的方法,编码是人为地将若 干位数码或符号的每一种组合均指定一种唯一的含义。编码的三个特征是唯一性、公共性和 易于记忆/便于识别性。常用的编码有 ASCII 码、BCD 码等。
ASCII码是计算机领域普遍应用的英文字母符号的编码方法,是用7位0和1的不同组 合来表示 10 个数字、26 个英文大写字母、26 个英文小写字母及其一些特殊符号的编码方法, 是信息交换的标准编码。
BCD 码,二-十进制编码,是用4位0和1的不同组合,按照与进位制保持一致的关 系,来表示 10 个十进制数字的方法。 4. 基本门电路
与门电路:是实现逻辑与运算的集成电路,即:只有当两个输入端为高电平(1)时,则 输出端为高电平(1);否则,输出端为低电平(0)。
或门电路:是实现逻辑或运算的集成电路,即:只有当两个输入端为低电平(0)时,则 输出端为低电平(0);否则,输出端为高电平(1)。
非门电路:是实现逻辑非运算的集成电路,即:当输入端为高电平(1)时,则输出端为 低电平(0);输入端为低电平(0)时,则输出端为高电平(1)。
异或门电路:是实现逻辑异或运算的集成电路,即:当两个输入端同为高电平(1)或同 为低电平(0)时,则输出端为低电平(0);否则,输出端为高电平(1)。 5. 存储单元:存储地址和存储内容
存储器由若干存储单元组成,每一存储单元存储有一定字长的存储内容,且有一唯一的 地址,可按存储单元的地址读写存储单元的内容。存储地址和存储内容都可用0和1编码表 示,例如一 16 位的存储地址,可表示 1-216 个存储单元,而一 8 位字长的存储内容可表示 1-28 大小的存储内容。存储单元好比宾馆的房间,而存储地址则是房间编号,存储内容则是 住在房间的人员,字长好比房间的床位数,房间编号不变,而房间内的人员可以不断变化。 即存储单元的内容可变化,而存储单元的地址通常是确定的。
2-1
哈尔滨工业大学《计算机导论》课程复习提纲 任课教师:战德臣,聂兰顺
6. 机器指令 机器指令是 CPU 可以直接分析并执行的指令,一般由 0 和1的编码表示。通常情况下,
一条指令被区分为两部分:操作码和地址码;操作码告诉 CPU 所要进行的操作类别,如取 数、存数、计算等,而地址码告诉 CPU 所要操作的数据在哪里。机器指令有不同的操作数 读取机制,详细内容可学习汇编语言课程。
用机器指令编写的程序即机器语言程序,是可以被 CPU 直接解释和执行的。 7. 冯.诺依曼计算机:五大部件结构及其功能
冯.诺依曼计算机的五大基本部件:运算器、控制器、存储器、输入设备和输出设备。 其中运算器负责执行逻辑运算和算术运算,控制器负责读取指令、分析指令并执行指令,以 调度运算器进行计算,存储器负责存储数据和指令,输入设备负责将程序和指令输入到计算 机中,输出设备是将计算机处理结果显示或打印出来。
8. 微处理器、CPU、存储器、主存/内存、输入、输出 将运算器和控制器封装集成在一块芯片上,该芯片称为中央处理单元(CPU:Central
Process Unit),又称为微处理器。 广义存储器是指内存和外存的统称,内存通常是指使用半导体材料制作的、通常按地址
访问的、由若干存储单元构成的存储芯片,具有速度快、容量有限、和 CPU 按存储字/存储 单元交换信息、电信息易失性。由于其电信息易失性,适合于临时存储,又称为主存,在操 作系统、应用软件中等又被作为缓存使用。外存是指用磁性材料制作的、通常连续顺序存储 信息并具有信息存储永久性的存储器,适合于永久存储设备。
输入是指将外界信息输入到计算机内,而输出则是指将计算机内的信息传送到外界(显 示或打印)。
9. 现代计算机系统的构成 现代计算机系统由硬件和软件构成。硬件由主机和外部设备构成;主机由主电路板(简称
主板)、接口电路板(简称接口卡)、电源及软盘驱动器(软盘和软盘驱动器是分离的)、硬盘(含 硬盘驱动器,硬盘和硬盘驱动器是做在一起的)等部件构成。主板由 CPU、内存、总线等部 件构成。总线是主板上连接各部件的符合标准的电路连线和插槽,通常包括数据总线、控制 总线和地址总线三部分,外部设备可通过使其接口卡插入主板的插槽而与 CPU 和内存等相 连接。现代计算机也有将硬盘驱动电路直接做在主板上,此时硬盘可直接连接到总线上即可。 外部设备由显示器、键盘、鼠标以及硬盘、软盘驱动器等部件构成。所有部件通过总线与主 电路板相连接,也即和 CPU 与内存相连接.
10. 硬件、软件;系统软件、应用软件;ROM、RAM; 硬件:硬件是指构成计算机的物理实体,是指看得见摸得着的实物部分。 软件:软件则是控制硬件按指定要求进行工作的由有序命令构成的程序集合。现代软件
通常包括可执行的程序文件及若干附件的程序要使用的数据文件等。 系统软件是用于对计算机进行管理、控制、维护,或者编辑、制作、加工用户程序的一
类软件。常见系统软件包括操作系统、xx 语言编译器及其程序开发环境、数据库管理系统 软件及各类管理工具软件等。
应用软件则是用于解决各种实际问题、进行业务工作的软件。
ROM 和 RAM 统称内存,但二者有些差别。ROM:只读存储器 Read Only Memory,ROM 采用特殊工艺制作,存储信息不会丢失(即只读不写,信息永久不变),其他特性同内存,通 常容量特别小,仅能存放少量的信息。一般情况,ROM 存放机器接通电源即开机时所必须 的一些指令代码。
2-2
哈尔滨工业大学《计算机导论》课程复习提纲 任课教师:战德臣,聂兰顺
RAM:随机访问存储器 Random Access Memory,即常说的内存,通常是指使用半导体 材料制作的、按地址访问的、由若干存储单元构成的存储芯片,具有速度快、容量有限、和 CPU 按存储字/存储单元交换信息、电信息易失性。一般情况下,作为与 CPU 交换信息的部 件而存在:所有的程序和数据,如需要 CPU 处理,则其首先要装载到内存中。
11. 文件、目录、FAT 文件是操作系统管理信息的基本单位。用户不必关心文件在磁盘上是如何存取的,而只
需关注文件名及文件内容即可,操作系统通过文件名管理存储在磁盘上的各种文件及其信 息。
扇区是磁盘的基本操作单位。文件分配表(FAT)是磁盘上记录文件存储的簇块之间衔接 关系的信息区域。所谓簇块是指倍数且连续的扇区构成的存储区域。
目录是磁盘上记录文件属性、文件第一簇块号等相关信息的由文件名构成的文件清单。 12. 操作系统及其主要功能
操作系统(Operating System)是控制和管理计算机系统各种资源(硬件资源、软件资源和 信息资源)、合理组织计算机系统工作流程、提供用户与计算机之间接口以解释用户对机器 的各种操作需求并完成这些操作的一组程序集合,是最基本、最重要的系统软件。
操作系统的主要功能包括:处理机管理、存储管理、文件管理、设备管理和程序与作业 管理。
13. 算法、程序与计算机语言 算法是为解决一个特定问题而采取的确定的有限的步骤。 程序是计算机能够理解与执行的解决问题的步骤,是用计算机语言描述的解决问题的算
法。
计算机语言是人们设计的专用于人与计算机交互、进而计算机能够自动识别的语言,是
书写计算机程序的语言,是问题求解步骤的书写规范、语法规则、相关标准等的集合。 14.指令系统、机器语言、汇编语言、高级语言、源程序、汇编程序、编译程序
指令系统是 CPU 可以执行的由二进制编码的指令集合。 机器语言是用机器指令编写程序的语言。 汇编语言是用助记符号编写程序的语言。 高级语言是用类自然语言的语句为单位编写程序的语言。 源程序是用某一种语言编写的程序。 汇编程序是将用汇编语言编写的源程序转换成机器语言程序的程序。 编译程序是将用高级语言编写的源程序翻译成机器语言程序的程序。
15.汉字内码与汉字外码 汉字外码是用键盘可识别符号组合来编码每一个汉字的编码,是用来进行汉字输入的编
码。汉字内码是用两字节且最高位均为 1 的 0,1 型编码来编码每一个汉字的编码,是汉字在 计算机内部存储所使用的编码。 16. (图像/视频/音频的)采样、量化与编码;模拟信号与数字信号
所谓模拟信号是指随时间连续不间断产生的信号。而数字信号则是离散时间点产生的离 散数字信号。
模拟信号,需经采样、量化和编码形成数字信号后进行数字信号处理。所谓采样是指按 一定的采样频率对连续信号做时间上的离散化,即对连续信号隔一定周期获取一个信号点的 过程。量化是将所采集的信号点的数值区分成不同位数的离散数值的过程。编码则是将采集 到的离散时间点的信号的离散数值按一定编码规则编码并存储的过程。
2-3
哈尔滨工业大学《计算机导论》课程复习提纲 任课教师:战德臣,聂兰顺
2.2 基本思想与基本过程 1. 语义符号化思想
语义符号化是指将现实世界的语义用符号表达,进而进行基于符号的计算的一种思维, 将符号赋予不同语义,则能计算不同的问题。
例如,《易经》将现实世界分为阴和阳,阴即0,阳即1,进一步用阴阳的组合与变化, 即0,1 的组合与变化来反映大千世界的变化规律,例如八卦,用三位0,1 码的组合,每一种 组合抽象于一种自然现象,如“乾卦”抽象于天,表达具有天的特性的事物,则天为乾卦的 本体语义,而如果将乾卦放在“家庭空间”中,则表征“父”,而如果放在“身体空间”中, 则表征“首”,因此,符号可以被绑定不同的语义。由此符号化,则二十四节气的演变、生 命规律的演变等都可以用 0 和1,即阴和阳的变化来反映了。 2. 计算的实现:电子电路级的实现,即基于 0 和 1 的电子实现;
现实世界的各种信息可表示成0和1,可基于0和1进行算术运算和逻辑运算,在实现 过程中,能够表示0和1的元器件有很多,典型的如继电器开关:开(表示1)、关(表示0), 电路中的电信号:低电平(表示0)、高电平(表示1),二极管、三极管等不仅实现表示,还 实现控制。
利用基本元器件,如二极管、三极管可封装集成后制造“与”门、“或”门、“非”门等 门电路,并能确认这些基本门电路的正确性。
再将“与”门、“或”门、“非”门等门电路进行组合,形成更为复杂的组合电路。布尔 代数与数字逻辑是判断组合电路正确性的工具。
微处理器、内存储器等就是不断组合已有的门电路、组合电路,并将其集成在一块芯片 上所形成的。
3. 计算的实现:程序级的实现,即图灵机 图灵认为:所谓计算就是计算者(人或机器)对一条两端可无限延长的纸带上的一串 0 或
1,执行指令一步一步地改变纸带上的 0 或 1,经过有限步骤最后得到一个满足预先规定的 符号串的变换过程。基本思想:“基本动作”就是机器将输入转变为输出,“指令”是对基本 动作的控制,“程序”是有先后次序关系的指令串即控制规则,“自动执行”是依控制规则自 动将输入处理为输出,“输入/输出”及“程序”均用符号表达及最终由 0 和 1 表达。
上述思想可用形式化模型表达。图灵机是一个七元组 P = (Q, , , , q0, B, F ),其中 Q 是有穷状态集,是有穷输入字符集, 是有穷输入带字符集,=
图灵机模型被认为是计算机的基本理论模型,即计算机是使用相应的程序来完成任何设 定好的任务,是一种离散的、有穷的、构造性的问题求解思路,一个问题的求解可以通过构 造其图灵机(即程序)来解决。图灵认为:凡是能用算法方法解决的问题也一定能用图灵机解 决; 凡是图灵机解决不了的问题任何算法也解决不了,此即图灵可计算性问题。
4. 冯.诺依曼计算机和存储程序思想 冯.诺依曼计算机的五大基本部件:运算器、控制器、存储器、输入设备和输出设备。
其中运算器负责执行逻辑运算和算术运算,控制器负责读取指令、分析指令并执行指令,以 调度运算器进行计算,存储器负责存储数据和指令,输入设备负责将程序和指令输入到计算 机中,输出设备是将计算机处理结果显示或打印出来。
冯.诺依曼计算机的基本思想是存储程序的思想,即程序在执行之前事先存储在存储器 中,这样机器就可连续地从存储器中读取指令执行指令,实现连续自动的计算。
2-4
哈尔滨工业大学《计算机导论》课程复习提纲 任课教师:战德臣,聂兰顺
冯.诺依曼计算机又分为以运算器为中心的结构和以存储器为中心的结构。以运算器为 中心的结构,则使输入输出与计算都要经过运算器,而以存储器为中心的结构,则使输入输 出独立于运算器,因此后者的结构可使程序/数据的输入输出与程序中的各种计算相互独立, 从而做到并行执行,即一方面输入输出程序和数据的,另一方面可同时执行另外的程序进行 计算。
5. 计算机硬件执行过程;计算机系统执行过程 计算机硬件执行过程:机器提供了其可以执行的指令的集合,这些指令被称为机器指令;
用机器指令编写问题求解的程序,即机器指令序列;将机器指令序列及相关的数据存储于存 储器中;启动控制器工作;控制器发送第 1 条指令的存储地址给存储器;存储器取出指令返 给控制器;控制器分析指令并执行指令:发送操作数 x 所在地址给存储器;存储器取出操作 数 x 给运算器;控制器发送下一指令的存储地址给存储器;存储器取出指令返给控制器;控 制器分析指令并执行指令:发送操作数y所在地址给存储器;存储器取出操作数y给运算器; 控制器执行指令:通知运算器进行运算,如此循环往复,一条接一条地取指令、分析指令、 执行指令,直到程序终止!
计算机系统执行过程:计算机初始启动指令是放置在 ROM 中的,而大量的程序是放置 在磁盘上的。当计算机电源接通时,CPU 首先从 ROM 中读取启动指令,按照启动指令,到 磁盘上寻找操作系统,当找到操作系统后,则将其从磁盘上装载到内存中,CPU 就可从内 存中读取操作系统的程序指令并执行之。当操作系统装载成功后,CPU 就处于操作系统的 监控之下。当用户在操作系统下运行某一应用程序时,操作系统会到相应磁盘位置寻找应用 程序文件,如找到则将其装载到内存,同时使 CPU 执行该应用程序,应用程序进行工作, 当应用程序执行完毕,则操作系统会使释放应用程序所占用的内存,同时收回 CPU 的控制 权,如此执行。
6. 现代计算机的存储体系 现代计算机的存储体系由内存和外存等构成。内存是用半导体材料制作,具有速度较快、
容量有限、电信息易失性等特点;外存是用磁性材料制作,具有速度较慢、容量可无限扩展、 信息永久保存等特点。
现代计算机通常将内存和外存整合成一个存储体系:使使用者感到容量象外存的容量, 而速度象内存的速度,内存与外存的调度和处理由操作系统来实现而对使用者透明化;CPU 和内存按存储字/存储单元交换信息,而外存不与 CPU 直接交换信息,外存的信息首先按块 (Block, 也有称页 Page,一页约 512 字节或其倍数)装载到内存,然后再由 CPU 访问.即因 外存速度慢,则以批量交换信息,内存速度快,则以存储单元交换信息,以批量换速度,行 程存储体系。
内存又分为 ROM(只读存储器 Read Only Memory)和 RAM(随机访问存储器 Random Access Memory)。ROM采用特殊工艺制作,存储信息不会丢失,通常存放机器启动时所必 须的一些指令代码。RAM 即前述的内存。
磁盘又分为硬盘(Hard Disk)和软盘(Floppy Disk)。所谓硬盘通常是固定在计算机里面的、 具有大容量高速度的磁盘,而软盘通常是指可灵活更换盘片的磁盘,软盘虽然容量小,但因 可更换盘片,相当于具有无限容量。 7. 操作系统管理磁盘及文件的基本思想
磁盘被划分成一个个扇区,以扇区或扇区的倍数(被称为簇块)为单位和内存交换信息。 文件也被划分成一个个扇区或簇块存储于磁盘上,为记住构成文件的每一簇块之间的先后顺 序联系,操作系统在磁盘上建立了一张表,即 FAT 表(文件分配表)。磁盘上有多少个簇块,
2-5
哈尔滨工业大学《计算机导论》课程复习提纲 任课教师:战德臣,聂兰顺
FAT 表就有多少项,FAT 表项的编号与磁盘簇块编号有一一对应的关系。FAT 表项的内容指 出了该簇块的下一簇块的编号。例如 13 号表项内容为 24 说明 13 号簇块后面是 24 号簇块, 而由 24 号表项内容 26 可知,24 号簇块后面是 26 号簇块,依此类推,一直到表项为 End 的 簇块为止。这样构成文件的各簇块就由 FAT 表形成一个簇块指针链,前一个簇块指向后一 个簇块,一直到结束为止。
那么文件簇块指针链的第一个簇块编号存在哪呢?它与文件的文件名、文件的属性等信 息一起存放于磁盘的目录中。
因此,每张磁盘在使用之前要进行格式化。所谓格式化就是要给磁盘划分扇区、建立
FAT 表以及建立目录表(此目录称为根目录),以便于文件存储。磁盘目录、文件分配表是磁 盘上的重要数据保存地。 8. 操作系统管理外部设备的基本思想
操作系统管理外部设备像管理文件一样,使用户只需关心与设备的数据交换即可,而不 必关心设备的具体控制细节。
主板上是通过总线连接的 CPU、内存等。接口电路板与外部设备连接,同时通过插入 主板的总线插槽与 CPU 相连接。接口电路板也即所谓的 IO 控制器。操作系统通过设备无关 管理层、设备相关管理层的分层管理调用设备驱动程序。设备驱动程序进一步调用设备自身 的操作指令,控制设备的光机电动作。
其中,设备无关管理层:面向应用程序,处理外部设备就像处理文件一样,以打开、关 闭、读写数据等通用的方式描述对设备的操作;
设备相关管理层:面向设备驱动程序,它将前述的设备无关命令翻译成设备驱动程序所 能识别的命令,并调用设备驱动程序完成对设备的控制操作。
设备驱动程序层:负责将操作系统对设备的操作指令转换成设备操作指令。
设备操作指令层:设备自身的驱动光机电动作的指令。 9. 操作系统的启动与关闭过程
操作系统一般由以下几个部分组成:引导程序、基本输入输出程序、磁盘文件管理程序、 命令监控与解释执行程序和若干命令程序文件构成。每次机器接通电源后,首先由计算机的 ROM 里面读取指令开始,然后到磁盘中找引导程序,由引导程序引导载入操作系统的基本 输入输出程序。所说载入是指将其装入内存中处于可用状态,当引导程序完成基本输入输出 程序的载入后即执行之,控制权由此交给了基本输入输出程序。基本输入输出程序由两部分 组成。一部分固化在 ROM 中,称为 ROM BIOS,它包括常用输入/输出设备(显示器、键盘、 磁盘驱动器、行式打印机、异步通信适配器、日期和时间等)的驱动程序,是控制硬件工作 的程序。另一部分则存放在磁盘上,是 ROM BIOS 的扩充。执行基本输入/输出程序即是在 内存中设置好各种设备的驱动程序,进行各种初始化工作,然后读取磁盘文件管理程序,建 立操作系统的运行环境,随后将命令监控与解释执行程序载入内存,并执行命令监控与解释 执行器,控制权移交给命令解释器。命令解释器是用户和操作系统的直接界面。它负责监控、 接收、识别并执行用户通过键盘或鼠标输入的命令并执行之。
操作系统启动通常完成以下工作:初始化系统环境、加载设备驱动程序、加载服务程序 等、加载系统程序, 如程序管理器/命令解释器等。
操作系统关闭通常完成以下工作:保存用户设置、关闭服务程序、通知其他联机用户、 保存系统运行状态、将内存内容写回外存中、正确关闭相关设备等。 10. 计算机语言的发展轨迹
基本轨迹:机器语言汇编语言高级语言面向对象的程序设计语言可视化构造 2-6
哈尔滨工业大学《计算机导论》课程复习提纲 任课教师:战德臣,聂兰顺
语言。 CPU 可以执行二进制编码的机器指令,CPU 提供的机器指令集合被称为指令系统。用
机器指令编写程序的语言称为机器语言。所有程序均需转换成机器语言程序,计算机才能够 执行。由于二进制编码的机器指令难于识认和书写的不便性,人们提出了用助记符号编写程 序并进行自动翻译的思想。用助记符号编写程序的语言被称为汇编语言。将用汇编语言编写 的程序自动转换成机器语言的程序被称为汇编程序。由于汇编语言和机器指令的密切相关 性,程序编写仍相当复杂。于是,人们设计了各种高级语言。高级语言的表示形式近似于人
们的自然语言,以语句为单位编写程序,一条语句的功能往往相当于十几条甚至上百条汇编 语言的指令,且无需考虑机器指令系统。将用高级语言编写的程序翻译成机器语言程序的程 序被称为编译程序。 进一步,人们又提出了面向对象的程序设计语言,使程序员可以构造 积木块,然后就可以用积木块编写程序,进一步又提出了可视化的构造语言,像堆积木一样 编写程序。如此程序编写越来越容易,而编写的程序规模也越来越大! 11.汉字在计算机中的处理过程
汉字首先通过汉字外码进行输入,汉字外码是用键盘可识别符号组合来编码每一个汉字 的编码。汉字在计算机内部采用汉字内码进行存储,汉字内码是用两字节 0,1 编码每一个汉 字的编码。汉字的输出是通过汉字字形码,汉字字形码是用点阵形式表示汉字形状的编码, 汉字点阵中有笔画的点为 1 而无笔画的点为 0,可构成汉字的字形信息。由外码输入、转换 成内码存储、再映射到汉字字形码进行输出。
12.信息表示与处理的一般性思维 一般性思维是:首先研究信息或符号绑定语义的方法;进一步形成协议、标准或语言(被
称为广义的语言),然后基于所形成的广义语言,开发相应的解析器/编译器/执行器等(被称 为广义的编译器),实现自动处理。信息处理即是不断提出新的广义语言,同时提供广义编 译器来解析和执行用所提出的广义语言编写的信息,提高计算机的信息处理能力。 13.“分离”与“分层”思想
分离与分层是复杂问题求解的基本思维模式。分离是将共性的内容分离出来以单独的软 件或系统来管理,通过逐渐剥离共性内容使复杂问题的可解决内容越来越多,进而到最终求 解的思想;分层是将一个复杂问题分为不同层面,比如从宏观到微观的若干层,从概念到实 现的若干层等,每一层相对来讲比较简单,可清晰定义每一层的协议/标准并编制相应的处 理程序。然后再建立高层向低层的转换关系,从而实现复杂问题求解的一种思想。
附:计算机语言发展路线图
2-7
哈尔滨工业大学《计算机导论》课程复习提纲 任课教师:战德臣,聂兰顺
2-8
哈尔滨工业大学《计算机导论》课程复习提纲 任课教师:战德臣,聂兰顺
3.1 基本概念清单 1. 算法
第3章 问题求解
算法是一个有穷规则的集合,它用规则规定了解决某一特定类型问题的运算序列,或者 规定了任务执行或问题求解的一系列步骤,其基本特征为有穷性、确定性、有输入和输出以 及能行性。 2. 数学模型与数学建模
数学建模就是建立数学模型,就是用数学语言描述实际现象的过程。
数学模型就是对实际问题的一种数学表述,是关于部分现实世界为某种目的的一个抽象 的简化的数学结构,数学结构可以使数学公式、图表和框图等。 3. 数据结构
数据结构是数据的逻辑结构、存储结构及其操作的总称,它提供了问题求解/算法的数 据操纵机制,其中的逻辑结构反映了数据之间的关系,而存储结构是在反映数据逻辑关系的 原则下,数据在存储器中的存储方式。 4. 变量
变量是算法或程序运行过程中可发生改变的量。通常由符号表示,一个变量由变量名和 变量值构成,变量值可以不断发生变化。
本质上讲,变量是一系列存储单元,该存储单元的地址用符号来表示即变量名,即变量 名是用符号表示的存储单元地址,而变量值则是存储单元的内容。一个变量占用多少存储单 元,则是由变量类型决定的,变量名通常对应这一系列存储单元的起始地址。 5. 向量和表
向量是一有序数据的集合型变量,向量中的每一个元素都属于同一个数据类型,用一个 统一的向量名和下标来唯一的确定向量中的元素。在程序设计语言中,又称为数组。
表是按行按列组织数据的集合型变量,通常是一个二维向量。 6. 控制结构与典型的控制结构
控制结构是指算法或程序的步骤或规则的执行关系,它提供了问题求解/算法的过程控 制机制。
典型的控制结构有三种:顺序结构、分支结构和循环结构。 顺序结构是按顺序执行一条条规则的一种结构,即“执行 A,然后执行 B” 分支结构是按条件判断结果决定执行哪些规则的一种结构“,即如果 Q 成立,那么执
行 A,否则执行 B” ,Q 是某些逻辑条件。 循环结构:控制指令/规则的多次执行的一种结构—迭代(iteration)。
7. 流程图 流程图是图形方式表示算法的一种方法,它用矩形框表示一组顺序执行的规则或者程序
语句,用菱形框表示条件判断及根据判断结果执行不同的分支,用圆形框表示算法或程序的 开始或结束,用箭头线表示算法或程序的走向。 8. 程序设计语言的基本语法要素
程序设计语言的基本语法要素有:常量和变量、表达式、程序语句和函数。
3-1
哈尔滨工业大学《计算机导论》课程复习提纲 任课教师:战德臣,聂兰顺
所谓常量是程序运行过程中始终不变的量,变量是程序运行过程中可发生改变的量。表 达式为用算术运算符、逻辑运算符、比较运算符将变量、常量连接起来所形成的计算公式。 程序语句为一条条计算机可识别的计算规则的完整表示,是程序的基本构成单位,通常按行 书写,一行为一条语句,但也有在一行书写多条语句的,而多条语句之间通过分隔符予以区 分。所谓函数是系统已编制好并可直接在程序编写中使用的完成特定功能的程序,我们可直 接像表达式或变量一样使用它,它通常存储于随语言环境提供给我们的公用函数库中。 9.时间复杂性
如果一个问题的规模是 n,解这一问题的某一算法所需要的时间为 T(n),它是 n 的某一 函数,T(n)称为这一算法的“时间复杂性” 10. “系统”与“系统”的特性
系统是指由相互联系、相互作用的若干元素构成且具有特定结构和功能的统一整体。
系统的基本特征:环境特征、功能与过程特征、构件与结构特征及整体性、层次性和动 态性特征。
11. 环境、功能与过程、构件与结构 所谓系统的环境是指和系统相关的外部因素的总称,系统与系统外各元素(或者环境)之
间是相互作用的。 所谓构件是构成系统的一个个可相互独立的元素,又可称为模块、单元等;所谓结构是
指构件(或模块或单元)之间的相互连接方式与相互作用方式的框架。 所谓功能是指系统所表现出来的,具有并能够提供的特性、功效、作用和能力等,所谓
过程是各项功能在系统运行过程中的次序及约束关系。 12. 系统的整体性、层次性和动态性
整体性是指系统的非还原性和非加和性。所谓非还原性是指系统的整体具有但还原为部 分便不存在的特性,即“涌现性”。所谓非加和性是指整体不能完全等于各部分之和,即“贝 塔朗菲定律”
层次性是指系统的一个功能或构件仍然可以作为一个系统来看待。即系统由子系统构 成,而子系统作为系统,又是由其子系统构成的,体现为层次性。
动态性是指系统运行过程中随环境随时间空间而变化的特性。 13.系统科学方法的三原则:整体优化、动态优化和模型化
系统科学方法的三原则:整体优化、动态优化和模型化原则 14.现代程序的典型构成要素
程序的基本要素有:常量和变量、表达式、程序语句和函数。
而现代程序的典型构成要素,除包含程序的基本要素外,还有类、对象与方法。所谓类 是将不同类型的数据和与这些数据相关的操作封装在一起的集合体,类的结构是用来确定一 类对象的行为的,而这些行为是通过类的内部数据结构和相关的操作来确定的。所谓对象是 指该类的一个个的程序执行个体或称实例,对象是用类创建的,同一“类”的所有对象具有 相同形式的函数和变量,但处理各自的数据(变量名相同,但变量值是不同的)。所谓方法是 能执行特定功能的程序语句块。也称为“过程”或“函数”。
15.结构框架 结构框架是按照某一种体系结构(Architecture)实现的,用于连接、装配各种构件形成系
统的一套程序。 16. 软件体系结构;软件模式
软件模式是被前人发现,经过总结形成的一套解决某一类问题的可以重复利用的一般性
3-2
哈尔滨工业大学《计算机导论》课程复习提纲 任课教师:战德臣,聂兰顺
解决方案。其本质性特征:把若干类相似问题中的不变部分和变化部分分离出来,其不变的 部分形成了模式,而变化部分留给用户去解决该类问题中的某一个具体问题。
软件体系结构(Software Architecture)是为软件系统提供的一个结构(Structure)、行为和属 性的高级抽象,它从一个较高的层次来考虑组成系统的构件、构件之间的连接,以及由构件 与构件交互形成的拓扑结构。简单而言:体系结构 = 构件(或称组件) + 连接件 + 约束。 17. 系统的可靠性与安全性、软件系统的可靠性与安全性
可靠性(Reliability):产品或系统在规定的条件下和规定的时间内完成规定功能的能力, 它的概率度量称为可靠度。
软件可靠性:软件可靠性是软件系统在规定的时间内及规定的环境条件下,完成规定功 能的能力,是在规定的条件下,在规定的时间内,软件不引起系统失效的概率;
安全性(Safety):安全性是指使伤害或损害的危险限制在可以接受的水平内。
软件安全性是指软件系统遭受伤害或损害的危险程度,所谓的伤害是指数据被破坏或被 非授权修改、隐秘数据被公开、数据和系统不能正确为用户服务等现象。这种危险发生的概 率,可用于评估安全性:概率越小、安全性越高。
3.2 基本思想与基本过程 1. 算法类问题的求解框架
算法类问题的求解框架可以描述为:
(1)问题抽象及数学建模:首先要理解问题,将问题抽象为一个数学问题,并给出求解 该数学问题的算法模型。
(2)算法的数据结构和控制结构设计:将数学模型转换为可由计算机自动计算的算法, 其中涉及的数据要选择合适的数据结构进行表示和存储,要用流程图或规范的自然语言将算 法的步骤或基本思想表达出来。
(3)算法的实现:用程序设计语言编写算法实现的源程序,并经过编译、链接形成可执 行的程序。
(4)算法的分析:算法设计和实现后,需要分析算法的正确性和复杂性,判断能行性! 所谓能行性就是是否在现有资源可承受能力下完成的。 2. 程序设计过程
程序设计过程一般经过编辑源程序 编译 链接 执行。所谓编辑源程序是利用程序编 辑器,按照计算机语言的规范书写程序的过程;所谓编译是将编制好的源程序翻译成机器可 以执行的机器代码程序(又称为目标代码)的过程。所谓链接是将目标代码与公用函数库中的 函数实现代码集成起来形成最终可执行程序的过程。所谓执行就是程序的运行过程。
3. 算法的描述方法:流程图法和步骤描述法 参见讲义,自己举例掌握算法的描述方法。
4. 基本结构程序的编写训练、基本结构程序的识读训练 提示:要求能够编写基本结构的程序,并且能够模拟计算机执行基本结构的程序。基本
结构即:循环结构、分支结构、顺序结构、及其简单的混合结构(略,参见讲义); 5. 关于算法设计与算法分析的基本思想;典型算法策略。
算法设计与分析就是针对具体的问题,选择合适的算法策略,设计求解该问题的具体算 法。典型算法策略如贪心算法,它的基本思想是“今朝有酒今朝醉”,即把求解一个问题分 成若干步,每一步一定要做当前情况下的最好选择,否则将来可能会后悔,故名“贪心”。
求解 TSP 问题的贪心算法:从某一个城市开始,每次选择一个城市,直到所有城市都 3-3
哈尔滨工业大学《计算机导论》课程复习提纲 任课教师:战德臣,聂兰顺
被走完。每次在选择下一个城市的时候,只考虑当前情况,保证迄今为止经过的路径总距离 最短。
其他算法策略还有遍历与搜索算法、分治算法等等。
6. 算法的正确性与复杂性分析基本思想 算法设计和实现后,应采用证明方法或仿真分析方法,分析算法的正确性和复杂性。算
法的正确性分析是分析算法的输出是最优解还是可行解,如果是可行解,与最优解的偏差有 多大。算法的复杂性分析是分析算法的效率:时间效率和空间效率。空间复杂度是分析算法 在执行过程中所占存储空间的大小;时间复杂性是:如果一个问题的规模是 n,解这一问题 的某一算法所需要的时间为 T(n),它是 n 的某一函数,T(n)称为这一算法的“时间复杂性”。 通常采用大 O 记法,如Ο(n2) 、Ο(2n)等表示复杂性的量级。
当算法的时间复杂度的表示函数是一个多项式时,如 O(n2)时,则计算机对于大规模问 题是可以处理的。当算法的时间复杂度是用指数函数表示时,如O(2n),当n很大(如10000) 时计算机是无法处理的,在计算复杂性中将这一类问题被称为难解性问题。
所有可以在多项式时间内求解的问题称为 P 类问题,所有在多项式时间内可以验证的问 题称为 NP 类问题。 7. 从哪几个方面描述 “系统”?
主要应从三个方面描述“系统”:
(1)从环境角度描述系统。所谓系统的环境是指和系统相关的外部因素的总称。系统与 系统外各元素(或者环境)之间是相互作用的。
(2)从外特性或者说目的和作用角度描述系统。描述系统的功能与过程。所谓功能是指 系统所表现出来的,具有并能够提供的特性、功效、作用和能力等,所谓过程是各项功能在 系统运行过程中的次序及约束关系。
(3)从内特性或者说构成、构造角度描述系统。描述系统的构件与结构。系统是由若干 构件,按照一定的结构(Structure)构成的。所谓构件是构成系统的一个个可相互独立的元素, 又可称为模块、单元等;所谓结构是指构件(或模块或单元)之间的相互连接方式与相互作用 方式的框架。
8. 系统类问题的求解框架 系统类问题的求解框架可以描述为: (1)建立问题域模型:先建立不考虑计算系统的计算模型,即问题域模型,尽管目的是
刻画计算系统。若要建立计算系统,首先需理解计算系统,理解:如果由人来做,应如何计 算呢?
(2)建立软件域模型:建立计算系统的构建模型,即软件域模型,说清楚软件系统应怎 样?
(3)模块与系统的实现:用程序实现模块与系统。 (4)系统的部署与运行:将系统部署到应用环境中,利用系统进行业务工作。 (5)系统的结构与性能:设计系统时应关注系统结构的选择和可靠性、安全性问题。选
择合适的结构,保证系统的可靠性和安全性。 9. 整体优化、动态优化和模型化原则
整体优化原则:注意系统的非还原性和非加和性,系统整体优化,或者说全局优化是非 常重要的。
动态优化原则:注意系统总是动态的,永远处于运动变化之中。随时间、空间和环境而 变化的。例如:飞机造好了,但要考虑(1)适应各类天气的情况;(2)材料随使用的磨损等;
3-4
哈尔滨工业大学《计算机导论》课程复习提纲 任课教师:战德臣,聂兰顺
软件系统也是一样,当内存调度出现混乱时,当软件受到病毒的侵扰时,怎样回到正确状态? 当系统装载的内容越来越多,使用时间越来越长,系统会不会越来越慢?
模型化原则: 以模型代替真实系统。进行分析、设计、模拟和实验,达到认识真实系 统特性和规律性的方法。 10.问题域建模与软件域建模的基本思想
问题域建模主要是从功能/过程角度,即使用和作用的角度对系统进行模型化表达以达 到理解系统的目的,可从功能、过程、业务计算逻辑、信息、组织等视角建立模型。典型的 建模过程:(1)基本概念的澄清和相关信息的表示;(2)用少量典型数据模拟计算过程;(3)计 算模型的表达;(4)系统功能的识别、理解与定位;(5)其他方面的建模。
软件域建模则主要是从构件/结构角度,即构造系统的角度对系统进行模型化表达以达 到理解系统的目的。可从信息(对象)、功能与模块划分、程序类设计、功能/函数调用关系、 处理逻辑等视角建立模型。问题域信息模型强调信息要素,但更强调信息要素之间的整体集 成关系,是从信息的使用和分析角度看信息,而软件域信息模型则强调信息的存储结构,强 调信息存储和信息自动处理的有效性。问题域功能模型强调使用功能,而软件域功能模型则 强调模块划分,强调如何系统的制造与构造,强调构件与结构。 11.建模的主要目的是什么?
建模的主要目的是理解系统与表达思想,而不是绘制图形,尽管绘制模型图形是建模的 必要手段。建模是“思维的过程”,模型反映的是“思维的结果”。因此衡量模型优劣的标准 首先是检查其是否清晰地表达了思想、表达了关于一个系统(被建模对象)的思想,其次才是 其表达方式的规范性和一致性问题。
12. 软件系统的构成关系 软件系统(设计) 模块的集合 + 结构 + 数据库 模块 程序类的集合 + 各程序类对象间函数调用关系的集合 (程序)类 程序变量集合 + 函数(子程序) 的集合 函数 完成一个具体功能的程序 变量 函数处理与保存的数据 对象/实例 程序类的一个执行实体 数据库 永久保存的数据表的集合 数据表 数据库的基本控制单位
13. 软件系统的实现过程 模块的实现:将由软件模型划分出的一个个模块转换成正确的程序代码。 模块测试:模块实现程序必须进行测试,以保证正确性。 系统的部署:将开发的模块安装、部署到拟应用的环境中,并与其所处的环境形成一有
机的整体,即将所有模块统一管理并使用统一的数据和流程等。 系统测试:重点是各模块间冲突检查及系统 Bug 的发现与纠正。 系统应用:包括装载用户的数据和过程,用户利用系统进行业务工作。用户依赖系统的
程度即是系统应用的程度。 14. 从实现层面看什么是一软件系统
一个软件系统的实现要有一个运行支撑环境(即结构框架)、一批以目录形式组织的文件 (即部署管理的内容) 、一套配置文件(记录了客户对系统所做的个性化配置参数)、一套功能 菜单(即系统对功能的组织)、若干个过程(即各个功能的次序关系)、一套权限控制数据(角色 /权限/用户等) 和一套数据(用户产生的由系统使用和管理的数据)等。
3-5
哈尔滨工业大学《计算机导论》课程复习提纲 任课教师:战德臣,聂兰顺
15. 三种软件环境 三种软件环境是指开发环境、测试环境和应用环境。 开发环境:是为程序员开发应用程序所建立的环境。程序员在此环境中可开发实现一个
个模块,并用自己建立的菜单、过程和数据进行模块运行正确性的检验。核心构成:基础设 施;结构框架(运行支撑环境);各种编程工具。关注点:模块及系统的实现,重点是模块的 实现及模块 Bug 的发现与纠正。
测试环境:是为系统的统一测试所建立的环境。测试员站在系统角度建立统一的菜单、 过程和数据,并部署程序员实现的模块以进行系统正确性的检验。核心构成:基础设施;结 构框架(运行支撑环境);测试用数据库、过程、权限控制数据;测试用菜单。关注点:系统 及系统的正确性,重点是各模块间冲突及系统 Bug 的发现与纠正。
应用环境:是为客户运行系统所建立的环境,需要为客户建立可进行正常业务工作的环 境。核心构成:基础设施;结构框架(运行支撑环境);正式用数据库、过程、权限控制数据; 正式用菜单。关注点:关注系统,更关注数据、过程及权限控制等与客户业务密切相关的内 容。
3-6
哈尔滨工业大学《计算机导论》课程复习提纲 任课教师:战德臣,聂兰顺
第 4 章 计算机科学与技术学科介绍
4.1 基本概念清单 1. 计算学科的五个分支学科
计算学科目前被分为计算机科学、计算机工程、软件工程、信息系统和信息技术五个分 支学科。
计算机科学侧重计算与计算系统相关的理论研究,计算机工程侧重用硬件实现计算系统 的技术研究,软件工程侧重以软件的开发、管理与应用为对象进行计算系统的技术研究,信 息系统则以信息的组织、管理与应用为对象进行信息工程研究,信息技术则侧重于信息处理 手段、及处理手段的选择、组合与集成技术研究。
2. 计算学科的三种形态/过程 计算学科的三种形态/过程是抽象形态、理论形态与设计形态。 抽象形态是指由具体事物中发现其本质性特征和方法的过程,是“理解区分命名
表达”,是“寻找相同形式,处理可变内容”的过程,是感性认识世界的手段。 理论形态是对规律进行严密化描述及论证的过程,通常由定义、公理、性质、定理和证
明等内容构成,是发现现实世界规律的手段。 设计形态是构建计算系统的过程,是技术、原理在计算系统中实现的过程,是构造计算
系统来改造世界的手段。 3. 抽象形态的结果与两种类型的抽象
简单而言,两种类型的抽象一是方法论层面的抽象,研究一般性的抽象方法;另一是方 法论应用层面的抽象,用一般性方法做指导进行具体任务的抽象。
或者如下叙述:一方面是建立对客观事物进行抽象描述的方法,另一方面是要采用现有 的抽象方法建立具体问题的概念模型,从而实现对客观世界的感性认识。
抽象的结果是关于系统要素的概念模型,通常以可视化非数学模型、形式化模型来表达。 也可以表达为数学模型,如果必要的话。 4. 典型的学科方法及特征
典型的学科方法有: 形式化方法、递归方法、结构化方法和面向对象方法。
形式化方法是一种严密化(算法类和系统类)问题求解的方法,其典型特征是符号化、抽 象化、逻辑严格化。
递归方法是一种典型的算法和系统设计方法,是计算学科核心的构造性方法的典型代 表,其典型特征是自身调用自身、高阶调用低阶来实现求解!
结构化方法是一种分析系统、设计系统的思维方法,其典型特征是以功能为中心,自顶 向下分解。
面向对象方法是另一种分析系统、设计系统的思维,其典型特征是以对象为中心,逐一 地独立地分析每一对象的各种特性。 5. 形式化方法
形式化方法是用符号化,基于数学思维,严密描述被研究对象的一种方法,是在对事物 描述形式化的基础上,通过研究事物的形式化变化规律来研究事物变化规律的全体方法的总 称,形式化方法得到的是形式系统。
4-1
哈尔滨工业大学《计算机导论》课程复习提纲 任课教师:战德臣,聂兰顺
形式化是将事物的内容和形式相分离,用事物的某种形式(符号)来表示事物,以便寻找 相同的形式,处理可变的内容。 6. 形式系统的四个组成部分
形式系统的四个组成部分是初始符号、形式规则、公理、变形规则(或称定理)。 初始符号:是无需定义的符号集; 形式规则:它规定一种程序,借以判定哪些符号串是本系统中的公式,哪些不是。 公理: 即在本系统的公式中确定不加推导就可以断定的公式集。
变形规则: 变形规则亦称演绎规则或推导规则。变形规则规定从已被断定的公式如何得 出新的被断定公式。被断定的公式又称为系统中的定理。
在以上 4 个组成部分中,前两个部分定义了一个形式语言,后两个部分在该形式语言上 定义了一个演绎结构。形式系统是由形式语言和定义于其上的演绎结构组成的。 7. 计算技术中与递归有关的概念
与递归有关的概念有:递归关系、递归数列、递归过程、递归算法、递归程序、递归方 法等。
递归关系指的是一个数列的若干连续项之间的关系; 递归数列指的是由递归关系所确定的数列; 递归过程指的是调用自身过程的过程; 递归算法指的是包含递归过程的算法; 递归程序指的是直接或间接调用自身程序的程序; 递归方法也称递推法,是一种在有限步骤内,根据特定的法则或公式,对一个或多个前
面的元素进行运算得到后续元素,以确定一系列元素如数或函数的方法。 8.结构化方法与面向对象方法
结构化方法是计算学科的一种典型的分析系统、设计系统的思维方法,它采用了系统科 学的思想方法,依据层次分解思维,自顶向下地分析和设计系统。
面向对象方法是计算学科的一种典型的分析系统、设计系统的思维方法,它以对象为中 心,逐一地独立地分析或设计系统每一对象的各种特性,达到系统分析与设计的目的。 9. 对象、类、消息、事件
对象是现实世界中的一个个个体,具有以下特性:有唯一的标识,有自己的状态和数据, 对象自己执行自身的工作而无需其他对象干预,对象可为其他对象服务,或接受其他对象服 务,对象之间交互的唯一手段是消息。
消息是对象之间传递的内容,如指示、打听、请求等,本质是数据;
事件是一种能够激活对象功能的特殊的消息。当发生事件后将给所涉及对象发送一个消 息,对象便可执行相应的功能。
类是设计形态的概念,对象是运行形态的概念,一个类对应了形式上相同但内容不同的 若干对象。例如“学生”是一个类,它对应了“张三”、“李四”、“王五”等所有的是学生的对象。 类是一种“型”,而对象则是该型的一个个“值”,或者说,对象是类的一个个实例(Instance)。
4.2 基本思想与基本过程 1. 计算学科的各分支学科的研究内容
“计算机科学”是研究计算机和可计算系统的理论方面的学科。它主要研究(1)为硬件、 软件、网络方面的计算问题求解提供有效的解决方式和方法;(2)提出新的问题求解策略、 新的问题求解算法,在硬件、软件、互联网方面;(3)发现并设计使用计算机的新方式和新
4-2
哈尔滨工业大学《计算机导论》课程复习提纲 任课教师:战德臣,聂兰顺
方法, 尤其是互联网方面。 “计算机工程”是研究计算机的设计、建造和应用的偏工程性的学科。它主要研究(1)
设计和建造计算机及基于计算机的系统,涉及硬件、软件、通讯及其之间的接口;(2)构建 和建造计算机系统、通讯系统和嵌入式系统。
“软件工程”是研究软件的开发、测试、运行和维护的偏工程性的学科。它以“软件” 为研究对象,“软件”的无形性和软件操作的非连续性使得大型软件系统在开发、运行和维 护方面都有不同于其他有形产品的问题需要解决,例如如何准确地理解客户对软件的期望? (需求工程);如何开发软件使得能满足客户不断变化的需求? (软件复用与演化);如何检验 软件是一个可靠的、安全的、无 Bug、可自我修复的软件? (软件的正确性可信性)等。
“信息系统”是以信息的组织、管理与应用为对象进行信息工程研究,研究信息技术解 决方案与企业业务整合,为企业提供信息服务的,偏工程性与管理性的学科。
“信息技术”是研究信息处理手段、及处理手段的选择、组合与集成技术,通常而言研 究软件硬件网络产品的选型、安装、客户化、维护、集成等技术,偏应用性的学科。 2. 计算学科各分支学科的典型特点,其对人才要求的知识结构特征
典型特点:计算机科学偏重基础理论性的研究;计算机工程和软件工程均偏重工程性的 研究,前者偏重硬件技术,而后者偏重软件技术;信息系统和信息技术则均偏重于应用性的 研究,前者偏重信息,而后者偏重信息处理手段,二者又被广义的称为信息技术。
知识结构特征: 首先他们都要求有很好的计算思维基础和问题求解基础。在此基础上, 计算机科学强调数学理论基础和算法分析基础; 计算机工程强调系统工程基础和计算机硬件基础; 软件工程强调系统工程基础和计算机软件基础; 信息系统强调信息技术基础和业务基础,强调计算与业务相结合的复合型知识结构; 信息技术强调信息技术基础,强调通用性知识与典型产品相结合的专门型知识结构;
3. 抽象、理论与设计之间的关系 设计是指构造计算系统来改造世界的手段,是工程的主要内容,只有设计才能造福于人
类(设计的价值)。理论是发现世界规律的手段,理论,如果不能指导设计,则是反映不出其 价值的;设计,如果没有理论指导,则设计的严密性、可靠性、正确性是没有保证的(理论 的价值);抽象是感性认识世界的手段,理论和设计的前提都需要抽象,没有抽象二者都是 没有办法达成目标的(抽象的价值)。
区分并命名现实世界问题的每一个形式要素是抽象。理论指导下的抽象将更为严密,而 在很好的抽象基础上的理论是认识深入化的标志。理论的目的是数学化逻辑严密化各种概念 及规律的描述,抽象是理论研究的前提和保证。设计的目的是设计和实现计算系统。先抽象 再设计,深入认识形式系统,则可在更高层面实现计算系统。理论支持下的设计可使设计具 有正确性、完备性等特性。
4. 递归和迭代的本质区别 递归和迭代都是构造方法的典型案例。递归是自身调用自身、高阶调用低阶的方法;而
迭代则是通过循环来实现由低阶到高阶的运算。迭代不调用自身程序,是通过循环来实现的。 迭代程序都可以转换为与它等价的递归程序,反之,则不然。递归程序的实现要比迭代程序 的实现耗费更多的时间和空间,因此能用迭代程序的地方尽量少用递归程序实现。 5. 结构化方法的思维基础
系统论基础:系统是有目标的(作用性);系统是有边界的(外特性);系统是有组成要素 4-3
哈尔滨工业大学《计算机导论》课程复习提纲 任课教师:战德臣,聂兰顺
的且各组成要素之间是有关联的(内特性)。组成要素很多,可以仅描述与系统相关的组成要 素即可(复杂度)。
控制论基础:系统被区分为物理系统和控制系统。控制系统通常是计算系统,它接受来 自物理系统的数据及状态,进行决策并下达指令控制物理系统的运行(控制与被控)。
分解论基础:系统是复杂的,化解复杂为简单的办法就是分解,将系统分解为不同的部 分,各个击破。分解、再分解,直到清楚为止。 6.结构化方法的基本思想
结构化方法的基本思想是系统的外特性和内特性分离描述,首先刻画外特性,即系统的 边界和环境。外特性刻画清楚后,再刻画内特性,即系统的构成。
外特性的刻画方法如下,以功能或活动为中心,刻画功能的输入、输出、目标与控制和 支撑等;输入:从外界传到系统中的信息;输出:从系统中传到外界的信息;功能或活动: 被认为是将输入转换为输出的一种变换过程。一般,宏观层面称功能,而微观层面称活动。 目标与控制:功能应达到的目标,或者说,功能是在目标与控制的控制下执行。支撑:执行 功能或活动所需要的必要的支撑条件。外特性刻画中将系统内部构成封装起来,以屏蔽内部 细节对外特性描述的干扰。
内特性以单独的图来描述,描述其功能分解、每一子功能在该功能内的外特性及各个子 功能关系的描述。功能分解:上级功能被分解为若干个下级功能(被称为子功能),从逻辑上 这些子功能的集合应等价于该上级功能。子功能外特性的描述:描述每一个子功能的外特性。 子功能关系的描述:建立子功能之间的关系。可以认为:功能(内部构成)=子功能的集合+ 子功能外特性集合+子功能之间关系的集合。
如此自顶向下,逐级分解,便可由粗至细将一个复杂系统刻画清楚。 7. 结构化方法的基本原则
抽象原则:抽象原则是一切系统科学方法都必须遵循的基本原则,它注重把握系统的本 质内容而忽略与系统当前目标无关的内容,即:既能够理解细节,同时又能从细节中跳出来。
模型化原则:抽象的结果需要通过模型来表达,尽可能采用非数学化模型(图示化模型) 和形式化模型来表达(后者要比前者严格) 。必要情况下,也可以数学化模型来表达。典型 的模型包括:
分解原则:分解原则是结构化方法中最基本的原则,它是一种先总体后局部的思想原则, 在构造信息系统模型时,它采用自顶向下分层解决的方法。
模块化原则:模块化是结构化方法最基本分解原则的具体应用,它主要出现在结构化设 计阶段中,其目标是将系统分解成具有特定功能的若干模块从而完成系统指定的各项功能。
等价性原则:上级功能和下级子功能在边界范围内的宏观意义上的等价性原则。 8.面向对象方法的基本思想
面向对象方法的基本思想: (1)确定系统的范围,识别出系统可能涉及的对象(类); (2)对每一个对象做如下的工作:识别该对象的所有状态;识别对象的状态转换及转换
条件和动作;识别该对象的所有可能的活动;识别该对象的数据存储与显示;识别该对象的 其他特性。
(3)对所有对象,按识别的内容建立相关的模型。 简单而言,以对象为中心, 逐一地独立地分析或设计每一对象的各种特性。
4-4
哈尔滨工业大学《计算机导论》课程复习提纲 任课教师:战德臣,聂兰顺
6.1 基本概念清单 1. Linux 的诞生
第 6 章 Linux 操作系统的使用
Linux 诞生于 1991 年,是一种类 UNIX 操作系统,Linux 诞生的主要基础有 UNIX、 MINIX、GUN、POSIX 和 Internet。 2. Linux 发行版
Linux 免费的内核,以及用户或厂商自行搭配的其他应用程序,构成了“Linux Distribution”(内核+应用软件包),Linux 发行版有很多种,包括 Ubuntu、openSUSE、Debian 等。 3. Linux 的特点
开放性、多用户、多任务、良好的用户界面、设备独立性、丰富的网络功能、可靠地系
统安全、良好的可移植性。
4. 开源软件 开放源代码(Open Source)软件:在开放源代码许可证下发布的软件,保障软件用户
自由使用及接触源代码的权利,也保障了用户自行修改、复制以及再分发的权利。典型的软 件有 Eclipse、GNU Emacs、Apache、GCC 等。 5. Linux 需要掌握的基本命令
ls, date, cal, who, man, cat, head, tail, more, less, od, cp, mv, rm, ln, pwd, cd, mkdir, rmdir, find, useradd, usermod, userdel, passwd, groupadd, groupdel, gpasswd, id, su, groups, finger, chown, chgrp, chmod, vi, grep, tar, gzip, dpkg, apt-get install, apt-get update。 6. Linux 的基本目录及其内容
Linux 文件系统包括的目录有 bin, sbin, root, mnt, boot, lost+found, lib, dev, etc, var, usr, proc, initrd, tmp, home, opt。
具体内容参见讲义。 7. 在本科学习中能提供支撑的 GNU/Linux 软件
Linux, Gcc,gdb, Lex, YaCC, Eclipse, Apache, mySQL, Emacs, …。
6.2 基本思想与基本过程 1. Linux 的文件与存储管理
Unix/Linux 中,任何软硬件都被视为文件,文件是字节序列,分为常规文件、目录、设 备文件、符号链接文件、字符文件、套接字文件等。
Linux 文件没有“扩展名”的概念,文件的名称与类型无直接关系。
存储设备或存储设备的分区格式化为文件系统后,分为两部分,Block 用来存储数据, Inode 用来存储这些数据的信息,包括文件大小、属主、归属的用户组、读写权限等。操作 系统通过 inode 管理文件。
可以对文件创造硬链接和软链接(符号链接)。
文件系统采用分层树状目录结构管理文件,有根目录、home 目录和工作目录的概念, 有绝对路径和相对路径的概念。
6-1
哈尔滨工业大学《计算机导论》课程复习提纲 任课教师:战德臣,聂兰顺
2. Linux 的用户管理 Linux 是典型的多用户、多任务操作系统,用户在系统中分角色,不同角色具有不同权
限,能够完成不同的任务,典型的角色包括 root、虚拟用户和普通真实用户。 Linux 使用用户和用户组的概念管理用户和角色,用户与用户组之间的关系可以是一对
一、一对多、多对一等。 用户可以通过 su 命令改变角色。
3. Linux 的文件/目录的归属及权限控制 文件/目录的属性记录/控制着文件/目录的归属和权限,归属主要包括归属于哪个用户和
归属于哪个用户组两个方面,权限通过 9 个权限控制位定义,权限分为读、写、执行三种, 权限分为三部分,即文件属主、所属用户组和其他用户的权限。 4. Linux 下的 Shell 编程
Shell 是介于用户和 Linux 操作系统的内核(kernel)间的一个接口程序,能够作为解释 性的程序设计语言,支持 Shell 编程。
Shell 编程的基本过程是:(1) 编辑一个利用 Linux 命令和 Shell 脚本写成的程序文件; (2) 设置该文件的可执行权限;(3) 执行 Shell 程序。 5. Linux 的 I/O 重定向
Linux 命令执行时的 I/O(输入/输出)为,调用标准输出(stdout)进程–屏幕用于显示信 息,调用标准错误(stderr)进程–屏幕显示任何错误信息,调用标准输入(stdin) –键盘得到用 户输入的信息。
I/O 重定向是指更改系统的输入/输出,如将命令的输出重定向到一个文件,则命令的执 行结果将写入某一文件中而不是显示到屏幕上。
6-2
哈尔滨工业大学《计算机导论》课程复习提纲
任课教师:战德臣,聂兰顺
第 7 章 引论
7.1 基本概念清单 1.局域网、广域网、互联网、Internet 2.集线器、调制解调器和路由器 3.网络协议、OSI 七层协议、TCP/IP 协议 4. IP 地址,域名,DNS,URL,HTTP,WWW,HTTP,HTML 5.搜索引擎,网页,超链接与超文本,网站
6. 常用排版术语 7.典型的 Internet 服务:Ftp, Telnet, Email, WWW 8.计算机病毒 (概念的具体定义可参阅讲义)
7.2 基本思想与基本过程 1. 科技文章的编排要求,科技讲演稿的制作要求 2. 文字的相关格式有哪些;段落的相关格式有哪些;版面的相关格式有哪些;什么情况下 使用什么样的格式。 3. 局域网组建方法及设施;广域网组建方法及设施;互联网组建方法及设施 4. 连接到 Internet 的方法和过程,发布信息的方法和过程,获取信息的方法和过程 5. 常见的计算机安全威胁;病毒可能攻击的计算机部位及其危害 6. 常见的计算机与信息安全防护手段 7. 计算机行业应该遵守的职业道德 8. HTML 语言和 XML 语言的异同点及作用 9.通用搜索引擎的基本功能 (基本思想与基本过程的解释可参阅讲义)
7-1
