《计算机导论》 总复习提纲

PAGEPAGEPAGE22009级《计算机导论》课程复习提纲2010.1.6第一章计算机的基础知识1、了解计算机产生的标志性事件，并说明计算机发展过程中经历了哪几个阶段及其主要特点。（讲义01P5~8）2、了解计算机科学与技术学科的知识体系与主要研究方向。（讲义01P17~32）3、掌握计算机软件系统的层次结构。（讲义01P56）第二章走进计算机1、系统软件包括哪些？（PPT02P6）2、什么是操作系统？其主要功能是什么？（PPT02P7~8）3、操作系统如何管理外存上的程序与数据？（PPT02P17~19）操作系统采用文件（Files）和目录（Directories，俗称文件夹）来组织、存储和管理外存中的信息。操作系统按树（tree）型结构来组织目录与文件，以达到分类存储和快速定位的目的。4、如何描述某个文件的路径？5、BIOS是指什么？其主要作用是什么？（PPT02P22~23）6、了解邮件读取协议POP和简单邮件发送协议SMTP。试简要回答电子邮件的发送和接收过程。（PPT02P34~40）第三章媒体集成与PowerPoint1、什么叫媒体？什么是多媒体？（PPT03P4~5）一般把信息的表示，储存和传输称为媒体。多媒体技术是利用计算机对文字、图像、图形、动画、音频、视频等多种信息进行综合处理、建立逻辑关系和人机交互作用的产物。2、了解矢量图和位图的区别是什么？他们最简单的区别就是:失量图可以无限放大.而且不会失真.而位图而不能位图图象能够制作出颜色和色调变化丰富的图像，可以逼真地表现出自然界的景观。同时也很容易在不同软件之间交换文件。其缺点是它无法制作真正的三维图像，并且图像在缩放和旋转时会产生失真现象，同时文件较大，对内存和硬盘空间容量的需求也较高。位图图象广泛应用在照片和绘图图像中。位图图象是由像素组成的，图像放大后会失真。矢量图是以数学描述的方式来记录图像内容，它的内容民线条和色块为主，其文件所占的容量较小，也可以很容易地进行放大、缩小和旋转等操作，并且不会失真，可以制作三维图像。其缺点是:不易制作色调丰富或色彩变化太多的图像，失量图像与分辨率无关，将它缩放到任意大小和以任意分辨率在输出设备上打印出来，都不会遗漏细节和影响清晰度。它是文字和粗放图形的最佳选择。如徽标、美工插图、工程绘图。3、熟悉图片、音频、视频文件的常用格式有哪些？图片BMPJPEGJPGPSDAIGIFPNG

视频RMRMVBAVIMPEG3GPMP4

音频MP3WAVAACAC3MIDICDA4、媒体的数字化过程？多媒体数据压缩的必要性与可能性？（PPT03P18~22）数字化过程第一，空间采样第二，量化第三，编码必要性以数字图像为例，按VGA标准的屏幕分辨率（640×480）计算，每帧画面由307,200个像素点组成。如果用真彩色表示，每个像素点的色彩使用24位二进制数字表示，采用每秒25帧画面的PAL制式播放。实时播放每秒钟需传输的数据量为307,200×24×25＝184.32Mbps可能性数据冗余视觉特性5、超文本和超媒体的概念？（PPT03P24）超文本（hypertext）是一种信息组织与管理技术，它采用非线性网状结构组织块状信息。把多媒体信息引入了超文本，产生了超媒体(hypermedia)。WWW(WorldWideWeb)是超媒体系统的典型代表。在这个超媒体信息空间，用户可以通过专门的浏览器集进行访问。第四章数据处理1、Excel中相对引用、绝对引用与混合引用的表示方法？（讲义02P33~34）相对引用直接引用单元格区域地址，不需要加“$”符号。绝对引用绝对引用的单元格地址、列标和行号前面都带有“$”符号混合引用两种情况，一是列标前有“$”符号，而行号前不带“$”符号，则列绝对，行相对反之，列相对，行相对2、什么是DB、DBMS和DBS？（PPT04P16~19）数据库（database,DB）存储在计算机内、有组织、可共享的数据集合由DBMS统一管理，多用户共享数据库管理系统（databasemanagementsystem,DBMS)位于用户和操作系统之间的一层数据管理软件，是DBS的核心组成部分。系统软件，对数据库进行统一管理和控制主要功能：数据库的定义功能数据库的操纵功能（DML）数据库的建立和维护功能数据库的保护功能数据库的存储管理数据库运行控制功能数据库系统（databasesystem,DBS)带有数据库的整个计算机系统，包括硬件、软件、数据、人员硬件hardware大内存，放得下OS，DBMS核心，系统缓冲区，用户工作区等大容量、直接存取的外存设备，作数据备份的磁带CPU处理器与内存软件softwareOS，DBMS，高级语言编译系统及其与数据库的接口，应用开发工具，应用系统数据data目标数据：数据本身描述数据：对数据的说明信息用户最终用户(naiveusers)通过应用系统的用户接口（菜单等）使用数据库应用程序员(applicationprogrammers)基于外模式来编写应用程序系统分析员(systemanalysts)负责应用系统的需求分析和规范定义，确定系统的软硬件配置，参与数据库模式设计数据库管理员DBA(databaseadministrator)负责数据库的全面管理和控制3、了解数据挖掘与决策支持的含义。（PPT04P33~35）日常业务的大量运行数据常常不能直接供决策使用，数据使用之前需要经过仔细整理和深入分析，才能从中得到真正有用的数据。数据仓库（DataWarehouse）数据仓库（DataWarehouse）是一个面向主题的（SubjectOriented）、集成的（Integrate）、相对稳定的（Non-Volatile）、反映历史变化（TimeVariant）的数据集合，用于支持管理决策。首先，数据仓库用于支持决策，面向分析型数据处理，它不同于企业现有的操作型数据库；其次，数据仓库是对多个异构的数据源有效集成，集成后按照主题进行了重组，并包含历史数据，而且存放在数据仓库中的数据一般不再修改。数据挖掘与决策支持技术把“日常业务的大量运行数据”去粗取精、分析统计，变换为相对稳定且有规律的信息，供决策之用。第五章计算机体系结构与计算机网络基础1、什么是计算机？（PPT05P3~4）2、在计算机中如何表示数据、符号、英文字母和汉字？（讲义01P48~53）3、如何进行数制之间的转换？原码、补码和反码的表示方法？（PPT05P15~18）4、图灵机包括哪几部分，其工作原理是什么？（PPT05P23~39）5、简要说明冯·诺依曼体系结构计算机的设计思想。（PPT05P45~48）6、什么叫带宽（bandwidth）？什么叫宽带（Wideband）?（PPT05P51）7、电路交换的特点是什么？为什么在计算机网络中要采用分组交换？掌握分组交换的原理。（PPT05P63~73）8、开放系统互连参考模型OSI/RM共包括哪七层？TCP/IP体系结构模型共包括哪几层？（PPT05P82~86）9、什么是计算机网络的体系结构？（PPT05P87）10、五层协议的体系结构由哪几层组成？以两台计算机之间互相传送数据为例，理解五层协议的体系结构特点。（PPT05P94~113）11、TCP协议如何保证可靠性？（什么是流量控制技术？什么是差错控制技术？）（PPT05P128~129）12、为什么有时从因特网下载文件特别慢？（PPT05P131）13、什么是MAC地址？如何获取MAC地址？（PPT05P133~134）14、IP地址的表示方法？共分为几类IP地址，他们之间如何进行区分？（PPT09P136~140）（讲义01P138）15、计算机网络调试常用的命令有哪些？（实验六）16、为什么要采用域名？什么是域名系统DNS？（PPT05P143~144）17、试论述从域名地址到IP地址的映射过程（PPT05P150）18、万维网的工作原理是什么？（PPT05P154~157）第六章信息技术与信息安全*1、了解什么是信息？信息的基本特征是什么？（PPT06P3~5）2、了解什么是信息技术？信息技术主要包括哪些内容？（PPT06P6）3、图示说明计算机网络通信面临的四种威胁。（PPT06P11~12）注：所有PPT中出现的专业英语词汇均为要求掌握的内容。一、单选题（共20道试题，共40分。）V1.在计算机中通常是以()为单位传送信息的A.字B.字节C.位D.字块满分：2分2.计算机的主机指的是()。A.计算机的主机箱B.CPU和内存储器C.运算器和控制器D.运算器和输入/输出设备满分：2分3.可以更改“开始”菜单中（）的图标。A.程序和设置B.文档和设置C.查找D.程序和文档满分：2分4.CAM的含义是()。A.计算机辅助教育B.计算机辅助制造C.计算机辅助设计D.计算机辅助管理满分：2分5.使用菜单进行文件或文件夹的移动，需要经过（）。A.选择和剪切B.剪切和粘贴C.选择和粘贴D.选择、剪切和粘贴满分：2分6.ISO/OSI参考模型七层协议中第一层是()A.物理层B.数据链路层C.网络层D.传输层满分：2分7.UPS是指()。A.大功率稳压电源B.不间断电源C.用户处理系统D.硬盘中的信息满分：2分8.2、在Windows中，选中某一菜单后，其菜单项前有“√”符号，这表示()A.可单选的B.可复选的C.不可选的D.不起作用的满分：2分9.CPU执行计算机指令时使用()进行运算A.二进制B.八进制C.十进制D.十六进制满分：2分10.关于Windows2000，以下四项描述中，不正确的描述是（）。A.在“控制面板”中双击“鼠标”图标，在弹出的“鼠标属性”对话框中可以设置鼠标的左右手使用方式B.在“控制面板”中双击“鼠标”图标，在弹出的“属性”对话框中可以设置鼠标单击的速度C.在“控制面板”中双击“鼠标”图标，在弹出的“属性”对话框中可以设置鼠标双击的速度D.在“控制面板”中双击“鼠标”图标，在弹出的“属性”对话框中可以设置鼠标光标的形状满分：2分11.386微型机的CPU为Intel80386，它是()微机A.8位B.16位C.32位D.64位满分：2分12.逻辑运算的主要特点是()。A.没有进位B.只有两个值C.与算术运算相同D.按位运算满分：2分13.电子计算机能够自动地按照人们的意图进行工作的最基本思想是程序存储，这个思想是由()提出来的。A.布尔B.图灵C.冯.诺依曼D.爱因斯坦满分：2分14.1片1.44MB的软盘，可以存储大约140万个()。A.ASCⅡ字符B.中文字符C.磁盘文件D.子目录满分：2分15.计算机的主机指的是()。A.计算机的主机箱B.CPU和内存储器C.运算器和控制器D.运算器和输入/输出设备满分：2分16.人们常说486微机、586微机，其中的数字指的是()。A.硬盘的型号B.软盘的型号C.CPU的型号D.CPU的处理速度满分：2分17.在WindowsXP中有两个管理系统资源的程序组，它们是()。A."我的电脑"和"控制面板B."资源管理器"和"控制面板"C."我的电脑"和"资源管理器"D."控制面板"和"开始"菜单满分：2分18.微型机在使用过程中突然断电,则()中的信息将全部丢失。A.RAMB.ROMC.CD-ROMD.磁盘满分：2分19.WINDOWS环境下运行MS-D0S方式，有（）两种方法A.行编辑和全屏幕B.行编辑和窗口C.窗口和菜单D.全屏幕和窗口满分：2分20.文字处理软件是一种()A.应用软件B.工具软件C.免费软件D.系统软件满分：2分二、多选题（共20道试题，共40分。）V1.以下是个人计算机常用的输出设备（）。A.打印机B.扫描仪C.键盘D.显示器满分：2分2.多媒体计算机的主要硬件必须包括（）。A.CD—ROMB.EPROMC.网卡D.音频卡和视频卡满分：2分3.关于计算机病毒的传染途径，下列说法是对的（）。A.通过软盘复制B.通过交流软件C.通过共同存放软盘D.通过借用他人软盘满分：2分4.在资源管理器中，查找文件的方式有（）。A.按照建立文件的操作者姓名B.按需要查找的文件或文件夹的名称C.按照文件最后的修改日期D.按高级方式查找（可以给出需要查找文件的某些特征、状况）满分：2分5.某台计算机有病毒活动，指的是（）。A.该计算机的硬盘系统中有病毒B.该计算机的内存中有病毒程序在运行C.该计算机的软盘驱动器中插有被病毒感染的软盘D.该计算机正在执行某项任务，病毒已经进入内存满分：2分6.在Excel电子表格中，可对（）进行计算。A.数值B.文本C.时间D.日期满分：2分7.下面说法中，正确的是（）。A.一个完整的计算机系统由硬件系统和软件系统组成B.计算机区别于其它计算工具的最主要的特点是能存储程序和数据C.电源关闭后，ROM中的信息会丢失D.16位字长计算机能处理的最大数是16位十进制数5满分：2分8.如果输入编码以后没有预选汉字出现应当按______键。A.CtrlB.EnterC.AltD.空格满分：2分9.以下关于WindowsXP的说法是错误的（）。A.WindowsXP是个人计算机不可缺少的组成部分B.WindowsXP是一个32位计算机操作系统C.WindowsXP是一个游戏软件D.在WindowsXP系统中，可以在打印资料的同时玩游戏满分：2分10.关于机算机网络，以下说法哪个正确？（）A.网络传输介质分为有线和无线，有线介质主要有同轴电缆、红外线、光缆。B.网络节点间进行通信所遵从的规则称为协议。C.局域网中只能有一个服务器，PC机在安装系统软件后也可作为服务器。D.无论是服务器或客户机，它们组成局域网时，均需各自安装一块网卡。满分：2分11.显示和隐藏工具栏的操作是（）。A.视图菜单栏中选择“工具”子菜单，可以显示或隐藏所需工具栏B.隐藏[浮动工具栏]，可单击它的关闭按钮C.迅速隐藏工具栏可以用鼠标右键击此工具栏D.没有列在快捷菜单中的工具栏必须通过[工具]菜单的[自定义]命令来添加满分：2分12.在传统方式下，将高级语言源程序送入计算机后，必须使用系统软件（），使它生成可执行程序。A.编译程序B.目标程序C.连接程序D.汇编程序满分：2分13.下列各种数制的数中，数值大小相同的数是（）。A.101110BB.54OC.44DD.2AH满分：2分14.下列各种数制的数中，数值大小相同的数是（）。A.101110BB.54OC.44DD.2AH满分：2分15.下列（）是扫描输入汉字所必须配备的。A.扫描仪B.上好的白纸C.识别软件D.清晰的文字材料满分：2分16.有关计算机外部设备的知识，（）是正确的。A.喷墨打印机是击打式打印机B.键盘和鼠标器都是输入设备，它们的功能相同。C.显示系统包括显示器和显示适配器D.光盘驱动器的主要性能指标是传输速度和纠错性能。满分：2分17.下列对第一台电子计算机ENIAC的叙述中，（）是错误的。A.它的主要元件是电子管B.它的主要工作原理是存储程序和程序控制C.它是1946年在美国发明的D.它主要是数据处理满分：2分18.对文件改名，哪些说法是正确的？（）A.文件夹不能改名，只可对文件改名B.只读文件不可以改名C.文件改名后，对文件内容没有任何影响D.MS-DOS中建立的文件在Windows98中不能改名满分：2分19.某台计算机有病毒活动，指的是（）。A.该计算机的硬盘系统中有病毒B.该计算机的内存中有病毒程序在运行C.该计算机的软盘驱动器中插有被病毒感染的软盘D.该计算机正在执行某项任务，病毒已经进入内存满分：2分20.WindowsXP的桌面上一般包含有下列元素（）。A.开始按钮B.显示器屏幕C.快捷图标D.任务栏满分：2分三、判断题（共10道试题，共20分。）V1.段落"左缩进"的功能是使文本每个自然段起始位置空两个字。()A.错误B.正确满分：2分2.磁盘必须格式化后才能使用,凡是在一种计算机格式化过的磁盘,可在任何类型的计算机上使用。A.错误B.正确满分：2分3.能够同时进行数据双向发送的通信方式称为全双工通信A.错误B.正确满分：2分4.窗口和对话框中都有可供用户选择的菜单栏。A.错误B.正确满分：2分5.指令是计算机用以控制各部件协调动作的命令。A.错误B.正确满分：2分6.使用"主控文档"时，必须一一打开，即可打印所有子文档。()A.错误B.正确满分：2分7.工具栏中的"表格与边框"和格式中的"边框与底纹"功能完全相同。A.错误B.正确满分：2分8.Word97/2000只能将文本转换成表格,但不可以将表格转换成文本。()A.错误B.正确满分：2分9.发送和接收电子邮件时，需要SMTP和POP3邮件服务器。()A.错误B.正确满分：2分10.数据仓库不是一个新的平台，仍然使用传统的数据库管理系统，而是一个新的概念。A.错误B.正确满分：2分《计算机导论》复习纲要2010/6/2108:52第1章绪论1、第一台计算机；2、计算机发展的五个阶段；第一代（1945~1957）：电子管计算机（VacuumTubes）第二代（1958~1963）：晶体管计算机（Transistor）第三代（1964~1969）：小规模集成电路计算机IntegratedCircuits第四代（1970~1990）：以微处理器（Microprocessors）为标志的大规模/超大规模集成电路（LSI/VLSI）计算机（Large-scaleIntegratedCircuits）第五代（1991~目前）：以互联网（Internet）为标志的信息系统3、计算学科的定义计算学科是对描述和变换信息的算法过程，包括对其理论、分析、设计、效率、实现和应用等进行的系统研究。4、计算学科的根本问题计算学科的根本问题是：什么能被（有效地）自动进行。计算学科所有分支领域的根本任务就是进行计算，其实质就是字符串的变换。5、计算学科的5个分支学科计算机科学（ComputerScience，简称CS）信息系统（InformationSystem，简称IS）软件工程（SoftwareEngineering，简称SE）计算机工程（ComputerEngineering，简称CE）信息技术（InformationTechnology，简称IT）6、学科知识体计算机科学知识体由以下3个层次构成：（1）最高层是分支领域（area），它代表一个特定的学科子领域。（2）分支领域之下又分为更小的知识单元（unit），它代表该领域中的主题模块。（3）知识单元又被细分为众多的知识点（topic），这些知识点构成了知识体结构的最底层。7、计算机科学二维定义矩阵三个过程主领域抽象理论设计离散结构(DiscreteStructures)

程序设计基础(ProgrammingFundamentals)

算法和复杂性(Algorithms&Complexity)

计算机结构与组织(Architecture&Organization)

操作系统(OperatingSystems)

网络计算(NetworkComputing)

程序设计语言(ProgrammingLanguages)

人-机交互(Human-ComputerInteraction)

图形学与可视计算(Graphics&VisualComputing)

智能系统(IntelligentSystems)

信息管理(InformationManagement)

软件工程(SoftwareEngineering)

社会和职业问题(Social&ProfessionalIssues)

科学计算(ComputationalScience)

计算机科学二维定义矩阵是学科概念的认知模型。“纵向”关系，即计算机科学的研究领域。这些内容蕴含在学科3个过程中，并将学科各分支领域结合成一个完整的体系，而不是互不相关的领域。“横向”关系，即抽象、理论和设计3个过程的关系，是定义矩阵中最为重要的内容。它反映的是，人们在计算领域的认识规律，即是从感性认识（抽象）到理性认识（理论），再由理性认识（理论）回到实践（设计）的过程。“横向”关系还蕴含着学科中的基本问题。抽象、理论和设计3个过程（1）理论源于数学。应用数学家们认为科学的进展都是建立在数学基础之上。它的研究内容表现在两个方面：一方面是建立完整的理论体系，另一方面是在现有理论的指导下，建立具体问题的数学模型，从而实现对客观世界的理性认识。（2）抽象源于现实世界。抽象建模是自然科学的根本。（3）设计源于工程。设计是工程的根本。8、摩尔定律和“贝尔定律”在体系结构方面，有所谓“摩尔定律”（Moore’sLaw）和“贝尔定律”（Bell’sLaw）。前者断定微处理器的速度会每18个月提升一倍，而后者则认为如果保持计算能力不变，微处理器的价格和体积每18个月缩减一倍。第2章计算学科的基本问题什么是科学问题？科学问题是指一定时代的科学认识主体，在已完成的科学知识和科学实践的基础上，提出的需要解决且有可能解决的问题。它包含一定的求解目标和应答域，但尚无确定的答案。罗素悖论罗素悖论的表现形式：在对结果的观察中同时包含了观察者自身的行为，就会出现悖论。也就是说，理性无法回答关于自身的问题。希尔伯特纲领希尔伯特在数学基础的研究中提出了一个设想：将每一门数学的分支形式化，构成形式系统或形式理论，并在以此为对象的元理论即元数学中，证明每一个形式系统的相容性，从而导出全部数学的相容性。他企图寻找通用的形式逻辑系统，在该系统中，可以机械地判定任何给定命题的真伪，即该系统是完备的。任何系统的完备和一致性，可以由系统本身得到证明。希尔伯特这一设想，就是所谓的“希尔伯特纲领”。库尔特·哥德尔（K．Godel）提出的关于形式系统的“不完备性定理”中指出：形式系统不能穷尽全部数学命题，任何形式系统中都存在着该系统所不能判定其真伪的命题。没有一种公理系统可以导出数论中所有的真实命题，除非这种系统本身就有悖论。“哥德尔第一定理”，即哥德尔的“不完备性定理”：一个形式系统，如果是一致的（=相容的=无矛盾的），那么，就一定存在一个命题，这个命题在该系统中不能被证明，也不能被否证。换一种说法，这个命题在该系统中不能被证明，它的反命题在该系统中也不能被证明。“哥德尔第二定理”，即：任何一个被认为是一致的系统，它的一致性是不能在系统内部得到证明的。因此：形式系统是不完备的2.2哥尼斯堡七桥问题欧拉回路欧拉给出了哥尼斯堡七桥问题的证明，还用数学方法给出了三条判定规则(判定每座桥恰好走过一次,不一定回到原点,即对欧拉路径的判定)：（1）如果通奇数座桥的地方不止两个，满足要求的路线是找不到的。（2）如果只有两个地方通奇数座桥，可以从这两个地方之一出发，找到所要求的路线。（3）如果没有一个地方是通奇数座桥的，则无论从哪里出发，所要求的路线都能实现。根据第3点,可以得出,任一连通图存在欧拉回路的充分必要条件是所有顶点均有偶数度。哈密尔顿回路问题：在某个图G中，能不能找到这样的路径，即从一点出发不重复地走过所有的结点，最后又回到原出发点。这个问题也被称作周游世界问题。“哈密尔顿回路问题”与“欧拉回路问题”的不同点“哈密尔顿回路问题”是访问每个结点一次，而“欧拉回路问题”是访问每条边一次。对图G是否存在“欧拉回路”前面已给出充分必要条件，而对图G是否存在“哈密尔顿回路”至今仍未找到满足该问题的充分必要条件。计算问题可以分为可计算问题与不可计算问题。可计算问题：存在可解的算法。不可计算问题：不存在可解的算法。梵天塔问题说明了：理论上可以计算的问题，实际上并不一定能行，这属于算法复杂性方面的研究内容。算法复杂性中的难解性问题、P类问题和NP类问题算法复杂性包括算法的空间以及时间两方面的复杂性问题。在计算复杂性理论中，将所有可以在多项式时间内求解的问题称为P类问题，而将所有在多项式时间内可以验证的问题称为NP类问题。证比求易算法在计算机科学中，一般认为求解一个问题往往比较困难，但验证一个问题就比较简单。顺序算法和并行算法当将一个问题分解到多个处理器上解决时，由于算法中不可避免地存在必须串行执行的操作，从而大大地限制了并行计算机系统的加速能力。阿达尔定律（参看书本）一个不可计算问题：停机问题停机问题（HaltingProblem）是1936年图灵在其著名论文《论可计算数及其在判定问题上的应用》中提出，并用形式化方法给予证明的一个不可计算问题。停机问题引出了一个悖论——当一个程序无限循环时才会停机，并且当它停机时才会无限循环。什么是形式化方法：引入表达形式结构的符号语言,用符号与符号之间的联系表达命题或推理的形式结构。找零问题、背包问题与贪婪算法一类可以用启发式的贪婪算法来处理的典型问题。1.找零问题2.背包问题“哲学家共餐”问题与计算机资源管理计算机的资源分软件资源和硬件资源。硬件的资源主要指CPU、存储器以及输入和输出设备等；软件资源则是指存储在存储设备里面的各类文件。在计算机中，操作系统负责对计算机软硬资源进行控制和管理，要使计算机系统中的软硬件资源得到高效的使用，就会遇到由于资源共享而产生的问题。“哲学家共餐”问题哲学家进餐问题在计算机科学中所反映的问题实际上是程序并发执行时进程同步的问题：为了提高系统的处理能力和机器的利用率，并发程序被广泛地使用，因此必须彻底解决并发进程中的死锁和饥饿问题。并行处理并行计算时的完整性和同步性出现了问题。生产者－消费者问题一个生产者和一个消费者以及一个硬件资源。所谓消费者是指使用某一软硬件资源时的进程，而生产者是指提供（或释放）某一软硬件资源时的进程。一个重要的概念，即信号灯，它借用了火车信号系统中的信号灯来表示进程之间的互斥。生产者－消费者问题例如：大型数据库的共享、联网的售票系统、火车（航班）进出管理系统2.6“两军问题”与计算机网络计算机网络的定义计算机网络是将分散在不同地理位置上的，具有独立功能的多台计算机系统、各种终端设备、外部设备及其它附属设备，通过通信设备和通信线路连接起来，在网络协议和网络操作系统的管理和控制下，实现数据通信、资源共享和分布处理的系统。计算机网络发展的四个阶段计算机网络的发展，大致经历了四个阶段：1.远程终端联机阶段2.计算机网络阶段3.网络互连阶段4.信息高速公路（互联网）阶段计算机网络的功能资源共享、信息传输、提高系统的可靠性、分布处理，系统便于扩充。计算机网络的分类1.根据组成计算机网络的地理范围大小的不同，可分为广域网（WAN）、城域网（MAN）和局域网（LAN）三种。2.按网络的使用范围划分，可将计算机网络分为公用网和专用网。计算机网络的组成计算机网络由计算机通过通信线路互连而成，用户通过终端访问网络。从组成网络的设备或系统功能看，计算机网络由通信子网和资源子网构成。计算机网络的拓扑结构局域网中，构成网络服务器、工作站（又称节点）等设备通过电缆在物理上互连的几何构形，称为网络的拓扑结构。信道信道是指信号的传输通道，可分为物理信道和逻辑信道。其中，物理信道是指用来传递信号的一条物理通道，由传输介质和相关设备组成。按照传输方式分，信道可分为两类：点到点信道和广播信道。按使用的传输介质不同，信道可分为有线信道和无线信道。有线信道可以是架空明线、同轴电缆、光钎电缆及微波导管等信道。无线信道可以是微波信道、短波信道等。信道所能传送信号的频率宽度（即可传送信号的最高频率和最低频率之差）称为信道的带宽。网络协议计算机网络为了进行网络中的数据交换而建立的规则、标准或约定称为网络协议。网络协议规定了有关功能部件在通信过程中的操作，规定了传输数据的格式和有关的同步问题。网络的标准化组织为计算机网络制定标准的组织主要有三个：⑴国际标准化组织ISO⑵国际电子电器工程师协会IEEE⑶ARPA（AdvancedResearchProjectsAgency）参照计算机系统多层体系结构的原理，网络系统的通信结构也采用分层结构的方法。开放性系统互连（OSI）的参考模型局域网协议的标准IEEE802局域网的标准是由IEEE802制定的。IEEE802的标准只定义到最低两层，即物理层与数据链路层，较高层的功能则留给网络厂商决定。其中，数据链路层中又可分成两个子层：①逻辑连接控制LLC（LogicLinkControl）：让上层的网络在使用网络服务器时不必去考虑其下层是如何设置的。②介质存取控制MAC（MediumAccessControl）：定义多种不同的存取控制方法，以决定如何控制实际传送介质的使用。TCP/IP通信协议TCP/IP（TransmissionControlProtocol/InternetProtocol）是美国国防部早期为开发ARPANET的协议，提供连接不同厂家计算机主机的通信协议。TCP/IP主要有两个协议：①网际协议（IP）：制定所有在网络上流通的包标准，提供跨越多个网络的单一包传送服务。②传输控制协议（TCP）：在网际协议（IP）的上面，提供面向连接的可靠数据传输服务。确保所有送到某个系统的数据能正确无误的到达该系统。互联网软件的分层结构第3章3个学科形态信息系统模型信息系统是一个人造系统，它由人、计算机硬件、软件和数据资源组成，目的是及时和正确地收集、加工、存储、传递和提供决策所需的信息。与系统模型类似，信息系统包括输入、处理、输出和反馈4个部分。数据库系统数据库系统：DatabaseSystem构成数据库系统的有四个部分：数据、数据库管理系统、应用软件和用户DBMS，DatabaseManagerSystem，数据库管理系统DBMS由以下几个部分构成1．物理数据库2．数据库引擎3．数据库模式 DBMS支持的功能数据定义数据操纵：一般是指用来查询、添加、修改和删除数据库中数据数据控制：设置或者更改数据库用户或角色权限系统存储过程：目的在于能够方便地从系统表中查询信息，或完成与更新数据表相关的管理任务，包括系统管理任务DBMS还包括数据字典数据库体系结构和数据库模型数据库的体系结构——建立数据库的一个框架，这个框架用于解释数据库，也用于描述数据库的概念。而组织数据库中的数据，是数据库管理系统的核心，即DBMS所采用的数据库模型数据库的三级体系结构计算学科中理论、抽象和设计3种主要形态（过程）抽象形态包括以下4个步骤的内容：（1）形成假设；（2）建造模型并作出预测；（3）设计实验并收集数据；（4）对结果进行分析。理论形态包括以下4个步骤的内容：（1）表述研究对象的特征（定义和公理）；（2）假设对象之间的基本性质和对象之间可能存在的关系（定理）；（3）确定这些关系是否为真（证明）；（4）结论。设计形态包括以下4个步骤的内容：（1）需求分析；（2）建立规格说明；（3）设计并实现该系统；（4）对系统进行测试与分析。设计、抽象和理论3个形态针对具体的研究领域均起作用，在具体研究中，就是要在其理论的指导下，运用其抽象工具进行各种设计工作，最终的成果将是计算机的软硬件系统及其相关资料（如需求说明、规格说明和设计与实现方法说明等）。计算机语言的发展1.低级语言：机器语言汇编语言2.高级程序设计语言FORTRAN语言BASIC语言COBOL语言Pascal语言C语言语言处理程序1.汇编程序汇编语言翻译系统汇编语言翻译系统的主要功能是将用汇编语言书写的程序翻译成用二进制码0或1表示的等价的机器语言，形成计算机可以执行的机器指令代码。2.编译程序编译程序以高级程序设计语言书写的源程序作为输入，而以汇编语言或机器语言表示的目标程序作为输出。3.解释程序解释程序是按照源程序中的语句的动态顺序逐条翻译成机器代码并立即执行相应功能的处理系统。也称为高级程序设计语言解释系统由于解释程序它的方便性和交互性较好，早期一些高级语言采用这种方式，如BASIC、dBASE。但它的弱点是运行效率低，程序的运行依赖于开发环境，不能直接在操作系统下运行。自然语言自然语言是某一社会发展中形成的一种民族语言。例如，汉语、英语、法语和俄语等。其最基本、最普遍的形式是文字，文字是人类最普遍使用的自然语言符号系统。自然语言符号系统的基本特征：歧义性、不够严格和不够统一的语法结构。高级语言的歧义性问题高级程序设计语言也有语义的歧义性问题，但是高级程序设计语言存在较少的歧义性。形式语言人们在自然语言符号系统的基础上，逐步建立起了人工语言符号系统（也称科学语言系统），即各学科的专门科学术语（符号），使语言符号保持其单一性、无歧义性和明确性。人工语言符号系统发展的第二阶段叫形式化语言，简称形式语言。图灵机图灵的观点及结论：凡是能用算法方法解决的问题，一定能用图灵机解决；凡是图灵机解决不了的问题，任何算法也解决不了。与图灵机等价的计算模型：递归函数、λ-演算、POST规范系统从可计算理论可知每一个原始递归函数都是图灵机可计算的。冯•诺依曼型计算机：从原来对程序和数据的严格区别到一样看待，这个观念上的转变是计算机史上的一场革命，它反映的正是计算的本质，即符号串的变换。按照冯▪诺依曼原理构造的计算机又称冯▪诺依曼计算机，其体系结构称为冯▪诺依曼结构。冯▪诺依曼计算机的基本工作原理是存储程序和程序控制，其特点如下：将计算过程描述为由多条指令按一定顺序组成的程序，并放入存储器保存。指令按其在存储器中存放的顺序执行；控制器控制整个程序和数据的存取以及程序的执行；冯·诺依曼计算机的体系结构冯·诺依曼计算机的体系结构，即存储程序式计算机的体系结构，是将程序与数据一样看待，对程序像数据那样进行适当的编码，然后与数据一起共同存放在存储器中。这样，计算机就可以通过改变存储器中的内容，对数据进行操作。(1)计算机由运算器、控制器、存储器、输入设备和输出设备5大部分组成。控制器和运算器是其核心。(2)按存储程序原理进行工作。数据和程序以二进制代码形式不加区别地存放在存储器中，存储器是按线性编址的唯一结构进行地址访问，每个单元的位数是固定的。(3)机器以运算器为中心，输入输出设备与存储器间的数据传送都经过运算器。通过执行指令直接发出控制信号控制计算机的操作。(4)控制器根据存放在存储器中的指令序列（程序）进行工作，并由一个程序计数器控制指令的执行。(5)指令由操作码和地址码组成。指令同数据一样可以送到运算器进行运算，由指令组成的程序是可以修改的。冯·诺依曼型计算机体系结构图如下所示：输入设备和输出设备作用：是将信息输入计算机和输出计算机。存储器存储器是一种数据或信息的存储部件，它分成很多存储单元，并按照一定的方式进行排列。每个单元都编了号，称为存储地址。指令和数据存放在存储器中,对指令和数据同等对待，都不加区别地送到运算器中运算。指令在存储器中基本上是按执行顺序存储的，由指令计数器指明要执行的指令在存储器中的地址。存储器一般分为内存储器与外存储器两大类。内存一般安装在主机板上，根据材料和工作原理的不同，内存可分为随机存储器（RAM）和只读存储器（ROM）两种。控制器和运算器只能接受在内存中存放的指令和数据。外存一般安装在主机板之外，外存上面的信息可长久保存，但这些信息必须读入内存之后才能被控制器和运算器所利用。磁盘就是一种常用的外存。半导体存储器半导体存储器（semiconductormemory）是一种能存储大量二值信息(或称为二值的数据)的半导体器件。从存取功能上可以分为只读存储器(ROM，即ReadOnlyMemory)和随机存储器(RAM，即RandomAccessMemory)两大类。随机存储器RAM又分为静态随机存储器SRAM和动态随机存储器DRAM两大类非易失性存储器非易失性存储器，是指那些断电后数据仍然能保留的半导体存储器。对这类存储器，业界统称为非易失性随机访问存储器（NVRAM，Non-VolatileRandomAccessMemory）。在NVRAM产品中，“闪存”被广泛用在PC机的主板上，用来保存BIOS程序，便于进行程序的升级。其另外一大应用领域是用来作为硬盘的替代品，具有抗震、速度快、无噪声、耗电低的优点。磁存储器光盘存储系统CPU(运算器和控制器)中央处理器（CentralProcessingUnit,CPU）由控制器、运算器和寄存器组成，是整个计算机的核心，计算机的运算处理功能主要由它来完成。同时,它还控制计算机的其他零部件，从而使计算机的各部件协调工作。总线总线：CPU与主存储器之间通过总线连接，CPU通过总线提供存储单元目标地址以及读信号来选择、读取数据CPU通过总线提供存储单元目标地址以及写信号来放置、写入信号指令系统CPU能够解码并执行的机器指令集合CISC最初人们采用的是进一步增强原有指令的功能，并设置更为复杂的指令的方法，采用这种设计思路的计算机被称为复杂指令系统计算机（CISC）。RISC通过减少指令总数和简化指令的功能来降低硬件设计的复杂度，从而提高指令的执行速度。优点:与CISC技术相比，简化了指令系统，适合超大规模集成电路的实现；提高了机器执行的速度和效率；降低了设计成本，提高了系统的可靠性；提供了直接支持高级语言的能力，简化了编译程序的设计。机器指令机器指令系统——每台数字电子计算机在设计中，都规定了一组指令。机器语言——用机器指令形式编写的程序。在裸机级，计算机语言关于算法的描述采用的是实际机器的机器指令，它的符号集是{0，1}，支撑实际机器的理论是图灵机等计算模型；在图灵机等计算模型理论的指导下，有关设计形态的主要成果有冯·诺依曼型计算机等具体实现思想和技术，以及各类数字电子计算机产品。计算机语言在裸机级所取得的主要成果汇编语言：采用字符和十进制数来代替二进制代码的思想。汇编语言源程序经汇编程序翻译成机器指令，再在实际的机器中执行。从汇编语言的用户角度来看，机器是可以直接识别汇编语言的，从而产生了一个属于抽象形态的重要概念，即虚拟机的概念。虚拟机:抽象的计算机由软件实现，并与实际机器一样，都具有一个指令集并可以使用不同的存储区域。例如，一台机器上配有C语言和Pascal语言的编译程序，对C语言用户来说，这台机器就是以C语言为机器语言的虚拟机，对Pascal用户来说，这台机器就是以Pascal语言为机器语言的虚拟机。高级语言虽然与机器语言相比，汇编语言的产生是一个很大的进步，但是用它来进行程序设计仍然比较困难。于是人们着手对它进行改进。一是发展宏汇编，即用一条宏指令代替若干条汇编指令，从而提高编程效率。现在人们使用的汇编语言，大多数都是宏汇编语言。二是创建高级语言，使编程更加方便。3.7.6应用语言一般将计算机语言划分为5代：第一代为机器语言；第二代为汇编语言；第三代为高级语言；第四代为“非过程性语言”；第五代为自然语言。3.7.7自然语言计算机对自然语言的处理划分为四个层次：第一层次是文字和语音，即基本语言信息的构成；第二层次是语法，即语言的形态结构；第三层次是语义，即语言与它所指的对象之间的关系；第四层次是语用，即语言与它的使用者之间的关系。第4章计算学科中的核心概念（重点）本章介绍学科中最具方法论性质的概念——算法及数据结构、程序、软件、硬件、计算机中的数据等。二、八、十、十六进制之间的转换；原码、反码、补码的计算；ASCII码基础；汉字编码基础。算法算法定义：“解某种问题的任何专门的方法”。欧几里德算法给定两个正整数m和n，求它们的最大公因子，即能同时整除m和n的最大正整数。欧几里德算法如下：（1）以n除m，并令所得余数为r（r必小于n）；（2）若r=0，算法结束，输出结果n；否则继续步骤（3）；（3）将n置换为m，r置换为n，并返回步骤（1）继续进行。例4.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没有公因子）这个命题的真假。4.2.2算法的定义和特征1．算法的非形式化定义一个算法，就是一个有穷规则的集合，其中之规则规定了一个解决某一特定类型问题的运算序列。2．算法的重要特性算法的规则序列须满足如下五个重要条件：1,有穷性。算法必须总是在执行有穷步之后结束；2,确定性。算法的每一个步骤必须是确切地定义的；3,输入。算法有零个或多个输入；4,输出。算法有一个或多个输出；5,能行性。算法中有待执行的运算和操作必须是相当基本的，它们都是能够精确地进行的，算法执行者甚至不需要掌握算法的含义即可根据该算法的每一步骤要求进行操作，并最终得出正确的结果。算法实例例4.4求1+2+3+…+100例4.5求解调和级数Hn。例4.6求解斐波那契数算法的表示方法表示算法的语言主要有自然语言、流程图、伪代码、计算机程序设计语言等。它们的优缺点算法分析解一个问题，往往有若干不同的算法，这些算法决定着根据该算法编写的程序性能的好坏。在保证算法正确性的前提下，如何确定算法的优劣？在算法的分析中，一般应考虑以下3个问题：（1）算法的时间复杂度；（2）算法的空间复杂度；（3）算法是否便于阅读、修改和测试。通常用以下几个标准来评价算法的优劣：正确性：算法必须能正确解决问题。易读性：算法应当便于阅读和理解，以利于修改和改写成程序。健壮性：当输入非法数据时，算法也能做出特殊处理，不会继续操作或死机。高效率：算法的效率主要从时间和空间两个方面考虑。解决一个问题的算法如果使用时间少和占用空间少，则是算法高效率的体现。算法的研究算法：定义一项工作如何完成的步骤的集合在一台机器可以完成一个任务之前，必须找到完成这个任务的算法并且用与机器兼容的方式来描述数据结构数学模型可分为定量模型和定性模型两类。定量模型指的是可以用数值方程表示的一类模型，而定性模型则是指非数值性的数据结构（如表、树和图等）及其运算。在计算领域中，数据结构（DataStructure）指的是一类定性数学模型，它是计算机算法设计的基础，它在计算科学中占有十分重要的地位。数据结构的基本概念1．数据结构的组成数据结构是一类定性的数学模型，它由数据的逻辑结构、数据的存储结构（或称物理结构）及其运算3部分组成。数据的存储结构数据的存储结构是指在反映数据逻辑关系的原则下，数据在存储器中的存储方式。数据存储结构的基本组织方式有顺序存储结构和链式存储结构。（1）顺序存储结构：借助元素在存储器中的相对位置来表示数据元素的逻辑关系。（2）链式存储结构：借助指针来表示数据元素之间的逻辑关系，通常在数据元素上增加一个或多个指针类型的属性来实现这种表示方式。4．数据结构的基本运算内容（1）建立数据结构；（2）清除数据结构；（3）插入数据元素；（4）删除数据元素；（5）更新数据元素；（6）查找数据元素；（7）按序重新排列；（8）判定某个数据结构是否为空，或是否已达到最大允许的容量；（9）统计数据元素的个数。常用的几种数据结构1．线性表线性表是n个数据元素的有限序列，即（X[1]，X[2]，X[3]，…，X[i]，…，X[n]）。插入、删除和存取数据元素是所有数据结构的基本操作，若对线性表的这些基本操作加一定的限制，则形成下面几种特殊的线性表：（1）栈：也称为后进先出表（LIFO：LastIn,FirstOut）。它的所有插入、删除和存取都是在线性表的表尾进行的；进行删除和插入的一端称栈顶，另一堆称栈底插入一般称为进栈（Push），删除则称为退栈（Pop）。（2）队列：先进先出（FirstInFirstOut，简称FIFO）的线性表。它是限定在一端进行插入，另一端进行删除和存取的特殊线性表。通常把队列的删除和插入分别称为出队和入队。允许出队的一端称为队头，允许入队的一端称为队尾。所有需要进队的数据项，只能从队尾进入，队列中的数据项只能从队头离去。总是先入队的元素先出队，也称为先进先出（FirstInFirstOut，简称FIFO）。（3）链表：链表用一组任意的存储单元来依次存放线性表的数据元素，在存储每个结点值的同时，必须存储指示其后继（或前趋）结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。如果链表的每一个结点只有一个指针域，则这种链表称为单链表结点结构，如果链表的每一个结点有两个指针域，则这种链表称为双链表结点结构。一个指针域指向其前趋结点，一个指针域向其后继结点。2．数组数组是线性表的推广形式之一。如在一个mn的二维数组中，每个元素A[i,j]都分别属于两个线性表，即（A[i,1]，A[i,2]，…，A[i,n]）和（A[1,j]，A[2,j]，…，A[m,j]）。3．树和二叉树树和二叉树是一种具有层次关系的非线性结构，尤其以二叉树最为常用。（1）树树（Tree）是由n（n≥0）个结点组成的有限集合。若n=0，则称为空树，任何一个非空树均满足以下两个条件：①仅有一个称为根的结点；②当n>0时，其余结点可分为m（m≥0）个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树。（2）二叉树二叉树是n（n≥0）个结点组成的有限集合，它或者是空集（n0），或者由一个结点及两棵互不相交的子树组成，且这两个子树有左、右之分，其次序不能任意颠倒。要求：会写出某个二叉树的前序、中序、后序遍历4．图图是由结点和连接这些结点的边所组成的集合。在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。程序“程序”一词，从广义上讲可以认为是一种行动方案或工作步骤。计算机的程序也是一种处理事务的时间顺序和处理步骤。由于组成计算机程序的基本单位是指令，因此，计算机程序就是按照工作步骤事先编排好的、具有特殊功能的指令序列。一个程序具有一个单一的、不可分的结构，它规定了某个数据结构上的一个算法。沃思（NikiklausWirth）提出这样一个公式：算法+数据结构=程序算法和数据结构是计算机程序的两个最基本的概念。计算机软件的定义：计算机软件是在计算机上运行的各种程序、要处理的各类数据以及有关文档的总称。程序+文档+数据=软件软件系统的分层结构计算机软件系统是一个分层的软件结构，包括系统软件层、支撑软件层和应用软件层，其最底层是计算机硬件。（1）系统软件是计算机系统中最靠近硬件层次的软件。如操作系统、编译程序等。（2）支撑软件是支撑其他软件的开发与维护的软件。如数据库管理系统、网络软件、各种接口软件和开发工具等。（3）应用软件是特定应用领域的专用软件。如商业会计软件、教学软件等。软件的性质软件同传统的工业产品相比，有其独特的性质：1.表现形式不同2.生产方式不同3.维护方式不同4.软件的复杂性和规模不断增加操作系统的任务及功能定义：操作系统是管理软硬件资源、控制程序执行，改善人机界面，合理组织计算机工作流程和为用户使用计算机提供良好运行环境的一种系统软件。任务：操作系统的任务是管理好计算机的全部软硬件资源，提高计算机的利用率；担任用户与计算机之间的接口，使用户通过操作系统提供的命令或菜单方便地使用计算机功能：从资源管理的角度来看，操作系统的功能分为处理机管理、存储管理、I/O设备管理、文件系统和用户接口等。操作系统的主要特性1.并发性（Concurrence）是指两个或两个以上的运行程序在同一时间间隔段内同时执行。2.共享性。指操作系统中的资源（包括硬件资源和信息资源）可被多个并发执行的进程所使用。3.异步性。在多道程序环境中，允许多个进程并发执行，由于资源有限而进程众多，多数情况，进程的执行不是一贯到底，而是“走走停停”操作系统的分类1.单用户操作系统2.批处理操作系统（BatchSystem）3.实时操作系统4.分时操作系统5.网络操作系统6.分布式操作系统7.微机操作系统应用软件1.科学和工程计算软件2.字表处理软件3.图形图像处理软件4.网络应用软件5.应用数据库软件计算机系统是由计算机硬件和计算机软件组成的。硬件是计算机的“躯体”，软件是计算机的“灵魂”。广义的计算机硬件包含硬件本身（构成计算机系统的所有物理器件、部件、设备）及其工程技术（工作原理与设计、制造、检测等技术）两部分。计算机系统的物理元器件包括：集成电路、印制电路板，以及其他磁性元件、电子元件等。计算机系统的部件和设备包括：控制器、运算器、存储器、输入输出设备、电源等。硬件工程技术包括：印制电路板制造、高密度组装、抗环境干扰、抗恶劣环境破坏等技术，以及在设计和制造过程中为提高计算机性能所采取的措施等。数据存储和表示计算机用位的形式来表示数据。位（binarydigit，二进制数字，缩写为bit）是存储在计算机中的最小数据单位，位表示二进制数字的0或1，8位表示1个字节（byte）。在计算机中，数据和指令都是用二进制代码来表示的。对数值、字符、图像、声音的数据，需要进行相应的编码。在需要呈现给用户时，再对它们进行解码。数制转换在实际的程序中，由于二进制数不直观。因此：在程序的输入和输出中，一般仍采用十进制数；而在分析计算机内部工作时，常用十六进制（Hexadecimal）数。这样，就要进行相应的转换。1.十进制数与二进制数之间的转换（1）十进制数转换为二进制数（2）二进制数转换为十进制数2.八进制数与二进制数之间的转换（1）八进制数转换为二进制数（2）二进制数转换为八进制数3.十六进制数与二进制数之间的转换（1）十六进制数转换为二进制数（2）二进制数转换为十六进制数原码、反码、补码及其转换1.原码原码是一种最简单而又直观的编码方法。数的符号用一位数码表示，0表示正号，1表示负号，其余的数位与数值本身相同。原码的优点：表示简单，与真值间的转换很容易。缺点：由于只是简单地将符号数值化，而没有与数值统一编码，作加减运算时很不方便。2.反码反码是机器数的另一种编码表示法。它是一种正数与原码相同，负数将原码除符号位外其余各位求反的表示法。求反就是0变1，1变0的操作。3.补码负数的补码就是对反码加一，而正数的原码反码补码是一样的。4.原码、反码和补码的转换对正数来说，原码、反码和补码的表示形式是相同的；对负数来说，原码与反码的互换，“除符号位不变外，按位求反”，原码与补码的互换：“除符号位不变外，按位求反再加1”。字符、字符串和汉字1.字符ASCII码ASCII扩展2.字符串字符串是由字符序列所组成的，字符串可以表示成一系列字节，每个字节对应ASCII码中的一个特定字符。3.汉字对ASCII码进行扩展，使其区分不同汉字。汉字机内码是计算机内部存储和处理汉字的编码。常用两个字节表示，每个字节的最高位都设置为1。内码是以汉字拼音的顺序排序的。4.Unicode为了支持不同国家的语言字符集，ASCII码正在被Unicode码所代替，Unicode是一个16位的编码系统。它用16位二进制来表示每一个符号，这样Unicode就有216（65536）种不同的二进制编码。4.7.4图像在计算机中表示图像的技术两种：位图和矢量图。1.位图在位图技术中，图像被看作是点的集合，每一个点叫做一个像素。2.矢量图与位图不同，矢量图是以指令来描述图像的。它用指令来描述直线，曲线，矩形，圆形的形状、大小、材质等等。4.7.5声音计算机如何存储和处理是模拟信号的声音呢？将连续的模拟波形转换为一系列离散的数值。这一转换的过程包括“采样”和“量化”，然后进行“编码”。“采样”就是等时间间隔地读取波形的幅值“量化”是把读取声波的幅值表示为数字值“编码”是将量化得到的数字值进行编码。第5章学科中的数学方法重点：布尔代数与数字逻辑电路、递归和迭代、公理化方法。在计算学科中的数学方法，主要是离散数学的方法。数学的基本特征1.高度的抽象性2．逻辑的严密性3．普遍的适用性数学方法的作用数学方法是指解决数学问题的策略、途径和步骤。数学方法在科学技术方法论中的作用主要表现在以下3个方面：1.为科学技术研究提供简洁精确的形式化语言。2.为科学技术研究提供数量分析和计算的方法。3.为科学技术研究提供逻辑推理的工具5.4计算学科中常用的数学概念和术语5.4.1集合1．集合的概念2．集合的描述方法描述集合的方式主要有以下3种：（1）枚举法：列出所有元素的表示方法。（2）外延表示法：（3）谓词表示法：用谓词来概括集合中元素的属性。3．集合的运算传统的集合运算是二目运算，包括并、交、差、广义笛卡尔积四种运算。集合运算的论域参与运算的集合A和集合B具有相同的属性，且相应的属性取自同一个域。（1）集合的并（2）集合的差（3）集合的交（4）集合的乘积5.4.2函数和关系1．函数函数又称映射，是指把输入转变成输出的运算，该运算也可理解为从某一“定义域”的对象到某一“值域”的对象的映射。2．关系关系是一个谓词，其定义域为k元组的集合。通常的关系为二元关系，其定义域为有序对的集合，在这个集合中，我们说有序对的第一个元素和第二个元素有关系。3．等价关系在日常生活中，常常碰到对一些对象进行分类的问题。任意一个分类法总是在某一观点下把一些元素看做是同样的，并且希望每一个元素在这种分类法下都必定属于而且仅仅属于某一类，具有这种功能的分类法，在数学上就叫做一个等价关系。5.4.3代数系统从两个数确定第三个数，而且第三个数是由前两个数惟一确定的．这就是“代数运算”的最本质特点。代数运算的严格意义：对于一个非空集合A，可以定义，任意一个由AA到A的映射称为集合A上的一个二元运算，An到A的映射则称为集合A上的一个n元运算。由集合A以及连同若干定义在该集合上的运算f1，f2，fn所组成的系统称为代数系统，该系统可以形式化的描述为：<A，f1，f2，，fn>。群、环、格、布尔代数是4种最基本的代数系统。布尔代数布尔代数是一种特殊的格，它由0和1组成的集合以及定义在其上的“3个运算”构成。1.与逻辑（与运算）与逻辑的定义：与运算：决定事件的全部条件都满足时，事件才发生--这就是与逻辑关系。在函数式中，用“•”表示与运算，记做Y=A•B或Y=AB2.或逻辑（或运算）或逻辑的定义：或运算：决定事件的全部条件至少有一个满足时，事件就发生，称为或逻辑关系。在函数式中，用“＋”表示或运算，其函数表达式为：Y=A＋B。3.非逻辑（非运算）非逻辑指的是逻辑的否定。决定事件的条件满足时，事件不发生；条件不满足，事件反而发生。在函数式中，用“–”表示非运算。三种基本逻辑关系都可以由具体电路来实现。通常把实现"与"逻辑运算的单元电路称为"与门"；把实现"或"逻辑运算的单元电路称为"或门"；把实现"非"逻辑运算的单元电路称为"非门"（或称为反相器）。表5.1布尔代数三个基本的逻辑运算ABA·BA+B

00011011000101111100表5.2与、或、非门电路图及相应的布尔表达式5.4.4字母表、字符串和语言字母表可以理解为计算机输入键盘上符号的集合。字母可以理解为键盘上的每一个英文字母、数字、标点符号、运算符号等。字符串指的是由字符组成的有限序列。语言指的是给定字母表上的字符串的集合。语言是字符串的集合，因此，传统的集合运算（如并、交、差、补、笛卡尔积）对语言都适用。除此之外，语言还有一种重要的专门的运算，即闭包运算。语言、文法以及自动机有着密切的关系。语言由文法产生，文法是一种数学模型，它是建立在有限集合上的一组变换（运算）。根据代数系统的定义，也可以将文法看作是一种代数系统，而语言正是由这种代数系统产生的。计算机使用的语言是一种形式语言，在形式语言与自动机理论中，自动机是识别语言的数学模型，各类文法所对应的自动机分别是图灵机、线性有界自动机、下推自动机和有限状态自动机。需要指出的是，语言与数学模型不是一一对应的关系，一种语言可以由不同的文法产生，也可以由不同的自动机识别。5.4.5定义、定理和证明定义定义是对一种事物的本质特征或一个概念的内涵与外延确切而简要的说明。1.定义的作用（1）综合作用：（2）分析作用：（3）交流作用：2.定义的规则（1）定义必须揭示被定义对象的区别性特征；（2）定义项和被定义项的外延必须相等；（3）定义不能恶性循环；（4）定义不可用含混、隐晦或比喻性词语来表示。定理1、通过真命题（公理或其他已被证明的定理）出发，经过受逻辑限制的演绎推导，证明为正确的结论的命题或公式，例如“平行四边形的对边相等”就是平面几何中的一个定理。2、一般来说，在数学中，只有重要或有趣的陈述才叫定理，证明定理是数学的中心活动。相信为真但未被证明的数学叙述为猜想，当它被证明为真后便是定理。它是定理的来源，但并非唯一来源。一个从其他定理引伸出来的数学叙述，可以不经过证明成为猜想的过程，成为定理。如上所述，定理需要某些逻辑框架，继而形成一套公理（公理系统）。同时，一个推理的过程，容许从公理中引出新定理和其他之前发现的定理。在命题逻辑中，所有已证明的叙述都称为定理。5.4.6必要条件和充分条件（不考）必要条件，用计算机的行话来说，就是找不到一个反例的条件。5.5证明方法5.5.1直接证明法和间接证明法1．直接证明假定p为真，通过使用公理或已证明的定理以及正确的推理规则证明q也为真，以此证明蕴含式p→q为真。这种证明方法为直接证明法。2．间接证明因为蕴含式p→q与其逆否命题¬q→¬p等价，因此可以通过证明¬q→¬p来证明蕴含式p→q为真。这种证明方法为间接证明法。5.5.2反证法首先假定一个与原命题相反的命题成立，然后通过正确的推理得出与已知（或假设）条件、公理、已证过的定理等相互矛盾或自相矛盾的结果，用来证明原命题的正确。这种证明方法就是反证法，也称归谬法，是一种常用的数学证明方法。5.5.3归纳法1．归纳法的定义所谓归纳法，是指从特殊推理出一般的一种证明方法。归纳法可分为不完全归纳法、完全归纳法和数学归纳法。2．不完全归纳法不完全归纳法是根据部分特殊情况作出推理的一种方法，该方法多用于无穷对象的论证，然而，论证的结果不一定正确。因此，不完全归纳法不能作为严格的证明方法。3．完全归纳法完全归纳法也称穷举法，它是对命题中存在的所有特殊情况进行考虑的一种方法，用该方法论证的结果是正确的，然而，它只能用于“有限”对象的论证。4．数学归纳法（1）数学归纳法的概念数学归纳法是一种用于证明与自然数有关的命题正确性的证明方法，该方法能用“有限”的步骤解决无穷对象的论证问题。数学归纳法广泛地应用于计算理论研究之中，如算法的正确性证明、图与树的定理证明等方面。5.5.4构造性证明数学是形式化的思想元素，数学讲究严密的形式推理和证明。首先，数学证明旨在核实真理，它用严格的、逻辑的过程得出令人可信的结论；其次，数学证明最重要的价值是增进理解，只有当你理解了一个定理的证明，才能真正深入体会该定理的内容。1．存在性证明存在一个x使命题P(x)成立可表示为：xP(x)。对形如xP(x)的命题的证明称为存在性证明。2．构造性证明构造性的证明方法，对于要解决的问题，不光要证明该问题解的存在，还要给出解决该问题的具体步骤，这种步骤往往就是对解题算法的描述。5.6递归和迭代构造性是计算机软硬件系统的最根本特征，而递归和迭代是最具代表性的构造性数学方法，它广泛地应用于计算学科各个领域。递归和迭代密切相关，实现递归和迭代的基础基于以下一个事实。不少序列项，常常可以用这样的方式得到：由an–1得到an，按这样的法则，可以从一个已知的首项开始，有限次地重复做下去，最后产生一个序列。该序列是递归和迭代运算的基础。5.6.1递归1．递归及其有关概念在计算技术中，与递归有关的概念有：递归关系、递归数列、递归过程、递归算法、递归程序、递归方法。（1）递归关系指的是：一个数列的若干连续项之间的关系。（2）递归数列指的是：由递归关系所确定的数列。（3）递归过程指的是：调用“自身”的过程。（4）递归算法指的是：包含递归过程的算法。（5）递归程序指的是：直接或间接调用“自身”的程序。（6）递归方法（也称递推法），是一种在“有限”步骤内，根据特定的法则或公式对一个或多个前面的元素进行运算，以确定一系列元素（如数或函数）的方法。2．递归与数学归纳法与数学归纳法相对应，递归由递归基础和递归步骤两部分组成。数学归纳法是一种论证方法，递归是算法和程序设计的一种实现技术，涉及递归定义的证明通常采用数学归纳法。3．递归的定义功能递归不仅应用于算法和程序设计之中，它还广泛地应用于定义序列、函数和集合等各个方面。（1）定义序列例5.22（2）定义函数例5.23（3）定义集合5.6.2迭代“迭”是屡次和反复的意思，“代”是替换的意思，合起来，“迭代”就是反复替换的意思。在程序设计中，为了处理重复性计算的问题，最常用的方法就是迭代方法，主要是循环迭代。可以证明，迭代程序都可以转换为与它等价的递归程序，反之，则不然。5.7公理化方法5.7.2公理化方法的基本概念1．什么是公理化方法公理化方法是一种构造理论体系的演绎方法，它是从尽可能少的基本概念、公理出发，运用演绎推理规则，推出一系列的命题，从而建立整个理论体系的思想方法。用公理化方法构建的理论称为“公理系统”。公理系统需要满足三个条件：公理系统需要满足无矛盾性、独立性和完备性三个条件。5.8.1形式系统的组成、基本特点和局限性1．形式系统的组成形式系统由下面几个部分组成：（1）初始符号。初始符号不具有任何意义。（2）形式规则。形式规则规定一种程序，借以判定哪些符号串是本系统中的公式，哪些不是。（3）公理。即在本系统的公式中，确定不加推导就可以断定的公式集。（4）变形规则。变形规则亦称演绎规则或推导规则。变形规则规定，从已被断定的公式，如何得出新的被断定公式。被断定的公式又称为系统中的定理。2．形式系统的基本特点（1）严格性（2）抽象性3．形式系统的局限性一个形式系统，如果它是无矛盾的，那么它就具有下面两个局限性：（1）不完备性（2）不可判定性形式化与公理化形式化不一定导致公理化，公理系统也不一定是形式系统。如欧氏几何公理系统就不是形式系统。第6章学科中的系统科学方法6.2.2系统科学遵循的一般原则1．整体性原则亚里士多德以:“整体大于部分之和”来表述整体涌现性。贝塔朗菲定律：“整体不等于部分之和”。2．动态原则动态原则是指系统总是动态的，永远处于运动变化之中。3．最优化原则运用各种有效方法，从系统多种目标或多种可能的途径中选择最优系统、最优方案、最优功能、最优运动状态，达到整体优化的目的。